Population and Continuous Search

The companion lesson, Local Search and Optimization, built the state-space landscape and the single-state methods that move across it: hill climbing and the two ways it escapes a local optimum — random restarts and simulated annealing. Both hold exactly one current state. This lesson develops the alternatives that hold several states at once and let them share information, then leaves the discrete world entirely for continuous spaces, where the neighbor set is infinite and calculus takes over from enumeration.

Local beam search

Keeping a single current state in memory is a strong reaction to memory limits. Local beam search relaxes it slightly: instead of one state, it keeps track of $k$ states at once. It begins with $k$ random states; at each step it generates all successors of all $k$, halts if any is a goal, and otherwise selects the $k$ best successors from the pooled list and repeats.

This is not equivalent to running $k$ restarts in parallel. In $k$ random restarts each search is independent; in a beam search the $k$ threads share a single pool of successors, so information passes between them. If one state generates several excellent successors, they crowd out the neighbors of the poorer states, and the beam abandons unpromising regions and concentrates its slots where progress is being made.

The weakness of the plain version is loss of diversity: the $k$ states can quickly collapse into a small region, and the search degenerates into an expensive hill climb. Stochastic beam search addresses this the same way stochastic hill climbing addresses greedy climbing: rather than keeping the best $k$ successors, it keeps $k$ chosen at random, with the probability of picking a successor rising with its value. This preserves spread and resembles natural selection — offspring of a state populate the next generation in proportion to fitness.

Genetic algorithms

A genetic algorithm (GA) is a variant of stochastic beam search in which successors are produced by combining two parent states rather than modifying a single one. Where stochastic beam search is asexual reproduction, a GA is sexual: the analogy to natural selection is the same, but now offspring inherit from two parents.

A GA begins with a population of $k$ randomly generated states, each called an individual and encoded as a string over a finite alphabet. An 8-queens state can be written as eight digits, one per column, each in $\mathrm{1..8}$ giving that column's queen its row. One generation transforms the population through four stages.

The four stages, reading the figure left to right:

1. Fitness. Each individual is scored by a fitness function — the objective function, higher for better states. For 8-queens the natural choice is the number of nonattacking pairs of queens, which is $28$ for a solution. The four states shown score $24,23,20,11$.
2. Selection. Pairs are chosen for reproduction at random, with the probability of being chosen proportional to fitness. The fitter a state, the more offspring it is likely to seed; an individual may be picked twice, or not at all.¹
3. Crossover. For each pair a crossover point is chosen at random along the string. The first child takes the prefix of one parent and the suffix of the other; the second child takes the complementary halves. When the parents differ, crossover can produce a child far from either — large steps early, when the population is diverse, shrinking to small steps late, when individuals resemble each other.
4. Mutation. Each position is independently changed with a small probability, analogous to picking a queen at random and moving it within its column. Mutation injects the diversity that keeps the population from collapsing.

Carry the selection arithmetic through. The four states in the figure score $24,23,20,11$ nonattacking pairs, summing to $78$. Selection probability is fitness over total, so the states are chosen with probability $24/78=31\%$, $23/78=29\%$, $20/78=26\%$, and $11/78=14\%$. The fittest individual is more than twice as likely to reproduce as the weakest, which is why the population drifts toward high fitness across generations without any individual being guaranteed a place. Following one crossover: parents 32752411 and 24748552, cut after position $3$, yield the child 327|48552 — the prefix 327 from the first parent, the suffix 48552 from the second. A subsequent mutation flipping position $5$ from 8 to 1 gives 32748152. In 8-queens terms each digit is a column's queen-row, so crossover recombines whole blocks of queen placements and mutation nudges one queen within its column.

where $\text{Reproduce}(x,y)$ cuts the parents at a random point $c$ and appends the prefix of $x$ to the suffix of $y$:

The distinctive ingredient is crossover, and its value is subtle. It can be shown that if the string's positions are permuted into a random order first, crossover conveys no advantage. The benefit appears only when the encoding places related components adjacently: crossover then combines large blocks of digits that have evolved to do a useful job independently — a schema, a partially specified substring such as 246***** matching every 8-queens state whose first three queens sit in columns 2, 4, 6. If a schema's instances score above average, the schema spreads through the population. Genetic algorithms therefore work best when the representation is engineered so that meaningful sub-solutions map to contiguous blocks; a poorly chosen encoding hands crossover nothing to combine.

Local search in continuous spaces

Every algorithm so far assumes a finite set of successors. Most real environments are continuous: the state is a vector $\mathbf{x}\in {\mathbb{R}}^n$, and the set of neighbors is infinite. Only first-choice hill climbing and simulated annealing carry over unchanged, because they sample successors rather than enumerate them.

Consider siting three airports in Romania to minimize the sum of squared distances from each city to its nearest airport. A state is the six coordinates $(x_1,y_1,x_2,y_2,x_3,y_3)$, and with $C_i$ the set of cities closest to airport $i$, the objective in the neighborhood of the current state is

This is correct only locally: as an airport moves, the assignment $C_i$ of cities can change, so the expression is exact only while the sets $C_i$ stay fixed.

One option is to discretize: allow only moves that shift one coordinate by a fixed $\pm \delta$, turning the six-dimensional problem into twelve discrete successors and handing it back to the algorithms above. The alternative uses calculus: instead of trying a few neighbors and picking the best, compute the direction of steepest uphill from the slope itself, and step that way. The gradient of $f$ is the vector of partial derivatives,

pointing in the direction of steepest ascent with magnitude equal to the slope. Where a closed form exists, a maximum can sometimes be found by solving $\nabla f=0$ directly; here the gradient is only locally correct, so we instead take repeated uphill steps, the continuous analogue of hill climbing:

Choosing the step size $\alpha$ is a subject of its own. Too small and progress is slow; too large and each step overshoots the maximum. Line search doubles $\alpha$ along the current gradient direction until $f$ stops improving, then commits to that point. When the objective is not even differentiable — say its value comes from running a simulation — an empirical gradient estimates each partial by measuring the response to small increments in each coordinate, which amounts to steepest-ascent hill climbing on a discretized space.

Newton's method (Newton–Raphson) uses curvature to pick the step. It is a root-finder, $x\leftarrow x-g(x)/g^{\prime }(x)$, and finding a maximum means finding a zero of the gradient, so $g$ becomes $\nabla f$ and the update takes the matrix form

where ${\mathbf{H}}_f(\mathbf{x})$ is the Hessian of second derivatives, $H_{ij}={\partial }^{2}f/\partial x_i\partial x_j$. Newton's step is a locally quadratic model of $f$ that jumps directly to the model's optimum — fast near a solution, but each step costs the $n^2$ entries of the Hessian and its inversion, which is why high-dimensional practice leans on approximate versions.

These are the same tools that power the deep-learning optimization lessons, applied there to a loss over millions of parameters rather than six airport coordinates.² The same warning carries over: continuous spaces suffer from local maxima, ridges, and plateaus exactly as discrete ones do, and random restarts and simulated annealing remain the standard remedies. The exception is convex optimization, where the objective has no local optima distinct from the global one, so gradient methods are guaranteed to reach it — the reason so much of machine learning is engineered to be convex when it can be.

Local search in the wild

The algorithms in these lessons look small on 8-queens, but their descendants handle large industrial and scientific problems.

Simulated annealing was introduced by Kirkpatrick, Gelatt, and Vecchi (1983, Science), who borrowed the acceptance rule directly from the Metropolis algorithm of statistical physics (Metropolis et al., 1953). Their target was VLSI placement and wiring; the method is now a standard baseline for scheduling, protein-structure prediction, and any combinatorial objective with a rugged landscape. The theoretical guarantee — convergence to a global optimum as $T\to 0$ slowly enough — traces to Geman and Geman (1984), who showed a logarithmic cooling schedule $T_t=c/\log t$ suffices, though that rate is far too slow for practice, where geometric schedules $T_{t+1}=\alpha T_t$ with $\alpha$ near $0.95$ are used instead.

Local search on satisfiability is where these ideas reshaped an entire subfield. Selman, Levesque, and Mitchell's GSAT (1992, AAAI) and the WalkSAT family (Selman, Kautz, and Cohen, 1994) solve Boolean satisfiability by hill-climbing on the number of satisfied clauses, escaping local minima by occasionally flipping a variable in a random unsatisfied clause rather than the greedy-best variable. This random walk component made incomplete SAT solvers able to attack instances with hundreds of thousands of variables that systematic backtracking could not touch, and the same random-restart-plus-noise recipe underlies much of modern constraint satisfaction. The min-conflicts heuristic (Minton, Johnston, Philips, and Laird, 1992, Artificial Intelligence) is the CSP analogue: repair a complete assignment by moving the variable involved in the most conflicts to its least-conflicting value. It solves million-queens instances in seconds — the same phenomenon this lesson notes for random restart, made systematic.

Tabu search (Glover, 1989; Glover and Laguna, 1997) augments hill climbing with a short memory: a tabu list of the last $k$ visited states that may not be revisited. Forbidding immediate backtracking lets the search step through a local optimum and keep going, escaping traps that stall a memoryless climber, and it is a mainstay of operations-research optimization.

Evolution strategies and their modern form generalize genetic algorithms to continuous vectors. Rechenberg (1965) introduced evolution strategies for airfoil design; the current standard, CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation), adapts a full covariance matrix over the search distribution and is a leading black-box optimizer for expensive, non-differentiable objectives — hyperparameter tuning, controller design, and reinforcement-learning policy search among them.

Continuous optimization past the airport example underlies most of modern machine learning. The gradient methods here — gradient ascent, line search, Newton's method — scale to the loss surfaces of neural networks with millions of parameters, treated in the deep-learning optimization lessons. The exception this lesson names, convex optimization, has its definitive modern reference in Boyd and Vandenberghe (2004, Convex Optimization): when the objective is convex, every local optimum is global and gradient descent is guaranteed to reach it, which is why so much of applied optimization is engineered to be convex whenever the problem permits.

The common thread

Every algorithm across these two lessons is the same loop — hold a state (or a few), look at neighbors, move — differing only in how it escapes a local optimum. Hill climbing does not escape and pays for it. Random restart escapes by starting over. Simulated annealing escapes by tolerating downhill moves early. Beam search escapes by running several threads that share information. Genetic algorithms escape by recombining partial solutions. Continuous gradient methods trade the discrete neighbor set for a direction from calculus but inherit the same local optima. The algorithms are a catalogue of ways to keep making progress once the greedy step stops improving.