Local Search & Metaheuristics
Hill climbing, simulated annealing and genetic algorithms.
Min-conflicts solves the million-queens problem in about fifty moves after its initial placement, a size at which systematic backtracking would choke. Local search gives up completeness: it keeps one complete assignment and nudges it toward fewer violations. When does that work, how fast, and what can actually be proved about it?
What you’ll learn
- Define neighborhoods, local minima and plateaus, and compute the expected cost of random-restart hill climbing.
- Analyze min-conflicts and WalkSAT, and derive Schöning's bound for 3-SAT.
- Prove that the Metropolis chain behind simulated annealing has the Boltzmann stationary distribution, and state Hajek's cooling theorem.
- State the no-free-lunch and Luby–Sinclair–Zuckerman restart theorems, and say what each does and does not imply.
Landscapes, local minima and restarts
For 8-queens with one queen per column, a state has neighbors (move one queen within its column) and counts attacking pairs. Russell and Norvig report that from random states, steepest-descent hill climbing solves only 14% of instances, taking about 4 steps when it succeeds and 3 when it gets stuck. Allowing up to 100 consecutive sideways moves across plateaus raises the success rate to 94%, at about 21 steps per success and 64 per failure.
Run independent restarts, each succeeding with probability . The number of runs is geometric with mean , so on average runs fail before the one that succeeds:
Plain hill climbing on 8-queens, :
With up to 100 sideways moves, : far fewer restarts but longer runs, and a similar total:
Failure decays geometrically: restarts all fail with probability , so 99% success takes about 31 restarts when .
Each hill-climbing run from a random start succeeds with probability . On average, how many runs do you need, counting the successful one?
Show the answer
5 runs
The number of runs is geometric with mean : four failures on average, then the success. Rare successes are affordable when each run is cheap.
Min-conflicts and WalkSAT
function MIN-CONFLICTS(csp, max_steps) returns a solution or failure
current ← a complete assignment // e.g. greedy: each variable takes a least-conflict value
for i = 1 to max_steps do
if current is a solution then return current
var ← a randomly chosen conflicted variable
value ← a value of var minimizing CONFLICTS(var, value, current) // ties at random
set var = value in current
return failureMin-conflicts (Minton, Johnston, Philips & Laird, 1992), used to schedule observations for the Hubble Space Telescope. On -queens, after a greedy initial placement, the number of repairs is roughly independent of : about 50 on average even for a million queens.
For SAT the same idea, focused on clauses, is WalkSAT (Selman, Kautz & Cohen, 1994). Start from a random assignment and repeat: pick a random falsified clause; with probability flip a random variable in it (a noise step), otherwise flip the variable in it whose flip falsifies the fewest currently satisfied clauses. Focusing on a falsified clause guarantees that every flip repairs something, and the noise steps escape local minima. Like min-conflicts, WalkSAT is incomplete: it never proves unsatisfiability, but it often beats complete solvers on large satisfiable random instances.
A random walk with a guarantee
Fix a satisfying assignment and let be the Hamming distance from the current assignment to it. A falsified clause contains a variable on which the current assignment disagrees with , because satisfies the clause. Flipping one of its 3 variables at random therefore lowers with probability at least , and otherwise raises it by at most 1:
From distance , one way to hit 0 within steps is steps up and steps down in some order. By Stirling's formula up to polynomial factors:
A uniformly random start has , so by the binomial theorem one trial succeeds with probability, up to polynomial factors:
So about trials suffice in expectation, each of polynomial cost, against for brute force. For -SAT the per-step probability is , which gives .
Run Schöning's walk on 4-SAT, where a random flip in a falsified clause fixes a disagreement with probability at least . What is the base of its exponential running time?
Show the answer
B.
The general bound is , which for is . Wider clauses make wrong-way steps likelier, and the base approaches 2 as grows.
Simulated annealing
Hill climbing never moves uphill, so it stalls in the first local minimum. Simulated annealing (Kirkpatrick, Gelatt & Vecchi, 1983; Černý, 1985) sometimes accepts worse moves. At temperature it proposes a random neighbor and, with , accepts it with the Metropolis probability : improvements always, deteriorations with a probability that shrinks as grows or falls. At fixed this is a Markov chain, the same construction that MCMC uses for sampling.
Let be neighbors with , and let every state have neighbors. Then:
Check detailed balance for :
Detailed balance implies stationarity, and connectivity makes the unique stationary distribution (rejected moves supply self-loops, which rule out periodicity). For a global minimum and any costlier :
Think first Hajek's theorem guarantees convergence to a global minimum. Why doesn't that make simulated annealing an efficient algorithm for NP-hard problems?
The guarantee is asymptotic and slow. Under , reaching temperature takes steps, and the time until the chain sits in a global minimum with high probability can be exponential in the problem size, consistent with NP-hardness. In practice people use fast geometric schedules such as , which work well on many problems but void the guarantee.
Populations, free lunches and restarts
Genetic algorithms (Holland, 1975) evolve a population: select fit individuals, recombine pairs by crossover and apply random mutation. Crossover helps when good partial solutions combine; Holland's schema theorem formalizes one version of this, though how much it explains GA performance is contested. Local beam search, evolution strategies such as CMA-ES, and tabu search fill out the toolbox. Each carries an implicit bet about the problem's structure, and the next theorem says why it must.
The theorem does not make heuristics useless: real problems are far from uniformly random functions, and an algorithm wins exactly by matching their structure (smooth landscapes, dense solutions, decomposability). What it rules out is a universally best optimizer, the counterpart of the no-free-lunch theorem for learning.
Randomized search often has heavy-tailed run times: most runs are quick, a few extraordinarily long (Gomes, Selman, Crato & Kautz, 2000). Restarts cut the tail. When the run-time distribution is unknown, Luby, Sinclair and Zuckerman (1993) showed that restarting after time units has expected cost , where is the expected cost of the best fixed cutoff for that distribution, and that no universal strategy does better in the worst case by more than a constant factor. SAT solvers use this Luby sequence.
Key takeaways
- Local search keeps one complete state and moves to neighbors: memory-light and fast, but incomplete, with local minima and plateaus as its enemies.
- Random restarts turn a per-run success probability into expected cost ; sideways moves and noise trade longer runs for fewer restarts.
- Min-conflicts and WalkSAT aim each move at a violated constraint; Schöning's random walk solves 3-SAT in expected time.
- Simulated annealing's Metropolis chain has the Boltzmann stationary distribution; logarithmic cooling reaches global minima (Hajek) but can be exponentially slow.
- No free lunch: averaged over all problems, no optimizer wins, so heuristics succeed by matching structure; Luby restarts handle heavy-tailed run times near-optimally.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
At temperature , simulated annealing proposes a move that raises the cost by . With what probability is it accepted?
- : worse moves are never accepted
Show the answer
C.
The Metropolis rule accepts a deterioration with probability .
What does the no-free-lunch theorem for optimization imply?
- Simulated annealing is never better than random search
- Averaged uniformly over all cost functions on a finite domain, all non-repeating black-box optimizers perform the same, so any advantage comes from matching a problem class's structure
- Local search cannot solve NP-hard problems
- An algorithm that is optimal on one problem class is optimal on all of them
Show the answer
B. Averaged uniformly over all cost functions on a finite domain, all non-repeating black-box optimizers perform the same, so any advantage comes from matching a problem class's structure
The average runs over all functions, most of them patternless. On structured classes some algorithms do far better; the theorem only forbids a universal winner.
Why does Schöning's algorithm restart from a fresh random assignment after steps instead of walking on?
- Because the walk tends to drift away from the solution, so short walks from fresh random starts, some of which land close, give the best success probability per unit of work
- Because the formula changes after steps
- Because restarts make the algorithm complete
- Because steps always suffice to reach a solution
Show the answer
A. Because the walk tends to drift away from the solution, so short walks from fresh random starts, some of which land close, give the best success probability per unit of work
Each step moves away from with probability up to , so long walks rarely help. A short walk succeeds with probability about , mostly when the random start happens to be close, and restarting renews that chance.
A hill climber succeeds with probability per run; successful runs take 8 steps, failed ones 4. What is the expected total cost with random restarts?
- 20 steps
- 32 steps
- 12 steps
- 16 steps
Show the answer
A. 20 steps
: on average three failed runs, then one success.
Further reading
- S. Kirkpatrick, C. D. Gelatt & M. P. Vecchi, "Optimization by simulated annealing," Science 220(4598) (1983), 671–680.
- S. Minton, M. D. Johnston, A. B. Philips & P. Laird, "Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems," Artificial Intelligence 58 (1992), 161–205.
- B. Selman, H. Kautz & B. Cohen, "Noise strategies for improving local search," Proceedings of AAAI-94 (1994).
- U. Schöning, "A probabilistic algorithm for k-SAT and constraint satisfaction problems," Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999).
- H. H. Hoos & T. Stützle, Stochastic Local Search: Foundations and Applications (Morgan Kaufmann, 2004).