Simulated Annealing, in depth: the Metropolis rule, cooling schedules, an O(1)-delta TSP annealer and measured results

The idea: accept some bad moves

The rule comes from statistical physics. Metropolis, the Rosenbluths and the Tellers (1953) sampled states of a physical system at temperature T by proposing random changes and accepting a change that raises energy by delta with probability exp(-delta / T), always accepting improvements. Run long enough at a fixed T, that walk visits each state with probability proportional to exp(-cost / T), the Boltzmann distribution. At high T the distribution is nearly uniform; as T approaches zero it concentrates on the minimum-cost states.

Kirkpatrick, Gelatt and Vecchi (1983), and independently Cerny (1985), turned that sampler into an optimiser by lowering T slowly, the way a metallurgist cools metal so its atoms settle into a low-energy crystal instead of a glassy jumble. The cost function plays the role of energy and the neighbour move the role of thermal agitation.

Two consequences shape everything practical. Temperature is measured in the same units as the cost, so a T that suits one problem is meaningless for another; it must be calibrated from observed deltas. And at any fixed temperature the search keeps moving, so you must record the best state ever visited rather than trusting wherever the walk ends.

Cooling schedules: theory and practice

Theory offers a guarantee with a catch. Geman and Geman (1984) and Hajek (1988) showed that a logarithmic schedule, T_k = c / log(1 + k), reaches a global minimum with probability approaching 1, provided c is at least the depth of the deepest local minimum that is not global. Hajek's condition is the honest part: escaping a valley of depth d at temperature T takes on the order of exp(d / T) moves. A logarithmic schedule is so slow that on real problems it is outperformed by exhaustive search. The guarantee explains why annealing works, not how to run it.

Practice uses geometric cooling: hold T for L moves, then multiply it by alpha, typically 0.8 to 0.99. Three parameters matter. The starting temperature T0 should accept most uphill moves; a common heuristic samples random moves from the initial state, averages the positive deltas, and solves exp(-mean / T0) = 0.8. The moves per level L should scale with the neighbourhood size, often tens to hundreds of times the number of variables. The stopping rule is a final temperature (T0 x 1e-4 below), a stretch of levels with no improvement, or a wall-clock budget. Adaptive schedules that adjust T to hold a target acceptance rate, reheating, and parallel tempering (several chains at different temperatures that swap states) are refinements of the same idea.

Worked example: a 2-opt annealer for TSP

The travelling salesman problem makes a good worked example because the neighbour move and its delta are both classic. A state is a tour, a permutation of the cities. The move is 2-opt: pick two positions and reverse the segment between them, which removes two edges and reconnects the tour with two new ones. Only those four edges change, so the cost delta takes four distance calls however many cities there are. That locality is the single most important performance property of any annealer.

import math, random

def tour_length(pts, tour):
    return sum(math.dist(pts[tour[i - 1]], pts[tour[i]]) for i in range(len(tour)))

def two_opt_delta(pts, t, i, j):
    """Length change if t[i..j] is reversed: edges (a,b),(c,d) become (a,c),(b,d)."""
    a, b = pts[t[i - 1]], pts[t[i]]
    c, d = pts[t[j]], pts[t[(j + 1) % len(t)]]
    return math.dist(a, c) + math.dist(b, d) - math.dist(a, b) - math.dist(c, d)

def calibrate_t0(pts, tour, rng, accept=0.8, samples=500):
    """T0 at which an average uphill move is accepted with probability `accept`."""
    n, ups = len(tour), []
    while len(ups) < samples:
        i, j = sorted(rng.sample(range(1, n), 2))
        d = two_opt_delta(pts, tour, i, j)
        if d > 0:
            ups.append(d)
    return -(sum(ups) / len(ups)) / math.log(accept)

def anneal(pts, seed=0, alpha=0.95, moves_per_t=20_000, t_min_ratio=1e-4):
    rng = random.Random(seed)
    n = len(pts)
    tour = list(range(n))
    rng.shuffle(tour)
    cost = tour_length(pts, tour)
    best, best_cost = tour[:], cost
    t = t0 = calibrate_t0(pts, tour, rng)
    while t > t0 * t_min_ratio:
        for _ in range(moves_per_t):
            i, j = sorted(rng.sample(range(1, n), 2))
            d = two_opt_delta(pts, tour, i, j)             # O(1): four distances
            if d <= 0 or rng.random() < math.exp(-d / t):  # Metropolis rule
                tour[i:j + 1] = reversed(tour[i:j + 1])
                cost += d                                  # running cost, no recompute
                if cost < best_cost:
                    best, best_cost = tour[:], cost
        t *= alpha                                         # geometric cooling
    return best, tour_length(pts, best)                    # true cost, no drift

Notice what the loop never does: recompute the full tour length. The running cost is updated by the delta, and the best tour is copied only on improvement. Applying an accepted move still reverses a segment, which is O(n) in the worst case, but at low temperature few moves are accepted, so evaluation dominates. Production TSP codes reverse the shorter of the two complementary segments, or use doubly linked or tree-based tour representations, to cut that cost further.

Measured results on 200 cities

One run set, 200 cities placed uniformly at random in the unit square (seed 42), pure Python on one laptop. A random tour is 110.9 long. A single greedy 2-opt descent from a random tour, accepting any improving reversal until none is left, reaches 11.92. The best of 50 such descents from different random starts reaches 11.37. Annealing with the code above:

Three readings. A short anneal is no better than a single descent, because the walk never spends long enough at the useful middle temperatures. Ten times more moves per level makes annealing about 4 percent shorter than the best of 50 restarts, a large margin at this stage of optimisation. Beyond that the returns flatten: five times the compute bought nothing measurable between the second and fourth rows. The runs are not equal-time comparisons with the restarts, and two seeds are not statistics; reproduce with your own budget and at least ten seeds before concluding anything. For scale, the asymptotic Beardwood-Halton-Hammersley estimate for random uniform points, about 0.7124 times the square root of n, is 10.07 for 200 points, and boundary effects push the true optimum of a finite instance somewhat above that, so the better runs are within a few percent of optimal.

Designing moves, deltas and constraints

Moving annealing to a new problem means designing four things. The state should make every candidate representable and ideally only feasible ones. The move should be small enough that consecutive states have related costs, otherwise annealing degenerates into random search, and rich enough that any state can reach any other. The delta should be computed locally from the parts that changed. Constraints are handled either by moves that preserve feasibility or by a penalty term with a weight that grows during the run; a fixed small penalty lets the final answer stay infeasible, a fixed huge one freezes the search.

Classic successes follow that recipe. Standard-cell placement tools such as TimberWolf swapped and displaced cells with incremental wirelength deltas. Timetabling uses swap-two-events moves with penalties for soft constraints. Graph colouring recolours one vertex and counts the conflicts it creates or removes. When the problem has an exploitable structure, an exact method from integer programming or a guaranteed bound from approximation algorithms usually beats annealing; it earns its place when the objective is a black box or the constraints are messy.

Running it well

Run annealing like an experiment. Fix seeds and log them so a result can be reproduced. Log temperature, acceptance rate, current cost and best cost per level: a healthy run starts near the calibrated acceptance rate, falls through a transition where most improvement happens, and ends near zero acceptance. Spend compute where the transition is, either by slowing cooling there or by restarting from the best state at a moderate temperature. Since independent chains do not communicate, the cheapest parallelism is many seeds on many cores and keeping the best result. Always finish with a greedy descent from the best state, which is free polish. Compare against a baseline at equal wall-clock time, typically restarted local search, or a genetic algorithm when crossover makes sense for the encoding.

Failure modes

• Full cost recomputation. Computing the whole objective per move turns O(1) work into O(n) and makes every run 100 to 1,000 times slower than it needs to be.
• Temperature in the wrong units. A T0 copied from another problem is either so hot the run is random walk until the end or so cold it is greedy descent from the start. Calibrate from deltas.
• Returning the final state. The last state at a non-zero temperature can be worse than one seen earlier. Keep the best.
• Moves too large. Shuffling half the solution per move destroys the correlation between neighbouring costs and the schedule stops mattering.
• Floating-point drift. A running cost accumulated over millions of deltas drifts; recompute the true cost at each level and at the end.
• Overflow in exp. Python's math.exp raises OverflowError for a large positive argument; call it only for positive delta, as the code does.

Trade-offs

What to do next

1. Write the cost function and a small neighbour move; prove to yourself any state can reach any other.
2. Derive the delta for that move from only the changed parts, and test it against full recomputation on random moves.
3. Calibrate T0 to an 80 percent uphill acceptance rate from sampled deltas.
4. Start with alpha 0.95 and moves per level around 100 times the variable count; log acceptance and best cost per level.
5. Run at least ten seeds and compare the median with restarted descent at the same wall-clock budget.
6. Increase moves per level until the median stops improving, then stop paying for more.
7. Polish the best state with greedy descent and verify its cost from scratch before using it.