Stochastic Hill Climbing and Simulated Annealing
Accept bad moves on purpose — the sigmoid rule, the temperature dial, and the metallurgy metaphor that escapes local optima
The Simplest Explanation
Hill climbing is pure exploitation; a random walk is pure exploration. Simulated annealing sits between them with one dial:
Pick a random neighbor. If better, usually move. If worse, move anyway with probability — high when the temperature T is hot, near zero when cold.
Then cool T slowly. Early = wander widely; late = greedy descent. Like metallurgy: heat metal so atoms roam, cool slowly so they settle into a low-energy crystal.
ΔE > 0 (better) → P above 0.5. ΔE < 0 → P below 0.5. High T flattens everything toward 0.5 (random walk); low T sharpens into hill climbing.
The Algorithm
Mechanics of accepting: draw a random number in [0,1]; move if it falls below P.
The Temperature Dial
Vary ΔE, fix T = 10 (current value 107):
| Neighbor | ΔE | P(accept) |
|---|---|---|
| 150 | +43 | 0.99 |
| 120 | +13 | 0.79 |
| 107 | 0 | 0.50 |
| 100 | −7 | 0.33 |
| 80 | −27 | 0.06 |
Better neighbors accepted almost surely; terrible ones almost never.
Vary T, fix ΔE = +13:
| T | e^(−13/T) | P |
|---|---|---|
| 1 | ≈0 | ≈1.00 |
| 5 | 0.074 | 0.93 |
| 10 | 0.27 | 0.79 |
| 50 | 0.77 | 0.56 |
| 100 | 0.88 | 0.53 |
Hot T compresses every probability toward 0.5 — even good moves are coin flips.
Why It Escapes Local Optima
Two local maxima A and B with valley M between:
Descending from A to M costs a small ΔE drop → decent acceptance probability. Descending from B would need a huge drop → rarely accepted. So SA hops out of shallow local optima easily and deep ones rarely — exactly the right bias.
Properties
| Property | Value |
|---|---|
| Space | O(1) — current node only |
| Complete? | Not guaranteed in finite time; converges to global optimum as T→0 slowly enough (theoretical result) |
| vs Iterated HC | IHC randomizes starts; SA randomizes every move within one run |