Introduction

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−ΔE/Te^{-\Delta E / T}, where ΔE>0\Delta E > 0 is how much worse it is and TT is the current temperature. When TT is large, almost anything is accepted. As T→0T \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 TT drops from its initial value T0T_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 Tk+1=α⋅TkT_{k+1} = \alpha \cdot T_k for some α<1\alpha < 1 close to 1, and logarithmic cooling, where Tk=c/ln⁡(1+k)T_k = c / \ln(1 + k) for a constant cc. 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.

Try It

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.

<!-- Main layout: controls on top, canvas landscape below, status line -->
<div class="controls">
  <label>Cooling rate α = <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">Run</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="status" id="status">Adjust α then press Run.</div>
<div class="legend">
  <span class="dot landscape"></span> Energy landscape
  <span class="dot dot-current"></span> Current position
  <span class="dot dot-best"></span> Best found
</div>

/* Base reset + layout */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Energy landscape: a rugged 1-D function with several local minima and
// one global minimum, so the effect of the schedule is easy to see.
const W = 560, H = 220, PAD = 20;
const DOMAIN = [0, 10];
function energy(x) {
  // Composite sine landscape; global min near x=4.8
  return Math.sin(x) + 0.5 * Math.sin(2.2 * x + 0.8) + 0.3 * Math.sin(4 * x - 1) + 0.15 * Math.sin(7 * x);
}
// Pre-compute global minimum by brute-force scan
let globalMinX = 0, globalMinE = Infinity;
for (let i = 0; i <= 2000; i++) {
  const x = DOMAIN[0] + (DOMAIN[1] - DOMAIN[0]) * i / 2000;
  const e = energy(x); if (e < globalMinE) { globalMinE = e; globalMinX = x; }
}

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Map domain coordinates to canvas pixels
function toPixelX(x) { return PAD + (x - DOMAIN[0]) / (DOMAIN[1] - DOMAIN[0]) * (W - 2 * PAD); }
function toPixelY(e) { return H - PAD - ((e - (-2.5)) / (2.5 - (-2.5))) * (H - 2 * PAD); }

function drawLandscape(curX, bestX) {
  ctx.clearRect(0, 0, W, H);
  // Draw the energy curve
  ctx.beginPath();
  for (let i = 0; i <= 500; i++) {
    const x = DOMAIN[0] + (DOMAIN[1] - DOMAIN[0]) * i / 500;
    const px = toPixelX(x), py = toPixelY(energy(x));
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  }
  ctx.strokeStyle = '#a8c0d6'; ctx.lineWidth = 2.5; ctx.stroke();
  // Draw best position (teal)
  if (bestX !== null) {
    const bx = toPixelX(bestX), by = toPixelY(energy(bestX));
    ctx.beginPath(); ctx.arc(bx, by, 6, 0, 2 * Math.PI);
    ctx.fillStyle = '#2a9d8f'; ctx.fill();
  }
  // Draw current position (red)
  if (curX !== null) {
    const cx2 = toPixelX(curX), cy2 = toPixelY(energy(curX));
    ctx.beginPath(); ctx.arc(cx2, cy2, 5, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946'; ctx.fill();
  }
}

drawLandscape(null, null);

let running = false, animId = null;

function setStatus(txt, cls) {
  const el = document.getElementById('status');
  el.textContent = txt; el.className = 'status ' + (cls || '');
}

document.getElementById('alphaSlider').addEventListener('input', function() {
  document.getElementById('alphaVal').textContent = parseFloat(this.value).toFixed(3);
});

document.getElementById('runBtn').addEventListener('click', function() {
  if (running) return;
  running = true;
  if (animId) cancelAnimationFrame(animId);
  setStatus('Searching...', 'running');

  const alpha = parseFloat(document.getElementById('alphaSlider').value);
  // SA params: start hot, cool by alpha each step
  let T = 2.0;
  const Tmin = 0.001;
  let x = DOMAIN[0] + Math.random() * (DOMAIN[1] - DOMAIN[0]);
  let bestX = x, bestE = energy(x);
  let steps = 0;
  const BATCH = 40; // steps per animation frame

  function step() {
    if (!running) return;
    for (let b = 0; b < BATCH; b++) {
      if (T < Tmin) { finish(); return; }
      // Propose a random neighbour within ±0.4 of current x
      const dx = (Math.random() - 0.5) * 0.8;
      const nx = Math.max(DOMAIN[0], Math.min(DOMAIN[1], x + dx));
      const dE = energy(nx) - energy(x);
      // Metropolis acceptance: always accept improvements, accept worse with prob e^(-dE/T)
      if (dE < 0 || Math.random() < Math.exp(-dE / T)) { x = nx; }
      if (energy(x) < bestE) { bestE = energy(x); bestX = x; }
      T *= alpha; steps++;
    }
    drawLandscape(x, bestX);
    animId = requestAnimationFrame(step);
  }

  function finish() {
    running = false;
    drawLandscape(bestX, bestX);
    const gap = Math.abs(bestE - globalMinE);
    const cls = gap < 0.15 ? 'ok' : 'bad';
    setStatus(i18nFmt('Done in %steps% steps — gap from global min: %gap%', { steps: steps, gap: gap.toFixed(3) }), cls);
  }

  step();
});

document.getElementById('resetBtn').addEventListener('click', function() {
  running = false;
  if (animId) cancelAnimationFrame(animId);
  drawLandscape(null, null);
  setStatus('Adjust α then press Run.', '');
});
Result
Console

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 Real Complexity

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

  • Logarithmic schedule — Tk=c/ln⁡(1+k)T_k = c / \ln(1 + k): Hajek (1988) proved that if c≥Δ∗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/Δ∗c / \Delta^* steps.

  • Geometric schedule — Tk+1=α⋅TkT_{k+1} = \alpha \cdot T_k: here TT drops exponentially fast, so the number of steps is polynomial in log⁡(T0/Tfinal)\log(T_0 / T_{\mathrm{final}}). No general convergence guarantee exists, but in practice geometric schedules with α∈[0.9,0.999]\alpha \in [0.9, 0.999] and a large enough T0T_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?

Where It Matters

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 TT 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?

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/simulated-annealing-schedules/Content licensed under CC BY-NC 4.0.