AI AI-01.05
Local search and optimization
Hill climbing, local maxima and plateaus, simulated annealing, genetic algorithms, and beam search, the same idea behind LLM decoding.
The big idea
The searches so far care about the path: the sequence of turns from Ashford to Kingsport. Many problems only care about the final state. A delivery van has 30 stops and you want the shortest loop through them. Nobody needs to know which drafts of the route you tried first; you need a good route. A timetable, a chip layout, the weights of a neural network: same story.
For those problems there is a simpler and far more memory-friendly approach. Local searchOptimization that keeps one current solution (or a few) and repeatedly moves to a neighbouring solution, without remembering the paths explored. keeps a single complete solution, scores it, and repeatedly tries small changes, keeping the ones that help. It stores almost nothing, so it works on problems with more states than there are atoms in the universe.
Picture climbing a mountain in thick fog with an altimeter. You cannot see the summit. You can feel which direction goes up from where you stand, so you step that way, again and again. Most of the time you reach a peak. Whether it is the peak is another question, and the rest of the lesson is about that question.
How it works
Step 1: States, neighbours and a score
Local search needs three things:
- A complete solution as the state. For the delivery van, a tour that visits every stop once.
- A neighbourhoodThe set of solutions reachable from the current one by one small change, such as swapping two items or reversing a section of a route.: the solutions one small change away. For tours, a common move is to reverse a stretch of the route, which replaces two roads with two others (a "2-opt" move).
- An objective functionThe function local search tries to maximize or minimize, such as tour length, profit or the number of satisfied constraints. to maximize or minimize, such as total tour length.
Plotting the objective over all states gives a landscapeThe objective value plotted over all states, with neighbouring states next to each other. Peaks are good solutions for maximization.: hills where solutions are good, valleys where they are bad.
Step 2: Hill climbing, and where it gets stuck
Hill climbingLocal search that always moves to a better neighbour and stops when no neighbour is better. Also called greedy local search. is the fog walk: look at the neighbours, move to a better one, stop when none is better. It is fast and often good, but it stops at the first peak it reaches.
Three features of a landscape defeat hill climbing:
- A local maximumA state better than all of its neighbours but worse than the best state overall.: better than every neighbour, worse than the best solution overall.
- A plateau: a flat region where every neighbour scores the same, so there is no uphill direction.
- A ridge: a narrow rising crest where every single move steps off the side, even though the crest climbs.
Cheap fixes help. Random restarts run hill climbing from many random starting points and keep the best result; with enough restarts you eventually start on the slope of the global peak. Sideways moves allow a limited number of equal-score moves to cross plateaus. Stochastic hill climbing picks a random uphill neighbour instead of the steepest, which adds variety.
Step 3: Simulated annealing
Simulated annealingLocal search that always accepts improving moves and accepts a worsening move with probability exp(-delta / T), where the temperature T falls over time. takes its name from metalwork: heat metal, then cool it slowly, and its atoms settle into a strong, low-energy arrangement. The algorithm picks a random neighbour. If it is better, take it. If it is worse by , take it anyway with probability
where is a temperature that starts high and falls a little after every move. With a 30-stop tour and , a move that makes the tour 10 units longer is accepted with probability . Later, at , the same move is accepted with probability . Early on the search roams freely across the landscape, climbing out of local peaks; by the end it is plain hill climbing, polishing whatever region it settled in. Cool slowly enough and it finds the global optimum with probability approaching 1, though "slowly enough" can mean impractically slowly.
Try it
Each move reverses a stretch of the tour, and the run makes 100,000 moves while the temperature cools to a thousandth of where it started. Try this on map A:
- Leave the start temperature at 0 and press Run. This is pure hill climbing. The length drops fast from 4501, then freezes at 1444: a local optimum, where no single reversal helps.
- Set the temperature to 80 and run again. The length wanders and even rises at first (the search accepts about 2,700 worse moves), then settles as it cools, at 1372: shorter than hill climbing found.
- Set it to 5. Too cold to escape much: this run ends at 1482, worse than hill climbing. Now try maps B and C with 0 and then 20 to 80: annealing beats hill climbing on each one.
Going deeper
Genetic algorithms
A genetic algorithmPopulation-based search that evolves candidate solutions using selection of the fittest, crossover between pairs, and random mutation. keeps a whole population of solutions instead of one. Each generation:
- Selection: score every solution (its "fitness") and pick parents, favouring the fitter ones.
- Crossover: combine two parents into a child, for example the first half of one and the second half of the other.
- Mutation: change a small random part of the child, so the population keeps exploring.
Crossover is the distinctive part. It helps when good solutions are built from good independent pieces (a good morning schedule and a good afternoon schedule from two different parents). For tours, naive crossover produces invalid children that visit some cities twice, so special operators are needed. Genetic algorithms and their relatives are used for design problems such as antenna shapes and schedules, but they need many evaluations and careful tuning.
Beam search, and how LLMs pick words
Beam searchSearch that keeps only the k best partial solutions at each step, expanding all of them and again keeping the best k. With k = 1 it is greedy. keeps the best states (the "beam"), generates all their neighbours, and keeps the best of those. With it is greedy; with unlimited it is breadth-first search. In between, it trades memory for a wider view.
Language models generate text one token at a time, and choosing the most likely next token each time (greedy decoding) can miss a sentence that is more likely overall. Beam search keeps several partial sentences alive:
import math
# Toy "language model": P(next word | words so far)
NEXT = {
(): {"the": 0.5, "a": 0.4, "my": 0.1},
("the",): {"cat": 0.35, "dog": 0.35, "sun": 0.3},
("a",): {"cat": 0.9, "dog": 0.1},
("my",): {"cat": 0.5, "dog": 0.5},
}
for first in ("the", "a", "my"):
for second in ("cat", "dog", "sun"):
NEXT[(first, second)] = {"sat": 0.6, "ran": 0.4}
def done(seq):
return len(seq) == 3 # every sentence is three words
def beam_search(width):
beam = [((), 0.0)] # (words, log probability)
while not all(done(s) for s, _ in beam):
candidates = []
for seq, lp in beam:
if done(seq):
candidates.append((seq, lp))
continue
for word, p in NEXT[seq].items():
candidates.append((seq + (word,), lp + math.log(p)))
# keep only the best `width` partial sentences
beam = sorted(candidates, key=lambda c: -c[1])[:width]
return beam[0]
for width in (1, 2, 3):
seq, lp = beam_search(width)
label = "greedy" if width == 1 else f"beam {width}"
print(f"{label:7}: {' '.join(seq):14} p = {math.exp(lp):.3f}")Output
greedy : the cat sat p = 0.105
beam 2 : a cat sat p = 0.216
beam 3 : a cat sat p = 0.216 Greedy takes "the" (0.5) because it is the best first word, but then every continuation is mediocre: 0.5 x 0.35 x 0.6 = 0.105. A beam of width 2 keeps "a" alive too, and "a cat sat" scores 0.4 x 0.9 x 0.6 = 0.216, twice as likely. Beam search is common in translation and speech recognition. For open-ended chat, models usually sample instead, because the most likely text tends to be bland and repetitive; see Decoding and sampling .
Continuous spaces
When states are real numbers, the neighbours are infinitely many and "uphill" is a direction given by the gradient. Following it is gradient descent (or ascent), the local search that trains every neural network: Gradient descent, the engine of ML . The same problems appear there: local minima, flat plateaus, and narrow ravines, and the same remedies (randomness, momentum, restarts) carry over.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Hill climbing (plus random restarts) | Smooth landscapes, or when each evaluation is cheap and restarts are easy | Rugged landscapes: stops at the nearest peak |
| Simulated annealing | Rugged landscapes with one solution at a time and a tunable time budget | Needs a cooling schedule tuned per problem; slow if run carefully |
| Genetic algorithm | Solutions built from separable good parts; no gradient available | Many evaluations; crossover can create invalid solutions |
| Beam search | Building a solution step by step, as in decoding text, where greedy misses better sequences | Memory and compute grow with the beam width; still not guaranteed optimal |
Common mistakes
- Treating the first peak hill climbing finds as the best answer. Always compare against a few restarts.
- Cooling simulated annealing too fast. It turns into hill climbing before it has explored.
- Starting the temperature far too low or high for the problem's scale. should be comparable to typical worsening moves, so pick it from a few sample values.
- Choosing a neighbourhood that is too small. A move that cannot untangle crossing roads will leave crossings in every result.
- Calling beam search optimal. It prunes, so the best sequence can fall out of the beam early.
In the wild
Where you will see this: delivery and field-service route planners, airline crew and school timetabling, and chip placement tools all rely on local search, often simulated annealing or tabu search, because exact methods do not scale to their size. Speech recognizers and machine translation systems have long used beam search to pick output sentences. And every neural network is trained by a local search on a continuous landscape: gradient descent.
Check yourself
-
Why does local search use so little memory?
Show answer
B. It keeps one current solution (or a few) and not the paths explored Local search remembers only its current state, or a small population or beam, so memory does not grow with the size of the space.
-
Hill climbing stops and every neighbour scores lower, but the solution is clearly not the best. Where is it?
Show answer
C. At a local maximum Better than every neighbour but not best overall is the definition of a local maximum. On a plateau the neighbours would score the same.
-
In simulated annealing at temperature T = 10, a move worsens the score by 10. What is the chance of accepting it?
Show answer
B. About 0.37 e^(-10/10) = e^(-1), about 0.37. At a lower temperature the same move would be accepted far less often.
-
What happens to simulated annealing if the temperature is held at 0 from the start?
Show answer
B. It becomes hill climbing With T = 0, worse moves are never accepted, so only improvements are taken: hill climbing.
-
Greedy decoding picks the most likely next word each time. Why can beam search find a more likely sentence?
Show answer
B. It keeps several partial sentences, so a weaker first word with strong continuations survives The probability of a sentence is the product of all its steps. A slightly worse first word can lead to much better continuations, and only a beam keeps it long enough to find out.
Recap
- Local search keeps a complete solution and improves it by small moves; it suits problems where only the final answer matters.
- Hill climbing is fast but stops at local maxima and stalls on plateaus; random restarts help.
- Simulated annealing accepts worse moves with probability exp(-delta / T), less often as T cools, to escape local peaks.
- Genetic algorithms evolve a population with selection, crossover and mutation.
- Beam search keeps the k best partial solutions; it is how many systems decode the most likely output sequence.