Simulated Annealing — Probabilistic Optimization
- Year
- 1983
- Type
- Probabilistic metaheuristic / local search
What does it do?
Simulated annealing is a probabilistic local-search metaheuristic introduced by Kirkpatrick, Gelatt, and Vecchi in 1983.
It models the physical annealing process in metallurgy — where a material is heated and then slowly cooled to reach a low-energy crystalline state — and uses this analogy to escape local optima in combinatorial and continuous optimization problems.
The intuition behind the method
Imagine trying to find the lowest point in a hilly landscape while blindfolded. A purely greedy search always steps downhill and gets stuck in the first valley it finds — which may not be the deepest one. Simulated annealing introduces a controlled randomness: early on, when the 'temperature' is high, the algorithm is willing to step uphill occasionally, accepting a worse solution by chance. As temperature decreases according to a cooling schedule, the algorithm becomes increasingly selective, converging on a solution. This willingness to accept worse moves at high temperature is what allows the method to escape shallow local optima and explore the landscape more thoroughly.
History
Simulated annealing was introduced by Kirkpatrick, Gelatt, and Vecchi in their landmark 1983 paper in Science, which drew an explicit analogy between the thermodynamic annealing of solids and combinatorial optimisation. The same idea was independently proposed by Cerny (1985) in the context of the travelling salesman problem. van Laarhoven and Aarts (1987) provided the first rigorous theoretical treatment, proving convergence properties under various cooling schedules. Since then the method has become one of the most widely studied and applied metaheuristics, used across engineering design, operations research, VLSI layout, and machine learning hyperparameter tuning.
When to use it
Simulated annealing is applicable to any problem where a neighbourhood structure can be defined over the solution space, regardless of whether the objective function is differentiable, convex, or even analytically expressible. It is particularly well-suited to combinatorial problems (scheduling, routing, graph problems) and continuous black-box optimisation. No training data or normality assumption is required. The cooling schedule and neighbourhood structure must be tuned to the problem; running fewer than roughly 1 000 iterations risks premature convergence to a local optimum, in which case a simpler deterministic local search should be preferred instead.
Limitations and considerations
- Solution quality is sensitive to the cooling schedule; a poor schedule can yield results no better than random search.
- The neighbourhood structure must be designed for each problem class, which requires domain expertise.
- Convergence to the global optimum requires extremely slow cooling in practice, making runtime long for high-quality guarantees.
- Does not leverage gradient or structural information, so gradient-based methods outperform it on smooth, differentiable problems.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Can escape local optima through probabilistic acceptance of worse solutions, unlike pure hill-climbing.
- Applies to virtually any problem type — combinatorial, continuous, mixed — as long as a neighbourhood structure is defined.
- Requires no gradient information and is indifferent to the mathematical structure of the objective function.
- Has a theoretical guarantee of convergence to the global optimum under sufficiently slow cooling (Hajek 1988).
- Few hyperparameters: initial temperature, cooling rate, and neighbourhood structure.
Applications
- Combinatorial scheduling and timetabling problems where the solution space is too large for exhaustive search.
- Travelling salesman and vehicle routing problems in logistics and operations research.
- VLSI circuit layout and chip floor-planning in electrical engineering.
- Protein folding and molecular conformation problems in computational biology.
- Hyperparameter optimisation for machine learning models when gradient information is unavailable.
- Resource allocation and assignment problems in engineering and management science.
How it works
How it works
The algorithm begins with a starting solution — any feasible point in the search space — and a high initial temperature. The starting solution can be random or problem-specific; the initial temperature is typically set high enough that almost any neighbouring solution would be accepted at the start.
A neighbouring solution is generated by applying a small random change (a 'move') to the current solution. The neighbourhood structure must be tailored to the problem: for a scheduling problem a move might swap two tasks; for a continuous function it might add a small random perturbation to the current parameter vector.
The difference in objective value between the new and current solution is computed. If the new solution is better, it is always accepted. If it is worse, it is accepted with a probability that decays with the size of the deterioration and the current temperature — typically exp(−ΔE / T). This probabilistic acceptance is the core mechanism that prevents premature convergence.
After each iteration (or after a fixed number of moves at the same temperature), the temperature is reduced according to a cooling schedule — commonly a geometric schedule T ← α·T where α is slightly below 1. The choice of cooling schedule strongly affects solution quality: cooling too fast traps the search in a local optimum; cooling too slowly wastes computational time.
The algorithm stops when the temperature falls below a minimum threshold, a maximum number of iterations is reached, or the solution has not improved for a specified number of steps. The best solution encountered throughout the entire run — not just the final state — is returned as the result.
Common pitfalls
- Running too few iterations (roughly under 1 000) prevents the cooling schedule from functioning properly and leaves the search trapped in a local optimum — prefer tabu search or a deterministic local search if runtime is severely limited.
- Setting the initial temperature too low means the algorithm immediately behaves like greedy hill-climbing and loses its ability to escape local optima.
- Setting the cooling rate too aggressively (e.g., α below 0.9) causes premature convergence; verify final solution quality by restarting from multiple initial solutions.
- Applying a neighbourhood move designed for one problem type to a different problem can make moves infeasible or meaningless — always verify that every generated neighbour is a valid solution.
- Reporting only the final state rather than the best-ever solution seen during the run can miss the true optimum found at an intermediate step.
Frequently asked questions
How do I choose the cooling schedule?
The geometric schedule T ← α·T with α between 0.90 and 0.99 is the most common starting point. A practical approach is to set the initial temperature high enough that roughly 80% of moves are accepted at the start, then reduce it until fewer than 1% of uphill moves are accepted. If the final solution quality is poor, slow the cooling rate (increase α); if runtime is too long, speed it up. Always run the algorithm several times from different starting solutions to assess robustness.
How does simulated annealing differ from genetic algorithms or particle swarm optimisation?
Simulated annealing maintains a single solution and explores the neighbourhood through random perturbations, accepting worse solutions probabilistically. Genetic algorithms and particle swarm optimisation maintain a population of solutions and use crossover, mutation, or swarm movement to evolve the population. Simulated annealing is generally simpler to implement for problems with a natural neighbourhood structure, while population-based methods can be more effective for high-dimensional continuous problems.
Is the global optimum guaranteed?
Theoretically yes, under the condition that the temperature decreases sufficiently slowly (logarithmic cooling). In practice, such cooling is computationally infeasible, so the algorithm finds a near-optimal solution. The quality of the result improves with slower cooling and more iterations, but there is no finite-time guarantee. Running multiple restarts and keeping the best solution found is a practical way to increase confidence.
When should I prefer tabu search or a genetic algorithm instead?
Choose tabu search when you need a deterministic, memory-guided search that avoids revisiting recent solutions and can exploit problem structure efficiently in a shorter run. Choose a genetic algorithm or particle swarm optimisation when the problem is high-dimensional and continuous, or when a population of diverse solutions is needed to map the optimum landscape. Simulated annealing is a strong default for combinatorial problems with a clear neighbourhood structure and when implementation simplicity matters.
Related methods
Sources
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Open DOI referenceCopied.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
ISBN: 9789027725431Copied.