Hill Climbing & Simulated Annealing

Local search

Many problems are not about finding a path but about finding a good state: a timetable with few clashes, a circuit layout with short wires, the weights of a model. You can measure how good a state is with an objective function, but there are far too many states to try them all.

Local search keeps only one current state and repeatedly moves to a neighbouring state: a small change such as swapping two lessons or moving one point. Picture the states as a landscape: position = the state, height = its value. We want the highest point (the global maximum). This is the same picture as gradient descent, turned upside down, but local search does not need a gradient: it only compares values.

Hill climbing

current ← start
loop:
    best ← the highest neighbour of current
    if value(best) ≤ value(current): return current
    current ← best

This is steepest-ascent hill climbing: look at all the neighbours and take the best. It is like climbing a mountain in thick fog, feeling only the ground around your feet.

In the 3D model each state is a point of a 21 × 21 grid and has 8 neighbours. On Two hills, from the default start:

Step	State	Value
0	(−1.8, −2.1)	0.45
1	(−1.5, −1.8)	1.06
2	(−1.5, −1.5)	1.56
3	(−1.5, −1.2)	1.77, and no neighbour is higher: stop

But the tall hill reaches 2.97. The climber is stuck on a local maximum: every neighbour is lower, even though a better state exists elsewhere. Start on the slope of the tall hill and it reaches 2.97 in 7 steps. The answer depends entirely on where you start.

Hill climbing has three classic traps:

• Local maxima: a peak lower than the global one.
• Plateaus: flat areas where all neighbours have the same value, so there is no direction to go.
• Ridges: a narrow rising crest that the available moves keep stepping off.

Random restarts

The simplest fix: run hill climbing from many random starting points and keep the best summit. If a fraction p of all starts lead to the global maximum, then k independent restarts miss it with probability (1 − p)^k. On the bumpy landscape only about 30% of starts climb to the top, yet 8 restarts succeed about 94% of the time.

Simulated annealing

Simulated annealing sometimes goes downhill on purpose, which lets it escape local maxima. The name comes from annealing metal: heated metal is cooled slowly so that its atoms can settle into a low-energy structure.

current ← start; T ← T₀
repeat:
    next ← a random neighbour
    Δ ← value(next) − value(current)
    if Δ ≥ 0: current ← next                         # better: always accept
    else: current ← next with probability e^(Δ/T)   # worse: sometimes accept
    T ← T × cooling
return the best state seen

The temperature T controls how adventurous the search is:

Δ (how much worse)	T = 2	T = 0.5	T = 0.05
−0.1	0.95	0.82	0.14
−0.5	0.78	0.37	≈ 0
−1.0	0.61	0.14	≈ 0

• Hot (T large): almost every move is accepted, so the search wanders freely and can cross valleys.
• Cold (T small): downhill moves are almost never accepted, so it behaves like hill climbing and polishes the solution.
• Small steps downhill are accepted more often than large ones.

The model starts at T = 2 and multiplies T by 0.985 each step (geometric cooling), for 400 steps. Watch the thermometer: early on the ball wanders between hills; later it settles on one and climbs to its top.

How well do they do?

Running each method 1000 times from random starts (code below):

Landscape	Hill climbing	8 random restarts	Simulated annealing
Two hills	59%	100%	78%
Bumpy (17 local maxima)	30%	94%	95%

Plain hill climbing is fast but unreliable. Restarts and annealing both fix that in different ways: restarts by brute force, annealing by occasionally accepting worse states. Annealing does best when there are many small traps, because it does not have to start from scratch to escape each one.

Related methods

Method	Idea
First-choice hill climbing	Take the first random neighbour that is better (good when there are many neighbours).
Stochastic hill climbing	Choose randomly among the uphill moves.
Local beam search	Keep k states at once and keep the best k of all their neighbours.
Genetic algorithms	Keep a population and combine good states.
Tabu search	Remember recent states and forbid going back.

Code

import math, random

N, STEP = 21, 0.3                 # a 21 x 21 grid of states from -3 to 3

def two_hills(x, y):
    return 3.0 * math.exp(-((x - 1.3)**2 + (y - 0.9)**2) / 0.9) + 1.8 * math.exp(-((x + 1.4)**2 + (y + 1.2)**2) / 0.7)

def bumpy(x, y):
    return 0.5 * math.sin(3 * x) * math.cos(3 * y) + 2.2 * math.exp(-((x - 1.5)**2 + (y + 1.2)**2) / 1.0)

def value(f, s):
    return f(-3 + s[0] * STEP, -3 + s[1] * STEP)

def neighbours(s, r=1):
    """All grid states within r steps of s (r = 1: the 8 surrounding states)."""
    return [(s[0] + di, s[1] + dj) for di in range(-r, r + 1) for dj in range(-r, r + 1)
            if (di or dj) and 0 <= s[0] + di < N and 0 <= s[1] + dj < N]

def hill_climb(f, s):
    """Steepest ascent: move to the best neighbour while it is higher. Returns the path."""
    path = [s]
    while True:
        best = max(neighbours(s), key=lambda n: value(f, n))
        if value(f, best) <= value(f, s):
            return path                           # no neighbour is higher: a (local) maximum
        s = best
        path.append(s)

def random_restart(f, k, rng):
    """Run hill climbing from k random starts and keep the best summit."""
    tops = [hill_climb(f, (rng.randrange(N), rng.randrange(N)))[-1] for _ in range(k)]
    return max(tops, key=lambda s: value(f, s))

def anneal(f, s, rng, t=2.0, cooling=0.985, steps=400, r=3):
    """Simulated annealing: accept a worse random neighbour with probability e^(delta / T)."""
    best = s
    for _ in range(steps):
        n = rng.choice(neighbours(s, r))
        delta = value(f, n) - value(f, s)
        if delta >= 0 or rng.random() < math.exp(delta / t):
            s = n                                 # uphill always; downhill sometimes
        if value(f, s) > value(f, best):
            best = s
        t *= cooling                              # cool down
    return best

for f in (two_hills, bumpy):
    top = max(((i, j) for i in range(N) for j in range(N)), key=lambda s: value(f, s))
    rng = random.Random(1)
    starts = [(rng.randrange(N), rng.randrange(N)) for _ in range(1000)]
    hc = sum(hill_climb(f, s)[-1] == top for s in starts) / 1000
    rr = sum(random_restart(f, 8, random.Random(k)) == top for k in range(1000)) / 1000
    sa = sum(anneal(f, s, random.Random(k)) == top for k, s in enumerate(starts)) / 1000
    print(f'{f.__name__:9} global max {top} = {value(f, top):.2f}   hill climbing {hc:.0%}   8 restarts {rr:.0%}   annealing {sa:.0%}')
# two_hills global max (14, 13) = 2.97   hill climbing 59%   8 restarts 100%   annealing 78%
# bumpy     global max (15, 6) = 2.64   hill climbing 30%   8 restarts 94%   annealing 95%

path = hill_climb(two_hills, (4, 3))
print(path, round(value(two_hills, path[-1]), 2))
# [(4, 3), (5, 4), (5, 5), (5, 6)] 1.77
path = hill_climb(two_hills, (15, 6))
print(path, round(value(two_hills, path[-1]), 2))
# [(15, 6), (14, 7), (14, 8), (14, 9), (14, 10), (14, 11), (14, 12), (14, 13)] 2.97

Common mistakes

• Expecting hill climbing to find the global maximum. It finds a maximum, the first one it walks into.
• Getting the sign of the acceptance probability wrong. For a worse move Δ is negative, so e^Δ/T is below 1. A better move is always accepted.
• Cooling too fast. Then annealing freezes before it has explored, and it is no better than hill climbing.
• Returning the final state of annealing. Keep track of the best state ever seen; the last one may be worse.
• Confusing minimising and maximising. For a cost to minimise, flip the signs: accept a move that increases the cost with probability e^−Δ/T.