Local Search
Forget the path, just keep improving. When you only care about the final answer, hill climbing and simulated annealing search by climbing a landscape of solutions.
Every search so far cared about the route: the sequence of steps from start to goal. But for many real problems the route does not matter at all. If you are arranging exam timetables or placing components on a chip, nobody cares how you got to the answer, only that the final arrangement is good. Local search throws away the path entirely. It holds a single candidate solution and keeps tweaking it, trying to make it better and better. It is simple, memory-light, and surprisingly powerful, as long as you understand its one big weakness.
A different kind of problem
Some problems are about finding a path, like getting from one city to another. Others are about finding a good state, where the steps taken to reach it are irrelevant. These are optimisation problems, and they are everywhere: scheduling, layout, configuration, timetabling, and packing.
For these, the path-based searches from earlier weeks are overkill and often impossible, because the number of states is astronomical and there is no meaningful start-to-goal route. Local search takes a completely different approach: keep just one candidate solution in hand, look at small changes to it, and move to a better one. Repeat until you cannot improve. No frontier, no tree, almost no memory.
The landscape metaphor
The way to picture local search is as a landscape. Imagine every possible solution laid out along the ground, and the height at each point is how good that solution is, measured by an objective function. Good solutions are hills, bad ones are valleys.
- The global maximum is the highest peak: the best solution overall.
- A local maximum is a smaller hill: better than everything nearby, but not the best overall.
- A plateau is a flat region where neighbours are all equally good, giving no hint which way to go.
With this picture, local search becomes simple to describe: you are a hiker in fog who can only see the ground right around your feet, trying to reach the highest point. That limited view is the whole story of the topic.
Hill climbing
Hill climbing is the simplest local search, and it does exactly what the name says. Look at the neighbours of your current solution, move to the best one that is better than where you are, and repeat. Stop when no neighbour is any better.
It is fast, needs almost no memory, and often works well. But look closely at step 4: it stops the moment nothing nearby is better. That sounds reasonable, and it is exactly where the trouble starts.
Where hill climbing gets stuck
Because hill climbing only walks uphill, it stops at the top of whatever hill it happens to be on, even if that hill is tiny. Three landscape features trap it:
| Trap | What happens |
|---|---|
| Local maximum | All neighbours are lower, so it stops, even though a taller peak exists elsewhere |
| Plateau | Neighbours are all equal, so it has no direction to move and stalls |
| Ridge | The only way up is a sequence of moves that individually look sideways or down, so it cannot follow the crest |
Two simple fixes help. Random-restart hill climbing runs the climb many times from different random starts and keeps the best result, betting that one start lands near the global peak. Allowing a few sideways moves across plateaus can also help it escape flat regions. But the more elegant fix is to let the search occasionally move downhill on purpose.
Simulated annealing
Simulated annealing is hill climbing with a clever twist borrowed from metallurgy. When metal is cooled slowly from hot to cold, its atoms settle into a strong, low-energy arrangement. The algorithm imitates this: it starts hot and cools down over time.
The key idea is that it sometimes accepts a worse move, and how often depends on a temperature that falls as the search runs:
- A better neighbour is always accepted, just like hill climbing.
- A worse neighbour is sometimes accepted, with a probability that is higher when the temperature is high and when the move is only slightly worse.
- The temperature starts high (lots of random exploration, even downhill) and slowly drops (behaving more and more like plain hill climbing).
Early on, the willingness to go downhill lets the search jump out of small local maxima and roam the landscape. As it cools, it settles into the best region it has found and climbs to its peak. Done right, it reliably escapes the traps that stop hill climbing dead.
Climb the landscape yourself
Here is the whole idea in one picture. The curve is a landscape of solutions, taller is better, and the marker is the current solution starting near a small local hill on the left. Run hill climbing and watch it climb the nearest peak and stop, trapped. Then switch to simulated annealing, set the starting temperature, and watch it wander over the low ground and find the tall global peak on the right.
Taller ground is a better solution. The marker is the current solution; the goal is the highest peak.
The optimisation family
Local search is the first member of a family of optimisation methods you will meet over the next two weeks. They all keep improving candidate solutions rather than building paths, and they differ in how they escape local maxima.
| Method | Holds | Escapes local maxima by |
|---|---|---|
| Hill climbing (this week) | One solution | It does not, that is its weakness |
| Simulated annealing (this week) | One solution | Occasionally accepting worse moves while hot |
| Evolutionary algorithms (week 6) | A population | Mutation and recombining many solutions |
| Swarm intelligence (week 7) | A population | Sharing information across many agents |
Seen this way, next week's genetic algorithms are the natural next step: if one climber gets stuck, run a whole population of them and let them share and combine what they find.
Key points and practice
- Local search suits optimisation problems where only the final state matters, not the path.
- It keeps one solution and moves to better neighbours, using almost no memory.
- Hill climbing only moves uphill and gets stuck at a local maximum, plateau, or ridge.
- Random restart and sideways moves help; the elegant fix is to allow downhill moves.
- Simulated annealing accepts worse moves with a probability that falls as the temperature cools, escaping local maxima.
- Hot means explore, cold means exploit.
Local search keeps only the current state and does not record the path taken to reach it, so it cannot report a route. That is fine for optimisation problems, where only the quality of the final state matters and the sequence of steps is irrelevant. For problems that need the actual path from start to goal, a path-based search is required instead.
Hill climbing only ever moves to a better neighbour and never downhill, so it stops as soon as it reaches the top of any hill. If that hill is a local maximum rather than the global maximum, it returns a suboptimal answer, and it can also stall on plateaus and ridges. The problem can be reduced with random-restart hill climbing, running the search from many random starting points and keeping the best result, which raises the chance that one run reaches the global peak.
Simulated annealing sometimes accepts a worse move, which lets it step down off a small hill and cross to a better region rather than getting trapped. The probability of accepting a worse move depends on the temperature: when the temperature is high the search explores freely and often moves downhill, and as the temperature cools this becomes rarer until the search behaves like plain hill climbing and settles on a peak. Starting hot and cooling slowly lets it explore first and refine later.
