Simulated Annealing (Concept) — Beginner-Friendly Notes

1. What It Fixes

Hill climbing gets stuck on local maxima because it never moves downhill. Simulated annealing sometimes moves to worse states early, then gradually stops — like cooling metal (annealing) that escapes local defects.

Hill climbing = greedy. Simulated annealing = greedy + occasional bad moves that decrease over time.

2. How It Works (one idea + one formula)

At each step:

• Pick random neighbour.

• If neighbour is better: always move.

• If worse (delta $ΔE = Value(next)-Value(current) < 0$ for maximisation, or $ΔE > 0$ for minimisation cost): move with probability $P = e^{ΔE / T}$ (for maximisation; for cost, $P = e^{-ΔE/T}$).

• $T$ = temperature (high → more random moves, low → more greedy). $T$ decreases over time by a cooling schedule (e.g., $T_{k+1}= α \cdot T_k$, $0<α<1$).

T = T0
current = initial
loop:
  T = schedule(T)  # cool down
  if T == 0: return current
  next = random neighbour
  ΔE = Value(next)-Value(current)
  if ΔE > 0: current = next
  else if random() < e^{ΔE/T}: current = next  # worse move with decreasing chance

3. Why It Works (beginner intuition)

• High T early: explore widely, jump out of local peaks.
• Low T late: settle and climb the best peak found — becomes hill climbing at the end.
• Theoretically: with slow enough cooling, will converge to global optimum with probability → 1 (but slow in practice).

4. Example — 8-Queens with Local Optima

Hill climbing at local max 25/28 would stop; SA at high T would jump to 22/28 (worse) to later reach 28/28 global optimum, then freeze as T→0.

5. Key Parameters for Exam

• Cooling schedule decides speed vs quality — fast cooling = fast but may miss optimum; slow cooling = good but slow.
• Uses $O(1)$ memory, like hill climbing.

6. One-Line Summary

Simulated annealing escapes local optima by probabilistically accepting worse moves with probability $e^{ΔE/T}$, high at high temperature and vanishing as $T$ cools, making it probabilistically complete for global optimisation.

7. Quick Self-Check

1. What is the probability of moving to a much worse state when $T$ is high vs low?
2. How does SA differ from random-restart hill climbing?