Info & Theory
Simulated annealing mimics the slow cooling of a metal. Heated atoms wander freely; as the metal cools they settle into a low-energy crystal. The algorithm treats the tour length as "energy" and cools a virtual temperature.
The travelling salesman problem
Given n cities, find the shortest closed tour
visiting each exactly once. It is NP-hard, so we search for a
short tour rather than the provably optimal one.
Neighbour moves
Each step proposes a neighbour tour using a
2-opt move (reverse a segment, uncrossing edges) or
a swap of two cities, then measures the change in
length ΔE.
The Metropolis criterion
If ΔE ≤ 0 the move is accepted. Otherwise it is
accepted with probability
P = exp(−ΔE / T). High T ⇒ almost
everything accepted (exploration); low T ⇒ greedy
(exploitation).
Geometric cooling
The temperature follows T ← α · T with the cooling
rate α just below 1. Slower cooling explores more
and usually finds shorter tours.
Escaping local minima
Pure hill-climbing gets trapped where every neighbour is worse. By sometimes accepting a worse tour, annealing can climb out and reach a better basin before the temperature locks it in.
FAQ
What is simulated annealing?
A probabilistic optimisation method inspired by the slow cooling of metals. It makes random changes, always accepting improvements but also accepting worse states with a temperature-dependent probability, which lets it escape local minima.
Why does it accept worse solutions?
Accepting worse moves with probability
e^(−ΔE/T) lets the search climb out of local
minima. At high temperature it explores widely; as the
temperature falls it becomes greedy and settles into a good
basin.
What is the Metropolis acceptance criterion?
A move that lowers the cost is always accepted. A move that
raises the cost by ΔE is accepted with
probability exp(−ΔE/T), where T is
the current temperature.
What is a cooling schedule?
It defines how the temperature decreases. This simulation uses
a geometric schedule, T ← α·T with α just below
1. Slower cooling usually finds shorter tours but takes
longer.
What is the travelling salesman problem?
The shortest tour visiting every city exactly once and returning to the start. It is NP-hard, so simulated annealing finds short, near-optimal tours quickly.
What are 2-opt and swap moves?
A 2-opt move reverses a segment of the tour, uncrossing two edges. A swap move exchanges two cities. Both produce a neighbouring tour to compare against the current one.
What does the acceptance rate tell me?
The fraction of proposed moves accepted recently. It starts high while the temperature is high and drops toward zero as the schedule cools.
Does it find the optimal tour?
Not guaranteed. With infinitely slow cooling it converges to a global optimum in theory, but in practice it returns a high-quality near-optimal solution.
How does the cooling rate affect the result?
A rate close to 1 (e.g. 0.999) cools slowly and usually yields shorter tours. A smaller rate (e.g. 0.99) converges fast but is more likely to get stuck in a local minimum.
Where is it used in practice?
In VLSI chip layout, scheduling, vehicle routing, image reconstruction, neural-network training and many other combinatorial problems with large, rugged search spaces.