## Definition **Simulated Annealing (SA)** is a metaheuristic for global optimisation that occasionally accepts worse solutions to escape local optima. Inspired by the physical annealing process: heated metals cool slowly to reach low-energy crystalline states. Introduced by Kirkpatrick, Gelatt & Vecchi (1983). ## The Algorithm ``` x ← initial solution T ← initial temperature while T > T_min: for i = 1 to N(T): x' ← neighbour of x (random perturbation) Δ ← f(x') - f(x) if Δ < 0: x ← x' # better → accept else: x ← x' with probability exp(-Δ/T) # worse → maybe accept T ← α · T # cool (typically α = 0.95-0.99) return best solution found ``` The acceptance of worse moves is governed by the [[Metropolis Acceptance Criterion]]; the rate at which $T$ falls is governed by the [[Cooling Schedule]]. ## Why It Escapes Local Optima [[Hill Climbing]] gets stuck at the first local optimum it finds. SA's randomness allows occasional uphill moves — climbing *out* of basins, especially early when temperature is high. As cooling progresses, the algorithm becomes greedier and refines. The trade-off between exploration and exploitation is entirely controlled by $T$. ## Common Use Cases - **Travelling Salesman Problem.** Classic SA application. - **Job-shop scheduling.** - **Graph colouring.** - **Layout problems** (VLSI placement was the original 1983 application). - **Hyperparameter optimisation.** ## Strengths - Simple to implement. - General-purpose: works with any neighbourhood structure, no gradients needed. - Provably converges to the global optimum under a slow enough [[Cooling Schedule]] (Hajek 1988). ## Weaknesses - Slow: many iterations to converge well. - Hyperparameter-sensitive: the cooling schedule matters; bad choices fail. - Beaten by specialised algorithms on most well-studied combinatorial problems. ## When to Reach For SA - Combinatorial problem with no known specialised algorithm. - Neighbourhood structure is clear (small perturbations make sense). - Computational budget is generous. - Hard problem where you need *any* good solution. For well-studied problems (TSP, knapsack, SAT), specialised solvers usually win. SA shines as a general-purpose fallback. ## Related - [[Metropolis Acceptance Criterion]] — the probability rule $\exp(-\Delta/T)$ that decides whether a worse move is accepted - [[Cooling Schedule]] — how $T$ is lowered over time; controls the convergence guarantee (Hajek 1988) and the exploration/exploitation balance - [[Parallel Tempering]] — runs multiple SA chains at different temperatures and swaps configurations, escaping local optima more effectively - [[Quantum Annealing]] — physical realisation via quantum tunnelling (D-Wave); replaces thermal fluctuations with quantum superposition; practical advantage still debated - [[Hill Climbing]] — what SA degenerates to as $T \to 0$ - [[Genetic Algorithms]] — population-based alternative metaheuristic - [[Tabu Search]] — memory-based alternative to SA for combinatorial problems - [[Local vs Global Optimum]] — the core problem SA is designed to address