I4 · Problem Solving and Reasoning: Classical AI

Local Search and Optimisation

Local search algorithms keep a single current solution, or a small set, and repeatedly move to a neighbouring solution that scores better on an objective function. They do not remember paths, so they use little memory and can tackle huge problems. Hill climbing always moves uphill; simulated annealing sometimes accepts worse moves to escape local optima; genetic algorithms evolve a population of solutions by selection, crossover and mutation.

12 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

A school must timetable 40 teachers, 30 classrooms and 1,200 lessons a week. There are more possible timetables than atoms in the universe. Nobody searches them all; instead, start with any timetable and keep improving it.

Local search algorithms keep a single current solution, or a small set, and repeatedly move to a neighbouring solution that scores better on an objective function. They do not remember paths, so they use little memory and can tackle huge problems. Hill climbing always moves uphill; simulated annealing sometimes accepts worse moves to escape local optima; genetic algorithms evolve a population of solutions by selection, crossover and mutation.

In simple words

Imagine finding the highest point in a hilly region in thick fog. You cannot see far, so you feel the ground and step uphill. You might end on a small hill rather than the tallest peak. Local search methods are clever tricks for not getting stuck on small hills.

Overview

  • Local search keeps one (or a few) current states and moves to neighbouring states, instead of remembering paths.
  • It uses very little memory and works on huge or continuous spaces.
  • An objective function scores each state; the aim is the global maximum or minimum.
  • It can get stuck in local optima, plateaus and ridges.
  • Random restarts and randomness in moves help escape poor regions.
  • Gradient descent in machine learning is a form of local search in continuous space.

Why it matters

Many real problems, such as timetables, delivery routes, chip layouts and factory schedules, care about a good final arrangement, not the path to it, and are far too large for systematic search. Local search finds high-quality solutions in reasonable time.

Key terms

Objective function
The score being maximised or minimised, such as the number of timetable clashes.
Neighbour
A solution reached by a small change, such as swapping two lessons.
Hill climbing
Always moving to the best neighbour if it improves the score.
Local optimum
A solution better than all its neighbours but not the best overall.
Simulated annealing
Accepting some worse moves, less often as a temperature parameter cools.
Genetic algorithm
Evolving a population of solutions through selection, crossover and mutation.

Types

There are several local search algorithms, from simple hill climbing to population-based methods.

1. Hill climbing

Repeatedly moving to the best neighbouring state until no neighbour is better.

  • How it works: It is fast and simple but stops at the first peak it finds, which may be only a local maximum.
  • Example: Improving a timetable by swapping two classes whenever it reduces clashes.
  • When to use it: Use it when a decent solution is needed quickly and the landscape is fairly smooth.

2. Random-restart and stochastic hill climbing

Running hill climbing many times from random starts, or choosing a random improving move instead of the best.

  • How it works: Restarts sample many peaks and keep the best; with enough restarts the global optimum is found with high probability.
  • Example: Solving the 8-queens puzzle: plain hill climbing succeeds about 14% of the time, but restarts almost always succeed.
  • When to use it: Use it as a cheap improvement over plain hill climbing.

3. Simulated annealing

Local search that sometimes accepts worse moves, with a probability that falls over time.

  • How it works: A worse move is accepted with probability e^(−Δ/T); the temperature T starts high (much exploration) and cools slowly, like annealing metal.
  • Example: Designing the layout of components on a microchip to minimise wire length.
  • When to use it: Use it for rugged problems with many local optima when there is time for many iterations.

4. Local beam search

Keeping k states at once and at each step selecting the k best of all their neighbours.

  • How it works: Good states attract more of the search effort, so information is shared between the k searches; stochastic beam search picks randomly by quality.
  • Example: Searching for good molecule designs with 20 candidates kept at each round.
  • When to use it: Use it when several promising regions should be explored in parallel.

5. Continuous optimisation (gradient-based)

Local search in continuous spaces using gradients.

  • How it works: Gradient ascent or descent moves along the slope; line search chooses step sizes; constraints can be handled with penalties.
  • Example: Choosing the locations of three new airports to minimise the total distance from cities.
  • When to use it: Use it whenever the objective is smooth and differentiable, as in training machine-learning models.

Explained in detail

Hill climbing and its traps

Hill climbing is simple: look at the neighbours of the current solution, move to the best one if it is an improvement, and stop when none is. It is fast and often good, but it has three traps. A local optimum is a small peak where every neighbour is worse, though a higher peak exists elsewhere. A plateau is a flat region where neighbours score the same, giving no direction. A ridge is a narrow rising path that single steps cannot follow. Common remedies are random restarts, running hill climbing many times from different random starting points and keeping the best, and allowing sideways moves on plateaus.

Simulated annealing

Annealing is a metalworking process: metal is heated and cooled slowly so its atoms settle into a strong, low-energy structure. Simulated annealing, introduced by Scott Kirkpatrick, Daniel Gelatt and Mario Vecchi in 1983, copies this. It picks a random neighbour; if it is better, it moves; if worse, it may still move with a probability that depends on how much worse it is and on a temperature. At high temperature it explores freely, even moving downhill; as the temperature lowers it becomes more like hill climbing. Cooling slowly enough lets it escape local optima and find excellent solutions, and it has been widely used for chip layout and scheduling.

Genetic algorithms

  • Represent each solution as a string, such as a list of lesson slots.
  • Start with a population of random solutions and score each with a fitness function.
  • Select fitter solutions as parents more often.
  • Crossover combines parts of two parents into children; mutation randomly changes small parts.
  • Repeat for many generations; the population tends to improve.

John Holland developed genetic algorithms in the 1960s and 1970s, inspired by natural evolution. NASA used an evolutionary algorithm to design an unusual, highly effective antenna for its Space Technology 5 satellites, launched in 2006.

Connection to machine learning

Local search ideaMachine-learning counterpart
Hill climbing on a scoreGradient descent on a loss (downhill instead of uphill)
Random restartsTraining several times with different random seeds
Simulated annealing's coolingLearning-rate schedules that shrink the step size
Genetic algorithmsEvolutionary hyperparameter and architecture search

How it works

  1. Define a solution, its neighbours and an objective function.
  2. Start from a random or simple solution.
  3. Repeatedly move to a better neighbour, or by the method's rule.
  4. Use restarts, annealing or a population to avoid local optima.
  5. Stop after a time limit or when no improvement appears; keep the best found.

In code

local_search.py
import math
import random

random.seed(1)
# A bumpy landscape on 0..10: many small hills, the tallest towards the right
f = lambda x: math.sin(3 * x) + 0.4 * math.sin(10 * x) + 0.15 * x

def hill_climb(x, step=0.05):
    while True:
        best = max([x - step, x + step], key=f)
        if f(best) <= f(x):
            return x
        x = best

def anneal(x, temp=2.0, cooling=0.995, steps=3000):
    best = x
    for _ in range(steps):
        cand = min(10, max(0, x + random.uniform(-0.5, 0.5)))
        if f(cand) > f(x) or random.random() < math.exp((f(cand) - f(x)) / temp):
            x = cand
        if f(x) > f(best):
            best = x
        temp *= cooling
    return best

start = 1.0
hc = hill_climb(start)
restarts = max((hill_climb(random.uniform(0, 10)) for _ in range(20)), key=f)
sa = anneal(start)
for name, x in [("hill climbing", hc), ("20 random restarts", restarts), ("simulated annealing", sa)]:
    print(f"{name:>20}: x = {x:.2f}, height = {f(x):.3f}")

Output

       hill climbing: x = 0.75, height = 1.266
  20 random restarts: x = 8.96, height = 2.724
 simulated annealing: x = 4.59, height = 1.998

Try it yourself

Stuck on a small hill

A scheduler improves a school timetable by swapping pairs of lessons.

Match the trap to the fix

Which technique helps with each problem?

  • Stuck on a local optimum
  • A flat plateau with no direction
  • A huge space of possible designs

Common mistakes

  • Trusting a single hill-climbing run as the best answer.
  • Cooling too fast in simulated annealing, turning it into hill climbing.
  • Defining neighbours so small that progress is impossibly slow.

Check yourself

Question 1

1. What is a local optimum?

Question 2

2. Why does simulated annealing accept some worse moves?

Question 3

3. Which machine-learning method is a downhill version of hill climbing?

Summary

  • Local search improves one solution step by step, using little memory.
  • Hill climbing gets stuck; restarts, annealing and genetic algorithms help escape.
  • These ideas reappear in gradient descent and hyperparameter search.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · UC Berkeley CS188: Introduction to Artificial Intelligence