Simulated Annealing — a dart

THE TECHNIQUE accept worse moves, cool the temperature

Minimize a bumpy 1-D landscape. Greedy (red) only ever steps downhill — it dies in the first valley it meets. Annealing (cyan) proposes random jumps; a jump uphill by ΔE is still taken with probability e^−ΔE/T. As T cools the jumps get pickier, and the walk settles in the deepest valley it found. live demo

propose x' = x + step·randn() ΔE = f(x') − f(x) if ΔE < 0 -> accept // downhill: always else accept with P = e^(−ΔE / T) // uphill: sometimes T <- T × cool // 0 < cool < 1

start x = T₀ = cool =

current & annealing best greedy (stuck) true global min (grid scan)

temperature T

—

current f(x)

—

annealing best

—

greedy stuck at

—

HISTORY & CREDIT credit where it is due

Simulated annealing is usually credited to one 1983 paper — and that team did coin the name. But this is a convergent discovery: at least four groups arrived independently, and the accept rule itself is older still. cited

1953 · Metropolis, Rosenbluth, Rosenbluth, Teller & Teller (Los Alamos) — the Metropolis algorithm: accept an uphill move with probability e^−ΔE/T. The engine annealing rides on. J. Chem. Phys.
1970 · Martin Pincus — a Monte-Carlo route to constrained minima. An early, often-overlooked precursor.
1979–81 · Khachaturyan, Semenovskaya & Vainshtein — the same cooling idea for crystallography, independently.
1983 · Scott Kirkpatrick, C. Daniel Gelatt & Mario P. Vecchi (IBM) — named it “simulated annealing,” framed it as general optimization, solved chip layout & TSP. Science 220, 671.
1985 · Vlado Černý (Comenius Univ., Bratislava) — independently discovered the same method for the travelling salesman. J. Optim. Theory Appl.

So the honest line: the name and the popular framing are Kirkpatrick–Gelatt–Vecchi (1983); the method was co-discovered by Černý (1985) and foreshadowed by Pincus and by Khachaturyan’s group; the accept probability is Metropolis et al. (1953). Calling it “Kirkpatrick’s algorithm” flat-out is the common over-simplification. open

RECOMMEND FOR I-13 seeded, not ambient

Annealing needs two things I-13 seems to lack: a source of randomness (the probabilistic accept) and exp(). I asked the real compiler. The first result is a refusal, and it is the right one — proven, not asserted:

$ i13 run t_random.i13 t_random.i13:1:8 E0202 unknown function `random` (no ambient randomness) $ i13 run t_exp.i13 t_exp.i13:1:8 E0202 unknown function `exp` (no transcendental builtin)

The tempting fix is “add random() and exp() as builtins.” Don’t — at least not random(). The whole method is expressible today, deterministically, with a seeded PRNG written in the language itself. I built one (a 31-bit LCG) plus a Taylor exp, and ran it twice:

$ i13 run t_anneal.i13 (seeded LCG + Taylor exp, pure I-13) s1 = 1250496027 u1 = 0.5823075897060335 s2 = 1116302080 u2 = 0.5198186635971069 s3 = 1964818176 u3 = 0.9149397611618042 e = 0.6065321180555555 (true e^-0.5 = 0.6065306597... 6-digit match) run #2 -> byte-identical. deterministic. a receipt, not a coin-flip.

Recommend — REMOVE nothing, ADD sparingly:
• Keep random() rejected. E0202 is a feature. Ambient randomness would break I-13’s determinism and its receipt discipline — two runs must agree. Standardize instead a seeded PRNG library def (the LCG above): the seed is an explicit operand, so the entropy is on the tape and every draw is reproducible.
• Ship exp as a library def, not a builtin — the Taylor version already lands within 2×10⁻⁶. Zero new alphabet symbols, zero new opcodes.
• Bonus, measured: the brief says “no %.” The live binary disagrees — 7 % 3 checks VALID and runs to 1. A modulo BinOp discriminant has already landed, which is exactly what makes the LCG’s mod 2^31 possible. The compiler evolved past the doc; the doc should catch up.
Tradeoff (honest): a seeded PRNG is only as “random” as its generator — an LCG has real spectral flaws and is unfit for cryptography. For optimization that is fine, and the win is total: annealing runs on I-13 as shipped, and the recurring galaxy law holds — seeded, not ambient.