Local and Metaheuristic Optimization

Local search algorithms differ fundamentally from the path-finding search covered in earlier modules: rather than tracking a path from a start state to a goal, they operate on a single current state and an objective function that scores how good that state is, moving toward better-scoring neighboring states one step at a time. This makes them well suited to problems where the path is irrelevant and only the final configuration matters — crew scheduling, circuit layout, and the N-queens problem are classic examples where a solution is judged purely by its own quality, not by how it was reached. Hill climbing is the simplest such algorithm: at each step, it evaluates every neighboring state and moves to whichever neighbor most improves the objective function, stopping when no neighbor is better than the current state — an approach often described as "greedy local search," since it always takes the best immediately available move without any lookahead, much like climbing a hill in dense fog by always stepping uphill from wherever your feet currently are.

This greediness is also hill climbing's central weakness. Picture a one-dimensional objective landscape with two peaks: a lower "local maximum" at state value 6 and a higher "global maximum" at state value 9, separated by a dip. A hill-climbing search that starts on the local maximum's slope will climb to height 6 and then stop, because every neighboring state from that peak scores lower — the algorithm has no way to see, let alone cross, the dip that separates it from the taller peak elsewhere in the landscape. This is the local optima problem, and it is compounded by plateaus (regions where neighboring states all score equally, giving hill climbing no directional signal at all) and ridges (regions where the true uphill direction only appears as a sequence of diagonal steps, invisible to an algorithm that only compares straight neighbors). All three obstacles share a common cause: hill climbing makes its decisions using only strictly local information about the current state's immediate neighborhood, with no memory of where it has already been and no ability to look more than one step ahead, so any landscape feature larger than a single step is, by construction, invisible to it.

Several variants attempt to mitigate these failure modes without abandoning hill climbing's simplicity. Stochastic hill climbing chooses randomly among the uphill moves rather than always the single steepest one, sometimes helping it slip past small plateaus. First-choice hill climbing generates successors in random order and takes the first one found that improves on the current state, which is efficient when a state has very many neighbors. Random-restart hill climbing simply runs the basic algorithm repeatedly from different randomly chosen starting states and keeps the best result found across all runs — trading extra computation for a substantially higher chance that at least one run starts on the slope leading to the global optimum. None of these variants provide a formal guarantee of finding the global optimum, which is precisely the gap that simulated annealing, covered next, is designed to close. All three variants, notably, still only ever move to states that are at least as good as, or randomly among, the currently improving options — none of them deliberately accepts a worse state on purpose, which is the qualitatively different idea simulated annealing introduces.

Simulated annealing addresses hill climbing's local-optima problem by occasionally accepting a move to a worse state, rather than only ever moving uphill. The technique takes its name and its acceptance rule from the physical process of annealing metal — heating it and then cooling it slowly so its atoms settle into a low-energy, highly ordered crystal structure rather than freezing into a disordered, higher-energy state. Kirkpatrick, Gelatt, and Vecchi's 1983 paper in Science, "Optimization by Simulated Annealing," established the formal connection between this physical process and combinatorial optimization, showing that a search procedure modeled on annealing could be applied to problems like circuit placement that have no obvious physical analog at all. The probabilistic rule for accepting a worse move traces back further still, to the Metropolis algorithm for simulating physical systems at thermal equilibrium, which Kirkpatrick and colleagues adapted directly into an optimization procedure. The reframing is elegant precisely because it is domain-agnostic: any problem that can be cast as minimizing (or maximizing) some numeric objective over a space of candidate configurations can be handed to simulated annealing, whether or not it has anything to do with physical particles or temperature in any literal sense.

Mechanically, simulated annealing maintains a temperature parameter T that starts high and is gradually lowered according to a cooling schedule. At each step, a random neighboring state is generated and its change in objective value, ΔE (using ΔE negative for a worse move, following the energy-minimization convention), is computed; if ΔE is an improvement, the move is always accepted, exactly as in hill climbing, but if it is a decline, the move is still accepted with probability e^(ΔE/T). Consider a worsening move with ΔE = −2 at temperature T = 4: the acceptance probability is e^(−2/4) = e^(−0.5) ≈ 0.61, so the search accepts this particular downhill step roughly 61% of the time — a substantial chance of escaping a shallow local optimum. Now consider the same ΔE = −2 move much later, once the schedule has cooled to T = 0.5: the acceptance probability drops to e^(−2/0.5) = e^(−4) ≈ 0.018, under 2%, so by this point the search behaves almost exactly like plain hill climbing, only rarely tolerating a worse move.

This gradual cooling is the crux of the method: early on, high temperature makes the search behave almost like a random walk, freely exploring the landscape and escaping local optima it would otherwise be trapped in; as temperature falls, the search increasingly commits to improving moves, settling — ideally — into the neighborhood of the global optimum before finally behaving like ordinary hill climbing near the end of the schedule. Kirkpatrick and colleagues showed that with a sufficiently slow cooling schedule, the procedure converges in probability to a global optimum, though in practice the schedule must be tuned to the problem, since cooling too quickly reintroduces the local-optima problem while cooling too slowly wastes computation. The method has been applied successfully to VLSI circuit placement (the domain of the original 1983 paper), scheduling, and large instances of the traveling salesman problem. Because the only problem-specific pieces needed are an objective function and a way to generate a random neighboring state, simulated annealing can be dropped into a new combinatorial problem with comparatively little custom engineering, which is a large part of why it remains a standard baseline metaheuristic decades after its original publication.

Tabu search is a metaheuristic that, rather than relying on randomness to escape local optima, uses explicit short-term memory to forbid the search from undoing its own recent moves. Fred Glover's 1990 tutorial in Interfaces describes tabu search as a "higher-level" heuristic procedure designed specifically to guide simpler local-search methods past the trap of local optimality, using a tabu list that records recently visited states or recently applied moves and temporarily forbids the search from returning to them, preventing the short cycles that a plain hill climber can otherwise fall into when it oscillates between two or three nearby states. Because a rigid tabu list can sometimes forbid a move that would actually lead to an excellent new solution, tabu search also incorporates aspiration criteria — override conditions that permit an otherwise-tabu move when, for instance, it would produce a better result than any solution found so far in the entire search.

Local beam search takes a different approach to escaping single-state myopia: rather than tracking one current state, it tracks k states in parallel, generates all of their successors at each step, and keeps only the best k states overall from that combined successor pool to carry forward into the next iteration. This is meaningfully different from simply running k independent random-restart hill climbers, because local beam search shares information across its k threads — if one of the k states is producing unusually good successors, several or even all of the next round's k states may descend from it, concentrating the search's effort on the most promising region found so far rather than splitting effort evenly regardless of quality. A stochastic variant, stochastic beam search, chooses the k successors to keep with probability proportional to their objective value rather than deterministically taking the top k, which helps maintain diversity among the k threads and reduces the risk that beam search converges prematurely onto a single locally-clustered region.

Genetic algorithms extend this population-based idea further, framing local search as evolution: a population of candidate states ("individuals," often encoded as strings) is maintained, and each generation selects fitter individuals more often as "parents," combines pairs of parents via crossover (splicing pieces of two individuals together) and applies random mutation, producing a new generation that — over many iterations — tends to drift toward higher-fitness regions of the search space. Genetic algorithms can be viewed as a stochastic variant of local beam search with the added mechanism of information sharing between individuals via crossover, rather than each thread evolving independently. Across tabu search, beam search, and genetic algorithms, the unifying theme of this module is a deliberate trade: none of these metaheuristics offer hill climbing's simplicity or A*'s optimality guarantee, but all of them scale to state spaces — real-world scheduling, layout, and combinatorial design problems — far too large for exhaustive or even heuristic path-based search to handle.