Optimisation & Search

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

Greedy climber
Annealer

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?

How it works

  1. Start with a random route.
  2. Propose a small change: reverse a stretch of the route.
  3. If shorter, accept it.
  4. If longer, accept with chance e^(−extra / temperature). Hot means likely.
  5. Cool the temperature slowly towards zero.
  6. 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).