Simulated Annealing (SA)
SA is a single-solution, trajectory-based metaheuristic — it keeps one current state and walks the space sequentially, unlike the population-based methods that dominate this wiki. Introduced by Kirkpatrick, Gelatt & Vecchi (1983) for the travelling-salesman problem, it borrows the metallurgical metaphor of heating then controlled cooling. Source: Wikipedia (independent of andrey-dik).
How it works
A temperature T starts high and cools toward zero. From the current state it proposes a
neighbour and accepts worse solutions with probability exp(−(e′−e)/T) (Metropolis criterion):
- High
T→ exploration: the walk “wander[s] initially towards a broad region of the search space,” freely accepting uphill moves to escape local optima. - Low
T→ exploitation: it “increasingly favor[s] moves that go downhill … and avoid those that go uphill.” The cooling schedule is the exploration-vs-exploitation schedule, made temporal.
Why it matters here
SA is the wiki’s first non-population optimizer, widening the field beyond population-based methods. It has a clean convergence guarantee (“probability … approaches 1 as the annealing schedule is extended”) that is practically useless (“the time required … will usually exceed the time required for a complete search”) — a sharp lesson that asymptotic guarantees don’t beat the no-free-lunch-theorem in practice.
Related
metaheuristic-optimization · exploration-vs-exploitation · no-free-lunch-theorem · genetic-algorithm · differential-evolution · deterministic-oscillatory-search