Simulated Annealing

Simulated annealing is a probabilistic optimization algorithm that searches for low-cost configurations of a problem by analogy with the physical process of annealing in metallurgy, in which a material is heated and then slowly cooled to settle into a low-energy crystalline state. The algorithm was introduced for combinatorial optimization by Kirkpatrick, Gelatt, and Vecchi in 1983 and independently by Černý in 1985, and it has remained one of the standard tools for problems where the search space is discrete, the objective is rough, and gradient information is unavailable. At each step the algorithm proposes a move to a neighboring configuration, accepts an improvement unconditionally, and accepts a worsening move with probability exp(-ΔE/T), where ΔE is the change in cost and T is a temperature parameter. As the algorithm runs, T is gradually lowered; early in the run, T is high and the algorithm tolerates large worsening moves, allowing it to escape local optima; late in the run, T approaches zero and the algorithm behaves like greedy local search, settling into a low-cost configuration.

The mechanism is a controlled sampling of configuration space whose exploration radius is set by the temperature parameter rather than by the geometry of the problem. Generating a neighbor is cheap because simulated annealing imposes no structure requirements beyond the ability to evaluate cost and perturb the current state. Acceptance of worsening moves via the Metropolis criterion is what distinguishes the algorithm from greedy local search and gives it the theoretical property that, in the limit of an infinitely slow cooling schedule, it converges to the global optimum with probability one. Practical cooling schedules — geometric, logarithmic, adaptive — abandon that guarantee in favor of tractable runtime, and the art of using simulated annealing well lies in choosing a schedule and neighborhood that produce useful behavior in finite time for a given problem.

The tradeoffs against more modern alternatives are well known. Simulated annealing is simple to implement, makes few assumptions about the problem, and can outperform specialized algorithms when the cost function has high irregularities or the search space is poorly understood. It is also slow relative to methods that exploit gradient information, ineffective in continuous high-dimensional problems where gradient-free methods are dominated by gradient-based optimizers like Adam and its variants, and slow to converge on tightly-coupled multi-variable problems. In contemporary machine learning, the algorithm is rarely used to train neural networks directly but is widely used as a component — neural architecture search loops often invoke simulated annealing to explore the discrete space of network structures; chip placement systems like those used for Google's TPUs drive placement refinement with simulated annealing; and certain graph, scheduling, and combinatorial problems in operations research continue to use it as a baseline.

Open questions in the field concern how the algorithm interacts with modern hardware and modern problem structures. Whether simulated annealing can be made to scale to billion-parameter combinatorial problems, where the cost of evaluating each proposed move becomes a dominant fraction of total runtime, is partly a question of clever neighborhood generation and partly a question of using the algorithm as one component of a larger pipeline rather than as the sole optimizer. Connections to diffusion models and to Markov chain Monte Carlo methods remain mathematically close — the Metropolis acceptance is a special case of the broader Metropolis-Hastings scheme — and there is active research on whether modern generative-model machinery can serve as a faster sampler for the kind of distributions simulated annealing implicitly defines. As of mid-2026, the algorithm retains a place in the toolbox as a robust baseline and as a subroutine for discrete exploration, not as a primary optimizer for the kinds of problems that define frontier AI research.