Cool Down to Solve
A salesman must visit 20 towns by the shortest route. A hot robot tries wild changes, then calms down. A greedy robot never goes backwards.
Both of us start with the same messy route. Press Run. I will sometimes accept a worse route while I am hot. That is my secret!
Two robots, one map
Challenges
Near perfect: let the annealer finish within 5% of the best known route.
Beat the climber: finish a run where the annealer is shorter than the greedy robot (try New cities if it ties).
Stuck climber: finish a run where the greedy robot ends 3% or more above the best known.
Brave moves: let the annealer accept 100 worse routes on purpose.
What just happened?
- Both robots use the same move: pick a stretch of the route and reverse it. If the route gets shorter, keep it.
- The greedy robot refuses every bad move, so it gets stuck in a dip where any single change makes things worse.
- The annealer sometimes accepts a worse route. That lets it climb out of dips. As it cools, it accepts fewer and fewer.
- Cooling too fast freezes it in a poor route. Too hot at the end and it just wanders.
- Neither is guaranteed to be perfect. The "best known" is the shortest of three long annealing runs.
How it works
- Start with a random route.
- Propose a small change: reverse a stretch of the route.
- If shorter, accept it.
- If longer, accept with chance
e^(−extra / temperature). Hot means likely. - Cool the temperature slowly towards zero.
- Keep the best route seen along the way.
For grown-ups: what's really going on
Simulated annealing is a stochastic local search inspired by cooling metal. It samples from a Boltzmann distribution over routes whose temperature T shrinks over time.
- Move: 2-opt (reverse the segment between two cut points). Acceptance: the Metropolis rule, accept with probability
min(1, e−Δ/T), whereΔis the change in route length. - Schedule: geometric cooling
T(t) = T₀ (T_end / T₀)t/N. With a logarithmically slow schedule, annealing provably converges to the global optimum, but that is too slow to use; practical schedules are a trade-off. - The greedy robot is hill climbing (here, descending): it stops at a local optimum, a route that no single 2-opt move can improve.
- The travelling salesman problem is NP-hard: the number of routes grows factorially, so we rely on heuristics. Here the reference value is only a very good heuristic answer, not a proof of optimality.
Further reading: Kirkpatrick, Gelatt and Vecchi, Optimization by Simulated Annealing, Science (1983).