Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 46 ยท Informed Search

Simulated Annealing and Genetic Algorithms

Escape local optima with simulated annealing and genetic algorithms: temperature schedules, acceptance probability, crossover, mutation, a travelling salesman demo and tuning tips.

Hill climbing is fast and simple, but it has one fatal habit: it only ever moves uphill, so it gets stuck on the first peak it finds. This lesson covers two classic ways around that problem. Simulated annealing sometimes accepts a worse move on purpose, and does so less and less often as the search goes on. Genetic algorithms keep a whole population of candidate solutions and breed new ones from the best.

Both methods are metaheuristics: they do not need a model of the problem, only a way to score a candidate and a way to change it a little. That is why they are used for scheduling, circuit layout, route planning and tuning parameters, wherever the search space is huge and a "good enough" answer is fine. We will use the travelling salesman problem (TSP) as a test bed throughout.

The test problem: a tour through 25 cities

In the TSP you must visit every city once and return to the start, using the shortest possible loop. A candidate solution is simply an ordering of the cities, and its cost is the total length of the loop. The cost is what we want to minimize (a "fitness" to maximize is just the negative cost).

For 25 cities there are more than 10^23 distinct tours, so enumeration is out of the question. The natural neighbor move for a tour is a 2-opt move: pick two positions and reverse the section between them. This replaces two edges with two others and often removes a crossing.

Python TSP setup: random tours versus a greedy tour

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 numbers show the usual picture: random tours are awful, greedy is decent, and hill climbing with 2-opt improves it until no single reversal helps. That final tour is a local optimum, not necessarily the best one.

Simulated annealing

Metallurgists make strong metal by heating it and cooling it slowly, so the atoms settle into a low-energy arrangement instead of freezing into a flawed one. Simulated annealing copies that idea. It uses a temperature T that starts high and slowly drops.

At each step:

  1. Pick a random neighbor of the current state.
  2. Let delta = new_cost - old_cost.
  3. If delta <= 0 (better or equal), accept it.
  4. Otherwise accept it anyway with probability exp(-delta / T).

When T is large, almost everything is accepted and the search wanders freely. When T is tiny, only improvements are accepted and the search behaves like hill climbing. The cooling schedule is a smooth passage from one to the other.

graph LR
    A["High T<br/>explore widely"] --> B["Medium T<br/>accept small<br/>worsening moves"]
    B --> C["Low T<br/>behaves like<br/>hill climbing"]

Temperature controls how willing the search is to go downhill.

The acceptance probability

The probability exp(-delta / T) has an intuitive shape: bad moves are accepted more often when they are only slightly bad and when the temperature is high. Look at it directly.

Python Acceptance probability exp(-delta / T)

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.

Read across a row: a move that makes things 5 units worse is accepted most of the time at T=100 but almost never at T=1. Read down a column: at a fixed temperature, big setbacks are far less likely than small ones.

Cooling schedules

The most common schedule is geometric cooling: T = T0 * alpha^k with alpha slightly below 1 (such as 0.95 to 0.9999). Linear cooling and logarithmic cooling also exist. Theory says a logarithmic schedule guarantees finding the global optimum in the limit, but it is far too slow to use, so practitioners tune a geometric schedule by experiment.

A good starting temperature T0 is one at which roughly 60-80% of worsening moves are accepted. A good final temperature is low enough that the search is effectively greedy. If the delta values in your problem are about 10 units, a T0 of 0.001 is pointless and a T0 of 10,000 wastes time.

Annealing the TSP

Python Simulated annealing on the 25-city 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.

Compare the three rows. A very fast schedule (alpha=0.99) cools so quickly that the search freezes early, close to plain hill climbing. Slower cooling gives the search time to find better basins before it commits. The price is runtime, which is the central trade-off of annealing: more patience buys better answers.

Tip: Always keep the best state seen so far separately from the current state. Annealing wanders, so the final state is not always the best one it visited.

Genetic algorithms

A genetic algorithm (GA) is inspired by evolution. It maintains a population of candidate solutions (called individuals or chromosomes) and repeats these steps for many generations:

  1. Evaluate each individual's fitness.
  2. Select parents, favoring fitter ones.
  3. Crossover: combine two parents to make children.
  4. Mutate: randomly tweak children a little.
  5. Replace the old population with the new one, often keeping a few top individuals unchanged (elitism).
graph TD
    P["Population"] --> F["Evaluate fitness"]
    F --> S["Select parents"]
    S --> C["Crossover"]
    C --> M["Mutate"]
    M --> N["New population<br/>(keep the elite)"]
    N --> P

One generation of a genetic algorithm. The loop runs until time or generations run out.

Each step has a job. Selection pushes the population toward good solutions (exploitation). Mutation injects new variety so the search cannot get permanently stuck (exploration). Crossover is the distinctive part: it lets good building blocks found in different individuals come together in one child.

Representation matters

How you encode a solution decides which crossover and mutation operators make sense. For bit-string problems you can cut two parents at a random point and swap the tails (one-point crossover), and mutate by flipping each bit with a small probability. For the TSP, a plain cut would produce tours that visit a city twice, so we need a permutation-preserving operator.

Order crossover (OX) copies a slice from parent 1, then fills the remaining positions with the missing cities in the order they appear in parent 2. The child is always a valid tour. A good mutation for tours is to swap two cities.

Start with a simpler problem to see the loop: evolve a bit string toward a target pattern.

Python A tiny genetic algorithm on bit strings

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.

Notice that the average fitness climbs steadily even though no individual was designed: selection plus variation does the work.

A genetic algorithm for the TSP

Python Genetic algorithm with order crossover 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.

The top section of the output shows the best tour shrinking from about 960 to about 440 over 150 generations. The bottom compares runs with and without mutation across four seeds: with the mutation rate at 0 every run ends well above 550, while mutation brings them down to roughly 400-550. Notice also that this plain GA does not beat annealing with 2-opt moves (about 384 on the same cities). That is typical: a GA shines when you have good operators or add local improvement, and a neighbor-based method with a well-chosen move is often the stronger baseline.

Tuning pitfalls

Both methods have knobs, and bad settings are the usual reason they "do not work".

  • Premature convergence (GA). If one individual dominates early, the population fills with copies of it and crossover produces nothing new. Remedies: larger populations, gentler selection (smaller tournaments), more mutation, or injecting random newcomers.
  • Too-fast cooling (SA). Equivalent to hill climbing with extra steps. If repeated runs end at very different costs, you are cooling too fast.
  • Wrong temperature scale (SA). T must match the typical size of delta. Rescaling the cost function changes the right schedule.
  • Bad operators. A neighbor move or crossover that mostly produces terrible candidates wastes the budget. Moves should make small, meaningful changes. 2-opt works for tours because it changes only two edges.
  • Judging from one run. These methods are random. Compare settings over several seeds and report the mean and best, as the demos above do. Fixed seeds make your experiments repeatable.
  • Using them when something better exists. For problems with structure, such as shortest paths or small constraint satisfaction problems, an exact algorithm is better. Reach for annealing and GAs when exact methods are impractical and a good answer is enough.

Neither method guarantees an optimal answer in finite time, and neither tells you how close you are. Treat the output as a good solution, not a proof.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In simulated annealing, when is a worse neighbor accepted?

    A worse move is accepted with probability exp(-delta / T). It is likely when delta is small or T is high, and unlikely when delta is large or T is low.
  2. 2. What happens if the cooling schedule is too fast?

    Cooling quickly removes the search's ability to escape local optima early on. It then behaves like greedy hill climbing.
  3. 3. Why does a genetic algorithm for the TSP use order crossover instead of cutting tours at a point and swapping tails?

    A tour is a permutation. Order crossover keeps a slice of one parent and fills the rest from the other in order, so the child is always a valid permutation.
  4. 4. What is the main purpose of mutation in a genetic algorithm?

    Mutation adds random variation. Without it, selection and crossover can only recombine what the population already contains.
  5. 5. Why is it good practice to run randomized search from several seeds?

    Annealing and genetic algorithms are stochastic. Comparing means and bests over several fixed seeds gives a fair, repeatable comparison.

Summary

  • Simulated annealing accepts worse moves with probability exp(-delta / T) and lowers T over time, moving from exploration to greedy refinement.
  • Geometric cooling (T = T0 * alpha^k) is the practical default; slower cooling usually gives better answers at the cost of time.
  • A genetic algorithm evolves a population using selection, crossover, mutation and elitism.
  • The representation decides which operators are valid: use order crossover and swap mutation for permutations such as TSP tours.
  • Watch for premature convergence, a badly scaled temperature and unrepresentative single runs.
  • Both are metaheuristics: good for huge search spaces, but with no guarantee of optimality.

Next: Constraint Satisfaction Problems.