Hill Climbing and Simulated Annealing
Local search climbs towards better solutions — but gets stuck on local peaks. Simulated annealing adds controlled randomness to escape.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
3 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. Some problems have too many possible solutions to search them all. Local search starts somewhere and keeps improving. Let us see how, and where it goes wrong.
Hill climbing. Imagine every possible solution as a point on a landscape, where height means quality. Hill climbing looks at its neighbours and steps to whichever is higher. It climbs quickly, but here it gets stuck on a small local peak, even though a much higher peak exists.
The problem. Hill climbing fails in three classic ways. Local maxima, where every neighbour is worse even though a better peak exists. Plateaus with no slope to follow. And ridges, where you must first step sideways.
Simulated annealing. Simulated annealing borrows an idea from metalworking. At first the temperature is high, and it often accepts worse moves, jumping around the landscape. As it cools, it becomes pickier. Here it escaped the local peak and settled on the global maximum. Because it uses randomness, it usually escapes, though not on every run.
The acceptance rule. The rule is simple. Better moves are always accepted. A worse move is accepted with probability e to the power delta over T. When the temperature is high, bad moves are often accepted. As it cools, they become rare.
Recap. To recap. Hill climbing always steps uphill, but gets trapped. Simulated annealing accepts some worse moves while hot, which helps it escape local peaks before settling down.