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.

Genealogy and schedule mechanics

SA didn’t spring from one mind. It “is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system” (Metropolis et al., 1953), and the same idea was “independently introduced on several occasions, including Pincus (1970), Khachaturyan et al. (1979, 1981), Kirkpatrick, Gelatt and Vecchi (1983), and Cerny (1985)” wikipedia-simulated-annealing — so Černý (1985) is the standard co-credit alongside Kirkpatrick. The acceptance rule the page above describes is just the Metropolis test borrowed wholesale.

Two refinements matter in practice. Adaptive SA “connect[s] the cooling schedule to the search progress” instead of fixing it up front, and restarting lets the walk “move back to a solution that was significantly better” rather than always stepping from the current state wikipedia-simulated-annealing — both ways of keeping the exploration-vs-exploitation budget responsive to what the search has found.

Related

metaheuristic-optimization · exploration-vs-exploitation · no-free-lunch-theorem · genetic-algorithm · differential-evolution · deterministic-oscillatory-search · tabu-search · wikipedia-simulated-annealing