Optimization

Simulated Annealing

Borrow the physics of slow cooling: accept worse solutions with a temperature-dependent probability to escape local minima.

An analogy to cooling metal

Simulated annealing mimics annealing in metallurgy, where slow cooling lets atoms settle into a low-energy crystalline state. The optimizer treats the objective as an energy to minimize and a temperature parameter T that starts high and decreases. At high T it accepts many uphill moves to explore; as T falls it becomes increasingly greedy.

The Metropolis acceptance rule

Kronos motion — learning physics

From the current point, propose a random neighbor. If it lowers the objective, accept it. If it raises the objective by delta, accept it anyway with probability exp(-delta / T). High temperature makes uphill moves likely, enabling escape from local minima; low temperature makes them rare, so the search settles.

The cooling schedule

Geometric: T_{k+1} = alpha * T_k with alpha near 1 (e.g. 0.95).
Logarithmic: T_k = c / log(k), which has a theoretical convergence guarantee but is impractically slow.
Adaptive schedules adjust cooling based on acceptance statistics.

Convergence guarantee

With a sufficiently slow (logarithmic) cooling schedule, simulated annealing converges in probability to the global optimum. In practice faster schedules are used, sacrificing the guarantee for speed. The result is a robust heuristic that handles discrete, continuous, and combinatorial problems.

Strengths and uses

Simulated annealing needs only the ability to evaluate the objective and generate neighbors, so it works on black-box, nonsmooth, and combinatorial problems like the traveling salesman problem and circuit layout. It requires little problem structure but can need many evaluations, making it less suitable when each evaluation is very expensive.

python

import math, random
def anneal(f, x, neighbor, T=1.0, alpha=0.95, steps=10000):
    for _ in range(steps):
        y = neighbor(x); d = f(y) - f(x)
        if d < 0 or random.random() < math.exp(-d/T):
            x = y
        T *= alpha
    return x

Simulated annealing tackles rugged combinatorial layout and scheduling problems where the landscape is riddled with local minima.