Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 36 ยท Swarm and Other Metaheuristics

Simulated Annealing and Hill Climbing

Compare single-solution metaheuristics with genetic algorithms. Code hill climbing, random restarts and simulated annealing in Python, and learn when each wins.

A genetic algorithm keeps a whole population of solutions. Many other metaheuristics keep just one. They start somewhere, make a small change, and decide whether to accept it. These single-solution methods are easy to code, use little memory, and are surprisingly competitive. They also make a perfect baseline: if your GA cannot beat simulated annealing on your problem, you do not need the GA.

This lesson covers three of them: hill climbing, random-restart hill climbing and simulated annealing. We use the same toy problem for all, so the results are comparable.

A test problem: the bumpy landscape

We will maximize a function of one variable with many peaks:

TEXT
f(x) = x * sin(10 * x) + 2 * cos(3 * x)        for x in [0, 10]

A neighbour of x is x plus a small random step.

Hill climbing

The simplest local search: look at a neighbour; if it is better, move there; otherwise stay. Repeat. It climbs the nearest hill and stops on the top of it, which might be a small bump far below the highest peak. This is the problem of local optima.

Random-restart hill climbing

A cheap fix: run hill climbing many times from different random starting points, and keep the best result. With enough restarts, one of them starts on the slope of the best hill.

Simulated annealing

Simulated annealing (SA) gets out of local optima by sometimes accepting worse moves. The name comes from metallurgy: a hot metal's atoms jiggle freely, and as it cools slowly, they settle into a low-energy crystal.

The rule (for maximization) is the Metropolis criterion:

  • If the neighbour is better, accept it.
  • If it is worse by delta, accept it with probability exp(-delta / T), where T is the temperature.

At high T, nearly any move is accepted: the search wanders. As T falls (the cooling schedule), bad moves become unlikely and SA behaves like hill climbing. The most common schedule is geometric: T = T * 0.95 per step.

flowchart TD
    S["Start: x, high temperature T"] --> N["Pick a random neighbour y"]
    N --> D{"f(y) >= f(x)?"}
    D -- yes --> A["Accept: x = y"]
    D -- no --> P{"random < exp(-delta / T)?"}
    P -- yes --> A
    P -- no --> R["Reject: keep x"]
    A --> C["Cool: T = alpha * T"]
    R --> C
    C --> N

SA is hill climbing with a temperature-controlled chance of going downhill.

Python Hill climbing vs restarts vs simulated annealing

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 the pattern: a single hill climb rarely reaches the global peak (about 6 percent of runs here), restarts raise the average a lot but their small steps seldom land exactly on the top of the best hill, and simulated annealing reaches the global peak most often because its early, large wandering lets it leave poor hills.

Choosing the temperature

Temperature is relative to the typical size of a bad move. A good starting rule: pick T0 so that about 50 to 80 percent of worsening moves are accepted at the start. Then cool until almost none are. If you cool too fast, SA is just hill climbing; if you cool too slowly, you waste time.

SA also works for combinatorial problems: the neighbour of a tour is the same tour with two cities swapped, for example. That makes it a useful partner to the traveling salesman GA later in this course.

Python Annealing a 25-city 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 neighbourhood move here, reversing a segment, is called 2-opt. Choosing a good neighbourhood is half the battle in any local search.

When does each method win?

Method Wins when
Hill climbing The landscape is smooth with one peak, or you need a cheap polish step
Random restarts Many peaks, evaluations are cheap, and basins are wide
Simulated annealing A rugged landscape, a good neighbourhood move exists, little memory available
Genetic algorithm Good building blocks can be recombined, or you need a diverse set of answers

A powerful hybrid called a memetic algorithm runs a short hill climb on each GA offspring. You get the global exploration of the GA and the fast local refinement of hill climbing.

Common mistakes

  • Comparing methods by a single run. Use many seeds.
  • Wrong temperature scale. Temperature must match the size of your objective differences.
  • Forgetting to remember the best. SA may wander away from the best solution it has seen; keep a separate record.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does simulated annealing sometimes accept a worse solution?

    Occasional downhill moves let the search leave a small hill and find a higher one.
  2. 2. At very high temperature, simulated annealing behaves like:

    Almost every move is accepted, so the path is nearly random.
  3. 3. What does geometric cooling (T = 0.95 * T) do?

    Each step multiplies T by 0.95, so T decays exponentially.
  4. 4. What is a memetic algorithm?

    Combining global search with local refinement often beats either alone.

Summary

  • Single-solution methods keep one candidate and accept or reject small changes.
  • Hill climbing is greedy and gets stuck; restarts or annealing fix that.
  • Simulated annealing accepts worse moves with probability exp(-delta / T), cooling over time.
  • The neighbourhood (for example 2-opt for tours) matters as much as the algorithm.
  • They are excellent baselines: always compare your GA against them.

Next: Ant Colony Optimization