Skip to main content

Hill climbing; simulated annealing

Short answer

Hill climbing is a local greedy search that stops at any peak without backtracking; its problems are local maxima, plateaus, and ridges, handled by random restarts, sideways moves or big jumps, and multi-direction moves. Simulated annealing occasionally accepts worse moves with probability e^(deltaE/T), letting it escape local maxima and approach the global optimum as temperature falls.

Discuss the hill climbing search algorithm along with the problems associated with it and discuss their solutions. Why is simulated annealing important?

Hill climbing is a local search that repeatedly moves from the current state to the neighbouring state with the highest value of the evaluation function, and stops when no neighbour is better. It keeps only the current state (O(1) memory), has no backtracking and no look-ahead, like climbing a hill in fog.

current = initial state
loop:
   best = highest-valued neighbour of current
   if value(best) <= value(current): return current
   current = best

Variants: simple (first better neighbour), steepest-ascent (best neighbour), stochastic and first-choice hill climbing.

Problems and solutions

ProblemMeaningSolution
Local maximumA peak better than its neighbours but not the best overall; search stopsRandom-restart hill climbing, backtracking, simulated annealing
PlateauA flat area; all neighbours have equal value, so no direction is betterTake a big random jump, or allow a limited number of sideways moves
RidgeA narrow high path; every single move goes downhill though the ridge risesApply several moves at once or move in more directions (e.g. diagonally)

The algorithm is not complete and not optimal, but it is fast and uses almost no memory.

Importance of simulated annealing

Simulated annealing is hill climbing that sometimes accepts a worse move. A random neighbour is chosen; if it is better it is accepted; if worse (change ΔE < 0), it is accepted with probability e^(ΔE/T), where T is a "temperature" that is slowly lowered (cooling schedule). At high T the search wanders and escapes local maxima; as T falls it behaves like hill climbing and settles on a good solution. With a slow enough cooling it finds the global optimum with probability approaching 1, so it solves the main weakness of hill climbing.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Artificial Intelligence chapter 3 questions →