Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 49 ยท Heuristics and Practice

Simulated Annealing and Other Metaheuristics

Escape local optima with simulated annealing: the acceptance rule, cooling schedules and a full TSP run, plus tabu search and genetic algorithms compared.

Local search has one big weakness: it stops at the first local optimum. In the last lesson, hill-climbing from random starting tours sometimes ended near 392 when the best tour has length 345.8. To do better we need a way to climb out of valleys, that is, to occasionally accept a move that makes the solution temporarily worse.

Simulated annealing (SA) does this with a beautifully simple rule borrowed from physics. It was proposed by Scott Kirkpatrick, C. Daniel Gelatt and Mario Vecchi in 1983, and independently by Vlado ฤŒernรฝ in 1985. Its inspiration is the way blacksmiths and glassmakers cool metal slowly so that atoms settle into a low-energy, well-ordered state, rather than freezing into a brittle, disordered one.

A cost landscape with a local and a global minimum, and acceptance probabilities falling with temperature
Caption: At high temperature the search readily accepts worse moves and hops over hills; as the temperature falls the chance of a +5 move drops from 61 percent to under 1 percent.

What you will learn

  • The simulated annealing algorithm and its acceptance rule exp(โˆ’ฮ”/T).
  • How cooling schedules and starting temperature affect the results.
  • How to apply SA to the traveling salesman problem and measure its benefit.
  • How tabu search and genetic algorithms differ, and how to choose between methods.

Key terms

Temperature (T): a control parameter; high values mean the search accepts many worse moves, low values few.

ฮ” (delta): the change in cost caused by a candidate move; positive means worse for a minimization problem.

Metropolis rule: accept a worse move with probability exp(โˆ’ฮ”/T), named after Nicholas Metropolis and colleagues (1953).

Cooling schedule: the rule for lowering T, commonly geometric: T โ† ฮฑ ยท T with ฮฑ slightly below 1.

Tabu search: a local search that keeps a short-term memory of recent moves and forbids undoing them.

The algorithm

  1. Start from any solution and a high temperature T.
  2. Pick a random neighbor (for tours, a random 2-opt move) and compute ฮ” = new cost โˆ’ current cost.
  3. If ฮ” < 0 (better), accept it. If ฮ” โ‰ฅ 0 (worse), accept it anyway with probability exp(โˆ’ฮ” / T).
  4. Lower the temperature slightly (T โ† ฮฑ T) and repeat.
  5. Remember the best solution ever visited, and return it at the end.

The acceptance rule explains the behavior. At high T, exp(โˆ’ฮ”/T) is near 1 even for big ฮ”, so the search wanders almost freely and explores the whole landscape. At low T it is near 0 for any ฮ” > 0, so the method becomes plain hill-climbing and polishes the solution it has. For example, accepting a move that is 5 units worse has probability e^{โˆ’5/10} = 0.61 at T = 10, but e^{โˆ’5/1} = 0.0067 at T = 1.

Acceptance probability explorer

Annealing the 12-city tour

Now the real thing. The program starts from a random tour, uses the random 2-opt move, begins at T = 30 (about the size of a typical edge) and multiplies the temperature by 0.999 after each of 15,000 steps. It tracks the current and the best tour length.

Python Simulated annealing on the TSP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At the start the current length bounces around a high level: the search accepts almost everything. As the temperature falls it concentrates on better and better tours, and finally freezes into a short one.

One run proves little. Compare 20 runs of simulated annealing with 20 runs of pure hill-climbing (accept only improving moves) from random starts, with the same number of steps.

Python Annealing versus hill-climbing, 20 runs each

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The generator is seeded, so you will see the same figures every time: annealing finds the exact optimum in 18 of the 20 runs (mean 346.3, worst 351.0), while hill-climbing with the same number of steps reaches it in only 6 of 20 (mean 354.4, worst 392.4). Both methods use the same number of steps, so the better reliability costs nothing extra.

Choosing parameters

  • Starting temperature. Choose T0 so that early on, about 50 to 80 percent of worse moves are accepted. A quick rule: set T0 close to the typical size of ฮ” for random moves.
  • Cooling rate. ฮฑ between 0.95 and 0.9999. Slower cooling (closer to 1) gives better results and costs more time. Total steps are roughly ln(T_end/T0) / ln(ฮฑ).
  • Neighborhood. Use small, meaningful moves (swap two items, reverse a segment, shift a job). Too large and it behaves randomly; too small and it moves slowly.
  • Restarts and runs. Run several seeds and report the best, the mean and the spread.

Other metaheuristics in a nutshell

Method Core idea Typical use
Tabu search (Fred Glover, 1986) Always move to the best neighbor, even if worse, but forbid recently used moves for a few steps Scheduling, routing
Genetic algorithms (John Holland, 1975) Keep a population of solutions; combine parts of two parents (crossover), add random changes (mutation), keep the fittest Design, scheduling, parameter tuning
Ant colony optimization (Marco Dorigo, 1992) Simulated ants lay "pheromone" on good edges, guiding later ants Routing
Iterated local search Perturb the current local optimum, re-run local search, accept if better Many combinatorial problems

None of these is better in general; the "no free lunch" idea says that averaged over all possible problems, no search method beats another. The right choice depends on the structure of your problem and how easily you can define good moves. The genetic algorithms track explores population methods in depth.

A worked acceptance example

Suppose the current tour has length 350 and a random 2-opt move gives a tour of length 358, so ฮ” = +8. At T = 30 the acceptance probability is e^{โˆ’8/30} = e^{โˆ’0.267} โ‰ˆ 0.77: the move is accepted about three times in four. When the temperature has cooled to T = 4, the probability is e^{โˆ’2} โ‰ˆ 0.135; at T = 1 it is e^{โˆ’8} โ‰ˆ 0.0003, essentially never. The same move that is routinely accepted early on is rejected late, which is exactly the shift from exploration to refinement.

A good starting temperature makes a sizable share of worse moves acceptable at the beginning. A simple recipe is to run a few hundred random moves, record the typical size of the cost change |ฮ”|, and set T0 so that e^{โˆ’|ฮ”|/T0} is around 0.5 to 0.8. That is why the 12-city example uses T0 = 30, close to a typical edge length.

Restarts, reheating and stopping

Annealing has several practical refinements. Restarts run the whole procedure several times from different starting solutions and keep the best, which guards against a bad random early phase. Reheating raises the temperature again after a long time without progress. And a stopping rule ends the run when the best solution has not improved for a long time or when the temperature falls below a threshold. As with every heuristic, record the random seed, run several seeds, and report the best, the average and the spread, not a single lucky run.

Common misconceptions

"Annealing is guaranteed to find the optimum." Only with an infinitely slow cooling schedule. In practice it is a heuristic with no guarantee.

"Accepting worse moves is a mistake in the code." It is the whole point: it lets the search leave local optima.

"Higher temperature is better." Too hot and the search is a random walk; too cold and it is hill-climbing. The schedule must pass through the middle range slowly.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A move worsens the cost by ฮ” = 6 at temperature T = 3. What is the acceptance probability?

    exp(โˆ’ฮ”/T) = exp(โˆ’6/3) = exp(โˆ’2) โ‰ˆ 0.135.
  2. 2. What happens to the search as the temperature approaches zero?

    exp(โˆ’ฮ”/T) tends to 0 for any worse move, so only better moves are accepted.
  3. 3. Why record the best solution ever visited?

    Annealing may leave a very good solution by accepting a worse move, so the best-so-far is stored separately.
  4. 4. Which method forbids recently used moves for a few steps?

    Tabu search keeps a short-term memory (the tabu list) to prevent cycling back.
  5. 5. Cooling with ฮฑ = 0.99 from T0 = 100: about how many steps to reach T = 1?

    ln(1/100)/ln(0.99) = (โˆ’4.605)/(โˆ’0.01005) โ‰ˆ 458 steps.

Summary

  • Simulated annealing accepts a worse move with probability exp(โˆ’ฮ”/T), which lets it escape local optima.
  • Starting hot and cooling slowly turns exploration into refinement; keep the best solution seen.
  • On the 12-city TSP, annealing found the exact optimum in most runs, where plain hill-climbing often got stuck.
  • Tabu search, genetic algorithms and ant colonies are other metaheuristics; none wins on every problem.

Next: From messy problem to decision