What Is Simulated Annealing?

Simulated annealing is a probabilistic optimization algorithm that searches for a near-optimal solution to a combinatorial or continuous optimization problem by mimicking the physical process of slowly cooling a material to reduce its energy to a low-lying state. At each step, the algorithm generates a neighboring candidate solution and decides whether to accept it based on the change in objective function value and a control parameter called temperature. Moves that improve the objective are always accepted; moves that worsen it are accepted with a probability that decreases as temperature falls. This controlled acceptance of worse solutions allows the algorithm to escape local optima, a capability that purely greedy local search lacks.

The method was introduced by S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi in their 1983 paper in Science, where they drew an explicit analogy between combinatorial optimization and the statistical mechanics of systems approaching thermal equilibrium. The algorithm's central insight is that a Boltzmann acceptance probability, P = exp(-delta/T), applied to uphill moves gives the search a systematic way to trade exploration for exploitation as the optimization proceeds.

The Physical Annealing Analogy

In metallurgy, annealing is the process of heating a metal or glass to a high temperature and then cooling it slowly so that atoms settle into a low-energy crystalline arrangement rather than a disordered, high-energy amorphous state. Rapid quenching locks in defects because atoms lack the thermal energy to rearrange themselves past local energy barriers. Slow cooling gives them enough energy at each stage to cross small barriers while still biasing them toward lower-energy configurations overall. Simulated annealing translates this directly: the objective function plays the role of energy, the current solution plays the role of atomic configuration, and the temperature schedule governs how quickly the algorithm narrows its acceptance window. When the analogy is taken seriously, the algorithm's long-run behavior is governed by the Metropolis-Hastings criterion from statistical physics, which guarantees that at any fixed temperature the algorithm samples configurations with the correct Boltzmann distribution. The original Metropolis et al. (1953) paper in the Journal of Chemical Physics introduced this Monte Carlo sampling technique decades before Kirkpatrick applied it to combinatorial optimization.

Temperature Schedules and Convergence

The cooling schedule determines how temperature decreases over the course of the algorithm and is critical to performance. A logarithmic schedule, T(k) = c / log(1+k) for iteration k, guarantees asymptotic convergence to a global optimum under mild conditions, but is impractically slow for real problems. Geometric schedules, T(k) = alpha * T(k-1) with alpha close to 1 (typically 0.8 to 0.99), are the practical standard: they converge quickly enough to be useful while still allowing substantial exploration early in the run. The initial temperature is typically set so that a large fraction of uphill moves are accepted at the start, ensuring the search explores the solution space broadly before concentrating on refinement. Relaxation methods in this context refer to the gradual tightening of the acceptance criterion as temperature drops, which progressively restricts the neighborhood of candidate solutions the algorithm entertains.

Relationship to Other Metaheuristics

Simulated annealing belongs to the family of trajectory-based metaheuristics: at each step it maintains a single current solution and modifies it incrementally, in contrast to population-based methods such as genetic algorithms or particle swarm optimization that maintain a set of solutions simultaneously. Its main advantage is conceptual simplicity and ease of implementation. For many hard combinatorial problems, including VLSI placement, graph partitioning, and the traveling salesman problem, well-tuned simulated annealing produces solutions competitive with more sophisticated heuristics. A review published in Statistical Science surveys the theoretical convergence properties of simulated annealing and catalogs the range of combinatorial problems to which it has been successfully applied.

Applications

Simulated annealing has applications in a wide range of fields, including:

• VLSI circuit layout, placement, and routing
• Traveling salesman and vehicle routing problems in logistics
• Protein structure prediction and molecular docking in bioinformatics
• Parameter estimation and training in machine learning models
• Scheduling and resource allocation in operations research