Simulated Annealing

A bar of steel pulled from a furnace is not immediately useful. A blacksmith heats it to a glowing orange, hammers it into shape, and lets it cool slowly. Cool too fast and the metal locks into a brittle crystal. Cool slowly, and the atoms have time to find a low-energy arrangement — strong, ordered, useful.

Simulated annealing borrows this physical process to solve mathematical problems. In 1983, physicists Scott Kirkpatrick, C. D. Gelatt Jr. and Mario Vecchi published a landmark paper in Science showing that optimization problems — finding the shortest route, the lightest circuit layout, the best schedule — can be attacked by mimicking the cooling of molten metal.

The core idea is disarmingly simple. Suppose you are trying to minimize some cost — say, the length of a route through a set of cities. A naive strategy is hill climbing: always take a step that makes things better. The problem is that hill climbing gets stuck. It finds a local minimum — a solution better than all its neighbors — and stops, even though a much better global minimum might lie just over the next hill.

Simulated annealing adds a thermometer. At high temperature, the algorithm is adventurous: it will accept a worse move with high probability, shaking itself free of local traps. As the temperature falls, it becomes more conservative, eventually settling only into genuine improvements. If the cooling is slow enough, the result is a near-optimal solution.

There is no polynomial-time guarantee. Simulated annealing is a metaheuristic — a strategy for attacking NP-hard problems like the Traveling Salesman Problem when exact methods are hopeless. It trades provable optimality for practical speed, and for many real-world problems it delivers excellent solutions in reasonable time.

Below are 20 cities scattered at random. The algorithm starts with a random tour (the red path connecting all cities) and tries to shorten it by simulated annealing. At each step it picks two random edges, considers swapping them (2-opt move), and accepts the swap immediately if it shortens the tour — or with a shrinking probability if it makes the tour longer.

<div class="controls">
  <button id="annealBtn" type="button">{{btn_anneal}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_new_cities}}</button>
  <span class="temp-label">T = <span id="tempVal">—</span></span>
</div>
<canvas id="canvas" width="460" height="300"></canvas>
<div class="stats">
  <span>{{label_tour_length}} <b id="tourLen">—</b></span>
  <span>{{label_best}} <b id="bestLen">—</b></span>
  <span id="statusMsg"></span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #fff; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.temp-label { font: 600 13px ui-monospace, monospace; color: #555; margin-left: .3rem; }
canvas { display: block; border: 1px solid #d0d7de; border-radius: 8px; background: #f8fafc;
         max-width: 100%; }
.stats { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-top: .45rem;
         font-size: .88rem; color: #444; }
.stats b { color: #1d3557; }
#statusMsg { font-weight: 600; color: #0a7d33; }

// Code not found

Watch what happens: at high temperature the tour thrashes wildly, accepting detours that look terrible. As the temperature falls the improvements stabilize, crossing edges untangle, and the final tour is far shorter than the random starting point. Press Anneal again for a different random instance — the algorithm nearly always finds a good solution, but the path it takes differs every time.

Simulated annealing is not a magic bullet — understanding what it can and cannot guarantee is essential.

• No optimality certificate. Unlike exact algorithms for special cases (Dijkstra for shortest path, the simplex method for LP), simulated annealing gives no proof that its answer is optimal. It is a heuristic.
• Convergence in theory requires infinite time. The classical result (Geman & Geman, 1984) says: if you cool at a rate no faster than

  $$T(t) = \frac{C}{\log(1+t)}$$

  — logarithmically slowly — the algorithm converges in probability to a global optimum. That schedule is so slow it is useless in practice.
• In practice, geometric cooling works. Real implementations use

  $$T(t) = T_0 \cdot \alpha^t$$

  where $\alpha \approx 0.99$, cutting temperature by 1% each step. This is fast enough to be practical, but the optimality guarantee vanishes.
• The underlying problems are NP-hard. Traveling Salesman, graph coloring, VLSI placement — these belong to the class of problems for which no polynomial-time exact algorithm is known. Simulated annealing does not solve NP-hardness; it approximates it under a time budget.
• Why it escapes local minima. The acceptance probability for a worse move is $\exp(-\Delta E / T)$. At high $T$ this is close to 1 — almost any move is accepted. At low $T$ it approaches 0, so only strict improvements are taken. The parameter $T$ is the single knob that controls the explore-exploit tradeoff.

The insight that connects this to statistical physics is deep: the probability distribution over states converges to a Boltzmann distribution at each temperature, and the global optimum is the ground state. Annealing slowly is a physical simulation of finding that ground state.

Simulated annealing became an immediate sensation after the 1983 paper because it solved a real industrial problem — VLSI chip placement — and beat specialized heuristics of the time. Its influence spread quickly:

• Chip design: the placement of millions of transistors and routing of wires on a chip is a giant combinatorial optimization. IBM used simulated annealing in production tools within a year of the original paper.
• Logistics and routing: delivery networks, airline scheduling, and warehouse picking are all variants of the Traveling Salesman Problem or its kin. Annealing provides good practical tours within a time budget.
• Protein structure prediction: folding an amino-acid sequence into its minimum-energy 3D shape is an NP-hard search over a vast conformation space. SA is one of several heuristics that probe this landscape.
• Image reconstruction and machine learning: Boltzmann machines — an early generative neural network — are trained by an annealing-like procedure. The connection between statistical mechanics and learning is not accidental; it runs straight through the Kirkpatrick paper.
• Scheduling and timetabling: school timetables, nurse rosters, and exam schedules are all constraint-laden optimization problems where SA finds near-optimal solutions without exhaustive search.

What unites all these applications is the same geometry: a rugged cost landscape with exponentially many local minima, and a need for a good-enough answer in polynomial (or at least finite) time. Simulated annealing navigates that landscape with physics as its compass.

Simulated annealing is a reminder that the best algorithms sometimes come from the strangest places. A furnace, a slow cool-down, and a Boltzmann distribution gave us a general-purpose heuristic that beats naive hill-climbing on almost every hard combinatorial problem.

Its limits are real: there is no polynomial-time guarantee of optimality, and the cooling schedule is an art as much as a science. But in a world where the problems we care about — routing, scheduling, design — are NP-hard and exact solutions are out of reach, "very good in reasonable time" is often exactly what we need.

The next time you order a package that arrives via a cleverly optimized route, or use a chip with a billion transistors placed by automated tools, there is a good chance simulated annealing played a role — patiently cooling the chaos into something close to perfect.