Local Search and Optimization

The uninformed and informed search algorithms keep one or more paths in memory and record, at every node, which alternatives have already been tried. When a goal turns up, the path that reached it is the solution — the order of moves is the answer. For a large class of problems that bookkeeping is wasted effort. In the 8-queens problem the answer is a board configuration with no two queens attacking; the sequence in which the queens were placed is irrelevant. The same holds for integrated-circuit layout, factory-floor scheduling, job-shop scheduling, telecommunications-network routing, vehicle routing, and portfolio management: what you want is a good final state, not a route to it.¹

When the path does not matter, keep only the current state and try to improve it. Local search algorithms operate on a single current node and move only to neighbors, discarding the paths behind them. They are not systematic, so they give up the completeness guarantees of tree search, but they buy two things in return: they use a constant amount of memory, and they can find reasonable solutions in state spaces far too large — or continuous, hence infinite — for any systematic method to enumerate.

Local search also solves problems that the standard framing of Chapter 3 cannot express at all: optimization problems, where there is no explicit goal test, only an objective function to be made as large (or small) as possible. Nature runs one such problem — Darwinian evolution maximizes reproductive fitness with no goal and no path cost — and much of engineering runs the rest.

This lesson develops the single-state methods: the landscape metaphor, hill climbing and its failure modes, and the first two ways to escape those failures — random restarts and simulated annealing. The methods that keep a population of states (beam search and genetic algorithms) and the calculus for continuous spaces follow in the companion lesson, Population and Continuous Search.

The state-space landscape

The right mental picture for local search is a terrain. Give each state two attributes: a location, fixed by the state itself, and an elevation, given by the value of the objective function (or of a heuristic cost, if we are minimizing). Plot elevation against location and the state space becomes a surface with peaks and valleys. If elevation is value, we want the highest peak, the global maximum; if elevation is cost, we want the lowest valley, the global minimum. The two are interchangeable — negate the function and a maximization problem becomes a minimization problem — so we fix ideas on maximization and speak of climbing.

A complete local search always finds a goal if one exists; an optimal one always finds the global maximum. The features of this one-dimensional landscape — shoulders, local maxima, plateaus — are what make those two guarantees hard to achieve, and every algorithm below is a strategy for coping with one of them.

Hill climbing

The simplest local search is hill climbing, in its steepest-ascent form: a loop that repeatedly moves to the neighboring state of highest value, and halts when no neighbor is higher. It keeps no search tree — the only state it records is the current node and its objective value — and it never looks past its immediate neighbors. Russell and Norvig liken it to finding the top of Mount Everest in a thick fog while suffering from amnesia.²

Hill climbing is sometimes called greedy local search: it grabs the best neighbor without any thought for where to go next. Greed usually pays. Because a bad state is typically easy to improve, hill climbing makes rapid progress — from a random 8-queens position it reaches a near-solution in only a handful of steps. When it works, it works fast.

The 8-queens formulation

To see the algorithm at work, use the complete-state formulation of 8-queens: every state has all eight queens on the board, one per column, and the successors of a state are the $8\times 7=56$ states reached by moving a single queen to another square in its own column. The heuristic $h$ is the number of pairs of queens attacking each other, directly or indirectly; the global minimum of $h$ is $0$, attained only by a genuine solution.

From a randomly generated 8-queens state, steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of instances. But it is fast where it does not stall: about four steps to reach a solution, three to reach a dead end — respectable for a space of $8^8\approx 17$ million states.

A short trace shows the greedy loop at work. Start from a state with $h=17$ attacking pairs. Of its $56$ successors, the best drops $h$ to $12$ (there may be several tied at $12$; pick one), so the climber takes it. From the new state the best successor reaches $h=8$, then $h=5$, then $h=3$, then $h=1$. At $h=1$ every one of the $56$ successors has $h\ge 1$ — no single queen move removes the last conflict without creating another — so the best neighbor ties or worsens the current value, the halting test fires, and hill climbing returns a state with one attacking pair still on the board.

Five steps of steep, cheap progress, then a wall: the state with $h=1$ is a local minimum of the cost $h$ (equivalently a local maximum of the nonattacking pairs objective), one conflict short of a solution and unable to take the last step. This is the $86\%$ case in miniature — fast to a near-solution, then stuck.

Why hill climbing gets stuck

The 86% failure rate comes from three features of the landscape, each visible in the one-dimensional figure above.

Ridges are the subtler trap. A ridge is a sequence of local maxima aligned along a direction the available moves cannot follow: the grid of states is laid over a slope that rises diagonally, so from each state every single-step move points downhill even though a diagonal combination would climb. Greedy search cannot see the diagonal and stalls, oscillating along the crest.

The plateau case exposes a design choice. The algorithm above halts when the best neighbor merely ties the current value, which surrenders on every shoulder. Allowing sideways moves — stepping to an equal-valued neighbor in the hope the plateau is a shoulder — fixes shoulders but risks an infinite loop on a flat local maximum. The standard compromise caps the number of consecutive sideways moves (say, 100 for 8-queens). That single change lifts the 8-queens success rate from 14% to 94%, at the cost of longer runs: about 21 steps per success and 64 per failure.

Variants of hill climbing

Because the failure modes are landscape-shaped, several cheap modifications of the greedy rule help on landscapes of different shape.

• Stochastic hill climbing chooses at random among the uphill moves, weighting the choice by steepness. It usually converges more slowly than steepest ascent but finds better solutions on some landscapes, because it is less prone to march straight into the nearest local maximum.
• First-choice hill climbing implements stochastic hill climbing without enumerating all successors: it generates successors at random and takes the first one that improves on the current state. This is the right choice when a state has thousands of successors and computing all of them is wasteful.
• Random-restart hill climbing attacks incompleteness head-on. It runs a series of hill climbs from randomly generated initial states, keeping the best result, until a goal is found. It is complete with probability approaching 1, because eventually a starting state lands in the global maximum's basin — or is the goal.

Random restart has a clean cost analysis. If each hill climb succeeds with probability $p$, the expected number of restarts to reach a goal is $1/p$. For 8-queens without sideways moves, $p\approx 0.14$, so roughly $1/0.14\approx 7$ restarts suffice — six failures and one success. The expected total work is the cost of one success plus $(1-p)/p$ times the cost of a failure, about 22 steps in all. With sideways moves allowed, $p\approx 0.94$, so $1/0.94\approx 1.06$ restarts and about $(1\times 21)+(0.06/0.94)\times 64\approx 25$ steps. Even three-million-queens instances fall in under a minute.

Whether random restart succeeds depends entirely on the shape of the landscape. A landscape with few local maxima and shallow plateaus surrenders after a handful of restarts; an NP-hard problem, whose surface resembles a widely scattered family of balding porcupines on a flat floor — a spike of local optima on every needle — may have exponentially many traps. Even then, a reasonably good local maximum is often reachable in a few restarts.

Simulated annealing

Hill climbing never steps downhill, so it is doomed to stop at the first local maximum it climbs into. A pure random walk — move to a uniformly random neighbor, ignoring value — is complete (it eventually visits every state, the global maximum included) but hopelessly slow. Simulated annealing combines the two: mostly climb, but occasionally allow a downhill move, and let the willingness to go downhill shrink over time.

The physical metaphor makes the schedule intuitive. Switch to minimizing cost (gradient descent) and picture rolling a ping-pong ball into the deepest crevice of a bumpy surface. Let it roll and it settles in the first dent — a local minimum. Shake the surface and the ball hops out; shake too hard and it never settles anywhere. The trick is to shake hard at first, enough to bounce the ball out of shallow local minima, then gradually shake more gently so that once the ball finds the deep global minimum it stays. Shaking hard is a high temperature $T$; cooling is lowering $T$ on a fixed schedule.

The acceptance rule is where the temperature enters. Let $\Delta E$ be the change in value a proposed move would produce (positive if the move improves things). Improving moves are always accepted. A worsening move, $\Delta E<0$, is accepted with probability

Two properties make this the right rule. It decreases exponentially with the badness of the move: a slightly worse neighbor is often accepted, a much worse one rarely. And it decreases as $T$ falls: bad moves are common early, when $T$ is high, and progressively forbidden as the schedule cools. If $T$ is lowered slowly enough, simulated annealing finds a global optimum with probability approaching 1.³

Put numbers to it. Suppose the objective is a cost being minimized (so $\Delta E$ is negative for a worsening move) and a proposed move worsens the cost by $|\Delta E|=2$. The acceptance probability $e^{\Delta E/T}=e^{-2/T}$ then depends entirely on where the schedule stands:

Read down a column and the cooling story is plain: at $T=10$ a move that worsens cost by $2$ is accepted $82\%$ of the time — the search wanders almost freely — while at $T=0.5$ the same move is accepted under $2\%$ of the time, and at $T=0.1$ it is effectively forbidden. Read across a row and the badness story appears: at $T=1$, a worsening of $1$ is accepted $37\%$ of the time but a worsening of $5$ only $0.7\%$. High temperature early lets the ball bounce out of shallow traps; low temperature late pins it in the deepest basin it has found.

The inner loop is nearly identical to hill climbing; the two differences are that it picks a random successor rather than the best, and that a worsening successor is not rejected outright but accepted with probability $e^{\Delta E/T}$. Simulated annealing was first used for VLSI layout in the early 1980s and is now a staple of factory scheduling and other large-scale optimization.

Random restart and simulated annealing both work with a single current state. Another way to escape a local optimum is to keep several states at once and let them share what they learn — and once you allow states to combine, you have the door to genetic algorithms and, past the discrete world, to the calculus of continuous optimization. This continues in Population and Continuous Search.