Simulated Annealing

Simulated annealing is a probabilistic optimisation heuristic inspired by the thermodynamic process of annealing in metallurgy, where a material is heated and then slowly cooled to reduce defects and reach a low-energy crystalline state. In computational form, it searches a solution space by allowing moves that worsen the objective function with a probability that decreases over time — a controlled introduction of noise that prevents premature convergence to local optima.

The algorithm was introduced by Kirkpatrick, Gelatt, and Vecchi in 1983, drawing directly on the statistical mechanics of the Ising model. The temperature parameter controls the acceptance probability: at high temperature, almost all moves are accepted, allowing the system to explore widely; at low temperature, only improving moves are accepted, driving convergence. The cooling schedule — how temperature decreases — determines whether the algorithm finds the global optimum or freezes into a suboptimal configuration.

Simulated annealing belongs to a family of metaheuristics that trade guaranteed optimality for practical effectiveness on hard problems. It is particularly effective for problems with rugged energy landscapes — many local optima separated by high barriers — where greedy methods fail. Its thermodynamic inspiration is not merely metaphorical: the Boltzmann distribution governs the acceptance probability, and the algorithm's behaviour can be analysed using the same tools that physicists use to study phase transitions and spin glasses.

The connection between optimisation and thermodynamics revealed by simulated annealing is deeper than analogy. It suggests that the difficulty of finding global optima in complex landscapes is a form of computational phase transition: as the problem size grows, the landscape becomes increasingly rugged, and the time required to find good solutions diverges. Simulated annealing does not overcome this transition. It navigates it.