🌡️ Simulated Annealing
Escaping local minima on the TSP
Iteration 0
Best length: —
Setup
Controls
Stats
Temperature
—
Acceptance
—
Current length
—
Best length
—
Iterations
0
Status
Ready
Cooling curve
Info & Theory

Simulated annealing mimics the slow cooling of a metal. Heated atoms wander freely; as the metal cools they settle into a low-energy crystal. The algorithm treats the tour length as "energy" and cools a virtual temperature.

The travelling salesman problem

Given n cities, find the shortest closed tour visiting each exactly once. It is NP-hard, so we search for a short tour rather than the provably optimal one.

Neighbour moves

Each step proposes a neighbour tour using a 2-opt move (reverse a segment, uncrossing edges) or a swap of two cities, then measures the change in length ΔE.

The Metropolis criterion

If ΔE ≤ 0 the move is accepted. Otherwise it is accepted with probability P = exp(−ΔE / T). High T ⇒ almost everything accepted (exploration); low T ⇒ greedy (exploitation).

Geometric cooling

The temperature follows T ← α · T with the cooling rate α just below 1. One such cooling step is taken after each temperature level — a fixed batch of L = 2N proposed moves held at constant T (Kirkpatrick's Markov-chain length). The schedule therefore depends only on how many moves have been proposed, not on the frame rate: the Speed slider changes how fast the search runs in wall-clock time, never how quickly it cools. Slower cooling explores more and usually finds shorter tours.

Escaping local minima

Pure hill-climbing gets trapped where every neighbour is worse. By sometimes accepting a worse tour, annealing can climb out and reach a better basin before the temperature locks it in.

FAQ
What is simulated annealing?

A probabilistic optimisation method inspired by the slow cooling of metals. It makes 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 it explores widely; as the temperature falls it becomes greedy and settles into a good basin.

What is the Metropolis acceptance criterion?

A move that lowers the cost is always accepted. A move that raises the cost by ΔE is accepted with probability exp(−ΔE/T), where T is the current temperature.

What is a cooling schedule?

It defines how the temperature decreases. This simulation uses a geometric schedule, T ← α·T with α just below 1. Slower cooling usually finds shorter tours but takes longer.

What is the travelling salesman problem?

The shortest tour visiting every city exactly once and returning to the start. It is NP-hard, so 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 two cities. Both produce a neighbouring tour to compare against the current one.

What does the acceptance rate tell me?

The fraction of proposed moves accepted recently. It starts high while the temperature is high and drops toward zero as the schedule cools.

Does it 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.

How does the cooling rate affect the result?

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

Where is it used in practice?

In VLSI chip layout, scheduling, vehicle routing, image reconstruction, neural-network training and many other combinatorial problems with large, rugged search spaces.

About Simulated Annealing

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

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.