Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 (4/3)n(4/3)^n 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 8×7=568\times7=56 neighbors (move one queen within its column) and ff 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.

DerivationThe cost of random restarts
  1. E[cost]=csucc+1−pp cfail\E[\text{cost}]=c_{\text{succ}}+\frac{1-p}{p}\,c_{\text{fail}}

    Run independent restarts, each succeeding with probability pp. The number of runs is geometric with mean 1/p1/p, so on average (1−p)/p(1-p)/p runs fail before the one that succeeds:

  2. 4+0.860.14⋅3≈4+18.4≈22 steps4+\frac{0.86}{0.14}\cdot3\approx4+18.4\approx22\ \text{steps}

    Plain hill climbing on 8-queens, p=0.14p=0.14:

  3. 21+0.060.94⋅64≈21+4.1≈25 steps21+\frac{0.06}{0.94}\cdot64\approx21+4.1\approx25\ \text{steps}

    With up to 100 sideways moves, p=0.94p=0.94: far fewer restarts but longer runs, and a similar total:

  4. (1−p)r≤0.01  ⟺  r≥ln⁡0.01ln⁡(1−p)≈30.5(1-p)^r\le0.01\iff r\ge\frac{\ln0.01}{\ln(1-p)}\approx30.5

    Failure decays geometrically: rr restarts all fail with probability (1−p)r(1-p)^r, so 99% success takes about 31 restarts when p=0.14p=0.14.

Predict before you look

Each hill-climbing run from a random start succeeds with probability p=0.2p=0.2. 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 1/p=51/p=5: four failures on average, then the success. Rare successes are affordable when each run is cheap.

Min-conflicts and WalkSAT

text
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 failure

Min-conflicts (Minton, Johnston, Philips & Laird, 1992), used to schedule observations for the Hubble Space Telescope. On nn-queens, after a greedy initial placement, the number of repairs is roughly independent of nn: 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 pp 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

DerivationProof sketch for 3-SAT
  1. Pr⁡[J→J−1] ≥ 13,Pr⁡[J→J+1] ≤ 23\Pr[J\to J-1]\ \ge\ \tfrac13,\qquad\Pr[J\to J+1]\ \le\ \tfrac23

    Fix a satisfying assignment α∗\alpha^* and let JJ be the Hamming distance from the current assignment to it. A falsified clause contains a variable on which the current assignment disagrees with α∗\alpha^*, because α∗\alpha^* satisfies the clause. Flipping one of its 3 variables at random therefore lowers JJ with probability at least 1/31/3, and otherwise raises it by at most 1:

  2. Pr⁡[hit 0∣J0=j] ≳ (3jj)(13)2j(23)j≈(274⋅19⋅23)j=(12)j\Pr[\text{hit } 0\mid J_0=j]\ \gtrsim\ \binom{3j}{j}\Big(\tfrac13\Big)^{2j}\Big(\tfrac23\Big)^{j}\approx\Big(\tfrac{27}{4}\cdot\tfrac19\cdot\tfrac23\Big)^{j}=\Big(\tfrac12\Big)^{j}

    From distance jj, one way to hit 0 within 3j3j steps is jj steps up and 2j2j steps down in some order. By Stirling's formula (3jj)≈(27/4)j\binom{3j}{j}\approx(27/4)^j up to polynomial factors:

  3. ∑j=0n(nj)2−n 2−j=2−n(1+12)n=(34)n\sum_{j=0}^{n}\binom{n}{j}2^{-n}\,2^{-j}=2^{-n}\Big(1+\tfrac12\Big)^{n}=\Big(\tfrac34\Big)^{n}

    A uniformly random start has J0∼Bin(n,12)J_0\sim\mathrm{Bin}(n,\tfrac12), so by the binomial theorem one trial succeeds with probability, up to polynomial factors:

  4. E[trials]=O(poly(n) (4/3)n)\E[\text{trials}]=\order{\mathrm{poly}(n)\,(4/3)^n}

    So about (4/3)n≈1.334n(4/3)^n\approx1.334^n trials suffice in expectation, each of polynomial cost, against 2n2^n for brute force. For kk-SAT the per-step probability is 1/k1/k, which gives (2−2/k)n(2-2/k)^n.

Check your understanding

Run Schöning's walk on 4-SAT, where a random flip in a falsified clause fixes a disagreement with probability at least 1/41/4. What is the base of its exponential running time?

  1. (4/3)n(4/3)^n
  2. (3/2)n(3/2)^n
  3. (5/4)n(5/4)^n
  4. 2n2^n
Show the answer

B. (3/2)n(3/2)^n

The general bound is (2−2/k)n(2-2/k)^n, which for k=4k=4 is (3/2)n(3/2)^n. Wider clauses make wrong-way steps likelier, and the base approaches 2 as kk 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 TT it proposes a random neighbor s′s' and, with Δ=f(s′)−f(s)\Delta=f(s')-f(s), accepts it with the Metropolis probability min⁡{1,e−Δ/T}\min\{1,e^{-\Delta/T}\}: improvements always, deteriorations with a probability that shrinks as Δ\Delta grows or TT falls. At fixed TT this is a Markov chain, the same construction that MCMC uses for sampling.

DerivationProof of (a): detailed balance
  1. P(s→s′)=1r e−(f(s′)−f(s))/T,P(s′→s)=1rP(s\to s')=\frac1r\,e^{-(f(s')-f(s))/T},\qquad P(s'\to s)=\frac1r

    Let s,s′s,s' be neighbors with f(s′)≥f(s)f(s')\ge f(s), and let every state have rr neighbors. Then:

  2. πT(s) P(s→s′)=e−f(s)/TZT⋅e−(f(s′)−f(s))/Tr=e−f(s′)/TZT r=πT(s′) P(s′→s)\pi_T(s)\,P(s\to s')=\frac{e^{-f(s)/T}}{Z_T}\cdot\frac{e^{-(f(s')-f(s))/T}}{r}=\frac{e^{-f(s')/T}}{Z_T\,r}=\pi_T(s')\,P(s'\to s)

    Check detailed balance for πT(s)∝e−f(s)/T\pi_T(s)\propto e^{-f(s)/T}:

  3. πT(s⋆)πT(s)=e(f(s)−f(s⋆))/T →T→0 ∞\frac{\pi_T(s^\star)}{\pi_T(s)}=e^{(f(s)-f(s^\star))/T}\ \xrightarrow[T\to0]{}\ \infty

    Detailed balance implies stationarity, and connectivity makes πT\pi_T the unique stationary distribution (rejected moves supply self-loops, which rule out periodicity). For a global minimum s⋆s^\star and any costlier ss:

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 Tt=c/ln⁡(t+1)T_t=c/\ln(t+1), reaching temperature TT takes t≈ec/Tt\approx e^{c/T} 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 T←0.95 TT\leftarrow0.95\,T, 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 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,…1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,\dots time units has expected cost O(ℓlog⁡ℓ)\order{\ell\log\ell}, where ℓ\ell 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 pp into expected cost csucc+1−pp cfailc_{\text{succ}}+\frac{1-p}{p}\,c_{\text{fail}}; 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 O(poly(n) (4/3)n)\order{\mathrm{poly}(n)\,(4/3)^n} 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.

Question 1

At temperature T=2T=2, simulated annealing proposes a move that raises the cost by Δ=2\Delta=2. With what probability is it accepted?

  1. e−2≈0.14e^{-2}\approx0.14
  2. 00: worse moves are never accepted
  3. e−1≈0.37e^{-1}\approx0.37
  4. 1/21/2
Show the answer

C. e−1≈0.37e^{-1}\approx0.37

The Metropolis rule accepts a deterioration with probability e−Δ/T=e−2/2=e−1≈0.37e^{-\Delta/T}=e^{-2/2}=e^{-1}\approx0.37.

Question 2

What does the no-free-lunch theorem for optimization imply?

  1. Simulated annealing is never better than random search
  2. 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
  3. Local search cannot solve NP-hard problems
  4. 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.

Question 3

Why does Schöning's algorithm restart from a fresh random assignment after 3n3n steps instead of walking on?

  1. 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
  2. Because the formula changes after 3n3n steps
  3. Because restarts make the algorithm complete
  4. Because 3n3n 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 α∗\alpha^* with probability up to 2/32/3, so long walks rarely help. A short walk succeeds with probability about (3/4)n(3/4)^n, mostly when the random start happens to be close, and restarting renews that chance.

Question 4

A hill climber succeeds with probability p=0.25p=0.25 per run; successful runs take 8 steps, failed ones 4. What is the expected total cost with random restarts?

  1. 20 steps
  2. 32 steps
  3. 12 steps
  4. 16 steps
Show the answer

A. 20 steps

csucc+1−pp cfail=8+3⋅4=20c_{\text{succ}}+\frac{1-p}{p}\,c_{\text{fail}}=8+3\cdot4=20: 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).