Local search and optimization

Intermediate

Introduction

For many problems the path does not matter, only the result: a timetable with no clashes, a delivery route that is as short as possible, eight queens on a board that do not attack each other. The space of possible answers is far too large to search systematically. Local search keeps one candidate and repeatedly improves it with small changes. It uses almost no memory and often finds very good answers quickly.

How it works

Local search needs three things:

  • a state: one complete candidate answer, such as one queen in each row;
  • neighbours: the states one small change away, such as moving one queen to another column of its row;
  • an objective function that scores a state, such as the number of pairs of queens that attack each other (to be made 0).

Hill climbing (here, hill descending) moves to the best neighbour as long as that improves the score. In steepest-ascent hill climbing, every neighbour is scored and the best is taken; the search stops when no neighbour is better.

It stops for one of three reasons: it found a global optimum (a real solution); it reached a local optimum, a state better than all its neighbours but not a solution; or it is on a plateau, where neighbours are equally good. For 8 queens from a random start, steepest hill climbing gets stuck most of the time.

Two cheap fixes:

  • Random restarts: run again from a new random state. If one run succeeds with probability p, about 1/p runs are needed.
  • Simulated annealing: pick a random neighbour; always accept it if it is better, and accept a worse one with probability e^(−Δ/T), where Δ is how much worse it is and T is a temperature that falls slowly. Early on, the search wanders and escapes local optima; later, it settles down.

The travelling-salesman problem is a classic use: a state is a tour, and the 2-opt neighbour reverses a stretch of the tour, which removes two crossing roads.

Syntax

while True:
    best = min(neighbours(state), key=score)
    if score(best) >= score(state):
        break               # local optimum (or solution)
    state = best

Example

import random


def attacking_pairs(cols):
    n = len(cols)
    return sum(
        1
        for a in range(n)
        for b in range(a + 1, n)
        if cols[a] == cols[b] or abs(cols[a] - cols[b]) == b - a
    )


def hill_climb(cols):
    steps = 0
    while True:
        current = attacking_pairs(cols)
        best, move = current, None
        for row in range(len(cols)):
            for col in range(len(cols)):
                if col != cols[row]:
                    score = attacking_pairs(cols[:row] + [col] + cols[row + 1:])
                    if score < best:
                        best, move = score, (row, col)
        if move is None:
            return current, steps
        cols[move[0]] = move[1]
        steps += 1


random.seed(2026)
n = 8
for attempt in range(1, 51):
    cols = [random.randrange(n) for _ in range(n)]
    start = attacking_pairs(cols)
    left, steps = hill_climb(cols)
    if left:
        print(f"try {attempt}: {start} attacking pairs -> stuck at {left} after {steps} steps")
    else:
        print(f"try {attempt}: {start} attacking pairs -> solved after {steps} steps")
        break
for col in cols:
    print(" ".join("Q" if c == col else "." for c in range(n)))
Open in compiler

Line by line

  1. A state is a list cols: the queen in row r stands in column cols[r].
  2. attacking_pairs counts pairs in the same column or on the same diagonal; 0 means solved.
  3. hill_climb tries every move of one queen within its row and takes the best one, until nothing improves.
  4. With a fixed random seed, the program tries random starting boards until a climb ends with no attacking pairs.
  5. The failed tries stop at local optima with only one or two attacking pairs left: very close, but no single move fixes them.

Expected result

try 1: 7 attacking pairs -> stuck at 2 after 3 steps
try 2: 8 attacking pairs -> stuck at 1 after 4 steps
try 3: 7 attacking pairs -> solved after 5 steps
. . . . . Q . .
. . . Q . . . .
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .

In the real world

Local search schedules exams and sports leagues, places components on chips, routes delivery vans and tunes the settings of machine-learning models. Simulated annealing was first used for chip layout. Training a neural network with gradient descent is also local search, moving the weights a little downhill at each step.

Common mistakes

  • Treating the first local optimum as the answer without checking whether the score is the real target.
  • Choosing neighbours that change too much or too little, so the search jumps randomly or crawls.
  • Cooling too fast in simulated annealing, which turns it into plain hill climbing.
  • Forgetting to seed the random generator when results must be reproducible.

Best practices

  • Measure how often a single climb succeeds before deciding how many restarts to allow.
  • Keep the best state ever seen, not just the current one.
  • Make the objective function quick to compute, since it is called for every neighbour.

Summary

Local search keeps one state and moves to better neighbours. Hill climbing is fast but stops at local optima and plateaus; random restarts and simulated annealing escape them. It suits problems where only the final configuration matters, such as N-queens, scheduling and the travelling-salesman problem.

Quick check

1. What does local search keep in memory?
2. What is a local optimum?
3. How does simulated annealing escape local optima?
4. What does a 2-opt move do to a travelling-salesman tour?

Key takeaways

  • Local search uses very little memory and works on huge state spaces.
  • Hill climbing gets stuck in local optima; restarts and annealing are cheap ways out.
  • A good neighbourhood and objective function matter more than the algorithm.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.