Simulated Annealing for the Travelling Salesman Problem
After reading this you can explain how simulated annealing searches for a short tour, compute the acceptance probability of a worsening move by hand, and read the tour-length and temperature charts to tell a healthy run from a frozen one.
What simulated annealing does
The travelling salesman problem asks for the shortest closed tour that visits every city once. With 20 cities there are already 19!/2 \approx 6 \times 10^{16} distinct tours, so you cannot check them all. Simulated annealing does not try. It keeps one tour, proposes a small random change, and either keeps or rejects it. Repeat thousands of times per second and the tour shortens.
The trick that separates it from plain hill climbing is that it sometimes accepts a worse tour on purpose. Early in the run it accepts many. Late in the run it accepts almost none. A single number called the temperature T controls that willingness, and it falls steadily as the run proceeds. The name comes from metallurgy: heat a metal, then cool it slowly so its atoms settle into a low-energy crystal instead of a brittle glass.
On the tool, the blue path is the current tour that the algorithm is actively modifying. The orange path is the best tour seen so far, saved separately. The current tour writhes and occasionally lengthens; the best tour only ever improves.
When to reach for it, and when not
Simulated annealing suits problems where you can define a cost, propose a small random change cheaply, and compute the change in cost without recomputing everything. TSP fits perfectly. So do scheduling, layout, and many combinatorial puzzles with rugged cost surfaces full of local minima.
It is a poor fit when a cheaper exact or specialized method exists. For continuous, smooth problems with gradients, gradient methods converge far faster; see the Gradient Descent Visualizer. For small TSP instances (under about 15 cities) an exact solver settles the matter. Annealing gives no certificate: it returns a good tour, not a proof that no shorter tour exists.
Annealing is a metaheuristic, not a guarantee. The theorem that it finds the global optimum requires a cooling schedule so slow (temperature falling like 1/\log t) that no one uses it. The geometric schedule here is a practical compromise, which is exactly why the Reheat button exists.
The Metropolis rule and the 2-opt move
Every proposal here is a 2-opt move: pick two positions in the tour and reverse the segment between them. That deletes two edges and adds two, so the change in tour length depends on only four edge lengths.
Here the tour visited a \to b and later c \to e. Reversing the segment from b through c replaces those two edges with a \to c and b \to e. Computing \Delta from four distances is O(1), which is what lets the tool test thousands of moves per frame.
The move is accepted by the Metropolis criterion:
If the move shortens the tour (\Delta \le 0) it is always taken. If it lengthens the tour by \Delta \gt 0, it is taken with probability e^{-\Delta/T}. Two things shrink that probability: a larger \Delta (worse moves are rarer) and a smaller T (as the run cools, all worsening moves get rarer).
The temperature cools geometrically. After each step,
with a cooling rate \alpha just below 1, for example \alpha = 0.995. Starting from T_0 = 100, after 1000 steps T = 100 \times 0.995^{1000} \approx 0.67.
A worked acceptance calculation
How often is a worse move accepted?
Suppose a proposed 2-opt move lengthens the tour by \Delta = 5. How likely is the annealer to accept it at three different temperatures?
- At T = 100: e^{-5/100} = e^{-0.05} \approx 0.951. Nearly always accepted, so the search wanders almost freely.
- At T = 10: e^{-5/10} = e^{-0.5} \approx 0.607. A coin-flip and then some.
- At T = 1: e^{-5/1} = e^{-5} \approx 0.0067. About 7 acceptances per 1000 tries.
- At T = 0.1: e^{-50} \approx 2 \times 10^{-22}. Effectively never. The search is now pure hill climbing.
Same move, four temperatures, acceptance falling from 95% to essentially zero. That collapse is the whole schedule in one number.
Reproducing a run with the defaults
The circle preset, whose optimum you know
Load the Circle preset and press Run with the default initial temperature and cooling rate. The circle is the one layout with an obvious answer: the shortest tour visits the cities in order around the ring, so its length is the perimeter of a regular polygon.
- For n cities equally spaced on a circle of radius r, adjacent cities are separated by angle 2\pi/n.
- The chord between neighbours has length 2r \sin(\pi/n).
- The optimal tour is n such chords: L^* = 2nr \sin(\pi/n).
- With n = 20 and r = 200 pixels: L^* = 2 \times 20 \times 200 \times \sin(9^\circ) \approx 8000 \times 0.1564 \approx 1251 pixels.
A run that ends near 1251 has essentially found the optimum. A run stuck at, say, 1400 has a crossing or two left in it: press Reheat and watch it usually untangle.
Compare against the nearest-neighbour baseline the tool draws. Nearest neighbour builds a tour greedily, always hopping to the closest unvisited city. On random layouts it typically lands 20% to 25% above optimal. Annealing then trims most of that gap.
Reading the charts and the status line
Two curves tell you what is happening. The temperature curve is a smooth exponential decay: T_n = T_0 \alpha^n plots as a straight line on a log scale. The tour-length curve is the interesting one. Early on the best-so-far length drops fast while the current length jitters up and down. Later both flatten.
The status line reports the recent fraction of worsening moves that were accepted. Use it as a thermometer for the search itself:
- Above ~50% accepted
- The search is still hot and mostly exploring. Fine early, wasteful if it lasts.
- Around 5% to 30%
- The productive middle. The tour is being refined while still escaping small traps.
- Near 0% accepted
- Frozen. Only improving moves get through, so this is now hill climbing. If the length has stopped falling and you are above the known optimum, reheat.
Common mistakes
Starting too cold is the most common error. If T_0 is small relative to typical \Delta values, the run accepts almost no worsening moves from the first step and behaves like hill climbing. It freezes into the first local minimum. A useful rule: set T_0 so that even a fairly bad early move (a large \Delta) is accepted maybe 80% of the time.
Cooling too fast is the same mistake in a different costume. With \alpha = 0.90, temperature falls by a factor of 1000 in only 66 steps (0.90^{66} \approx 0.001), so the search barely explores before it hardens. With \alpha = 0.999 it takes about 6900 steps for the same drop, giving far more time to find good structure. Slower cooling costs more proposals but usually pays off.
Cooling too slowly wastes effort at the other end: you spend thousands of proposals at high temperature accepting nearly everything, which is close to random shuffling. Watch the status line and get the acceptance fraction into the productive middle band reasonably quickly.
Finally, do not read one run as the truth. Annealing is randomized. Two runs from the same settings can differ by several percent in final length. Judge settings by running several times, not once.
Related tools
Simulated annealing is one of several search strategies for hard landscapes. Particle Swarm Optimization keeps many candidate solutions moving together instead of one, which suits continuous functions with several basins. For smooth differentiable objectives where gradients exist, the Gradient Descent Visualizer shows why following the slope beats random proposals. And if your problem is tracking a moving state through noise rather than optimizing a fixed cost, the Kalman Filter Visualizer is the tool that fits.
Frequently asked questions
Why accept moves that make the tour worse?
Because the shortest tour is often hidden behind a wall of worse tours. From a local minimum, every single 2-opt move lengthens the tour, so pure hill climbing stops there. Accepting a worsening move lets the search climb out of that basin and possibly reach a deeper one. The temperature controls how far it is willing to climb.
What initial temperature and cooling rate should I use?
Choose T_0 from the size of typical worsening moves so that early acceptance is high (roughly 0.8), then use a cooling rate between 0.995 and 0.999 and let the run be long. If it freezes above the length you expected, reheat rather than restart.
Does simulated annealing find the shortest possible tour?
Not with certainty. Guaranteed convergence needs logarithmic cooling that is too slow to run. In practice you get a tour within a few percent of optimal on most instances, and on the circle preset you can check the gap directly against 2nr\sin(\pi/n).
What does the Reheat button actually do?
It raises the temperature again from its cooled value, restoring the probability of accepting worsening moves. That lets a run escape a local minimum it froze into, then cool back down toward a possibly better tour. It keeps the best-so-far tour, so reheating can only help or leave you where you were.
Why 2-opt moves rather than swapping two cities?
Reversing a segment removes exactly two edge crossings at a time and changes only four edge lengths, so its cost delta is O(1) to compute and it maps naturally onto untangling a tour. Swapping two arbitrary cities changes up to four edges too but tends to make larger, more disruptive jumps that the search accepts less often once cool.
Related tools
Gradient Descent Visualizer
Race SGD, Momentum, RMSProp and Adam across contour maps of five classic loss landscapes.
Kalman Filter Visualizer
Track a moving target through noisy measurements with a full linear Kalman filter.
Particle Swarm Optimization
Fly a swarm of particles across classic test functions and watch it converge on the minimum.
AI Learns to Drive (Neuroevolution)
Watch a population of neural-network cars evolve from crashing into corners to lapping a race track.
Backpropagation Step-by-Step
Walk through one forward and backward pass of a tiny neural network, number by number.
Decision Tree Builder
Grow a CART decision tree split by split and watch the partition map and tree diagram build together.