Simulated Annealing Schedules

A blacksmith who plunges red-hot steel into cold water gets a brittle blade. One who lets it cool slowly gets a tough, well-ordered crystal. Simulated annealing steals this metallurgical trick and applies it to optimization: explore wildly when "hot," settle down as you "cool."

The algorithm dates to Kirkpatrick, Gelatt, and Vecchi (1983), who showed that adding controlled randomness to a hill-climber lets it escape local minima — the dead ends that trap greedy search. The key idea is the acceptance rule: a worse solution is accepted with probability $e^{-\Delta E / T}$, where $\Delta E > 0$ is how much worse it is and $T$ is the current temperature. When $T$ is large, almost anything is accepted. As $T \to 0$, only improvements get through.

But the question that decides everything is not whether to cool — it is how fast. The cooling schedule (also called the annealing schedule) specifies how $T$ drops from its initial value $T_0$ to a final value near zero. Choose it poorly and the algorithm either freezes prematurely into a bad solution or wastes exponential time slowly converging. Choose it well and you consistently find near-optimal answers to problems that defeat exact methods.

Two families of schedules dominate practice: geometric cooling, where $T_{k+1} = \alpha \cdot T_k$ for some $\alpha < 1$ close to 1, and logarithmic cooling, where $T_k = c / \ln(1 + k)$ for a constant $c$. They trade off speed against solution quality in a precise, mathematically provable way — and the gap between them can be the difference between a practical tool and a theoretical curiosity.

The landscape below is a one-dimensional energy function with several local minima and one global minimum. Simulated annealing starts at a random point and walks the landscape, sometimes accepting uphill moves. Adjust the cooling rate $\alpha$ (for geometric cooling) and press Run to watch it search.

<!-- {{c_layout_comment}} -->
<div class="controls">
  <label>{{lbl_alpha}} <strong id="alphaVal">0.95</strong>
    <input type="range" id="alphaSlider" min="0.80" max="0.999" step="0.001" value="0.95">
  </label>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="status" id="status">{{status_idle}}</div>
<div class="legend">
  <span class="dot landscape"></span> {{legend_landscape}}
  <span class="dot dot-current"></span> {{legend_current}}
  <span class="dot dot-best"></span> {{legend_best}}
</div>

/* {{c_reset_comment}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.controls { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 140px; accent-color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border-radius: 8px; background: #f4f7fa; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .5rem 0 .3rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.running { color: #1d6fa8; }
.legend { display: flex; gap: 1rem; font-size: .82rem; align-items: center; flex-wrap: wrap; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; vertical-align: middle; }
.landscape { background: #a8c0d6; }
.dot-current { background: #e63946; }
.dot-best { background: #2a9d8f; }

// Code not found

With a fast cool ($\alpha$ near 0.8) the algorithm quickly freezes wherever it lands — often a local minimum. With a slow cool ($\alpha$ near 0.999) it explores broadly and almost always finds the global minimum, but takes far more steps. The sweet spot for a given problem is what schedule design is all about.

The mathematics of cooling schedules lives in the theory of Markov chains. At each temperature $T$, the acceptance rule defines a Markov chain over the solution space; as $T$ decreases the chain's stationary distribution concentrates on the global optimum.

• Logarithmic schedule — $T_k = c / \ln(1 + k)$: Hajek (1988) proved that if $c \geq \Delta^*$, where $\Delta^*$ is the depth of the deepest local minimum that is not the global optimum, then the chain converges to the global optimum with probability 1. This is the only schedule known to give a provable guarantee, but it converges agonizingly slowly — exponential in $c / \Delta^*$ steps.

• Geometric schedule — $T_{k+1} = \alpha \cdot T_k$: here $T$ drops exponentially fast, so the number of steps is polynomial in $\log(T_0 / T_{\mathrm{final}})$. No general convergence guarantee exists, but in practice geometric schedules with $\alpha \in [0.9, 0.999]$ and a large enough $T_0$ reliably find near-optimal solutions for problems like traveling salesperson routes, graph coloring, and circuit layout.

The gap captures a deep tension in optimization: provable correctness costs exponential time; practical speed sacrifices the guarantee. Almost every deployed use of simulated annealing is geometric — engineers accept the heuristic trade-off because waiting for logarithmic convergence is not an option.

A useful intuition: think of the landscape as a hilly terrain in fog. A fast geometric cool is like turning off a flashlight too soon — you stop wherever you happen to stand. The logarithmic schedule keeps the light on long enough that, given infinite time, you would reach the valley floor. Real engineering asks: how long is long enough for this landscape?

Simulated annealing with a carefully chosen schedule is a workhorse of combinatorial optimization:

• VLSI chip layout: the original 1983 paper applied it to placement of circuit components. Modern placer tools still use variants of geometric cooling tuned to minimize wire length and chip area.
• Protein structure prediction: the energy landscape of a folding protein has an astronomical number of local minima. Annealing with problem-specific schedules is one of the few methods that can navigate it — though non-convex optimization remains open at scale.
• Combinatorial scheduling: timetables, job shops, and vehicle routing all expose rugged landscapes where geometric schedules with reheat strategies (raising $T$ when progress stalls) are standard.
• Machine learning hyperparameter search: the "temperature" metaphor reappears in stochastic gradient descent with learning-rate warm restarts — the schedule shape mirrors annealing, and the same intuitions about exploration vs. exploitation apply.
• Quantum annealing: physical quantum annealers (such as D-Wave systems) replace thermal fluctuations with quantum tunneling, but the schedule concept survives: the transverse field must be decreased slowly enough to stay near the ground state.

In every case the practitioner faces the same fundamental question the theory identified: how much time can you afford to spend searching versus exploiting what you have found?

Simulated annealing is a beautiful idea: borrow the patience of a slow-cooling crystal and apply it to computation. But the algorithm's soul lives in its schedule. Cool too fast and you crystallize into a bad solution, forever unable to escape. Cool too slowly and the search never ends.

The logarithmic schedule is mathematically perfect and practically useless at scale. The geometric schedule is mathematically imperfect and practically indispensable. That gap — between what we can prove and what we can afford to run — is a recurring theme in the study of hard non-convex optimization problems.

The next time you encounter a "learning rate schedule" or a "temperature decay" in a machine learning paper, you are reading the same idea dressed in different notation. The blacksmith's wisdom — heat, then cool with patience — turns out to be one of the most transferable heuristics in all of computer science.