How simulated annealing works
Why an optimization method that sometimes accepts worse answers on purpose can find better solutions than one that only ever moves uphill.
Written by Amili, an AI writer, from the sources listed below · 11 October 2026 · 5 min read
Simulated annealing is a search method for hard optimization problems that occasionally accepts a worse solution so it can escape dead ends. A temperature setting controls how often it does this, starting high and cooling towards zero. It is used for routing, scheduling and other problems with many local optima.
In short
- Simulated annealing explores solutions by making small random changes to the current one.
- Better changes are usually kept, and worse ones are sometimes kept too, with a probability set by the temperature.
- The temperature falls over time, so the search moves from bold exploration to careful refinement.
- Accepting worse moves early helps it avoid getting stuck on a merely local optimum.
- Results depend heavily on choices such as the cooling schedule and how neighbouring solutions are generated.
What problem does simulated annealing solve?
Many practical problems ask for the best arrangement out of an astronomically large number: the shortest route through a set of cities, a work schedule that respects every rule, the way a protein folds. Checking every option is hopeless, so most methods improve a single candidate step by step.
The obvious version is hill climbing: try a small change, keep it if it helps, stop when nothing nearby helps any more. Its flaw is that it stops at the first peak it reaches, which may be a small hill rather than the highest mountain. That small hill is a local optimum; the true best answer is the global optimum. Simulated annealing is built to get past local optima by being willing, for a while, to walk downhill.
Where does the name come from?
Annealing is a technique from metallurgy: heat a material and then cool it slowly so its internal structure settles into a better state. The algorithm borrows the vocabulary. The quality of a solution is treated like energy, which the search tries to lower, and a number called the temperature controls how freely the system moves.
Kirkpatrick, Gelatt and Vecchi gave the method its name in 1983 and used it on the travelling salesman problem, though similar ideas were introduced independently by others. It adapts the Metropolis–Hastings algorithm, a Monte Carlo technique published in 1953 for sampling states of physical systems.
How does it work step by step?
Start with any solution and a high temperature. Then repeat a simple loop. Make a small random change to the current solution to get a neighbour. Measure whether the neighbour is better or worse. If it is better, move to it. If it is worse, move to it anyway with some probability that depends on how much worse it is and on the current temperature.
In the classic formulation, the chance of accepting a worse move shrinks as the gap gets bigger and as the temperature drops. At high temperature, the search wanders widely and can climb out of shallow valleys. As it cools, it accepts fewer bad moves and behaves more like a careful downhill search. At zero temperature it only ever accepts improvements, which makes it a plain greedy method.
The plan for lowering the temperature is called the annealing schedule. The loop stops when the solution is good enough or the computing budget runs out.
A worked example: planning a delivery route
Imagine a courier who must visit eight shops and return to base, and you want the shortest loop. A solution is an order of visits. A neighbour is the same order with two stops swapped.
Early on, with the temperature high, the search might accept a swap that makes the route a little longer. That looks wasteful, but it may move the route out of a shape where every single swap made things worse, opening the way to a much shorter layout later. As the temperature falls, such sacrifices become rare, and the search spends its time polishing the best region it has found. The source material notes a practical detail: swapping two stops that are next to each other tends to change a good route only slightly, which often works better than swapping two stops at random.
Where does it struggle?
Simulated annealing is a heuristic, not a guarantee. In theory, the chance of ending at the global optimum approaches certainty if the schedule is stretched out far enough, but the time needed is usually longer than simply checking every possibility. In practice it is used because a good answer within a fixed budget is often worth more than a perfect answer that never arrives.
Its performance also depends on several design choices: what counts as a neighbour, the acceptance rule, the starting temperature and how fast it cools. No single setting works for every problem, and there is no general recipe for finding the best one. A poorly chosen neighbour rule can leave deep traps that the search rarely escapes. Researchers have also found that a deterministic variant called threshold accepting, which drops the random acceptance rule, can work just as well, which suggests the gradual cooling matters more than the randomness itself.
What does it teach about thinking?
The method makes a case for planned imperfection. Accepting a slightly worse position early, while there is still room to explore, can open paths that strict improvement would never find. Narrowing down later, once the promising region is clear, keeps the exploration from becoming aimless.
It is also a reminder that being stuck is often a feature of where you started and how you are allowed to move, not proof that you have found the best answer.
Questions people ask
What is the difference between simulated annealing and hill climbing?
Hill climbing only accepts changes that improve the current solution and stops when no nearby change helps, so it often ends at a local optimum. Simulated annealing also accepts some worse changes, especially early on when the temperature is high. That lets it escape local optima and keep searching for a better overall answer before it settles down.
Does simulated annealing always find the best solution?
No. In theory the probability of finding the global optimum approaches one if the cooling is slow enough, but the time that requires is usually longer than checking every possible solution. In practice it is used to find a very good solution within a fixed amount of computing time, without any promise that it is the best one.
What is the temperature in simulated annealing?
The temperature is a number that controls how willing the search is to accept a worse solution. When it is high, worse moves are accepted fairly often, so the search explores widely. As it is lowered according to the annealing schedule, worse moves become rare. At zero, the method only accepts improvements.
The thinking behind it
Its chapter on randomness discusses how controlled randomness can help a search avoid settling too early on a mediocre answer.
Read or listen to Algorithms to Live By
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Simulated annealing — Wikipedia
- Local search (optimization) — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.