Simulated Annealing: Escaping Local Minima

The problem with greedy search

The travelling-salesman problem asks for the shortest tour that visits every city once and returns home. It is NP-hard, so for anything but small instances you cannot check every tour - the number of possible routes explodes factorially. A greedy local search fixes that by starting from any tour and repeatedly applying small changes, such as a 2-opt move that reverses a segment of the route, keeping the change only if it shortens the tour. The trouble is that this kind of hill-climbing stops at the first local minimum it finds and has no way back out, even though a much shorter tour might be sitting just over a small hill.

Borrowing physics: the Metropolis criterion

Simulated annealing, introduced by Kirkpatrick, Gelatt and Vecchi in 1983, borrows its escape hatch from statistical mechanics. Slowly cooled metal atoms settle into a low-energy crystal lattice; cooled too fast, they freeze into a disordered, higher-energy glass. The Metropolis-Hastings rule from the 1953 Monte Carlo literature captures this: propose a random change, and if it improves the objective, always accept it. If it makes things worse by an amount delta-E, accept it anyway with probability e to the power of minus delta-E divided by a temperature T.

const candidate = perturb(tour);           // e.g. reverse a random segment
const dE = cost(candidate) - cost(tour);
if (dE < 0 || Math.random() < Math.exp(-dE / T)) {
  tour = candidate;                        // accept, sometimes even if worse
}
T *= alpha;                                // cool down, alpha close to 1

At a high starting temperature, delta-E over T is small, so the exponential is close to 1 and almost every move is accepted - the search wanders freely and explores the whole landscape. As T falls, worse moves become exponentially less likely, and by the time T is near zero the process accepts only improving moves and behaves like plain hill-climbing, but now starting from a much better neighbourhood of the search space than a single greedy run would have found.

Choosing the cooling schedule

The schedule is the whole algorithm in practice. The original theoretical result guarantees convergence to the global optimum only for a logarithmic schedule, T(k) proportional to 1 divided by log(k), which is far too slow to run. Real implementations use a geometric schedule, T(k+1) = alpha times T(k) with alpha around 0.95 to 0.999, sometimes holding the temperature fixed for a batch of moves at each level before cooling further. Too fast a schedule freezes the search into a bad local minimum, same as quenching; too slow wastes computation with no further gain. Restarting from the best solution found so far, and stopping when the acceptance rate drops near zero, are common practical refinements.

Why it generalises beyond the travelling salesman

Nothing in the Metropolis rule is specific to tours. Any optimisation problem with a cost function and a way to propose small perturbations to a candidate solution can be annealed: circuit board placement, protein folding energy minimisation, neural network hyperparameter search, job-shop scheduling. What makes it useful is that it needs no gradient and no convexity assumption - only a cost function and a neighbourhood structure - which is why it remains a standard baseline for combinatorial optimisation problems that gradient-based methods cannot touch.

Frequently asked questions

Try it live

Everything above runs in your browser - open Simulated Annealing and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.