Simulated annealing is an optimization algorithm inspired by the way metals cool and settle into low-energy crystalline structures. It works by exploring possible solutions to a problem, occasionally accepting worse solutions on purpose so it can escape dead ends and find a better overall answer. Since its formalization in the early 1980s, it has become one of the most widely used methods for tackling problems where the number of possible solutions is so vast that checking them all is impossible. Its appeal comes from a surprising simplicity and a remarkable flexibility across very different kinds of problems.
The Physical Metaphor Behind the Algorithm
When a blacksmith heats a piece of metal and lets it cool slowly, the atoms rearrange themselves into a highly ordered, low-energy crystal. If the metal cools too quickly, atoms get stuck in disordered positions and the result is brittle. Slow, controlled cooling gives the atoms enough thermal energy to jiggle past unfavorable arrangements and eventually settle into the strongest possible structure.
Simulated annealing borrows this idea and applies it to abstract problems. Instead of atoms, you have a candidate solution. Instead of physical energy, you have a “cost” you want to minimize, like the total distance of a delivery route or the error in a machine-learning model. And instead of actual temperature, there is a numerical parameter called the temperature that controls how willing the algorithm is to accept a worse solution at any given moment.
How the Algorithm Actually Works
The process starts with some random or initial solution and a high temperature setting. At each step, the algorithm makes a small random change to the current solution, producing a neighbor. If the neighbor is better (lower cost), it is always accepted. If the neighbor is worse, it might still be accepted, with a probability that depends on how much worse it is and how high the temperature currently is. When the temperature is high, the algorithm freely accepts worse solutions, wandering broadly across the landscape of possibilities. As the temperature drops, it becomes increasingly picky, until eventually it only accepts improvements and settles into whatever good solution it has found.
The rule for deciding whether to accept a worse solution is called the acceptance criterion. The most common version, known as the Metropolis criterion, comes from statistical physics and accepts a worse neighbor with a probability that decreases exponentially as the quality gap grows. Research has formally characterized the full class of acceptance criteria that maintain the right statistical properties, confirming that the Metropolis rule and the less common Barker criterion are the canonical choices within this framework.1Mathematics of Operations Research. Classification of Acceptance Criteria for the Simulated Annealing Algorithm
Why Accepting Bad Moves Is the Whole Point
Most optimization problems have a rugged landscape full of local optima, solutions that look good compared to their immediate neighbors but are far from the best possible answer. A purely greedy algorithm that only ever moves downhill will get trapped in the first valley it finds. Simulated annealing’s willingness to climb uphill, especially early on when the temperature is high, lets it hop out of these traps and explore regions of the search space that a greedy method would never reach.
This is not just a practical trick. There are theoretical guarantees backing it up. Under certain conditions, if the temperature decreases slowly enough, simulated annealing is proven to converge to the globally optimal solution with probability approaching one. Specifically, as long as the algorithm satisfies a condition called weak reversibility, the stationary distributions converge so that non-optimal solutions are generated with probability zero in the limit.2SIAM Journal on Control and Optimization. Note on the Convergence of Simulated Annealing Algorithms In practice, running the algorithm long enough to reach that theoretical guarantee is usually impractical, but it is reassuring to know the math is sound. Real implementations trade off a bit of optimality guarantee for reasonable computation time.
Getting the Cooling Schedule Right
The cooling schedule, how quickly the temperature drops, is the single most important parameter to get right. Cool too fast and the algorithm behaves like a random restart of greedy search, getting stuck in mediocre solutions. Cool too slowly and you waste enormous amounts of computation time exploring solutions that the algorithm will never keep.
Classic approaches use a simple geometric schedule: multiply the temperature by a fixed factor (say 0.95) after each step or each batch of steps. But this one-size-fits-all approach does not adapt to the difficulty of the problem. Adaptive cooling schedules, which adjust the rate of cooling based on what the algorithm is finding as it runs, tend to produce better results. One approach tracks how many proposed moves are being accepted and adjusts accordingly. Research on the traveling salesman problem has shown that the amount of data the algorithm retains about recent acceptance rates directly influences both the shape of the cooling schedule and the quality of the final solution.3Physica A: Statistical Mechanics and its Applications. Investigation of acceptance simulated annealing — A simplified approach to adaptive cooling schedules
The starting temperature also matters. Set it too low and the algorithm never explores broadly enough. Set it too high and it wastes time in a phase where every move is accepted regardless of quality. Practitioners have developed methods to estimate a good starting temperature automatically by sampling the problem landscape and picking a value that yields a desired initial acceptance rate.
Neighborhood Structure and Problem Design
Another design choice that quietly shapes performance is the neighborhood structure: what counts as a “small random change” to the current solution. For a traveling salesman route, a neighbor might be produced by swapping two cities in the sequence, or by reversing a segment of the tour. For an assignment problem, it might mean swapping which worker is assigned to which task. The choice is not trivial.
Experiments across several classic combinatorial problems, including the traveling salesman problem and the quadratic assignment problem, have found that smaller neighborhoods tend to perform better than larger ones for a given annealing schedule.4Computers & Operations Research. A note on the effect of neighborhood structure in simulated annealing This is somewhat counterintuitive. You might expect that making bigger jumps would help the algorithm explore more of the landscape, but what actually seems to happen is that large neighborhoods introduce too much randomness at lower temperatures, undoing progress the algorithm has already made. Small, focused perturbations allow for more precise refinement as the system cools.
The Traveling Salesman Problem as a Testing Ground
The traveling salesman problem, finding the shortest route that visits a set of cities exactly once and returns to the starting point, has been the benchmark for simulated annealing since the algorithm’s earliest days. It is a natural fit because the search space grows factorially with the number of cities, making brute-force approaches impossible for anything beyond a few dozen locations. Simulated annealing does not guarantee the absolute shortest route, but it reliably finds very good ones.
Researchers have continued to refine SA-based approaches for this problem. One line of work introduced a roulette-wheel selection strategy for choosing which edges to modify during neighborhood generation, using either distance information or historical solution data to bias the search toward promising regions. Tested across 11 well-known benchmark sets, these approaches consistently outperformed conventional simulated annealing with simple swap moves in reaching optimal or near-optimal solutions, largely by improving convergence without sacrificing the algorithm’s randomness.5Mathematical and Computational Applications. A new simulated annealing approach for the traveling salesman problem
Logistics and Vehicle Routing
Beyond the abstract traveling salesman problem, simulated annealing has found heavy use in real logistics operations where the constraints are messier. Consider a delivery company that needs to design routes for a fleet of trucks leaving from a central depot, each truck having a weight limit and each delivery consisting of rectangular items that physically need to fit on the truck. This kind of problem layers geometric packing constraints on top of the routing problem, making it far harder than a standard shortest-path calculation.
Simulated annealing handles these layered constraints well because it naturally accommodates feasibility checks during the neighbor-generation step. Researchers have applied SA with a repeated cooling-and-reheating mechanism to solve versions of this capacitated vehicle routing problem with two-dimensional loading constraints, covering scenarios with and without last-in-first-out stacking rules and with or without allowing rotation of goods.6European Journal of Operational Research. A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints The reheating trick, periodically raising the temperature partway back up after it has cooled, helps the algorithm escape local traps that form in these highly constrained spaces.
Similar approaches have been applied to cross-docking scenarios, where goods arrive at a central hub and are immediately sorted onto outbound trucks without long-term storage. In these settings with mixed fleet sizes, simulated annealing has produced reasonable solutions in terms of both cost and computation time.7Procedia – Social and Behavioral Sciences. Vehicle Routing Problem with Cross Docking: A Simulated Annealing Approach
Protein Structure and Molecular Science
One of the more striking applications of simulated annealing is in determining the three-dimensional structures of proteins. When researchers use nuclear magnetic resonance (NMR) spectroscopy to study a protein, they do not get a direct picture of the structure. Instead, they get a set of distance constraints between pairs of atoms. Figuring out the three-dimensional arrangement of atoms that satisfies all those constraints is itself a massive optimization problem, and simulated annealing has been the dominant computational approach for solving it.8PubMed Central. Systematic solution to homo-oligomeric structures determined by NMR
The algorithm works here because the energy landscape of a protein, the relationship between atomic arrangement and physical energy, is fantastically rugged. A protein with a few hundred amino acids has an astronomical number of possible conformations, most of them physically unreasonable. Simulated annealing’s ability to climb out of local energy minima makes it well suited to navigating this landscape and converging on the native fold.
More recent work has pushed the approach further with strategies like multiple simulated annealing coupled with molecular dynamics simulations. By running many SA trajectories and feeding their results into physics-based molecular dynamics, researchers have achieved significantly more efficient identification of native peptide and miniprotein structures compared to running continuous molecular dynamics or conventional single-pass simulated annealing alone.9Scientific Reports. Multiple Simulated Annealing-Molecular Dynamics (MSA-MD) for Conformational Space Search of Peptide and Miniprotein
How It Compares to Genetic Algorithms
The most common question about simulated annealing is how it stacks up against genetic algorithms, the other big family of nature-inspired optimization. Genetic algorithms maintain a population of solutions that evolve through selection, crossover, and mutation, loosely mimicking biological evolution. Simulated annealing tracks just one solution at a time and explores by random perturbation.
The tradeoff tends to be quality versus speed. In a direct comparison on the problem of maximizing thermal conductance in harmonic lattices, genetic algorithms consistently found better solutions than simulated annealing, but at the cost of significantly longer computation time.10Computational Materials Science. A comparison of genetic algorithms and simulated annealing in maximizing the thermal conductance of harmonic lattices This pattern shows up across many problem types: genetic algorithms can explore more diverse regions of the search space thanks to their population-based approach, but each generation requires evaluating many candidates simultaneously. Simulated annealing is leaner, requiring less memory and fewer function evaluations per step, which makes it attractive when evaluating a single solution is expensive.
A common criticism of simulated annealing is that its convergence speed can be slow, particularly on problems with very rugged landscapes where the algorithm needs a long cooling schedule to avoid getting stuck.11Computers & Structures. Damage detection by an adaptive real-parameter simulated annealing genetic algorithm This has motivated a great deal of work on hybrid methods that combine the strengths of both approaches.
Hybrid Methods and Modern Extensions
Rather than treating simulated annealing and other methods as competitors, many practitioners now blend them. One recent approach combines simulated annealing with tabu search, a method that maintains a memory of recently visited solutions and forbids the algorithm from revisiting them. In a portfolio optimization problem involving both continuous decisions (how much to invest in each asset) and discrete decisions (which assets to include at all), the hybrid divides the labor: simulated annealing handles the continuous weight optimization through stochastic exploration, while tabu search handles the discrete asset-selection layer through structured neighborhood moves with memory.12Journal of Heuristics. Simulated annealing–Tabu search integration for downside-risk portfolio optimization with cardinality constraints
This kind of coordinated hybridization is different from simply running two algorithms sequentially. The SA and tabu search components communicate during the run, with each method’s results informing the other’s search. The approach reflects a broader trend in optimization: the most effective solvers for real-world problems are often composites, borrowing the exploration strengths of one method and the exploitation strengths of another.
Landscape-Aware Simulated Annealing
Standard simulated annealing is, in a sense, blind to the overall shape of the search space. It compares the current solution to the proposed neighbor and decides based on the temperature, without any broader awareness of whether it is in a promising region or wandering through a wasteland. This has led to efforts to make SA “landscape-aware” by incorporating information about the fitness landscape into the acceptance probability function.
One line of research uses measures like fitness-distance correlation, which captures how well the quality of solutions tracks with their distance from known good solutions, and autocorrelation, which captures how quickly solution quality changes as you walk through the neighborhood. By embedding these measures into the acceptance function, the algorithm can distinguish between phases where it should be exploring broadly and phases where it should be exploiting a promising region more intensively.13International Journal of Computing. BOOSTING SIMULATED ANNEALING WITH FITNESS LANDSCAPE PARAMETERS FOR BETTER OPTIMALITY The insight motivating this work is that standard SA only ever compares the current solution to the proposed one at whatever the current temperature happens to be, completely ignoring the relationship between where it is searching and what the overall landscape looks like.
Quantum Annealing and How It Differs
The term “quantum annealing” sounds like it might be simulated annealing running on a quantum computer, but the relationship is more subtle than that. Quantum annealing is a physical process that uses quantum-mechanical effects, particularly quantum tunneling, to search for low-energy states of a system. Companies like D-Wave have built specialized hardware that performs quantum annealing on problems encoded as energy landscapes.
The two approaches share the broad metaphor of gradually reducing fluctuations to settle into an optimal state, but the underlying dynamics are different. Classical simulated annealing explores by thermally hopping over energy barriers, which means it needs enough temperature to climb over each barrier it encounters. Quantum annealing can tunnel through barriers, a fundamentally different mechanism that can sometimes reach good solutions faster. Recent research analyzing probability fluxes through state space has found that while the two dynamics are broadly similar in many respects, quantum tunneling produces qualitative differences in how the system moves between states.14arXiv. Distinguishing thermal versus quantum annealing using probability-flux signatures across interaction networks
Whether quantum annealing actually offers a practical speedup over classical simulated annealing on real problems remains an active and contested area of research. For many problem types, well-tuned classical SA running on conventional hardware is competitive with or superior to current quantum annealing hardware, in part because that hardware is still limited in the number of variables it can handle and the types of connections between them. The field is evolving quickly, though, and purpose-built digital annealing chips inspired by both classical and quantum ideas are being developed to accelerate optimization tasks on conventional silicon.
When Simulated Annealing Is the Wrong Choice
For all its versatility, simulated annealing is not always the best tool. If your problem is convex, meaning it has a single basin with no local traps, gradient-based methods will find the optimum far faster. If your problem is small enough that exact methods like integer programming solvers can handle it in reasonable time, those will give you a guaranteed optimum rather than a probabilistic near-optimum. SA shines specifically on large, non-convex, combinatorial problems where the search space is too rugged and too vast for exact methods but where you need a reasonably good answer without the overhead of maintaining a population of solutions.
Another limitation is reproducibility. Because the algorithm relies on random perturbations, two runs with different random seeds can produce different solutions. This is usually handled by running the algorithm multiple times and keeping the best result, but it means SA is less attractive in settings where deterministic behavior is required, such as safety-critical engineering applications where the optimization result needs to be auditable and repeatable.
The algorithm also struggles with problems that have many constraints that are hard to satisfy. If most random perturbations produce infeasible solutions, the algorithm spends most of its time rejecting proposals and making little progress. Constraint-handling techniques exist, like penalty functions that add a cost for violating constraints, but heavily constrained problems often respond better to specialized methods designed with those constraints in mind.
Manufacturing and Energy Applications
Simulated annealing has found steady use in manufacturing optimization, where the problems tend to involve balancing multiple competing objectives. Assembly line balancing, for instance, requires assigning tasks to workstations so that cycle time is minimized while energy consumption stays low. In two-sided robotic assembly lines, where robots work on both sides of a product simultaneously, the combinatorial complexity grows quickly, and simulated annealing with restart mechanisms has been applied to search for configurations that reduce both time and energy use.15Journal of Cleaner Production. Minimizing energy consumption and cycle time in two-sided robotic assembly line systems using restarted simulated annealing algorithm
The restart strategy here echoes the reheating idea from vehicle routing: when the algorithm appears to have converged, you reset the temperature and let it explore again from the current best solution. This is especially useful in multi-objective settings where the tradeoff surface between competing goals is complex and a single cooling run tends to find only one region of that surface. Multiple restarts from different starting conditions, or reheats from the current best, help map out more of the tradeoff space.
Energy-sector applications have grown as grid management has become more complex. Scheduling power generation across different fuel sources, routing electricity through networks, and planning maintenance windows for equipment all involve combinatorial decisions with real costs attached to suboptimal choices. Simulated annealing’s ability to handle mixed continuous and discrete variables without requiring the problem to be reformulated into a specific mathematical form makes it a practical choice for engineering teams that need a good solution by tomorrow morning rather than a perfect solution by next quarter.