You can get stuck in a local optimium, especially in low-dimensional spaces (or with bad representations).
simulated annealing is a stochastic optimization technique that tries to avoid getting stuck in local optima by allowing some uphill moves with a probability that decreases over time.
beam search is a technique that keeps track of candidate solutions at once, allowing it to explore multiple paths in the search space simultaneously (can also be made stochastic, by sampling candidates based on score). This is different from parallel runs of hill-climbing, as beam search shares information between the candidates.
Both SA and BS can still get in local optima, but you have a knob to tune exploration vs exploitation by increasing the temperature or the beam width respectively.
Interestingly self-organized criticality also helps prevent local optima, without any annealing.