Simulated annealing is a mathematical optimization method that searches for low-cost solutions by occasionally accepting changes that make the current solution worse. Its name comes from physical annealing, in which a material is heated and then cooled under controlled conditions so that its microscopic structure can approach a low-energy configuration. In the computational method, an objective function plays the role of energy, and an artificial temperature controls the willingness to accept unfavorable changes.
The method is particularly useful when a search space contains many local optima, derivatives are unavailable, or solutions are discrete structures such as schedules, routes, and circuit layouts. At high temperatures, the search can move relatively freely; as temperature decreases, it increasingly favors improvements. Under appropriate mathematical conditions and sufficiently slow cooling, simulated annealing converges toward globally optimal solutions. Practical implementations usually cool much faster and therefore function as heuristics rather than as procedures that certify optimality.
Simulated annealing connects statistical mechanics, Markov chains, and global optimization. Its effectiveness depends not only on the cooling schedule but also on how solutions are represented, which changes are proposed, and how computational effort is distributed across temperatures.
Physical origins and historical development
The physical analogy behind simulated annealing concerns the competition between energy reduction and thermal fluctuations. In a material at thermal equilibrium, low-energy configurations are favored, but configurations with higher energy remain possible because of thermal motion. Slow cooling can allow structural rearrangements before those fluctuations become too weak. Rapid cooling, by contrast, can leave a material trapped in a metastable configuration. Simulated annealing translates this distinction into the difference between searching broadly enough to leave a local optimum and settling too early into a poor solution.
The key computational precursor was the 1953 paper “Equation of State Calculations by Fast Computing Machines” by Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Their procedure generated configurations of a physical system by proposing random changes and accepting energy-increasing changes with a temperature-dependent probability. This became known as the Metropolis algorithm. Its original purpose was equilibrium sampling rather than optimization: temperature was a physical parameter, not necessarily a quantity reduced during the computation.
Scott Kirkpatrick, C. Daniel Gelatt Jr., and Mario P. Vecchi presented simulated annealing as a general optimization approach in their 1983 paper “Optimization by Simulated Annealing.” They related difficult combinatorial problems to energy landscapes and demonstrated the relevance of annealing to electronic circuit design. Vladimír Černý independently developed a related approach, published in 1985, using the traveling salesman problem as a central example. These contributions established the now-standard idea of treating an objective value as an artificial energy and gradually lowering an algorithmic temperature.
Theoretical analysis developed alongside practical applications. Stuart Geman and Donald Geman’s 1984 work on Bayesian image restoration connected annealing with probabilistic image models and established convergence results for suitably slow cooling. Bruce Hajek’s 1988 analysis gave a precise characterization of cooling requirements in terms of the depth of nonoptimal energy wells. These results explained why logarithmic cooling appears in convergence theory and why rapidly decreasing schedules can freeze before the search escapes a deep local minimum.
The physical analogy is useful but has limits. A computational temperature need not be measured in kelvin, and an optimization problem need not describe matter or heat. Physical annealing also involves dynamics, material defects, and cooling-rate effects that a basic algorithm does not explicitly model. What carries over mathematically is the use of temperature-dependent transition probabilities to balance exploration against preference for low objective values.
State spaces, energy landscapes, and equilibrium distributions
A simulated annealing problem begins with a search space and an objective to be minimized. An element is called a state or configuration. It may represent a permutation of cities, an assignment of jobs to machines, or a vector of continuous parameters. The global minimizers form the set
For a finite state space at fixed temperature , the target probability distribution is commonly the Boltzmann distribution
The normalizing quantity , called the partition function, is usually unnecessary for implementing the algorithm. The physical Boltzmann constant is absorbed into the numerical definition of temperature. Consequently, must be interpreted on the same scale as objective differences.
At high temperature, states with different energies have relatively similar probabilities. As decreases, probability becomes concentrated on low-energy states. In a finite space, approaches the uniform distribution over global minimizers as . This equilibrium statement does not by itself prove that a cooling algorithm finds those minimizers: the evolving chain must have enough time to move between relevant regions while the temperature changes.
A neighborhood structure determines which configurations can be proposed from one another. It converts the search space into a graph, allowing ideas from graph theory to describe accessibility and barriers. A local minimum is a state with no improving neighbor under this chosen structure. Thus local optimality is not a property of the objective alone. A tour that is locally optimal under exchanging two cities may admit improvement under reversing a segment.
The landscape metaphor includes valleys, plateaus, and barriers, but these have precise algorithmic counterparts. A barrier is the necessary objective increase along a path between regions; a plateau consists of connected states with equal objective values. The difficulty of a landscape depends on both the objective and the available moves. Large, well-designed moves can bypass obstacles that appear severe under small changes.
For continuous spaces, the corresponding equilibrium distribution is a probability density function, with a normalizing integral rather than a finite sum. Its existence requires integrability. Concentration near minimizers then depends on the geometry of the objective and the reference measure, and does not generally produce a uniform distribution across isolated minima.
Transition rules and the basic algorithm
At iteration , simulated annealing maintains a current state and a temperature . A candidate is drawn from a proposal distribution . For a symmetric proposal, meaning , the standard Metropolis acceptance probability is
An improving move is always accepted, as is an equal-energy move. A worsening move of size is accepted with probability . If rejected, the next state remains ; rejection is therefore a genuine self-transition, not a request to keep drawing until some proposal is accepted.
The ratio , rather than either quantity alone, controls behavior. A worsening move of size is accepted with probability about at temperature , but only about at temperature . The random decision can be implemented by drawing uniformly from and accepting when
This form avoids explicitly calculating a very small exponential function value.
For an asymmetric proposal, the Metropolis–Hastings algorithm supplies the corrected probability
when the relevant proposal probabilities are defined. At fixed temperature, this construction satisfies detailed balance with respect to . Together with suitable accessibility conditions, it gives the desired stationary distribution. Some optimization heuristics omit the proposal ratio, but then the usual Boltzmann equilibrium argument may no longer apply.
A basic implementation can be expressed as follows:
choose an initial state x
best ← x
for each temperature T in the cooling schedule:
repeat a prescribed number of times:
propose y from the neighborhood of x
compute ΔE = E(y) − E(x)
accept or reject y using the acceptance rule
if accepted:
x ← y
if E(x) < E(best):
best ← x
return best
The current state and the best state serve different purposes. The current state must be allowed to worsen so that the chain can leave local minima. The best state records the strongest solution encountered and is normally returned at termination. Replacing the current state with the best state after every worsening move would destroy the intended dynamics.
For a symmetric proposal, the zero-temperature limit rejects all strictly worsening moves while accepting nonworsening ones. The method then becomes a randomized form of local search. Simulated annealing differs chiefly in its controlled use of positive temperatures before reaching that regime.
Cooling schedules and parameter calibration
A cooling schedule specifies the temperature sequence and the amount of work performed at each temperature. One common organization uses temperature levels , with several proposals at each level. Another changes temperature after every proposal. These formulations can be translated into one another, but their iteration counts must be distinguished: a schedule indexed by temperature levels is not equivalent to the same formula indexed by individual objective evaluations.
Geometric cooling is widely used:
Its popularity reflects its simplicity and predictable allocation of temperature levels. A factor closer to one gives slower cooling, but the factor alone does not determine computational effort. Ten proposals per temperature and ten thousand proposals per temperature produce very different searches even with identical values of . Linear cooling, , reaches zero in finite time; logarithmic schedules decrease much more slowly.
Initial temperature is meaningful only relative to typical objective changes. If a representative worsening move has size , and a desired acceptance probability for that move is , then
For example, and give . This is a calibration relation, not a universal prescription. Using a mean or quantile of observed positive changes gives only an approximation to the overall uphill acceptance rate, because different moves have different sizes and the distribution changes during the search.
Scaling the objective illustrates the same point. If every energy is multiplied by a positive constant , preserving acceptance probabilities requires multiplying temperature by . Adding a constant to all energies changes nothing, because acceptance depends on differences. These invariances are important when comparing implementations that use different units or normalizations.
Adaptive schedules adjust cooling in response to observed behavior, such as acceptance rate, objective fluctuations, or elapsed time without improvement. Reheating temporarily raises temperature after apparent stagnation. Both can be useful heuristics, but their behavior depends on the adaptation rule; convergence results for a predetermined schedule do not automatically carry over.
Stopping rules include a fixed evaluation budget, a minimum temperature, or a specified number of temperature levels without improvement. None of these alone certifies global optimality. A low acceptance rate may indicate freezing, an unsuitable neighborhood, or badly scaled proposals. Conversely, a high acceptance rate can persist when most proposals are tiny or move across a flat plateau. Acceptance statistics are informative only when interpreted together with move sizes and objective progress.
Convergence theory and energy barriers
The main theoretical question is whether the evolving state reaches the set of global minimizers as temperature approaches zero. At fixed positive temperature, a finite, irreducible, aperiodic Markov chain converges to its stationary distribution. Simulated annealing is more difficult to analyze because its transition probabilities change over time. It is a time-inhomogeneous stochastic process, and its distribution may lag far behind the equilibrium distribution associated with its current temperature.
For a finite state space with a fixed connected undirected neighborhood graph, barrier heights provide a useful characterization. Let a path from to be a sequence of allowed moves. Define the communication height by
For a nonglobal state , its depth can be defined as the least necessary rise before reaching a strictly lower-energy state:
The critical depth is the largest such depth among nonglobal states. It measures the deepest trap that must be escaped, rather than the full range of objective values.
Under standard finite-state assumptions, a logarithmic schedule of the form
with and larger than the critical depth yields convergence in probability to the global-minimizer set. The precise conditions depend on the proposal mechanism and schedule. The central insight is that cooling must remain slow enough to permit escape from the deepest relevant nonoptimal wells.
The reason logarithms appear can be understood from rare transitions. Crossing a barrier of height has a characteristic suppression proportional to . Substituting gives a scale resembling . If cooling makes escape opportunities decay too quickly, the process can retain a positive probability of never leaving a nonglobal basin. This argument captures the mechanism, although full proofs must account for paths, repeated visits, and changing transition probabilities.
Convergence in probability is not the same as a practical runtime guarantee. Nor does it necessarily mean that a sample path eventually stays at one optimum forever. A theorem may establish that the probability of being outside the optimal set tends to zero without providing a useful finite-time error estimate.
Logarithmic cooling is often prohibitively slow, and the critical depth is usually unknown. Determining it can itself require substantial knowledge of the landscape. The theory therefore explains the trade-off between escape and freezing more directly than it supplies an operational schedule. Faster geometric cooling is a deliberate compromise, not an implementation of the same asymptotic guarantee.
Representations, neighborhoods, and constraints
The representation of a solution determines which parts of a problem simulated annealing can exploit. In a routing problem, a state can be a permutation of destinations. In a binary selection problem, it can be a bit vector. In parameter estimation, it can be a point in Euclidean space. Encodings that create many invalid or redundant states can consume much of the computational budget without improving the search over meaningful solutions.
Neighborhoods should be assessed in terms of reachability, move cost, and the scale of structural change. For tours, useful moves include exchanging two cities, relocating a city, and reversing a segment. For assignments, a move might transfer one task or swap two tasks. A neighborhood that never connects certain feasible configurations prevents exploration of the entire feasible set, regardless of how slowly temperature decreases.
Incremental evaluation can be as important as the acceptance rule. In a symmetric traveling salesman problem, a 2-opt move removes edges and , reverses the intervening segment, and introduces and . Its cost change is
Only four edge costs are needed to evaluate the difference. This constant-size calculation can make many more proposals possible than recomputing the entire tour length. The formula requires symmetric edge costs; in an asymmetric problem, reversing the segment also changes the costs of its internal directed edges.
Constraints can be handled by proposing only feasible states, rejecting infeasible candidates, repairing them, or adding penalties. For inequality constraints , one possible penalized objective is
A finite penalty coefficient does not automatically make the best penalized solution feasible. Excessively large penalties can also create barriers that inhibit movement between feasible regions. Feasibility-preserving moves avoid this scaling problem but may be difficult to design or may disconnect the search space.
Repair procedures introduce a further subtlety. If many proposed states map to the same repaired state, the effective proposal probabilities can become asymmetric. Repair may also bias the search toward particular regions. Such procedures can still be useful, but their transition mechanism differs from the simple symmetric Metropolis model.
In continuous optimization, proposals often take the form , where is a random displacement. Temperature controls acceptance, whereas controls spatial scale. Shrinking either too quickly can prevent exploration. Bounds may be enforced by reflection, rejection, or reparameterization; each choice changes the induced proposal distribution and may affect whether the standard equilibrium analysis applies.
Applications in engineering, science, and operations research
Simulated annealing is most attractive when candidate solutions can be evaluated and modified more easily than the problem can be solved analytically. Many applications belong to combinatorial optimization, where the number of configurations grows rapidly with problem size. The method does not remove that combinatorial difficulty, but it provides a common framework into which domain-specific representations and moves can be inserted.
Electronic circuit design was an important early application. In placement, components must be assigned positions while controlling quantities such as estimated wire length, congestion, overlap, and timing-related costs. Moving a component can temporarily worsen the objective while enabling later rearrangements. Annealing naturally accommodates such nonmonotonic sequences. The objective is often a weighted combination of engineering criteria, so its scaling and the treatment of hard constraints materially affect the result.
Routing and scheduling are prominent applications in operations research. For traveling-salesman variants, annealing can use exchanges and segment reversals. For job-shop scheduling, states may encode machine orderings, while moves alter selected precedence relations. Feasibility is a substantial issue: an arbitrary swap can introduce a cyclic precedence structure or violate a technological requirement. Effective implementations therefore use problem-specific encodings rather than treating every schedule as an unconstrained list.
Image analysis provides a different class of examples. A state may assign a label, such as foreground or background, to each pixel. An energy combines disagreement with observations and penalties for neighboring pixels receiving incompatible labels:
Here measures local data mismatch, while expresses spatial structure. When this energy is a negative log posterior up to an additive constant, minimizing it corresponds to maximum a posteriori estimation. Single-pixel or block updates then define the annealing dynamics. For particular energy classes, specialized exact algorithms can be preferable.
In molecular modeling, configurations can encode atomic coordinates or molecular conformations, and the objective can represent potential energy or a score incorporating experimental restraints. Computational annealing can help cross conformational barriers, but the resulting minimum is not automatically an equilibrium ensemble or a complete description of molecular behavior. Results depend on the energy model, constraints, and search protocol.
Continuous parameter fitting and engineering design provide further uses, especially when objectives are discontinuous, noisy, or unavailable in differentiable form. Nevertheless, annealing is not inherently superior to gradient descent, integer programming, or specialized optimization methods. Its practical niche is determined by the structure available in a problem and the cost of exploiting that structure.
Related algorithms and extensions
Simulated annealing belongs to the broader family of randomized search methods, but its temperature-controlled acceptance rule distinguishes it from several close relatives. Random-restart local search repeatedly descends from new initial states. It crosses between basins by restarting rather than by accepting worsening transitions along a continuous search trajectory. Either method may perform better depending on whether promising basins are easy to enter and whether useful solutions share nearby structure.
Its relationship with Markov chain Monte Carlo is especially close. At fixed temperature, a correctly constructed annealing transition is an MCMC sampler for a Boltzmann distribution. During optimization, however, the target changes as temperature decreases. A sequence of optimization states should therefore not be treated automatically as samples from a single equilibrium distribution. Likewise, a method intended to estimate expectations must control sampling bias and dependence rather than merely retain the best objective value.
Parallel tempering, also called replica exchange, maintains several replicas at different temperatures. Each replica evolves at its own temperature, and occasional swaps allow configurations to move between hotter and colder environments. With inverse temperatures and , swapping states has the standard acceptance probability
Hot replicas can explore broadly, while cold replicas concentrate on low energies. Unlike ordinary annealing, the temperatures may remain fixed.
Other extensions alter proposals or replace stochastic decisions. Fast simulated annealing uses heavy-tailed moves, including Cauchy-type proposals, to make occasional long jumps possible. Threshold accepting permits worsening moves only when their cost increase lies below a decreasing threshold, rather than accepting them with an exponential probability. Such methods preserve the broad-to-selective search strategy but do not share all the same probabilistic properties.
Hybrid algorithms combine annealing with deterministic improvement, population search, or exact subproblem solvers. A local optimizer can polish a final result, or selected proposals can invoke more expensive structural changes. If every proposal is immediately mapped to a local minimum, the algorithm effectively searches a transformed landscape of basins. This can be powerful, but it changes both the neighborhood and the theoretical interpretation.
Quantum annealing is conceptually distinct. It uses quantum fluctuations, typically represented by a changing Hamiltonian, rather than classical thermal acceptance alone. Simulated quantum annealing uses classical computation to model aspects of quantum systems. Similar terminology does not make these procedures interchangeable with classical simulated annealing, and performance comparisons depend on the specific problem and computational model.
Performance evaluation and practical limitations
Simulated annealing produces random outcomes, so performance cannot be characterized adequately by a single run. Repeated independent runs can reveal the distribution of final objective values, variability in runtime, and frequency of reaching a specified target. Reporting only the best result obscures reliability: an algorithm that occasionally finds an excellent solution may be less suitable for a fixed deadline than one that consistently finds slightly weaker solutions.
Meaningful comparisons require comparable computational budgets. Objective evaluations are often a useful measure, but they are not always equal in cost. An incremental move evaluation may be much cheaper than a complete simulation of a candidate. Wall-clock time captures implementation effects but also depends on hardware and software. Experiments therefore benefit from distinguishing proposal counts, full evaluations, and elapsed time rather than treating “iterations” as a universal unit.
When an optimum is known, solution quality can be expressed as an absolute gap , or as a relative gap when normalization is meaningful. A common relative measure for nonzero is
Relative gaps can be misleading near zero or when objective values can be shifted arbitrarily. If the optimum is unknown, a valid lower bound can quantify a remaining gap, whereas a best-known solution is merely an empirical reference.
For repeated runs with success probability , independence gives a probability of at least one success in runs. This can guide comparisons between long runs and multiple shorter restarts. It does not establish independence when runs share adaptive information or random-number streams, and must be estimated with uncertainty rather than inferred from one favorable result.
Noisy objective evaluations create a separate difficulty. If estimated differences are dominated by measurement or simulation noise, the acceptance rule responds partly to that noise rather than to the true landscape. Repeated evaluations can reduce variance, but increase cost. Specialized noisy-annealing schemes require their own assumptions; the classical finite-state convergence argument presumes access to the specified objective values.
The principal limitations remain high computational cost, sensitivity to representation and schedule, and lack of a general finite-time optimality certificate. Poorly designed moves can make an apparently sophisticated schedule ineffective. Reproducible studies therefore specify the encoding, proposal probabilities, initialization, cooling rule, work per temperature, stopping condition, random seeds or seed-generation procedure, and the method used to retain the best solution.