Greedy optimization gets stuck: it never accepts a worse move, so it settles into the first local minimum it finds and stays there. Simulated annealing borrows from metallurgy — heat a metal and let it cool slowly and its atoms settle into a low-energy crystal. Here, a temperature controls how willing we are to accept a worse solution: always take an improvement, but also accept a worse move with probability e^(−Δ/T). Start hot (bold, escaping local minima), cool slowly (picky, refining). Watch a tangled traveling-salesman tour untangle itself as the temperature falls.
accept worse moves with prob e^(−Δ/T) · cool T slowly · escapes local minima
energy / cost
What we minimize — here the total length of the traveling-salesman tour.
temperature T
Controls boldness: high T accepts many worse moves; low T is nearly greedy.
accept rule
Take any improvement; accept a worse move (Δ>0) with probability e^(−Δ/T).
cooling schedule
T is lowered gradually (e.g. multiplied by 0.99 each step) toward zero.
anneal.js — heat to explore, cool to commit
Ready
A random tour through the cities — long and tangled. Each step proposes a small change (reverse a segment). We always take improvements, and accept worse moves with probability e^(−Δ/T). Auto to anneal.
100
temperature
–
tour length
–
best so far
How it works
The whole method lives in one line: accept a proposed move if it improves the cost, or — if it makes things worse by Δ — accept it anyway with probability e^(−Δ/T). Read that probability at two extremes. When T is large, e^(−Δ/T) is close to 1, so even fairly bad moves are often accepted: the search roams freely and jumps out of local minima. As T falls toward 0, the probability collapses toward 0, so only improvements survive: the search behaves greedily and locks in refinements. Cooling slowly enough gives the search time to explore before it commits — which is what lets it find a near-global optimum on problems where pure greedy gets trapped.
1
Start hot with any solution
Begin from a random solution and a high temperature. At high T the search is willing to accept almost anything, so it explores broadly rather than diving into the nearest dip.
2
Propose a small random change
Perturb the current solution slightly — for a tour, reverse a random segment (a 2-opt move). Measure the change in cost, Δ.
3
Accept by the temperature rule
If Δ ≤ 0 (better or equal), accept. If Δ > 0 (worse), accept anyway with probability e^(−Δ/T). Accepting the occasional worse move is how it climbs out of local minima.
✓
Cool and repeat
Lower the temperature a little and repeat. As T approaches 0 the acceptance of worse moves vanishes and the search settles into a refined, near-optimal solution.
Accepts worse
e^(−Δ/T)
High T
explores
Low T
greedy
Escapes
local minima
The code
# simulated annealing for a minimization problem
cur = random_solution(); T = T0
best = cur
while T > T_min:
nxt = perturb(cur) # small random change
delta = cost(nxt) - cost(cur)
if delta <= 0 or random() < exp(-delta / T):
cur = nxt # accept (worse moves too, prob e^-Δ/T)if cost(cur) < cost(best): best = cur
T *= cooling_rate # e.g. 0.99 — cool slowly
Quick check
1. What makes simulated annealing able to escape a local minimum?
A greedy search never accepts a worse move and gets stuck in the first local minimum. Annealing accepts worse moves with probability e^(−Δ/T), letting it climb out of dips — especially while the temperature is high.
2. What happens as the temperature T approaches zero?
As T → 0, the acceptance probability for any worse move goes to 0, so the search only accepts improvements — behaving like greedy hill-climbing and locking in a refined solution.
3. Why cool the temperature slowly rather than quickly?
Cooling too fast freezes the search into whatever region it happens to be in (much like quenching metal). Slow cooling lets it explore widely while hot and refine while cool, which is what yields near-global solutions.
FAQ
What is simulated annealing?
A probabilistic optimization method inspired by metal annealing. It makes small random changes, always accepting improvements and sometimes accepting worse moves with probability e^(−Δ/T), where T is a temperature lowered over time. Accepting worse moves lets it escape local minima that trap greedy search.
Why is it called "annealing"?
From metallurgy: annealing heats a metal and cools it slowly so its atoms settle into a low-energy crystal (fast cooling locks in defects). The algorithm mimics this — high temperature lets the search move freely, slow cooling settles it into a low-cost configuration.
How does simulated annealing compare to hill climbing?
Hill climbing accepts only improving moves and stops at the first local optimum. Simulated annealing adds probabilistic acceptance of worse moves, controlled by temperature, letting it escape local optima and find better solutions on rugged landscapes — at the cost of more iterations and tuning the cooling schedule.
What problems is simulated annealing good for?
Hard combinatorial optimization with huge, local-optima-filled search spaces where a good solution suffices: traveling salesman, VLSI placement and routing, scheduling, protein folding models, and layout/assignment problems. It’s a general metaheuristic needing only a cost function and a perturbation.