--- title: Local Search and Optimization module: Search moduleNumber: 2 lessonNumber: 5 order: 205 summary: > When the path to a goal is irrelevant and only the final state matters, we can discard the search tree entirely and keep just the current state, moving to a better neighbor at each step. This lesson builds the state-space landscape metaphor, works through hill climbing and the three obstacles that defeat it (local maxima, ridges, plateaus), then develops the first escapes: random restarts and simulated annealing with its temperature schedule. The population-based methods and continuous-space calculus follow in the next lesson. topics: [Search] sources: - book: AIMA ref: "Ch. 4 — Beyond Classical Search; §4.1 Local Search Algorithms and Optimization Problems" - book: AIMA ref: "§4.1.1 Hill-climbing search; §4.1.2 Simulated annealing" --- The [uninformed](/artificial-intelligence/search/uninformed-search) and [informed](/artificial-intelligence/search/informed-search) search algorithms keep one or more paths in memory and record, at every node, which alternatives have already been tried. When a goal turns up, the path that reached it _is_ the solution — the order of moves is the answer. For a large class of problems that bookkeeping is wasted effort. In the 8-queens problem the answer is a board configuration with no two queens attacking; the sequence in which the queens were placed is irrelevant. The same holds for integrated-circuit layout, factory-floor scheduling, job-shop scheduling, telecommunications-network routing, vehicle routing, and portfolio management: what you want is a good final state, not a route to it.[^aima-local] When the path does not matter, keep only the **current state** and try to improve it. **Local search** algorithms operate on a single current node and move only to neighbors, discarding the paths behind them. They are not systematic, so they give up the completeness guarantees of tree search, but they buy two things in return: they use a _constant_ amount of memory, and they can find reasonable solutions in state spaces far too large — or continuous, hence infinite — for any systematic method to enumerate. > **Definition (Local search).** A search that maintains a single current state > (rather than a frontier of paths) and iteratively moves to a neighboring state, > retaining no memory of the states already visited. Because it stores only the > current node, its memory cost is constant in the size of the state space. Local search also solves problems that the standard framing of Chapter 3 cannot express at all: **optimization problems**, where there is no explicit goal test, only an **objective function** to be made as large (or small) as possible. Nature runs one such problem — Darwinian evolution maximizes reproductive fitness with no "goal" and no path cost — and much of engineering runs the rest. > **Definition (Optimization problem).** A problem defined not by a goal test but > by an **objective function** $f(s)$ assigning a real value to each state $s$; > the task is to find a state that maximizes (or minimizes) $f$. A goal-finding > problem is the special case where $f$ is an indicator of goalhood. This lesson develops the single-state methods: the landscape metaphor, hill climbing and its failure modes, and the first two ways to escape those failures — random restarts and simulated annealing. The methods that keep a _population_ of states (beam search and genetic algorithms) and the calculus for _continuous_ spaces follow in the companion lesson, [Population and Continuous Search](/artificial-intelligence/search/population-and-continuous-search). ## The state-space landscape The right mental picture for local search is a terrain. Give each state two attributes: a **location**, fixed by the state itself, and an **elevation**, given by the value of the objective function (or of a heuristic cost, if we are minimizing). Plot elevation against location and the state space becomes a surface with peaks and valleys. If elevation is _value_, we want the highest peak, the **global maximum**; if elevation is _cost_, we want the lowest valley, the **global minimum**. The two are interchangeable — negate the function and a maximization problem becomes a minimization problem — so we fix ideas on maximization and speak of climbing. $$ % caption: A one-dimensional state-space landscape. Elevation is the objective % function; a hill-climber (current state, at the arrow) moves uphill toward the % nearest peak. Only the global maximum is the true optimum; local maxima, % shoulders, and flat local maxima are the traps defined in the text. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axes \draw[->, black] (0,0) -- (11.4,0) node[anchor=west, black, font=\footnotesize] {state space}; \draw[->, black] (0,0) -- (0,4.4) node[anchor=south, black, font=\footnotesize, align=center] {objective\\function}; % the landscape curve, left to right: % rise to a shoulder, up to global max, down, up to a local max, down to a flat local max, taper \draw[black, thick] (0.4,0.7) .. controls (1.1,0.7) and (1.3,1.7) .. (1.9,1.75) % shoulder (flat then rise) .. controls (2.6,1.8) and (2.8,3.9) .. (3.5,3.95) % global maximum peak .. controls (4.2,4.0) and (4.6,0.9) .. (5.6,0.85) % down into valley .. controls (6.3,0.8) and (6.9,2.7) .. (7.5,2.7) % up to a local maximum .. controls (8.0,2.7) and (8.3,1.15) .. (8.9,1.15) % down .. controls (9.5,1.15) and (9.6,1.9) .. (10.0,1.9) % up to a flat local max .. controls (10.5,1.9) and (10.7,1.9) .. (11.0,1.6); % flat top then taper % labels for features (kept off the curve) \node[anchor=south, font=\footnotesize] at (3.5,4.05) {global maximum}; \node[anchor=east, font=\footnotesize] at (1.55,2.35) {shoulder}; \draw[black] (1.7,2.25) -- (1.85,1.85); \node[anchor=south, font=\footnotesize] at (7.5,2.8) {local maximum}; \node[anchor=south, font=\footnotesize] at (10.0,2.0) {f\/lat local maximum}; % current state and the uphill move \fill[acc] (6.55,1.45) circle (2.2pt); \draw[->, acc, very thick] (6.7,1.7) -- (7.25,2.55); \node[acc, anchor=north, font=\footnotesize] at (6.55,1.35) {current state}; \end{tikzpicture} $$ A **complete** local search always finds a goal if one exists; an **optimal** one always finds the global maximum. The features of this one-dimensional landscape — shoulders, local maxima, plateaus — are what make those two guarantees hard to achieve, and every algorithm below is a strategy for coping with one of them. ## Hill climbing The simplest local search is **hill climbing**, in its **steepest-ascent** form: a loop that repeatedly moves to the neighboring state of highest value, and halts when no neighbor is higher. It keeps no search tree — the only state it records is the current node and its objective value — and it never looks past its immediate neighbors. Russell and Norvig liken it to finding the top of Mount Everest in a thick fog while suffering from amnesia.[^aima-hc] ```algorithm caption: $\textsc{Hill-Climbing}(problem)$ — returns a state that is a local maximum $current \gets \textsc{Make-Node}(problem.\textsc{Initial-State})$ loop $neighbor \gets$ a highest-valued successor of $current$ if $\textsc{Value}(neighbor) \le \textsc{Value}(current)$ then return $current.\textsc{State}$ $current \gets neighbor$ ``` Hill climbing is sometimes called **greedy local search**: it grabs the best neighbor without any thought for where to go next. Greed usually pays. Because a bad state is typically easy to improve, hill climbing makes rapid progress — from a random 8-queens position it reaches a near-solution in only a handful of steps. When it works, it works fast. ### The 8-queens formulation To see the algorithm at work, use the **complete-state formulation** of 8-queens: every state has all eight queens on the board, one per column, and the successors of a state are the $8 \times 7 = 56$ states reached by moving a single queen to another square in its own column. The heuristic $h$ is the number of pairs of queens attacking each other, directly or indirectly; the global minimum of $h$ is $0$, attained only by a genuine solution. $$ % caption: The 8-queens complete-state formulation. Each state fixes one queen per % column; a move slides one queen within its column, giving 56 successors. The % objective to minimize is h, the count of attacking queen pairs, and h = 0 marks % a solution. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % 8x8 board grid \foreach \x in {0,...,8} \draw[black] (\x*0.55,0) -- (\x*0.55,4.4); \foreach \y in {0,...,8} \draw[black] (0,\y*0.55) -- (4.4,\y*0.55); \draw[black, thick] (0,0) rectangle (4.4,4.4); % one queen per column (as dots), an example configuration \foreach \c/\r in {0/5, 1/2, 2/6, 3/0, 4/7, 5/3, 6/1, 7/4} { \fill[acc] ({\c*0.55+0.275},{\r*0.55+0.275}) circle (2.6pt); } % highlight one column and a candidate move within it \draw[red, thick] (1*0.55,0) rectangle (2*0.55,4.4); \draw[->, red, thick] ({1*0.55+0.275},{2*0.55+0.275}) to[bend left=30] ({1*0.55+0.275},{5*0.55+0.275}); % annotations kept outside the board \node[anchor=west, font=\footnotesize] at (4.7,3.6) {move one queen}; \node[anchor=west, font=\footnotesize] at (4.7,3.15) {within its column}; \node[anchor=west, red, font=\footnotesize] at (4.7,2.3) {56 successors}; \node[anchor=west, font=\footnotesize] at (4.7,1.85) {per state}; \node[anchor=west, font=\footnotesize] at (4.7,1.0) {minimize h =}; \node[anchor=west, font=\footnotesize] at (4.7,0.55) {attacking pairs}; \end{tikzpicture} $$ From a randomly generated 8-queens state, steepest-ascent hill climbing gets _stuck_ 86% of the time, solving only 14% of instances. But it is fast where it does not stall: about four steps to reach a solution, three to reach a dead end — respectable for a space of $8^8 \approx 17$ million states. A short trace shows the greedy loop at work. Start from a state with $h = 17$ attacking pairs. Of its $56$ successors, the best drops $h$ to $12$ (there may be several tied at $12$; pick one), so the climber takes it. From the new state the best successor reaches $h = 8$, then $h = 5$, then $h = 3$, then $h = 1$. At $h = 1$ every one of the $56$ successors has $h \ge 1$ — no single queen move removes the last conflict without creating another — so the best neighbor _ties or worsens_ the current value, the halting test fires, and hill climbing returns a state with one attacking pair still on the board. | Step | $h$ (attacking pairs) | Best successor $h$ | Action | | --- | --- | --- | --- | | $0$ | $17$ | $12$ | move (improves) | | $1$ | $12$ | $8$ | move | | $2$ | $8$ | $5$ | move | | $3$ | $5$ | $3$ | move | | $4$ | $3$ | $1$ | move | | $5$ | $1$ | $1$ | halt (no improvement) | Five steps of steep, cheap progress, then a wall: the state with $h = 1$ is a **local minimum** of the cost $h$ (equivalently a local maximum of the "nonattacking pairs" objective), one conflict short of a solution and unable to take the last step. This is the $86\%$ case in miniature — fast to a near-solution, then stuck. ### Why hill climbing gets stuck The 86% failure rate comes from three features of the landscape, each visible in the one-dimensional figure above. > **Definition (Local maximum).** A state higher than all its neighbors but lower > than the global maximum. A hill-climber that wanders into its basin is drawn to > the peak and then trapped: every move is downhill, so the greedy rule refuses to > take one. **Ridges** are the subtler trap. A ridge is a sequence of local maxima aligned along a direction the available moves cannot follow: the grid of states is laid over a slope that rises diagonally, so from each state every _single-step_ move points downhill even though a diagonal combination would climb. Greedy search cannot see the diagonal and stalls, oscillating along the crest. $$ % caption: Why ridges defeat hill climbing. The available moves lie on a grid % (dots) laid over a slope that rises from lower-left to upper-right. Each dot is a % local maximum relative to its grid neighbors, so every single move points % downhill; the true ascent runs diagonally, which no single move reaches. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % faint contour lines of a diagonal ridge (rising to upper-right) \foreach \k in {0,1,2,3,4} { \draw[black] ({0.6+\k*0.7},2.9) -- ({2.4+\k*0.7},0.4); } \node[anchor=west, black, font=\footnotesize] at (5.1,2.6) {ridge rises}; \node[anchor=west, black, font=\footnotesize] at (5.1,2.15) {this way}; \draw[->, black, thick] (4.9,2.35) -- (5.05,2.55); % grid of states as dots along the crest, each a local max \foreach \i in {0,...,4} { \coordinate (n\i) at ({1.4+\i*0.7},{1.0+\i*0.32}); \fill[acc] (n\i) circle (2.4pt); } % from a middle state, both single moves point downhill (short down-arrows) \draw[->, red, thick] (n2) -- ++(-0.55,-0.35); \draw[->, red, thick] (n2) -- ++(0.55,-0.72); \node[anchor=south, red, font=\footnotesize, fill=white, inner sep=1pt] at (2.8,1.95) {both moves go down}; \node[anchor=north, acc, font=\footnotesize, fill=white, inner sep=1pt] at (2.8,0.4) {crest of local maxima}; \end{tikzpicture} $$ > **Definition (Plateau).** A flat region of the landscape where neighboring > states share the current state's value. A plateau may be a **flat local > maximum**, with no uphill exit, or a **shoulder**, a flat stretch from which the > ground rises again farther on. Hill climbing cannot tell the two apart from a > single step, and may wander a plateau indefinitely. The plateau case exposes a design choice. The algorithm above halts when the best neighbor merely _ties_ the current value, which surrenders on every shoulder. Allowing **sideways moves** — stepping to an equal-valued neighbor in the hope the plateau is a shoulder — fixes shoulders but risks an infinite loop on a flat local maximum. The standard compromise caps the number of consecutive sideways moves (say, 100 for 8-queens). That single change lifts the 8-queens success rate from 14% to 94%, at the cost of longer runs: about 21 steps per success and 64 per failure. ### Variants of hill climbing Because the failure modes are landscape-shaped, several cheap modifications of the greedy rule help on landscapes of different shape. - **Stochastic hill climbing** chooses at random among the uphill moves, weighting the choice by steepness. It usually converges more slowly than steepest ascent but finds better solutions on some landscapes, because it is less prone to march straight into the nearest local maximum. - **First-choice hill climbing** implements stochastic hill climbing without enumerating all successors: it generates successors at random and takes the first one that improves on the current state. This is the right choice when a state has thousands of successors and computing all of them is wasteful. - **Random-restart hill climbing** attacks incompleteness head-on. It runs a series of hill climbs from randomly generated initial states, keeping the best result, until a goal is found. It is complete with probability approaching 1, because eventually a starting state lands in the global maximum's basin — or _is_ the goal. $$ % caption: Random-restart hill climbing. Each restart drops the climber at a random % location; it then walks uphill to whatever local maximum owns that basin. Most % restarts land in a suboptimal basin (short peaks), but with enough tries one lands % in the global maximum's basin. The success probability per restart is p; expected % restarts to a goal is 1/p. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \draw[black, thick] (0,0.4) .. controls (0.8,0.4) and (1.0,1.5) .. (1.5,1.5) .. controls (2.0,1.5) and (2.2,0.5) .. (2.9,0.5) .. controls (3.7,0.5) and (4.0,3.0) .. (4.7,3.0) .. controls (5.4,3.0) and (5.7,0.6) .. (6.4,0.6) .. controls (7.0,0.6) and (7.2,1.7) .. (7.8,1.7) .. controls (8.3,1.7) and (8.5,0.5) .. (9.0,0.5); \fill[red] (4.7,3.0) circle (2pt); \node[red, font=\scriptsize, anchor=south] at (4.7,3.05) {global max}; % three restarts: two into short basins, one into the tall one \fill[acc] (0.6,0.42) circle (1.6pt); \draw[acc,->] (0.65,0.5) .. controls (1.0,0.9) .. (1.45,1.42); \fill[acc] (5.6,0.75) circle (1.6pt); \draw[acc,->] (5.55,0.85) .. controls (5.0,2.0) .. (4.75,2.9); \fill[acc] (8.4,0.55) circle (1.6pt); \draw[acc,->] (8.35,0.63) .. controls (8.1,1.2) .. (7.85,1.62); \node[acc, font=\scriptsize, anchor=north] at (0.7,0.3) {restart 1}; \node[acc, font=\scriptsize, anchor=north] at (5.7,0.62) {restart 2}; \node[acc, font=\scriptsize, anchor=north] at (8.4,0.42) {restart 3}; \end{tikzpicture} $$ Random restart has a clean cost analysis. If each hill climb succeeds with probability $p$, the expected number of restarts to reach a goal is $1/p$. For 8-queens without sideways moves, $p \approx 0.14$, so roughly $1/0.14 \approx 7$ restarts suffice — six failures and one success. The expected total work is the cost of one success plus $(1-p)/p$ times the cost of a failure, about 22 steps in all. With sideways moves allowed, $p \approx 0.94$, so $1/0.94 \approx 1.06$ restarts and about $(1 \times 21) + (0.06/0.94) \times 64 \approx 25$ steps. Even three-million-queens instances fall in under a minute. Whether random restart succeeds depends entirely on the shape of the landscape. A landscape with few local maxima and shallow plateaus surrenders after a handful of restarts; an NP-hard problem, whose surface resembles a widely scattered family of balding porcupines on a flat floor — a spike of local optima on every needle — may have exponentially many traps. Even then, a reasonably good local maximum is often reachable in a few restarts. ## Simulated annealing Hill climbing never steps downhill, so it is doomed to stop at the first local maximum it climbs into. A pure random walk — move to a uniformly random neighbor, ignoring value — is complete (it eventually visits every state, the global maximum included) but hopelessly slow. **Simulated annealing** combines the two: mostly climb, but occasionally allow a downhill move, and let the willingness to go downhill shrink over time. > **Definition (Simulated annealing).** A stochastic local search that, at each > step, proposes a random neighbor and accepts it outright if it improves the > objective, but accepts a worsening move only with a probability that shrinks > both with the size of the worsening and with a falling **temperature** parameter > $T$. Named after the metallurgical process of heating and slowly cooling a metal > to reach a low-energy crystalline state. The physical metaphor makes the schedule intuitive. Switch to minimizing cost (gradient _descent_) and picture rolling a ping-pong ball into the deepest crevice of a bumpy surface. Let it roll and it settles in the first dent — a local minimum. Shake the surface and the ball hops out; shake too hard and it never settles anywhere. The trick is to shake _hard at first_, enough to bounce the ball out of shallow local minima, then gradually shake more gently so that once the ball finds the deep global minimum it stays. Shaking hard is a high temperature $T$; cooling is lowering $T$ on a fixed **schedule**. The acceptance rule is where the temperature enters. Let $\Delta E$ be the change in value a proposed move would produce (positive if the move improves things). Improving moves are always accepted. A worsening move, $\Delta E < 0$, is accepted with probability $$ P(\text{accept}) \;=\; e^{\Delta E / T}. $$ Two properties make this the right rule. It decreases exponentially with the _badness_ of the move: a slightly worse neighbor is often accepted, a much worse one rarely. And it decreases as $T$ falls: bad moves are common early, when $T$ is high, and progressively forbidden as the schedule cools. If $T$ is lowered slowly enough, simulated annealing finds a global optimum with probability approaching 1.[^aima-sa] Put numbers to it. Suppose the objective is a cost being minimized (so $\Delta E$ is negative for a worsening move) and a proposed move worsens the cost by $|\Delta E| = 2$. The acceptance probability $e^{\Delta E / T} = e^{-2/T}$ then depends entirely on where the schedule stands: | $T$ | $\Delta E = -1$ | $\Delta E = -2$ | $\Delta E = -5$ | | --- | --- | --- | --- | | $10$ | $0.905$ | $0.819$ | $0.607$ | | $2$ | $0.607$ | $0.368$ | $0.082$ | | $1$ | $0.368$ | $0.135$ | $0.0067$ | | $0.5$ | $0.135$ | $0.018$ | $0.00005$ | | $0.1$ | $0.00005$ | $0.0000000021$ | $\approx 0$ | Read down a column and the cooling story is plain: at $T = 10$ a move that worsens cost by $2$ is accepted $82\%$ of the time — the search wanders almost freely — while at $T = 0.5$ the same move is accepted under $2\%$ of the time, and at $T = 0.1$ it is effectively forbidden. Read across a row and the badness story appears: at $T = 1$, a worsening of $1$ is accepted $37\%$ of the time but a worsening of $5$ only $0.7\%$. High temperature early lets the ball bounce out of shallow traps; low temperature late pins it in the deepest basin it has found. ```algorithm caption: $\textsc{Simulated-Annealing}(problem, schedule)$ — returns a solution state input: $problem$; $schedule$, a mapping from time to temperature $current \gets \textsc{Make-Node}(problem.\textsc{Initial-State})$ for $t = 1, 2, 3, \ldots$ do $T \gets schedule(t)$ if $T = 0$ then return $current$ $next \gets$ a randomly selected successor of $current$ $\Delta E \gets \textsc{Value}(next) - \textsc{Value}(current)$ if $\Delta E > 0$ then $current \gets next$ else $current \gets next$ with probability $e^{\Delta E / T}$ ``` $$ % caption: Left: a cooling schedule, temperature T falling with time t (here % geometric, T_t = T_0 * 0.95^t). Right: the acceptance probability for a worsening % move, e^{dE/T}, plotted against the size of the worsening at three temperatures -- % high T accepts almost anything, low T accepts almost nothing. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % --- cooling schedule --- \begin{scope} \draw[->, black] (0,0) -- (3.4,0) node[right, font=\scriptsize, text=black] {time t}; \draw[->, black] (0,0) -- (0,2.9) node[above, font=\scriptsize, text=black] {T}; \draw[acc, thick] (0.1,2.6) .. controls (0.7,1.4) and (1.4,0.55) .. (2.2,0.3) .. controls (2.7,0.2) and (3.0,0.15) .. (3.2,0.13); \node[acc, font=\scriptsize, anchor=west] at (1.6,1.15) {cooling}; \node[font=\scriptsize, anchor=north, text=black] at (1.7,-0.15) {schedule}; \end{scope} % --- acceptance probability --- \begin{scope}[xshift=5.2cm] \draw[->, black] (0,-0.35) -- (3.4,-0.35) node[right, font=\scriptsize, text=black] {worsening}; \draw[->, black] (0,-0.35) -- (0,2.9) node[above, font=\scriptsize, text=black] {P(accept)}; \node[font=\scriptsize, text=black, anchor=east] at (-0.05,2.5) {1}; % high T: shallow decay \draw[acc, thick] (0,2.5) .. controls (1.2,2.2) and (2.2,1.9) .. (3.0,1.6); \node[acc, font=\scriptsize, anchor=west] at (3.05,1.6) {high T}; % mid T \draw[black, thick] (0,2.5) .. controls (0.8,1.5) and (1.6,0.9) .. (3.0,0.5); \node[font=\scriptsize, anchor=west] at (3.05,0.5) {mid T}; % low T: steep decay \draw[red, thick] (0,2.5) .. controls (0.35,0.7) and (0.8,0.15) .. (3.0,0.02); \node[red, font=\scriptsize, anchor=west] at (3.05,0.05) {low T}; \end{scope} \end{tikzpicture} $$ The inner loop is nearly identical to hill climbing; the two differences are that it picks a _random_ successor rather than the best, and that a worsening successor is not rejected outright but accepted with probability $e^{\Delta E / T}$. Simulated annealing was first used for VLSI layout in the early 1980s and is now a staple of factory scheduling and other large-scale optimization. Random restart and simulated annealing both work with a single current state. Another way to escape a local optimum is to keep _several_ states at once and let them share what they learn — and once you allow states to combine, you have the door to genetic algorithms and, past the discrete world, to the calculus of continuous optimization. This continues in [Population and Continuous Search](/artificial-intelligence/search/population-and-continuous-search). [^aima-local]: **Russell & Norvig**, _Artificial Intelligence: A Modern Approach_ (3rd ed.), §4.1 — Local Search Algorithms and Optimization Problems: local search keeps a single current node, uses constant memory, and suits problems where only the solution state matters, including pure optimization with an objective function and no goal test. [^aima-hc]: **Russell & Norvig**, _AIMA_ (3rd ed.), §4.1.1 — Hill-climbing search: the steepest-ascent loop, the 8-queens complete-state formulation ($56$ successors, $h$ = attacking pairs), the local-maximum / ridge / plateau failure modes, sideways moves, and the stochastic, first-choice, and random-restart variants with their 8-queens statistics. [^aima-sa]: **Russell & Norvig**, _AIMA_ (3rd ed.), §4.1.2 — Simulated annealing: the annealing metaphor, the random-neighbor proposal with the $e^{\Delta E / T}$ acceptance rule for worsening moves, the cooling schedule, and the guarantee of a global optimum as $T \to 0$ slowly.