Simulated Annealing

Simulated annealing, introduced by Kirkpatrick Gelatt and Vecchi (1983) and independently by Cerny (1985), is a single-solution metaheuristic that emulates the slow cooling of metals to form low-energy crystalline structures. The algorithm starts at a high initial temperature T0 and evaluates each neighbourhood move by Δ = f(new) − f(current): improving moves (Δ < 0) are always accepted, while worsening moves (Δ > 0) are accepted with the Metropolis probability P = exp(−Δ / T). Accepting worsening moves is the defining feature that lets the algorithm escape local-optimum basins. Temperature drops over time according to a cooling schedule: geometric T_k+1 = αT_k with α ∈ [0.85, 0.99], logarithmic (Geman and Geman 1984, convergent in theory but slow), or adaptive. The cooling schedule, initial temperature (a practical rule sets it so the initial acceptance rate is about 80 percent), number of trials per temperature, and stopping criterion are the critical parameters. Compared with genetic algorithms, simulated annealing maintains only one candidate, requires no population, and uses minimal memory. Applications include VLSI placement, vehicle routing, scheduling, and facility layout. On combinatorial problems it competes closely with tabu search. References: Aarts and Korst (1989), Henderson Jacobson Johnson (2003).