Local Search: Hill Climbing, Simulated Annealing and Beam Search

In many problems we do not care about the path to the goal — only the goal itself. The 8-queens puzzle, timetabling, chip layout and hyperparameter tuning all ask for a configuration that is good. Local search algorithms keep a single current state (or a few), and repeatedly move to neighbouring states. They use constant memory and can find reasonable solutions in enormous or continuous spaces. They are also your first step towards understanding gradient-based learning.

The state-space landscape#

Imagine every state placed on a landscape whose height is its objective value (or negative cost). Local search tries to find the global maximum. The terrain contains:

• Local maxima — peaks higher than their neighbours but lower than the global maximum.
• Plateaus — flat regions where no neighbour is better.
• Ridges — sequences of local maxima that are hard to navigate with axis-aligned moves.

Hill climbing#

Steepest-ascent hill climbing moves to the best neighbour and stops when no neighbour is better.

import random

def conflicts(board):
    """board[c] = row of the queen in column c. Count attacking pairs."""
    n, total = len(board), 0
    for i in range(n):
        for j in range(i + 1, n):
            if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
                total += 1
    return total

def hill_climb(n=8, max_steps=1000):
    board = [random.randrange(n) for _ in range(n)]
    for _ in range(max_steps):
        current = conflicts(board)
        if current == 0:
            return board
        best, best_move = current, None
        for col in range(n):
            for row in range(n):
                if row != board[col]:
                    old = board[col]; board[col] = row
                    c = conflicts(board)
                    if c < best:
                        best, best_move = c, (col, row)
                    board[col] = old
        if best_move is None:
            return None               # stuck in a local minimum
        board[best_move[0]] = best_move[1]
    return None

print(hill_climb())

From a random start, steepest-ascent hill climbing solves 8-queens only about 14% of the time — it gets stuck in local optima. But it is very fast, averaging about 4 steps when it succeeds.

Fixes for hill climbing#

• Sideways moves allow moving across plateaus (with a cap on consecutive moves). This raises the success rate for 8-queens to roughly 94%.
• Stochastic hill climbing picks randomly among uphill moves.
• First-choice hill climbing generates random neighbours until one is better — good when neighbourhoods are huge.
• Random-restart hill climbing repeats from new random states until success. If each attempt succeeds with probability $p$, the expected number of restarts is $1/p$. It is surprisingly effective.

Simulated annealing#

In metallurgy, annealing cools a metal slowly so its atoms settle into a low-energy crystal. Simulated annealing mimics this: it picks a random move; if it improves, accept it; if it worsens the objective by $\Delta E < 0$, accept it with probability

where the temperature $T$ decreases over time according to a schedule. At high temperature the search explores widely, even going downhill; as $T \to 0$ it behaves like hill climbing.

import math, random

def simulated_annealing(state, energy, neighbor, T0=10.0, alpha=0.995, steps=20000):
    current, e_cur = state, energy(state)
    best, e_best = current, e_cur
    T = T0
    for _ in range(steps):
        cand = neighbor(current)
        e_new = energy(cand)
        delta = e_cur - e_new             # positive means improvement (minimising energy)
        if delta > 0 or random.random() < math.exp(delta / T):
            current, e_cur = cand, e_new
            if e_cur < e_best:
                best, e_best = current, e_cur
        T = max(T * alpha, 1e-8)
    return best, e_best

Local beam search#

Keep $k$ states instead of one. At each step generate all successors of all $k$ states and keep the best $k$. Unlike $k$ independent restarts, information is shared — states that are doing well attract the search. Stochastic beam search chooses successors with probability proportional to their value, avoiding a collapse into one region. (Beam search reappears in NLP for decoding sequences.)

Continuous spaces and gradients#

When states are real-valued vectors $\mathbf{x}$ and the objective $f$ is differentiable, the best local move is in the direction of the gradient:

This is gradient ascent — hill climbing with infinitesimal steps. Replace ascent with descent on a loss function and you have the engine that trains every neural network. Local optima, plateaus and ridges all have analogues in the loss landscapes of deep networks (saddle points, flat regions, narrow valleys).