Freeze too fast, stay stuck

A delivery route tangled across forty stops improves one swap at a time — occasionally accepting a worse swap on purpose, the heat that lets it wriggle out of a bad tangle. Cool that heat too fast and the route locks in wherever it happened to be. Cool it slowly, and it finds something close to the best route there is.

What you're seeing

Forty stops, one tour, and a search that only ever knows how to do one thing: pick two spots in the route at random and reverse everything between them — a "2-opt" move, the standard local move for tour improvement. If the swap shortens the route, take it. If it lengthens the route, take it anyway sometimes — with a probability set by a temperature that starts high and cools every try. That willingness to occasionally accept a worse tour is the whole trick: it is what lets the search back out of a promising-looking dead end instead of committing to it forever.

Drag the cooling rate down toward 0.95 and hit "Start cooling": the temperature collapses in barely a hundred tries, the search locks in almost immediately, and the route settles wherever the first few swaps happened to leave it — still visibly crossed and tangled. Drag it up toward 0.999 and the same search gets roughly fifty times longer to explore before it has to commit, and the route it locks into is dramatically shorter and cleaner. Nothing about the destination changed — only how much looking-around the route got to do before the door closed.

The rule, exactly. Each try reverses tour segment [i+1, j]; the length change has a closed form using only the two edges that actually change, ΔL = [d(A,C) + d(B,D)] − [d(A,B) + d(C,D)] where A,B and C,D are the tour's edges at i and j. Accept if ΔL≤0, else accept with probability exp(−ΔL / T) — the Metropolis rule, the same one that drives Exhibit 43's magnet. Temperature cools as T(step) = T₀·α^step, starting at T₀=80 until it drops below the freeze threshold 0.5 — so the number of tries before that happens is fixed by α alone. Verified in node (improve/verify/49-simulated-annealing.js): the O(1) reversal-cost formula matches a full recompute exactly across hundreds of random reversals; on a small, brute-forceable 8-city map, slow cooling finds the true optimum in 20 of 20 independent runs. Negative control: run α=0.95 and α=0.999 each to its own freeze point on the very same fixed 40-city layout — 99 tries versus 5,073 — and the fast schedule lands 143% longer, roughly 2.4× the distance, than the slow one — holding across ten different random search seeds on that one layout, every single time.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 49.