--- title: Population and Continuous Search module: Search moduleNumber: 2 lessonNumber: 6 order: 206 summary: > Single-state local search escapes a trap by restarting or tolerating downhill moves. This lesson develops the alternatives that keep several states at once — local beam search, which shares successors across parallel threads, and genetic algorithms, which recombine two parents through crossover and mutation — then crosses into continuous spaces, where calculus replaces the finite neighbor set: gradient ascent, line search, and Newton's method. It closes with the industrial descendants of these methods and the loop they all share. topics: [Search] sources: - book: AIMA ref: "Ch. 4 — Beyond Classical Search; §4.1.3 Local beam search; §4.1.4 Genetic algorithms" - book: AIMA ref: "§4.2 Local Search in Continuous Spaces" --- The companion lesson, [Local Search and Optimization](/artificial-intelligence/search/local-search), 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. $$ % caption: Local beam search keeps k current states (here k = 3). Each step % expands all k, pools every successor, and keeps the k best. Unlike k independent % restarts, the beam concentrates its k slots wherever the most promising % successors appear, so information passes between the parallel threads. \begin{tikzpicture}[>=stealth, font=\footnotesize, s/.style={circle, draw, minimum size=6mm, inner sep=0pt, font=\footnotesize}] \definecolor{acc}{HTML}{2348F2} % level 0: k current states \node[s, draw=acc, text=acc] (a) at (0,2.4) {}; \node[s, draw=acc, text=acc] (b) at (0,1.2) {}; \node[s, draw=acc, text=acc] (c) at (0,0.0) {}; \node[anchor=east, acc, font=\footnotesize] at (-0.35,1.2) {k current}; % level 1: pooled successors (many) \foreach \i/\y in {1/3.0,2/2.4,3/1.8,4/1.2,5/0.6,6/0.0,7/-0.6} \node[s] (p\i) at (2.6,\y) {}; \node[anchor=south, font=\footnotesize] at (2.6,3.35) {all successors}; % edges from currents to a spread of successors \draw[black] (a) -- (p1); \draw[black] (a) -- (p2); \draw[black] (a) -- (p3); \draw[black] (b) -- (p3); \draw[black] (b) -- (p4); \draw[black] (b) -- (p5); \draw[black] (c) -- (p5); \draw[black] (c) -- (p6); \draw[black] (c) -- (p7); % level 2: the k best kept \node[s, draw=acc, text=acc] (k1) at (5.4,2.4) {}; \node[s, draw=acc, text=acc] (k2) at (5.4,1.2) {}; \node[s, draw=acc, text=acc] (k3) at (5.4,0.0) {}; \node[anchor=west, acc, font=\footnotesize] at (5.75,1.2) {keep k best}; \draw[->, acc, thick] (p2) -- (k1); \draw[->, acc, thick] (p3) -- (k2); \draw[->, acc, thick] (p6) -- (k3); \end{tikzpicture} $$ 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 $1..8$ giving that column's queen its row. One generation transforms the population through four stages. $$ % caption: One generation of a genetic algorithm on 8-queens, each state an % 8-digit string. States are ranked by fitness (nonattacking pairs); pairs are % selected for mating in proportion to fitness; each pair crosses over at a random % cut point to form offspring; and each offspring is randomly mutated. \begin{tikzpicture}[>=stealth, font=\footnotesize, g/.style={draw, minimum width=20mm, minimum height=6mm, font=\ttfamily\footnotesize, align=center}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % column headers \node[font=\footnotesize] at (0,3.1) {population}; \node[font=\footnotesize] at (2.7,3.1) {f\/itness}; \node[font=\footnotesize] at (5.6,3.1) {selection}; \node[font=\footnotesize] at (8.5,3.1) {crossover}; \node[font=\footnotesize] at (11.4,3.1) {mutation}; % (a) population \node[g] (p1) at (0,2.3) {24748552}; \node[g] (p2) at (0,1.5) {32752411}; \node[g] (p3) at (0,0.7) {24415124}; \node[g] (p4) at (0,-0.1) {32543213}; % (b) fitness numbers \node at (2.7,2.3) {24}; \node at (2.7,1.5) {23}; \node at (2.7,0.7) {20}; \node at (2.7,-0.1) {11}; \foreach \i in {1,2,3,4} \draw[->, black] (p\i.east) -- (2.2,{2.3-(\i-1)*0.8}); % (c) selected pairs \node[g] (s1) at (5.6,2.3) {32752411}; \node[g] (s2) at (5.6,1.5) {24748552}; \node[g] (s3) at (5.6,0.7) {32752411}; \node[g] (s4) at (5.6,-0.1) {24415124}; \foreach \i in {1,2,3,4} \draw[->, black] (3.05,{2.3-(\i-1)*0.8}) -- (s\i.west); % crossover cut markers (dashed) at position 3 \draw[red, dashed] (5.6,2.62) -- (5.6,-0.42); % (d) crossed offspring \node[g] (c1) at (8.5,2.3) {32748552}; \node[g] (c2) at (8.5,1.5) {24752411}; \node[g] (c3) at (8.5,0.7) {32752124}; \node[g] (c4) at (8.5,-0.1) {24415411}; \draw[->, acc, thick] (s1.east) -- (c1.west); \draw[->, acc, thick] (s2.east) -- (c2.west); \draw[->, acc, thick] (s3.east) -- (c3.west); \draw[->, acc, thick] (s4.east) -- (c4.west); % (e) mutated \node[g] (m1) at (11.4,2.3) {32748152}; \node[g] (m2) at (11.4,1.5) {24752411}; \node[g] (m3) at (11.4,0.7) {32252124}; \node[g] (m4) at (11.4,-0.1) {24415417}; \foreach \i in {1,2,3,4} \draw[->, red, thick] (c\i.east) -- (m\i.west); \end{tikzpicture} $$ 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.[^aima-ga] 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. ```algorithm caption: $\textsc{Genetic-Algorithm}(population, \textsc{Fitness})$ — returns an individual input: $population$, a set of individuals; $\textsc{Fitness}$, a fitness function repeat $new\_population \gets$ empty set for $i = 1$ to $\textsc{Size}(population)$ do $x \gets \textsc{Random-Selection}(population, \textsc{Fitness})$ $y \gets \textsc{Random-Selection}(population, \textsc{Fitness})$ $child \gets \textsc{Reproduce}(x, y)$ if (small random probability) then $child \gets \textsc{Mutate}(child)$ add $child$ to $new\_population$ $population \gets new\_population$ until some individual is fit enough, or enough time has elapsed return the best individual in $population$, according to $\textsc{Fitness}$ ``` 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 $\textsc{Reproduce}(x, y)$ cuts the parents at a random point $c$ and appends the prefix of $x$ to the suffix of $y$: ```algorithm caption: $\textsc{Reproduce}(x, y)$ — one crossover of two parent strings input: $x$, $y$, parent individuals of length $n$ $c \gets$ random integer from $1$ to $n$ return $\textsc{Append}(\textsc{Substring}(x, 1, c), \textsc{Substring}(y, c{+}1, n))$ ``` $$ % caption: A schema is a partially specified string; positions marked * are % wildcards. The schema 246***** matches every 8-queens state whose first three % queens sit in columns 2, 4, 6. Crossover recombines whole matching blocks, so a % schema whose instances score above average spreads through the population. \begin{tikzpicture}[>=stealth, font=\footnotesize, fix/.style={draw, fill=acc!12, draw=acc, minimum size=6mm, font=\footnotesize\ttfamily, text=acc}, wild/.style={draw=black, fill=black!10, text=black, minimum size=6mm, font=\footnotesize\ttfamily}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\c in {0/2,1/4,2/6} \node[fix] at (\i*0.65,0) {\c}; \foreach \i in {3,4,5,6,7} \node[wild] at (\i*0.65,0) {*}; \node[anchor=west, font=\footnotesize] at (5.3,0.35) {f\/ixed: columns 2, 4, 6}; \node[anchor=west, black, font=\footnotesize] at (5.3,-0.35) {* = any column}; \node[acc, font=\footnotesize\ttfamily, anchor=east] at (-0.45,0) {schema}; \end{tikzpicture} $$ 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 $$ f(x_1, y_1, x_2, y_2, x_3, y_3) \;=\; \sum_{i=1}^{3} \sum_{c \in C_i} (x_i - x_c)^2 + (y_i - y_c)^2. $$ 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, $$ \nabla f = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial y_1}, \frac{\partial f}{\partial x_2}, \frac{\partial f}{\partial y_2}, \frac{\partial f}{\partial x_3}, \frac{\partial f}{\partial y_3} \right), $$ 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 = \mathbf{0}$ directly; here the gradient is only locally correct, so we instead take repeated uphill steps, the continuous analogue of hill climbing: > **Definition (Gradient ascent).** The update $\mathbf{x} \gets \mathbf{x} + > \alpha \nabla f(\mathbf{x})$, which moves the current point a distance controlled > by the **step size** $\alpha$ along the direction of steepest increase. Descent > (minimization) flips the sign: $\mathbf{x} \gets \mathbf{x} - \alpha \nabla > f(\mathbf{x})$. 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 \gets x - g(x)/g'(x)$, and finding a maximum means finding a zero of the gradient, so $g$ becomes $\nabla f$ and the update takes the matrix form $$ \mathbf{x} \;\gets\; \mathbf{x} - \mathbf{H}_f^{-1}(\mathbf{x})\, \nabla f(\mathbf{x}), $$ 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. $$ % caption: Gradient ascent versus Newton's method climbing a peak. Gradient ascent % takes many small fixed-size steps along the slope; Newton fits a quadratic to the % local curvature and jumps close to the optimum in one step, converging in far % fewer iterations near a solution but paying for the Hessian each step. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % a peak (concave curve) \draw[black, thick] (0,0.3) .. controls (1.6,0.4) and (2.4,2.6) .. (3.4,2.6) .. controls (4.4,2.6) and (5.2,0.4) .. (6.8,0.3); \fill[black] (3.4,2.6) circle (1.6pt); \node[font=\scriptsize, anchor=south] at (3.4,2.65) {optimum}; % gradient ascent: many small steps up left flank \foreach \x/\y in {0.5/0.55, 1.0/0.85, 1.5/1.3, 1.9/1.75, 2.25/2.1, 2.55/2.35} \fill[acc] (\x,\y) circle (1.3pt); \draw[acc, ->] (0.5,0.55) -- (1.0,0.85); \draw[acc, ->] (1.0,0.85) -- (1.5,1.3); \draw[acc, ->] (1.5,1.3) -- (1.9,1.75); \draw[acc, ->] (1.9,1.75) -- (2.25,2.1); \draw[acc, ->] (2.25,2.1) -- (2.55,2.35); \node[acc, font=\scriptsize, anchor=east] at (0.45,0.55) {gradient ascent}; % newton: two big jumps down right flank \fill[red] (6.2,0.55) circle (1.3pt); \fill[red] (4.4,2.2) circle (1.3pt); \draw[red, ->, thick] (6.2,0.55) -- (4.4,2.2); \draw[red, ->, thick] (4.4,2.2) -- (3.55,2.55); \node[red, font=\scriptsize, anchor=west] at (6.25,0.55) {Newton}; \end{tikzpicture} $$ These are the same tools that power the [deep-learning optimization](/deep-learning/optimization/gradient-descent-and-sgd) lessons, applied there to a loss over millions of parameters rather than six airport coordinates.[^aima-cont] 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](/artificial-intelligence/search/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](/deep-learning/optimization/gradient-descent-and-sgd) 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. [^aima-ga]: **Russell & Norvig**, _AIMA_ (3rd ed.), §4.1.3–4.1.4 — Local beam search and genetic algorithms: the $k$-state beam that shares successors across threads, stochastic beam search, and the population / fitness / selection / crossover / mutation cycle with schemata explaining crossover's advantage. [^aima-cont]: **Russell & Norvig**, _AIMA_ (3rd ed.), §4.2 — Local Search in Continuous Spaces: the airport-siting example, discretization, gradient ascent with step size $\alpha$ and line search, the empirical gradient, and Newton–Raphson with the Hessian.