Hill Climbing and Simulated Annealing — lecture notes
Local search climbs towards better solutions — but gets stuck on local peaks. Simulated annealing adds controlled randomness to escape.
0:001. 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.
0:122. 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.
0:313. 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.
0:464. 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.
1:095. 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.
1:266. 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.
Key takeaways
- Hill climbing moves to the best neighbour and can get stuck on local maxima.
- Simulated annealing accepts worse moves with probability e^(Δ/T).
- A high temperature encourages exploration; cooling focuses the search.
- Randomness means annealing usually — but not always — finds the global best.
Check yourself
- Why did hill climbing stop on the smaller peak?
Show answer
Every neighbour there was lower — At a local maximum every nearby move is worse, so hill climbing stops.
- What happens to simulated annealing as the temperature falls?
Show answer
It accepts worse moves less often — Lower temperature makes e^(Δ/T) smaller for bad moves.
- A move that improves the solution is accepted…
Show answer
Always — Improvements are always accepted; only worse moves are probabilistic.
Go deeper
- Local Search: Hill Climbing, Simulated Annealing and Beam Search · The AI Lecture Hall
- Genetic Algorithms and Evolutionary Computation · The AI Lecture Hall
© 2026 Janin A Apurba, CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. All rights reserved. Notes for the animated lecture at https://ai-in-motion.vercel.app/watch/hill-climbing-and-simulated-annealing.html