# Simulated annealing

> Source: https://aiwiki.ai/wiki/simulated_annealing
> Updated: 2026-07-24
> Fact-checked: 2026-07-24
> Categories: Algorithms, Machine Learning, Statistics, Training & Optimization
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) - attribute to "AI Wiki (aiwiki.ai)"
> Cite as: AI Wiki. "Simulated annealing." aiwiki.ai, 24 Jul 2026. https://aiwiki.ai/wiki/simulated_annealing
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution.

Simulated annealing is a probabilistic method for finding a good approximate solution to a global optimization problem, especially one with many local optima that trap ordinary hill-climbing methods. It searches by repeatedly making small random changes to a candidate solution and deciding whether to accept each change according to a rule borrowed from statistical physics: improvements are always accepted, and moves that make the solution worse are accepted with a probability that shrinks as a control parameter called the temperature is lowered. Because worsening moves are tolerated early on, the search can climb out of local minima before the cooling schedule gradually forces it to settle.[1][3]

The method was introduced under its current name by Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi in a 1983 paper in Science, and independently by Vladimir Cerny in 1985.[1][3] Its acceptance rule is the criterion from the 1953 Metropolis Monte Carlo algorithm, and the physical picture behind it is annealing in metallurgy, where a solid is heated and then cooled slowly so that its atoms settle into a low-energy crystalline arrangement rather than a defective, higher-energy one.[1][2] Simulated annealing remains one of the standard general-purpose metaheuristics for hard combinatorial problems, and its ideas resurface across machine learning in the form of temperature-scaled sampling, annealed importance sampling, and the [quantum processor](https://aiwiki.ai/wiki/quantum_processor) hardware built by D-Wave.

## The physical analogy

In metallurgy and materials science, annealing is a heat treatment: a material is raised to a high temperature and then cooled at a controlled rate. At high temperature the atoms have enough thermal energy to move freely and rearrange; as the temperature falls slowly, they tend to lock into a configuration of low internal energy, ideally a well-ordered crystal with few defects. Cooling too quickly (quenching) freezes the material into a disordered, higher-energy state full of dislocations. The slow schedule is what lets the system reach or approach its ground state.[1][3]

Kirkpatrick and his colleagues, who worked at IBM Research, drew an explicit correspondence between this process and optimization. A candidate solution to an optimization problem plays the role of a physical configuration; the cost or objective function being minimized plays the role of the energy; and an artificial temperature controls how willing the search is to move to a higher-cost state. Minimizing the cost function is then analogous to cooling the system toward its lowest-energy state. The name simulated annealing captures the idea directly: the algorithm simulates the annealing of a physical system to solve a numerical problem.[1]

## The Metropolis criterion

The acceptance rule at the core of simulated annealing predates it by three decades. In 1953, Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller published "Equation of State Calculations by Fast Computing Machines" in the Journal of Chemical Physics, describing a Monte Carlo method for computing the properties of interacting particles.[2] The calculations ran on the MANIAC computer at Los Alamos. Rather than sampling configurations at random and weighting each by its Boltzmann factor, their method generates configurations with a probability proportional to that factor and then averages them evenly.[2]

The mechanism, now called the Metropolis criterion, proposes a small random change to the current configuration and evaluates the resulting change in energy, written as the difference dE. If the move lowers the energy it is always accepted. If it raises the energy by dE, it is accepted with probability exp(-dE / kT), where T is the temperature and k is Boltzmann's constant; otherwise the system stays in its current configuration and the step is repeated. Sampling this way produces states distributed according to the Boltzmann distribution at temperature T.[2] This scheme is a special case of what later became known as the Metropolis-Hastings algorithm, a foundational method in [Markov chain Monte Carlo](https://aiwiki.ai/wiki/markov_chain_monte_carlo).[6] A historical note: at a 2003 conference marking the algorithm's fiftieth anniversary, Marshall Rosenbluth stated that he and Arianna Rosenbluth did the actual algorithm development, with Metropolis mainly providing computer time.[2]

Simulated annealing reuses this rule almost unchanged. It drops Boltzmann's constant (folding it into the temperature scale) and, crucially, treats the temperature not as a fixed physical quantity but as a parameter that is lowered over the course of the run.[1][3]

## The algorithm

A basic simulated annealing run keeps a single current solution and repeats the following loop. It generates a neighboring solution by a small random perturbation, computes the change in cost, and applies the Metropolis criterion using the current temperature. Over many iterations the temperature is reduced according to a cooling schedule (also called an annealing schedule). The best solution seen so far is usually tracked separately and returned at the end.[3]

The acceptance probability for a candidate move can be summarized as follows.

| Situation | Change in cost | Probability of acceptance |
|-----------|----------------|---------------------------|
| Move improves the solution | dE < 0 or dE = 0 | 1 (always accepted) |
| Move worsens the solution, high temperature | dE > 0, large T | close to 1 |
| Move worsens the solution, low temperature | dE > 0, small T | close to 0 |

At high temperature the search behaves almost like a random walk, accepting nearly every proposed move and exploring the solution space broadly. As the temperature approaches zero the algorithm increasingly favors downhill moves and rejects uphill ones, so it behaves more and more like greedy local search and eventually settles. The willingness to accept worsening moves in the early, hot phase is what distinguishes simulated annealing from ordinary [gradient descent](https://aiwiki.ai/wiki/gradient_descent) or hill climbing, which can get stuck in the first local optimum they reach.[1][3] Three ingredients must be specified for any application: the neighborhood structure that defines a random move, the cost function, and the cooling schedule.[1]

## Cooling schedules and convergence

The cooling schedule controls the tradeoff between solution quality and running time. Common practical choices include geometric cooling, where the temperature is multiplied by a constant factor slightly less than one at each stage, and linear or logarithmic reductions. A schedule that cools too fast quenches the search into a poor local minimum; one that cools too slowly wastes computation.[3]

Theoretical analyses give a clean but impractical guarantee. For a finite problem, if the temperature is lowered slowly enough, the probability that the algorithm ends in a globally optimal solution approaches one as the schedule is extended. A classic sufficient condition, associated with the analysis of stochastic relaxation by Stuart Geman and Donald Geman in the 1980s, is a logarithmic cooling schedule in which the temperature at step k is proportional to 1 divided by the logarithm of k.[8] The catch is that such a schedule is so slow that the time it guarantees typically exceeds the time needed to exhaustively enumerate the whole solution space, so the result matters more for theory than for practice.[3] Real applications use much faster schedules and accept that the output is a good approximation rather than a certified optimum.

## Applications

Simulated annealing is a general-purpose optimizer, and its first demonstrations targeted two problems that remain canonical examples.[1]

The traveling salesman problem asks for the shortest tour visiting a set of cities exactly once and returning to the start. It is a standard NP-hard benchmark for combinatorial optimization, and both the Kirkpatrick group and Cerny used it to show that annealing could find near-optimal tours. A random move typically reverses a segment of the tour or relocates a city, and the cost is the total tour length.[1][3]

The second showcase was physical design of integrated circuits. Kirkpatrick worked on placement and wiring problems in VLSI chip layout, where components must be positioned on a chip to minimize wire length and congestion subject to hard geometric constraints. The combinatorial explosion of possible placements makes exact optimization infeasible, and annealing gave usable layouts. Placement and floorplanning were among the earliest industrial adoptions of the method, and circuit partitioning was among the physical design problems treated in the original 1983 paper.[1] Beyond these, simulated annealing has been applied to Boolean satisfiability, job-shop and other scheduling problems, protein structure prediction, and many other cost-minimization tasks where the landscape is rugged and gradients are unavailable or unreliable.[3] Annealing over Gibbs distributions also drove Stuart Geman and Donald Geman's influential 1984 work on Bayesian image restoration.[8]

## Relation to Monte Carlo and other methods

Simulated annealing sits inside the broader family of Monte Carlo methods. Each fixed-temperature phase of the algorithm is a Metropolis-Hastings Markov chain Monte Carlo sampler targeting the Boltzmann distribution at that temperature; annealing strings such samplers together while lowering the temperature. One qualification is that when the temperature changes continually the chain does not actually reach the equilibrium distribution at any single temperature, so annealing is better understood as an optimization heuristic inspired by MCMC than as exact equilibrium sampling.[3]

The method is one of a family of general-purpose metaheuristics and black-box optimizers, alongside genetic and evolutionary algorithms, tabu search, and [Bayesian optimization](https://aiwiki.ai/wiki/bayesian_optimization). Related variants include parallel tempering (also called replica exchange), which runs several copies of the system at different temperatures and periodically swaps their states, and threshold accepting, a deterministic relative that accepts any move whose cost increase stays below a shrinking threshold.[3] Simulated annealing also has a lineage in neural computation: it is closely tied to the [Boltzmann machine](https://aiwiki.ai/wiki/boltzmann_machine), a stochastic counterpart of the [Hopfield network](https://aiwiki.ai/wiki/hopfield_network) whose units switch state with temperature-dependent probabilities; running such a network from a high temperature down to a low one is itself a form of simulated annealing.[12]

## Use in machine learning

Within machine learning, simulated annealing appears in several distinct roles rather than as a single dominant tool. As a black-box optimizer, it has been used for [hyperparameter](https://aiwiki.ai/wiki/hyperparameter) search[10] and occasionally as the search strategy in [neural architecture search](https://aiwiki.ai/wiki/neural_architecture_search),[11] where the objective (validation performance) is expensive, non-differentiable, and riddled with local optima. In these settings it competes with random search, Bayesian optimization, and evolutionary methods,[10] and it is valued for its simplicity and its ability to escape poor configurations, though it is not usually the first choice for large modern models where each evaluation costs a full training run.

A more enduring contribution is annealed importance sampling, introduced by Radford M. Neal in 2001 in the journal Statistics and Computing.[5][7] Annealed importance sampling combines the temperature-lowering idea of annealing with importance sampling to estimate ratios of normalizing constants, such as the intractable partition functions that appear in energy-based models and undirected graphical models. It constructs a sequence of intermediate distributions that bridge from an easy-to-sample distribution to the target, and accumulates importance weights along the path. In deep learning it became a standard tool for estimating the partition function of restricted Boltzmann machines and for approximating the likelihood of deep generative models, where a direct calculation is infeasible.[9]

The temperature idea also survives in other guises. Temperature scaling of softmax outputs, entropy-regularized objectives in [reinforcement learning](https://aiwiki.ai/wiki/reinforcement_learning), and various annealing schedules on regularization strength or noise level all echo the same principle of starting exploratory and gradually sharpening. These are conceptual descendants rather than direct uses of the annealing algorithm.

## Quantum annealing and D-Wave

Quantum annealing is a related but physically distinct optimization scheme. Instead of using thermal fluctuations to escape local minima, it uses quantum fluctuations: a transverse magnetic field lets the system tunnel through energy barriers, and the field is slowly reduced so the system relaxes toward the ground state of the problem it encodes.[4] The potential advantage is that tunneling probability depends on both the height and the width of a barrier, so quantum annealing may cross tall but thin barriers that thermal annealing struggles with, at least for certain landscapes.[4]

The idea was studied by Ray, Chakrabarti and Chakrabarti in 1989 and by Finnila and colleagues in 1994, and was formulated in its present form by Tadashi Kadowaki and Hidetoshi Nishimori in 1998.[4] The most visible commercial embodiment is the hardware built by D-Wave Systems, whose machines implement quantum annealing on superconducting processor chips. D-Wave announced its 128-qubit D-Wave One in 2011, and a 512-qubit generation was acquired in 2013 by a Google, NASA, and Universities Space Research Association collaboration.[4] In December 2015, Google reported that a D-Wave 2X outperformed simulated annealing and quantum Monte Carlo by up to a factor of one hundred million on tailored benchmark problems, while a 2014 study in Science had found no quantum speedup; such claims draw scrutiny because the comparison depends heavily on the choice of classical baseline and problem class, and general-purpose quantum advantage from these machines remains contested.[4] The key point for readers of the classical algorithm is that quantum annealing is a different mechanism running on special-purpose hardware, not simply simulated annealing sped up.[4]

## Limitations

Simulated annealing is easy to implement and makes few assumptions about the problem, which is much of its appeal, but it comes with real drawbacks. Its performance is sensitive to design choices with no general recipe: the neighborhood definition, the initial temperature, and the cooling schedule all have to be tuned per problem, and a bad schedule yields poor results or wasted time.[3] The convergence guarantee is asymptotic and, as noted, requires cooling so slow that it offers no practical speed advantage over exhaustive search.[3] For problems where gradients are available and the landscape is well behaved, gradient descent and related methods are far faster. For many combinatorial problems, specialized heuristics or exact solvers now outperform generic annealing. The method is best seen as a robust, widely applicable baseline for rugged optimization landscapes rather than a state-of-the-art solver for any particular problem.[1][3]

## See also

- [Markov chain Monte Carlo](https://aiwiki.ai/wiki/markov_chain_monte_carlo)
- [Gradient descent](https://aiwiki.ai/wiki/gradient_descent)
- [Bayesian optimization](https://aiwiki.ai/wiki/bayesian_optimization)
- [Boltzmann machine](https://aiwiki.ai/wiki/boltzmann_machine)
- [Hopfield network](https://aiwiki.ai/wiki/hopfield_network)
- [Convex optimization](https://aiwiki.ai/wiki/convex_optimization)

## References

1. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. "Optimization by Simulated Annealing." Science, vol. 220, no. 4598, pp. 671-680, May 13, 1983. https://www.science.org/doi/10.1126/science.220.4598.671
2. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. "Equation of State Calculations by Fast Computing Machines." Journal of Chemical Physics, vol. 21, no. 6, pp. 1087-1092, 1953. https://en.wikipedia.org/wiki/Equation_of_State_Calculations_by_Fast_Computing_Machines
3. "Simulated annealing." Wikipedia. https://en.wikipedia.org/wiki/Simulated_annealing
4. "Quantum annealing." Wikipedia. https://en.wikipedia.org/wiki/Quantum_annealing
5. Neal, R. M. "Annealed importance sampling." Statistics and Computing, vol. 11, no. 2, pp. 125-139, 2001. Preprint: https://arxiv.org/abs/physics/9803008
6. "Metropolis-Hastings algorithm." Wikipedia. https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm
7. "Radford M. Neal." Wikipedia. https://en.wikipedia.org/wiki/Radford_M._Neal
8. Geman, S., and Geman, D. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images." IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-741, 1984. https://doi.org/10.1109/TPAMI.1984.4767596
9. Salakhutdinov, R., and Murray, I. "On the Quantitative Analysis of Deep Belief Networks." Proceedings of the 25th International Conference on Machine Learning (ICML), 2008. https://www.cs.toronto.edu/~rsalakhu/papers/dbn_ais.pdf
10. Wainer, J., and Fonseca, P. "How to tune the RBF SVM hyperparameters?: An empirical evaluation of 18 search algorithms." 2020. https://arxiv.org/abs/2008.11655
11. Liu, C.-H., Han, Y.-S., Sung, Y.-Y., Lee, Y., Chiang, H.-Y., and Wu, K.-C. "FOX-NAS: Fast, On-device and Explainable Neural Architecture Search." 2021. https://arxiv.org/abs/2108.08189
12. "Boltzmann machine." Wikipedia. https://en.wikipedia.org/wiki/Boltzmann_machine