Skip to content
Computational Lab.

Simulated Annealing

Bad moves are allowed - while it's hot.

Intermediate / optimization / sampling

Simulated annealing escapes local optima by accepting worsening moves with probability exp(-delta/T) under a falling temperature T. The tour on 24 cities starts as a tangled mess; as the temperature cools, the Metropolis acceptance rate on the metrics drops and the 2-opt reversals settle toward a short route.

Tagged: Metropolis criterion, 2-opt, traveling salesman, cooling schedule

Live simulation

The acceptance rate is the thermometer: it freezes as the temperature falls.

Speed

The acceptance rate is the thermometer: it freezes as the temperature falls.

Mathematics

Simulated annealing accepts a worsening move with the Metropolis probability exp(-delta / T): at high temperature the search roams the energy landscape, at low temperature it only accepts improvements. Cooling T slowly is what earns the guarantee of settling near a good optimum.

accept if delta < 0, else with probability exp(-delta / T)

cooling: T <- T * coolingRate each move attempt

move: reverse tour[i..k] (2-opt); delta = added edges - removed edges

The 2-opt reversal is chosen because only two edges change under a tour reversal, so delta is computable in constant time - the difference between a toy and a real annealer. The acceptance-rate metric doubles as a thermometer: when it hits zero, the search has frozen wherever it stands.

How it works

24 cities live on a seeded plane; the tour is a permutation array. Each tick attempts a fixed number of reversal moves, applying Metropolis acceptance and cooling the temperature multiplicatively. The length history strip shows the classic annealing signature: early chaos, then rapid refinement, then stillness.

Reset replays the same city layout and shuffle for the same seed.

Implementation

src/engine/experiments/simulated-annealing.ts · 190 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4const CITIES = 24;
5
6/**
7 * Simulated annealing on a 24-city traveling-salesman tour: 2-opt reversal
8 * moves accepted by the Metropolis criterion under an exponential cooling
9 * schedule. Watch bad moves become rare as the temperature falls.
10 */
11export class SimulatedAnnealingExperiment extends BaseExperiment {
12 readonly id = "simulated-annealing";
13
14 private cityX = new Float64Array(CITIES);
15 private cityY = new Float64Array(CITIES);
16 private tour = new Int32Array(CITIES);
17 private length = 0;
18 private bestLength = Infinity;
19 private temperature = 1;
20 private accepted = 0;
21 private rejected = 0;
22 private acceptedRecent = 0;
23 private rejectedRecent = 0;
24 private history: number[] = [];
25
26 protected params(): ParameterDef[] {
27 return [
28 { key: "temp0", label: "Initial temperature", min: 0.2, max: 3, step: 0.1, defaultValue: 1.2 },
29 { key: "cooling", label: "Cooling rate", min: 0.9, max: 0.9995, step: 0.0005, defaultValue: 0.998 },
30 { key: "moves", label: "Move attempts per tick", min: 1, max: 60, step: 1, defaultValue: 12 },
31 ];
32 }
33
34 protected onReset(): void {
35 for (let i = 0; i < CITIES; i++) {
36 this.cityX[i] = 0.08 + this.rng() * 0.84;
37 this.cityY[i] = 0.1 + this.rng() * 0.8;
38 this.tour[i] = i;
39 }
40 // Seeded shuffle start.
41 for (let i = CITIES - 1; i > 0; i--) {
42 const j = Math.floor(this.rng() * (i + 1));
43 const tmp = this.tour[i];
44 this.tour[i] = this.tour[j];
45 this.tour[j] = tmp;
46 }
47 this.length = this.tourLength();
48 this.bestLength = this.length;
49 this.temperature = this.num("temp0");
50 this.accepted = 0;
51 this.rejected = 0;
52 this.acceptedRecent = 0;
53 this.rejectedRecent = 0;
54 this.history = [];
55 }
56
57 protected onParameterChange(key: string): void {
58 if (key !== "moves") this.reset();
59 }
60
61 resize(width: number, height: number): void {
62 this.width = width;
63 this.height = height;
64 }
65
66 private dist(a: number, b: number): number {
67 return Math.hypot(this.cityX[a] - this.cityX[b], this.cityY[a] - this.cityY[b]);
68 }
69
70 private tourLength(): number {
71 let sum = 0;
72 for (let i = 0; i < CITIES; i++) {
73 sum += this.dist(this.tour[i], this.tour[(i + 1) % CITIES]);
74 }
75 return sum;
76 }
77
78 private deltaFor(i: number, k: number): number {
79 // Reversal of tour[i..k]: only the two boundary edges change.
80 if (i === k || (i === 0 && k === CITIES - 1)) return 0;
81 const prev = this.tour[(i - 1 + CITIES) % CITIES];
82 const start = this.tour[i];
83 const end = this.tour[k];
84 const after = this.tour[(k + 1) % CITIES];
85 const removed = this.dist(prev, start) + this.dist(end, after);
86 const added = this.dist(prev, end) + this.dist(start, after);
87 return added - removed;
88 }
89
90 protected onUpdate(): void {
91 const moves = this.num("moves");
92 for (let m = 0; m < moves; m++) {
93 let i = Math.floor(this.rng() * CITIES);
94 let k = Math.floor(this.rng() * CITIES);
95 if (i > k) [i, k] = [k, i];
96 if (i === k || (i === 0 && k === CITIES - 1)) continue;
97 const delta = this.deltaFor(i, k);
98 // Metropolis criterion.
99 if (delta < 0 || this.rng() < Math.exp(-delta / Math.max(1e-9, this.temperature))) {
100 // Reverse tour[i..k].
101 for (let a = i, b = k; a < b; a++, b--) {
102 const tmp = this.tour[a];
103 this.tour[a] = this.tour[b];
104 this.tour[b] = tmp;
105 }
106 this.length += delta;
107 this.accepted += 1;
108 this.acceptedRecent += 1;
109 } else {
110 this.rejected += 1;
111 this.rejectedRecent += 1;
112 }
113 this.temperature *= this.num("cooling");
114 this.temperature = Math.max(1e-4, this.temperature);
115 }
116 this.length = this.tourLength();
117 this.bestLength = Math.min(this.bestLength, this.length);
118 this.history.push(this.length);
119 if (this.history.length > 500) this.history.shift();
120 if (this.acceptedRecent + this.rejectedRecent > 600) {
121 this.acceptedRecent = 0;
122 this.rejectedRecent = 0;
123 }
124 }
125
126 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
127 ctx.fillStyle = theme.bg;
128 ctx.fillRect(0, 0, this.width, this.height);
129 // Tour
130 ctx.strokeStyle = theme.accent;
131 ctx.lineWidth = 1.8;
132 ctx.beginPath();
133 for (let i = 0; i <= CITIES; i++) {
134 const city = this.tour[i % CITIES];
135 const px = this.cityX[city] * this.width;
136 const py = this.cityY[city] * this.height;
137 if (i === 0) ctx.moveTo(px, py);
138 else ctx.lineTo(px, py);
139 }
140 ctx.stroke();
141 ctx.fillStyle = theme.fg;
142 for (let i = 0; i < CITIES; i++) {
143 ctx.beginPath();
144 ctx.arc(this.cityX[i] * this.width, this.cityY[i] * this.height, 3, 0, Math.PI * 2);
145 ctx.fill();
146 }
147 // Length history
148 if (this.history.length > 2) {
149 let lo = Infinity;
150 let hi = -Infinity;
151 for (const h of this.history) {
152 lo = Math.min(lo, h);
153 hi = Math.max(hi, h);
154 }
155 const span = Math.max(1e-6, hi - lo);
156 ctx.strokeStyle = theme.viz[1];
157 ctx.lineWidth = 1.5;
158 ctx.globalAlpha = 0.85;
159 ctx.beginPath();
160 for (let i = 0; i < this.history.length; i++) {
161 const x = (i / (this.history.length - 1)) * this.width;
162 const y = this.height - 8 - ((this.history[i] - lo) / span) * 30;
163 if (i === 0) ctx.moveTo(x, y);
164 else ctx.lineTo(x, y);
165 }
166 ctx.stroke();
167 ctx.globalAlpha = 1;
168 }
169 }
170
171 getMetrics() {
172 const recentTotal = this.acceptedRecent + this.rejectedRecent;
173 return {
174 temperature: this.temperature.toFixed(3),
175 tourLength: this.length.toFixed(2),
176 best: this.bestLength.toFixed(2),
177 acceptRate: recentTotal > 0 ? `${((this.acceptedRecent / recentTotal) * 100).toFixed(0)} %` : "n/a",
178 moves: (this.accepted + this.rejected).toLocaleString("en-US"),
179 };
180 }
181
182 describe(): string {
183 return `Annealing on ${CITIES} cities: tour length ${this.length.toFixed(1)} at temperature ${this.temperature.toFixed(2)} (best seen ${this.bestLength.toFixed(1)}).`;
184 }
185
186 entities(): number {
187 return CITIES;
188 }
189}
190

Performance

Time per tick
O(1) per move attempt (constant-time delta for 2-opt)
Space
The tour array plus a length history
Notes
Reheat by raising the initial temperature and watch a frozen tour start moving again.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.