4.10 Local search and optimisation

What this is and why it exists

The problem changes shape here. Until now you wanted the path; now you want only the final state, and the route there is nobody's business. That single change lets you throw away the search tree and keep one current state, which is what makes these methods usable on state spaces far too large to enumerate — the ones where everything in the previous topics is hopeless. Hill climbing fails in three specific ways, and each of the other three methods is an answer to those failures.

The vocabulary

• Objective function — the number measuring how good a state is.
• State-space landscape — the picture of all states with height given by that number.
• Local maximum — a peak with no better neighbour, lower than the best peak.
• Ridge — a narrow rising region whose sides all slope down.
• Plateau — a flat region where no neighbour is better or worse.
• Annealing schedule — how the willingness to accept worse states falls over time.
• Beam — a fixed number of states carried forward together.
• Population, fitness, selection, crossover, mutation — the vocabulary of the evolutionary method.

The mental model

Some problems do not care how you got there. Arranging eight queens so none attacks another, assigning shifts to staff, laying out components on a board, choosing which items go in a container: what you deliver is the arrangement, and the sequence of edits that produced it is of no interest. Once the path is irrelevant, you need not remember it — no fringe, no tree, no visited set. The algorithm holds one current state, or a few, and its memory cost is constant regardless of how large the space is. That is what makes these methods applicable where the space has more states than there are atoms available to count them.

Picture it as a landscape. Each state is a point on a surface, and its height is the objective function's value. The search is a walker on that surface trying to reach high ground while only ever able to see the ground immediately around it. Every method here is a different rule for where to step.

Getting the objective function right matters more than the search method, and this is the part people skip. It has to give a useful gradient — a landscape that is flat everywhere except at the goal gives the walker nothing to climb, and no algorithm can help. For the queens problem, "is this arrangement valid" is a terrible objective because almost every state scores the same; "how many pairs of queens attack each other" is a good one, because it improves gradually and points the way down. Spend your effort here first.

Hill climbing steps to the best neighbour and stops when none is better. It is short to write, uses almost no memory, and works surprisingly well. It fails in exactly three ways, and naming which one you are in tells you what to do.

A local maximum is a peak where every neighbour is lower and the global peak is elsewhere. The walker is stuck: it can only see downhill, and it will not go there.

A ridge is a narrow region rising diagonally, where every single step available goes down even though the ridge itself climbs. The walker sees only its immediate neighbours and every one of them is worse, so it stops on a slope. This is the one people find least intuitive and it is common in problems where the useful move is a combination of two changes and each change alone is bad.

A plateau is a flat region where nothing is better and nothing is worse. The walker has no reason to prefer any direction and wanders or halts. A shoulder — a plateau with a rising exit somewhere — is worth escaping, and a true flat maximum is not, and from inside they look identical.

Two cheap partial repairs: allow sideways moves so plateaux can be crossed, with a limit so a flat maximum does not loop forever; and restart from a random state repeatedly, keeping the best result, which converts a method that gets stuck into one that succeeds with high probability given enough attempts.

Simulated annealing answers the local maximum properly, by sometimes stepping down on purpose. Pick a random neighbour. If it is better, take it. If it is worse, take it anyway with a probability that falls as the move gets worse, and falls as the run progresses according to a schedule. Early on the walker moves almost freely and can leave any peak; late on it accepts almost nothing worse and settles.

The name comes from metallurgy, and the analogy makes the schedule intuitive: heat a metal so its atoms move freely, then cool it slowly enough that they settle into a low-energy, well-ordered arrangement rather than being frozen into whatever disordered state they were in. Cool too fast and you get a poor arrangement; cool slowly and you get a good one, at the cost of time. That is exactly the trade in the schedule, and it is the main thing to tune.

Local beam search answers the "one walker sees too little" problem by keeping several states at once. Generate all the successors of all the states you hold, and keep the best few overall. It is not the same as running several searches independently, and the difference is the point: because the best states overall are kept, effort is concentrated where things look promising, and a state whose successors are all poor is abandoned in favour of one whose successors are good. The number carried is the tuning knob, and the characteristic failure is that all the states crowd into the same region and the diversity that justified keeping several is lost — choosing successors with some randomness rather than strictly by score is the standard fix.

Genetic algorithms add combination to that picture. Keep a population of states. Score each by a fitness function. Select parents with probability related to fitness. Produce children by crossover — taking part of the description from one parent and part from another — and apply occasional random mutation. Repeat.

Crossover is the distinctive ingredient and also the demanding assumption: it only helps if the state representation is arranged so that a useful chunk of one solution combines meaningfully with a useful chunk of another. Where that holds, the method assembles good partial solutions found separately. Where it does not, crossover is a fancy way of producing noise, and the method reduces to a slow random search with extra vocabulary. Ask whether your representation has meaningful parts before choosing this method — that question decides whether it is a good fit far more than any parameter does.

The comparison exercise is what makes these four concrete. Solve the same puzzle — eight queens, with the objective counting attacking pairs — with each method, and count how many states each one evaluated and how often each succeeded. Plain hill climbing succeeds surprisingly often and fails on the rest; hill climbing with random restarts succeeds nearly always at a few times the cost; annealing succeeds with a good schedule and wastes effort with a bad one; the evolutionary method works and generally does more computation for the same result on a problem this size. The lesson is that the simplest method with restarts is a strong baseline, and reaching for the elaborate one without measuring the simple one is the same mistake this curriculum keeps pointing at.

What you should now be able to explain or do

Explain the shift from finding a path to finding a state and what it lets you discard. Read a state-space landscape and write an objective function that gives a usable gradient. Run hill climbing and diagnose local maxima, ridges and plateaux by their symptoms. Apply sideways moves and random restarts, with their limits. Describe simulated annealing and explain why accepting a worse move works, using the cooling analogy. Run local beam search, say how it differs from independent searches, and name its failure. Apply the evolutionary method and state the assumption crossover requires. Compare all four on the same problem by cost and success rate.

Check yourself