Simulated Annealing

Prime #

473

Origin domain

Operations Research

Also from

Physics, Computer Science & Software Engineering

Aliases

Sa, Metropolis Hastings Optimization, Kirkpatrick Annealing

Related primes

metaheuristic optimization, genetic algorithm, tabu search, Monte Carlo Simulation, combinatorial optimization, Integer Linear Programming (ILP)

Core Idea

Simulated Annealing is a metaheuristic for combinatorial or continuous optimization that explores solutions randomly, occasionally accepting worse moves to escape local optima, gradually reducing "temperature" to refine toward better final solutions.

How would you explain it like I'm…

Slow cooling search

Imagine you're looking for the lowest spot in a bumpy field, but you're blindfolded. If you only ever step downhill, you might get stuck in a small dip. So sometimes you randomly take an uphill step to climb out of small dips and find a deeper one. As you get tired, you take fewer uphill steps and settle in. That's simulated annealing.

Cooling-down search

Simulated annealing is a way for computers to search for the best answer when there are tons of possibilities. The trick borrowed from how hot metal cools and settles is to let the search sometimes accept a worse answer, especially early on. That keeps it from getting stuck in the first "pretty good" spot. As the search goes on, it gradually stops accepting worse moves and locks into the best region it found. The willingness to take bad steps is highest at the start ("hot") and shrinks as time passes ("cools"), which is why the method is named after annealing in metalwork.

Simulated annealing

Simulated annealing is an optimization method inspired by how metals are cooled slowly to settle into low-energy structures. Starting from some candidate solution, the algorithm proposes a nearby solution, always accepts improvements, and accepts worsening moves with a probability that depends on how much worse the move is and on a "temperature" parameter. The temperature starts high so worsening moves are common, letting the search jump out of local optima, then gradually cools, so that toward the end only improvements are accepted and the search settles in. Under suitable cooling schedules, the method provably converges to a global optimum; in practice it's a workhorse for problems with rugged landscapes where pure hill-climbing gets stuck. Kirkpatrick, Gelatt, and Vecchi introduced it in 1983.

 

Simulated annealing is a metaheuristic for global optimization that combines local search with probabilistic acceptance of worsening moves, controlled by a temperature parameter that decreases over the course of the search. From an initial solution, the algorithm proposes a neighboring solution; improvements are always accepted, and worsening moves are accepted with probability exp(-Delta E / T), where Delta E is the degradation in the objective and T is the current temperature. At high T, worsening moves are accepted frequently, allowing escape from local optima; as T decreases on a cooling schedule, acceptance of worse moves becomes rare and the search concentrates on increasingly good regions. The method draws its acceptance rule from the Metropolis-Hastings algorithm in statistical physics (Metropolis et al. 1953) and was introduced as a general optimizer by Kirkpatrick, Gelatt, and Vecchi (1983), with Cerny (1985) independently applying it to the Traveling Salesman Problem. Under logarithmic cooling schedules (Hajek 1988), asymptotic convergence to the global optimum is provable, although practical schedules trade theoretical guarantees for efficiency. The method remains valuable for combinatorial problems with rugged landscapes and expensive objective evaluations, and it catalyzed the broader development of metaheuristics tabu search, genetic algorithms, particle swarm, ant colony.

Broad Use

• Circuit Layout: Minimizing wire length or signal delays by randomly swapping component placements, accepting some worsened layouts initially.

• Scheduling: Assigning tasks to timeslots, occasionally allowing a worse schedule to avoid being trapped in local minima.

• Machine Learning: Hyperparameter tuning via random jumps that can accept less optimal hyperparameters initially but converge over time.

• Logistics: Vehicle routing or warehouse location decisions solved with "annealing" jumps to avoid suboptimal clustering.

Clarity

Captures the analogy to thermal annealing in metallurgy: begin with high randomness to move widely in the solution space, then cool down to refine a stable, near-optimal arrangement.

Manages Complexity

Useful for large or NP-hard problems, it doesn't guarantee the absolute best solution but finds robust ones in feasible time, especially when more exact methods (like ILP) might be too slow.

Abstract Reasoning

Shows how controlled randomness can break free from local traps—a concept paralleling evolutionary or adaptive processes in nature, bridging random exploration with incremental selection.

Knowledge Transfer

• Sports Team Formation: Could use annealing to shuffle players across squads for balanced training.

• Agricultural Field Configuration: Minimizing water usage or optimizing field adjacency with flexible, iterative random reassignments.

Example

A global shipping company tackling container-loading or route design might run simulated annealing: start with a random solution, tweak routes, and sometimes accept higher-cost solutions to avoid local minima, gradually reducing acceptance probability (temperature) over many iterations.

Relationships to Other Primes

Parents (3) — more general patterns this builds on

• Simulated Annealing is a kind of Heuristic — Simulated Annealing is a kind of heuristic: probabilistic acceptance with a cooling schedule yields good-enough optima without exhaustive search.
• Simulated Annealing is a kind of Optimization — Simulated annealing is a specialization of optimization that searches by probabilistic neighbor moves under a cooling schedule.
• Simulated Annealing presupposes Stochasticity vs. Determinism — Simulated annealing presupposes the stochasticity-vs-determinism distinction because its escape from local optima depends on probabilistically accepting worsening moves.

Path to root: Simulated Annealing → Stochasticity vs. Determinism

Not to Be Confused With

• Simulated Annealing is not Monte Carlo Simulation because simulated annealing treats the solution space as a landscape to optimize with temperature controlling acceptance of worse moves, whereas Monte Carlo treats the sample space as an estimation source for empirical approximation without landscape optimization.
• Simulated Annealing is not Optimization because simulated annealing is a heuristic metaheuristic for combinatorial problems without optimality guarantees, whereas optimization seeks provably best solutions under constraint.
• Simulated Annealing is not Prioritization because simulated annealing accepts worsening moves probabilistically to escape local optima, whereas prioritization ranks items without exploring the full solution landscape.