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.
SOLVE IT YOURSELF
Solve it: escape a local minimum on purpose
Hill climbing walks downhill and stops at the first valley — usually the wrong one. Annealing adds one strange rule: sometimes accept a worse move, often while hot and almost never once cold. That single concession is what gets you out of the valley. Python or TypeScript.
YOUR TASK
Implement anneal(cities, seed) for a small travelling-salesman tour: start from any order, propose a 2-swap, accept it by the temperature rule, cool, repeat. Return the best tour found and its length.
HINTS — 8 IDEAS
The energy is whatever you are minimising — here, total tour length. A proposal is a tiny random change: swap two cities.
If a proposal improves the energy, always take it. That much is plain hill climbing.
If it makes things worse, take it anyway with probability exp(-Δ/T). Large damage and low temperature both push that toward zero.
So the same bad move is likely early and almost impossible late. Early on you are exploring; later you are polishing.
Cool geometrically — T ← T × α with α just under 1. Cooling too fast is just hill climbing with extra steps; too slow wastes the whole budget wandering.
Keep a separate record of the best tour ever seen. The current tour is allowed to get worse, so the final state is not necessarily your answer.
Use a seeded generator, not the system random. Otherwise the result changes every run and you can neither test nor debug it.
Nothing here proves optimality. Annealing buys a good answer to a problem where the optimum is unaffordable — and on 9 cities you can check it against brute force, which is exactly what the tests do.