Optimization by Simulated Annealing

Many optimization problems are like navigating a rugged landscape in the dark. The cost function defines the height at every point, and the goal is to find the lowest valley — the global minimum. The simplest approach, iterative improvement (hill climbing in reverse), repeatedly moves to a neighboring solution with lower cost. It always converges, but it converges to the nearest local minimum, which may be arbitrarily far from the best solution.

For small or smooth problems this is fine. But real-world combinatorial optimization problems — laying out millions of transistors on a chip, routing a delivery truck through hundreds of cities, scheduling thousands of tasks — have cost surfaces riddled with local minima. A greedy optimizer applied to a random starting point almost never reaches the global optimum.

When a blacksmith heats metal until it melts, atoms vibrate wildly and explore many configurations. If the metal is cooled slowly (annealed), atoms gradually settle into a regular crystal lattice — the arrangement with the lowest energy. But if cooled too fast (quenched), atoms freeze in a disordered arrangement with higher energy — they got trapped in a local energy minimum.

Kirkpatrick, Gelatt, and Vecchi noticed a deep analogy: the cost function of an optimization problem is like the energy of a physical system, and a candidate solution is like an atomic configuration. The Metropolis algorithm, invented in 1953 to simulate thermal equilibrium, already provided a recipe for sampling configurations at a given temperature. The key insight was to decrease the temperature over time — importing the annealing schedule from metallurgy into the optimization world.

The Metropolis algorithm is the engine inside simulated annealing. At each step it proposes a small random change to the current solution, computes the change in cost $\Delta E$, and decides whether to accept or reject. The decision rule is elegantly simple:

• If the new solution is better ($\Delta E \leq 0$): always accept.
• If the new solution is worse ($\Delta E > 0$): accept with probability $\exp(-\Delta E / T)$.

At high temperature $T$, even large uphill moves have a reasonable chance of acceptance — the algorithm explores freely. As $T$ decreases, the probability of accepting a worsening move shrinks exponentially, and the algorithm becomes increasingly greedy. This is the controlled transition from exploration to exploitation.

Think of it like a coin toss with a biased coin. The bias depends on two things: how bad the proposed move is ($\Delta E$), and how hot the system is ($T$). A barely-worse move at high temperature is almost certainly accepted. A much-worse move at low temperature is almost certainly rejected. The genius is that this simple mechanism is enough to guarantee convergence to the global optimum — given a sufficiently slow cooling schedule.

The cooling schedule controls how temperature decreases over time. It is the bridge between the physical analogy and practical optimization. Too fast and the algorithm quenches into a poor local minimum — too slow and it wastes computation exploring territory it has already mapped.

The original paper used a geometric schedule: $T_{k+1} = \alpha \cdot T_k$ with $\alpha$ typically between 0.9 and 0.99. At each temperature the algorithm runs enough iterations to reach quasi-equilibrium before cooling further. Other schedules include linear decay and logarithmic decay ($T_k = C / \ln(1+k)$), which has a theoretical guarantee of convergence but is impractically slow.

In practice, tuning the schedule is part art, part experiment: start hot enough that ~95% of moves are accepted, cool slowly through the temperature range where the acceptance ratio drops from 90% to 10% (this is where structure forms), then quench at the end.

Putting it all together, simulated annealing works in four stages:

• Initialize. Pick a random starting solution $s$ and a high initial temperature $T_0$.
• Propose. Generate a random neighbor $s'$ of the current solution.
• Decide. Compute $\Delta E = \text{cost}(s') - \text{cost}(s)$. If $\Delta E \leq 0$, accept $s'$. Otherwise, accept with probability $\exp(-\Delta E / T)$.
• Cool. After enough iterations at the current temperature, reduce $T$ according to the cooling schedule. Repeat until $T$ is near zero or the solution has stabilized.

The key design choices are: how to define the neighborhood (what counts as a "small change"), how to set the initial temperature, and which cooling schedule to use. These are problem-specific — there is no universal best setting, which is both the method's flexibility and its limitation.

The theoretical backbone of simulated annealing comes from the Boltzmann distribution in statistical mechanics. At thermal equilibrium, a physical system at temperature $T$ occupies state $s$ with probability proportional to $\exp(-E(s) / T)$. This means lower-energy states are exponentially more likely, but higher-energy states are not impossible — they occur with a frequency that depends on temperature.

The Metropolis algorithm generates a Markov chain whose stationary distribution is exactly the Boltzmann distribution at the current temperature. When $T$ is high, the distribution is nearly uniform — all states are explored. When $T$ is low, probability mass concentrates on the lowest-energy (lowest-cost) states. As $T \to 0$, the distribution converges to a point mass on the global minimum.

The convergence theorem states: if the temperature decreases slowly enough ($T_k \geq C / \ln(1+k)$ for a constant $C$ related to the energy landscape), then the algorithm converges to the global optimum with probability 1. This is a powerful guarantee — but the required cooling rate is too slow for practice, so real implementations use faster schedules and accept near-optimal solutions.

The original paper demonstrated simulated annealing on two NP-hard problems:

The Traveling Salesman Problem (TSP) — find the shortest route visiting every city exactly once. The neighborhood move is a 2-opt swap: reverse a segment of the tour. Kirkpatrick et al. tested on instances with hundreds to thousands of cities and found results competitive with the best-known heuristics of the time.

Graph partitioning for VLSI — divide a circuit's components into two groups so that the number of wires crossing the partition (the "cut") is minimized. This directly impacts chip manufacturing cost. The neighborhood move swaps a component between groups. Simulated annealing found partitions that significantly beat rapid quenching (greedy optimization from a random start), demonstrating that the controlled acceptance of uphill moves is essential.

Simulated annealing showed that borrowing ideas across fields — physics to computer science — could yield powerful algorithms with both theoretical guarantees and practical utility. Today it remains a go-to baseline for any new combinatorial optimization problem, and its descendants power everything from drug discovery to chip design.