[October 2026 edition]

Indexes and the Art of Searching, Part 6: Local Search and Nature-Inspired Methods

Published: Oct 2, 2026
Reading time: ~13 min

Part 5 covered searches that guarantee optimality or completeness. Part 6 lets go of those guarantees and covers search for cases where it is enough to find a usable solution quickly.

1. Classical Local Search

In a problem of deciding the order of deliveries, you can produce many candidates that change the current solution only slightly, such as the order obtained by swapping two stops in the current one. Local search repeatedly generates such candidates (the neighborhood), evaluates them, and decides whether to move to one; individual methods differ in how they build the neighborhood and in their acceptance rule. If you accept only candidates that improve things, the search stalls at a solution where every move in the neighborhood makes things worse (a local optimum). Simulated annealing, published in Science in 1983 by Kirkpatrick, Gelatt, and Vecchi, escapes local optima by also accepting worse candidates with a probability that depends on a temperature, and shrinking that probability as the temperature is lowered. Tabu search, devised by Glover in the 1980s, uses short-term memory to forbid revisiting recent solutions. The genetic algorithm, proposed by Holland, repeatedly applies selection, crossover, and mutation to a population of solutions.

For problems in continuous spaces, CMA-ES is the representative method. It scatters candidates around the current center, evaluates them, remembers in which directions and how far the well-performing candidates were spread, and stretches or shrinks the next scattering range along those directions. Its documentation describes it as a method that updates the search distribution by incrementally estimating the distribution’s covariance matrix. Because it learns from the problem which directions to stretch, its behavior changes little when the landscape is tilted at an angle or the scale of the objective values is relabeled, which makes it robust to monotone transformations of the objective function and to rotations of the space. On a simple quadratic function BFGS is far faster, while CMA-ES is strong on rugged problems with discontinuities, noise, and multiple peaks.

Which method is better changes from problem to problem. When looking for one sheet in a filing cabinet, if the documents are scattered at random with no relation to where they are kept, the average effort is the same whatever order you open the drawers in. If you line up every possible problem with equal weight and average over them, a method that is fast on one problem is slow on another, and the differences cancel out. Wolpert summarizes the No Free Lunch theorem as showing that all algorithms perform equally under the assumption that problems are uniformly distributed. Igel and Toussaint argued that the result holds only when the set of functions is closed under permutation of the domain. This is the condition that however you shuffle a problem’s evaluation values among its candidates, the shuffled problem still belongs to the same set. On a road network, for example, nearby intersections have similar travel times, and shuffling the evaluation values breaks this property, so the set of road-network problems falls outside the condition. Igel and Toussaint also argue that classes of real-world problems are unlikely to satisfy it. Real problems have structure, and that is why choosing and tuning a method to fit that structure is meaningful.

The methods in the following sections are named after the behavior of living things such as ants, honeybees, flocks of birds, bacteria, and slime molds. Biological behavior is a starting point for ideas, and the update rules of these methods are not derived from biological findings. What supports a method’s performance is evaluation on benchmarks and real data.

2. Ant Colony Optimization: Inspiration from the Double-Bridge Experiment

Ant colony optimization (ACO) draws on experiments on ant foraging and their mathematical models. In the double-bridge experiment by Goss et al., the nest and a food source are connected by two bridges of different lengths. Ants that happen to choose the short bridge reach the food and return first, so more pheromone accumulates on the short bridge and it becomes more likely to be chosen. The probability of choosing the first bridge is expressed as (m1+k)^h / ((m1+k)^h + (m2+k)^h), where m1 and m2 are the numbers of ants that have crossed each bridge, and k≒20 and h≒2 fit the experiment well. This formula inspired the transition probability in ACO.

In Dorigo et al.’s Ant System, the probability that ant k moves from city i to city j is proportional to τ^α · η^β, using the pheromone τ and problem-specific information η (the inverse of the distance). Pheromone is updated as τ ← (1−ρ)τ + Σ Δτ, adding 1/L_k to each edge ant k traversed, where L_k is the length of that ant’s tour. The experiments in the 1996 paper (Oliver30) set α=1, β=5, a persistence rate of 0.5, and Q=100, values chosen to fit that paper’s test problems. The paper itself acknowledges that it can lose to algorithms specialized for a given problem.

Ant Colony System greedily picks the best edge with probability q0, reduces pheromone slightly each time an edge is traversed to keep diversity within the same iteration, and applies the global update only to the edges of the best tour. What distinguishes it from Ant System is which components were changed and which problems they were fitted to.

ACO is an optimization framework built on the mechanism of the double-bridge experiment as inspiration; it computes path lengths directly and reflects them in the amount of pheromone, and it uses evaporation as a parameter for controlling the search. The Scholarpedia article likewise says that ACO has grown into a framework containing many elements unrelated to real ants.

3. Particle Swarm Optimization and Artificial Bee Colony: Simplifying the Swarm

Particle swarm optimization (PSO) was proposed by Kennedy and Eberhart in 1995. It started from simulations of flocks of birds and schools of fish; Reynolds’s boids produce flocking motion from three rules: separation, alignment, and cohesion. The PSO update simplifies this into a form where each individual is pulled toward its own past best p and its neighborhood’s best l. In the standard form, position x and velocity v are updated as v ← ωv + φ1 a⊙(p − x) + φ2 b⊙(l − x), x ← x + v (the formulation by Camacho-Villalón et al.). Each particle keeps some of the direction it was moving in just before, while being pulled both toward the best position it has found so far and toward the best position its nearby peers have found. Here a and b are random vectors, and what you tune are the inertia ω, the attraction coefficients φ1 and φ2, and how the neighborhood is defined.

Artificial bee colony (ABC) was proposed by Karaboga in 2005. It models honeybee foraging as a division of roles among employed bees, onlooker bees, and scout bees. Employed bees search around food sources, and onlooker bees choose food sources with probability proportional to their quality. A food source whose improvement has stalled for a set number of consecutive tries is abandoned, and a scout bee creates a new solution at random. The abandonment count, limit, sets the balance between exploration and exploitation. The paper evaluated the method on three functions, Sphere, Rosenbrock, and Rastrigin, and the author himself writes that the test problems are very limited.

4. Individual Movement: Chemotaxis and Lévy Flights

E. coli moves toward attractants using the change in concentration it senses as it swims. Macnab and Koshland showed in 1972 that a sudden drop in attractant concentration increases direction changes (tumbles), while a rise increases coordinated swimming. Bacteria sense a spatial gradient as a change over time that comes with their movement. Translated into a search procedure, this means comparing evaluation values one after another, continuing in the same direction while they improve and changing direction when they get worse, which reads as a biological version of hill climbing.

The Lévy flight is one distribution of step lengths for random search. The 1999 paper by Viswanathan et al. showed that when targets are sparse, a search that mixes short moves probing the vicinity with occasional very long moves has the advantage. In terms of the length of a single move, the optimal random search is the one where longer moves become rarer in inverse proportion to the square of their length, that is, an inverse-square power-law distribution of flight lengths, and the authors argued that data on animal foraging supports this. Among search algorithms, cuckoo search uses Lévy flight steps in its updates.

On whether animals actually move in Lévy flights, the biology side has both a reanalysis that rejects it (the 2007 study by Edwards et al.) and a report that movement patterns change with the environment (the 2010 study by Humphries et al.). As a component of a search algorithm, the Lévy flight can be treated as one choice of step-length distribution.

5. Slime Molds: Convergence to Shortest Paths Through Local Feedback

Slime molds build networks using only local feedback, in which the thickness of each tube changes with the flow through it. Nakagaki et al. reported in 2000 a slime mold solving a maze, and Tero et al. reported in 2010 that the networks a slime mold forms show efficiency, fault tolerance, and cost comparable to the Tokyo rail network.

The mathematical model by Tero et al. formulates as an adaptive network the mechanism by which tubes carrying more flow grow thicker and tubes carrying less flow thin out and disappear, and the parameter setting the strength of this feedback determines whether the shortest path can be found. Bonifaci et al. proved mathematically that the slime mold model converges to the shortest path regardless of the network’s complexity or the initial distribution of mass.

Implementations carry the cost of solving a system of linear equations at every iteration. A paper by Gao et al. on speeding it up notes that because convergence relies on iterating systems of linear equations, computational performance tends to be poor, and proposes pruning unnecessary nodes and edges and terminating early. If all you need is the shortest path, Dijkstra’s algorithm has the advantage in computational cost. The slime mold model therefore earns its place when borrowing the idea of building a network from local rules alone, or as teaching material.

6. Composing and Tuning the Components

Apart from the evaluation function, the methods so far can be viewed as combinations of components: how candidates are generated, the rules for accepting or selecting candidates, the rules for updating solutions, and the parameters. The following table breaks each method into these components and summarizes what is mainly tuned.

Method	Candidate generation	Acceptance, selection, update	Main parameters
Hill climbing	Neighborhood of the current solution	Move to improving candidates	How the neighborhood is defined
Simulated annealing	Neighborhood of the current solution	Also accept worse candidates probabilistically	Temperature and its cooling schedule
Ant colony optimization	Build paths from pheromone and problem-specific information	Pheromone evaporation and deposit	α, β, ρ, q0, number of ants
Particle swarm optimization	Update of position and velocity	Attraction toward personal best and neighborhood best	ω, φ1, φ2
Artificial bee colony	Neighborhood of a food source	Quality-proportional selection, abandonment of stalled food sources	Population size, abandonment count limit

Methods in papers are published with these component combinations tuned toward the datasets used in their evaluation, so in practice you take a paper’s settings as a starting point and retune the parameters on your own data. There are many methods named after animals, but looking at them by their component structure rather than their names opens up more situations where knowledge from existing methods applies. Grey wolf optimization (GWO) generates candidates around the 3 best solutions of each iteration, moves toward their average, and linearly decreases the coefficient that controls the spread from 2 to 0. In Camacho-Villalón et al.’s decomposition, this is a special case of one standard form of PSO, so tuning knowledge for PSO carries over directly.

A method’s constants are values fitted to the benchmarks its authors used. Aquila Optimizer switches between an exploration phase and an exploitation phase at 2/3 of the iterations, and this 2/3 is a constant set by the designer. Some methods, such as Bald Eagle Search, have a phase that moves through space along a spiral in polar coordinates. The spiral formula and the constants that switch phases can also be treated as components to tune on your own data.

There are two things to check when tuning. The first is performance on benchmarks with the optimum shifted. When a benchmark function has its optimum at the center of the search domain, a method with a habit of pulling candidates toward the center can score well on that habit alone, apart from any ability to solve the problem. Kůdela’s test used the geometric mean, over 13 functions, of the ratio of performance with the optimum moved away from the origin to performance with it at the origin, as a center-bias index measuring the strength of this habit. The more a method does well only when the optimum is at the center, the larger the ratio, and a value above 1E+01 is taken to indicate a tendency to gain an advantage on functions whose optimum lies at the center of the search domain. GWO scored 8.89E+05, Aquila Optimizer 2.26E+05, Bald Eagle Search 2.62E+08, Harris Hawks Optimization 1.62E+05, and PSO 0.97. PSO’s value indicates that its performance barely changes when the optimum is moved. If you apply a method to your own problem, where the optimum may lie away from the center of the search domain, measuring performance with the optimum’s location moved lets you check how much this tendency affects you.

The second is differences between implementations. In Vermetten et al.’s comparison of 294 implementations, algorithms with the same name performed very differently depending on the implementation. The implementation you adopt therefore also has to be measured on your own data. The decision to adopt a method rests on its performance after tuning on your own data, rather than on its ranking in a paper or its novelty. Methods for automating parameter tuning itself are covered in Part 8.

Part 7 moves on to the evaluation functions that set where a search is headed, covering heuristic functions, game evaluation functions, and how to build verifiers.