What is simulated annealing?

Simulated annealing is a probabilistic optimisation method inspired by the slow cooling of metals. It searches for a low-cost solution by making random changes, always accepting improvements but also accepting worse states with a temperature-dependent probability, which lets it escape local minima.

Why does it accept worse solutions?

Accepting worse moves with probability e^(−ΔE/T) lets the search climb out of local minima. At high temperature almost any move is accepted, so it explores widely; as the temperature falls the search becomes greedy and settles into a good basin.

What is the Metropolis acceptance criterion?

If a proposed move lowers the cost it is always accepted. If it raises the cost by ΔE it is accepted with probability exp(−ΔE/T), where T is the current temperature. This rule comes from the Metropolis–Hastings algorithm in statistical mechanics.

What is a cooling schedule?

A cooling schedule defines how the temperature decreases over time. This simulation uses a geometric schedule, T ← α·T with α just below 1 (the cooling rate). Slower cooling explores more and usually finds shorter tours but takes longer.

What is the travelling salesman problem?

The travelling salesman problem asks for the shortest tour that visits every city exactly once and returns to the start. It is NP-hard, so exact solving is impractical for many cities; simulated annealing finds short, near-optimal tours quickly.

What are 2-opt and swap moves?

A 2-opt move reverses a segment of the tour, uncrossing two edges. A swap move exchanges the positions of two cities. Both produce a neighbouring tour whose length is compared with the current one inside the acceptance rule.

What does the acceptance rate tell me?

The acceptance rate is the fraction of proposed moves that were accepted recently. It starts high while the temperature is high and drops toward zero as the schedule cools and the search becomes greedy.

Does simulated annealing find the optimal tour?

Not guaranteed. With infinitely slow cooling it converges to a global optimum in theory, but in practice it returns a high-quality near-optimal solution. Restarting or cooling more slowly improves the result.

How does the cooling rate affect the result?

A cooling rate close to 1 (e.g. 0.999) cools slowly, explores longer and usually yields shorter tours. A smaller rate (e.g. 0.99) cools fast, converges quickly but is more likely to get stuck in a local minimum.

Where is simulated annealing used in practice?

It is used in VLSI chip layout, scheduling, vehicle routing, image reconstruction, neural-network training and many other combinatorial problems where the search space is large and riddled with local minima.

Home▸Algorithms & AI▸Simulated Annealing — Escaping Local Minima

🌡️ Simulated Annealing — Escaping Local Minima

Solve a travelling-salesman tour with simulated annealing: accept worse moves with probability e^(−ΔE/T) while temperature cools, escaping local minima before settling on a short route.

Algorithms & AI3DModerate60 FPS

About Simulated Annealing

Simulated annealing (SA) is a probabilistic metaheuristic introduced by Kirkpatrick, Gelatt, and Vecchi in 1983, inspired by the physical process of controlled cooling in metallurgy: slowly cooling a molten material allows atoms to settle into low-energy crystal lattices, whilst rapid quenching traps them in high-energy amorphous states. In optimisation, SA starts at a high "temperature" T and accepts worse solutions with probability e^−ΔE/T (the Metropolis criterion), allowing escape from local minima; as T decreases according to a cooling schedule, the algorithm increasingly behaves like hill-climbing and converges. SA can find near-optimal solutions for NP-hard problems such as the Travelling Salesman Problem (TSP) where exhaustive search is infeasible.

This simulation applies SA to the TSP on a random set of cities: watch the route improve as the temperature cools, observe accepted worse moves highlighted in orange, and compare the final tour length to greedy nearest-neighbour. Adjustable parameters include starting temperature, cooling rate, and city count, letting you explore the quality-vs-runtime trade-off directly.

Frequently Asked Questions

Why does simulated annealing accept worse solutions?

Accepting worse solutions with probability e^−ΔE/T allows the algorithm to escape local minima — configurations where every small change worsens the solution, but which are not globally optimal. At high temperature T, almost all worse moves are accepted (the algorithm explores broadly); as T decreases, fewer worse moves are accepted and the algorithm focuses on exploitation. This balance between exploration and exploitation is the core mechanism that differentiates SA from simple hill-climbing.

What cooling schedule gives the best results?

Logarithmic cooling (T(t) = T₀/ln(1+t)) is theoretically guaranteed to find the global optimum as t→∞, but is impractically slow. In practice, geometric cooling T(t+1) = α·T(t) with α ∈ [0.95, 0.999] is standard: it cools fast enough to be practical but slowly enough to allow escape from local minima. The optimal α and initial T₀ depend on the problem; T₀ is often chosen so that 80% of worse moves are accepted initially, ensuring thorough early exploration.

How is simulated annealing applied to the Travelling Salesman Problem?

The TSP state is a tour (permutation of cities); the neighbourhood is defined by 2-opt swaps (reversing a segment of the tour) or 3-opt moves (reconnecting three tour segments). Energy E is the total tour length. Each iteration proposes a random neighbour: if shorter, accept it; if longer by ΔL, accept it with probability e^−ΔL/T. After millions of iterations with decreasing T, SA typically finds tours within 1–3% of the optimal for hundreds of cities.

Is simulated annealing guaranteed to find the global optimum?

With logarithmic cooling (T(t) = c/ln(t+2)), SA converges to the global optimum with probability 1 in infinite time — a result due to Hajek (1988). In practice, finite runs with geometric cooling do not guarantee the global optimum. For the TSP with n cities, the global optimum is NP-hard to compute, but SA with good 2-opt or Lin-Kernighan moves consistently finds solutions within a few percent of optimal for n ≤ 1000 cities in seconds.

What is the Metropolis criterion and where does it come from?

The Metropolis criterion e^−ΔE/T comes from statistical mechanics: in the canonical ensemble at temperature T, the probability of a system occupying an energy state E is proportional to e^−E/kT (the Boltzmann distribution). The acceptance ratio e^−ΔE/T for a move that increases energy by ΔE ensures that the Markov chain converges to the Boltzmann distribution at fixed T — a property that guarantees SA visits low-energy (good) solutions most often at low temperatures.

How does simulated annealing compare to genetic algorithms?

Both are population-inspired metaheuristics for NP-hard optimisation. SA maintains a single current solution and uses temperature to control diversity; genetic algorithms maintain a population of solutions and use crossover and mutation. SA is simpler to implement and tune; genetic algorithms can exploit solution structure through crossover. In practice, SA often outperforms basic genetic algorithms on TSP for moderate city counts, while genetic algorithms (especially with local search — "memetic algorithms") scale better to very large instances.

What is reheat and when should it be used?

Reheating periodically increases T back to a higher value if the algorithm has been stuck in what appears to be a local minimum for many iterations. This can help SA escape deep local basins that geometric cooling alone cannot escape. However, reheating complicates convergence analysis and may waste computation time. Adaptive cooling schedules that monitor acceptance rates and adjust T dynamically (e.g., maintaining a target acceptance rate of 20%) are often more principled alternatives.

What real-world problems use simulated annealing?

SA is used in VLSI chip layout (placing circuit elements to minimise wire length — IBM used it for the chip that became the original Mac), protein folding (minimising free energy), scheduling (exam timetabling, airline crew scheduling), telecommunications network design, and image reconstruction in tomography. Modern SA implementations are often hybridised with local search heuristics to dramatically improve solution quality within the same CPU budget.

How do you choose the initial temperature T₀?

A common heuristic: sample a set of random moves, compute the average energy increase ΔE̅ for those that worsen the solution, then set T₀ = −ΔE̅ / ln(χ₀) where χ₀ is the desired initial acceptance probability (typically 0.8). This ensures the algorithm starts "hot" enough to accept 80% of worse moves, guaranteeing broad initial exploration. Alternatively, T₀ can be set to the standard deviation of objective function values over random solutions, scaled by a constant.

What is the difference between simulated annealing and basin-hopping?

Basin-hopping (Wales and Doye, 1997) combines random perturbation steps with local minimisation: each SA "step" performs a full gradient descent to the nearest local minimum before applying the Metropolis criterion. This transforms the energy landscape into a simplified "basin" landscape (flat inside each basin, discontinuous at basin boundaries), which is much easier for SA to navigate. Basin-hopping is standard in computational chemistry for finding protein and cluster structures.

⚙ Under the hood

Solve a travelling-salesman tour with simulated annealing: accept worse moves with probability e^(−ΔE/T) while temperature cools, escaping local minima before settling on a short route.

simulated annealingoptimizationMetropolisTSPCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install