Introduction to Metaheuristics

Parts 2 through 5 built a formidable toolkit, but every tool in it was bought with an assumption. The simplex method needs linearity. Newton's method needs two derivatives. The KKT conditions need constraint qualifications and smoothness. Convexity — the property that made a local answer a global one — needs the problem to be convex, which most interesting ones are not. When the assumptions hold, use those methods: they are faster, they are exact, and they come with certificates. This chapter is about what to do when they do not.

Four kinds of rudeness show up repeatedly in engineering practice:

The combinatorial case deserves a number, because intuition consistently underestimates it. A travelling-salesman tour over \(n\) cities has \((n-1)!/2\) distinct routes. That is not a large number for \(n = 8\); it is \(2520\), and you could enumerate it by hand. For \(n = 20\) it is about \(6.1 \times 10^{16}\), and a machine checking a billion tours per second needs roughly two years. For \(n = 50\) the count exceeds the estimated number of atoms in the observable universe. Enumeration is not slow — it is impossible, and no faster computer will rescue it.

A heuristic (from heuriskein, to find) is a problem-specific rule of thumb that produces a good solution quickly, with no guarantee of quality. "Always visit the nearest unvisited city" is a heuristic for the TSP: it is fast, it is sensible, and it is sometimes badly wrong. Heuristics are built from domain knowledge and do not transfer — the nearest-neighbour rule says nothing about how to schedule a machine shop.

A metaheuristic sits one level up (Greek meta, beyond). It is a problem-independent strategy for guiding a search, a template into which problem-specific pieces are plugged. Simulated annealing does not know what a tour is; it knows how to accept and reject candidate moves. Supply it with a way to represent a solution, evaluate it, and perturb it, and the same code anneals a tour, a truss, or a controller.

One level higher still sits the hyper-heuristic, which searches the space of heuristics rather than the space of solutions — it decides which heuristic to apply next, and is the natural home of automated algorithm selection. The three-level picture is worth fixing:

Metaheuristics are also derivative-free and almost always stochastic. Randomness is not laziness; it is the mechanism that lets a search leave a region that a deterministic rule would never leave, and it is why two runs on the same instance give different answers. A metaheuristic result is therefore a sample, and honest reporting quotes a best, a mean, and a standard deviation over many runs — never a single lucky number.

Nearly every metaheuristic is a modification of one embarrassingly simple idea. Take a solution, look at solutions "near" it, move to a better one, repeat. This is local search, and making it precise requires a single new concept: the neighbourhood.

The neighbourhood is defined by the move operator, and choosing it is the single most consequential modelling decision in the whole of Part 6 — it is what imposes a geometry on a set that has none. Flip one bit of a binary string; swap two cities in a tour; add a small Gaussian perturbation to a real vector. Each choice creates a completely different landscape over the same solutions.

With a neighbourhood in hand, hill climbing (for a minimisation problem, more honestly descent) writes itself: from \(\mathbf{x}_k\), examine \(N(\mathbf{x}_k)\), move to a neighbour with lower cost, stop when none exists. Two variants differ in how much of the neighbourhood they inspect — steepest ascent evaluates all of it and takes the best; first improvement takes the first improving neighbour it stumbles on, which is cheaper per step and often better overall because it wastes less effort.

And here is the flaw that defines the entire field. Hill climbing stops when no neighbour is better — but "no neighbour is better" is a statement about \(N(\mathbf{x})\), not about \(S\). The point it stops at is a local optimum with respect to that neighbourhood, and there is no reason it should be global. Change the move operator and the same solution may stop being a local optimum at all.

The right-hand picture names the second key idea. The basin of attraction of a local optimum is the set of starting points from which pure descent ends there. Descent is deterministic, so the basins partition the search space, and the entire outcome of a hill-climbing run is decided by the initial point. If the global optimum's basin occupies 1% of the space, a single random start finds it 1% of the time — and no amount of clever descent changes that arithmetic.

Every metaheuristic in this book is an answer to one question, and the question is not "which direction is downhill?" It is: given a finite budget of function evaluations, how much of it should be spent examining new regions, and how much refining the best region found so far?

The two failure modes have names. Pure exploration is random search — unbiased, robust, and hopeless: it never uses what it learns. Pure exploitation is hill climbing — efficient and blind, converging fast to whatever it happened to land near. Useful methods live between, and most of them shift the balance over time: explore early, when the incumbent is worthless and information is cheap; exploit late, when the budget is nearly gone and the best region is known.

Read the classical methods of Parts 4 and 5 on this dial and they sit at the far right: steepest descent is pure exploitation, which is exactly why it is so good on convex problems (where exploitation is all you need) and so useless on rugged ones. Recognising the dial explains why parameters like a cooling schedule, a mutation rate, or an inertia weight are not incidental tuning constants — each is the mechanism by which its algorithm sets the balance.

If hill climbing's sole defect is that it halts at a local optimum, then the entire design space of metaheuristics is the space of answers to one question: how do you get out? Remarkably, there are only four fundamental devices, and every algorithm in Part 6 is a combination of them.

The first device is the most counter-intuitive and the most important: a search that never accepts a worse solution can never leave a valley. Getting out requires climbing the wall, which means going uphill, which means temporarily accepting a worse objective value. Simulated annealing makes this explicit with the Metropolis criterion, which accepts an uphill move of size \(\Delta\) with probability

Read the formula as a policy on the dial of Section 23-4. Large \(T\): the exponent is near zero, almost everything is accepted, the search wanders — exploration. Small \(T\): uphill moves are rejected almost surely and the method degenerates into hill climbing — exploitation. The cooling schedule that lowers \(T\) over the run is the exploration-to-exploitation slide, made into arithmetic. Notice also that the criterion is size-aware: a slightly worse solution is accepted far more readily than a disastrous one.

The fourth device is different in kind. A population does not merely search several basins in parallel — that would be no better than several independent runs. Its power is recombination: two mediocre solutions, good in different ways, can be combined into one that is better than both. That is a mechanism no single-solution method possesses, and it is why Chapter 24 opens the population half of Part 6.

Hundreds of metaheuristics have been published, many differing only in the animal on the cover. Three cuts organise the useful ones.

The first and most informative cut is how many solutions are carried. Single-solution (or trajectory) methods maintain one incumbent and trace a path through the space; they are simple, memory-light, and strong exploiters. Population-based methods maintain a set, sample many regions at once, and can recombine; they explore better and cost proportionally more evaluations.

The second cut is memory: does the method remember where it has been? Simulated annealing is memoryless — its next move depends only on the current point and the temperature, making it a Markov chain, which is precisely what allows its convergence to be proved. Tabu search is built entirely on memory. Ant colony optimization stores memory outside the solutions altogether, in a shared pheromone matrix.

The third cut is inspiration — annealing from metallurgy, evolution from biology, swarming from ethology. It is the cut that sells papers and the least useful of the three. Judge a method by its mechanism, not its metaphor: a "firefly algorithm" whose fireflies do what particles already do is not a new idea.

Strip away the metaphors and every method in Part 6 has the same skeleton. Learning it once means Chapters 24–26 are about filling in three boxes, not about learning three algorithms.

Because there is no optimality condition to check — no \(\nabla f = \mathbf{0}\) to satisfy — a metaheuristic never knows it is finished. Stopping is a budget decision, taken on one of these grounds: a fixed number of evaluations or wall-clock seconds; stagnation (no improvement in the last \(k\) iterations); a target value reached; or, for population methods, collapse of diversity. Note the honest consequence: the best solution found is reported, but never certified. Always keep the incumbent best separately from the current point — a search that wanders uphill will otherwise throw away the answer it already found.

Finally, a theorem that should temper any enthusiasm. Wolpert and Macready's No Free Lunch result says that averaged over all possible objective functions, every search algorithm has identical expected performance. No metaheuristic is universally best; a method that beats random search on one class of problems must lose to it on another.

So when a paper claims a new metaheuristic is best "on average", the theorem says the claim is either meaningless or an admission that the benchmark set was chosen favourably. The right question is never "which metaheuristic is best?" but "what does my landscape look like, and which method's assumptions fit it?"

Several of these ask for judgement rather than arithmetic — say which method fits and why, in terms of the four escape devices and the exploration–exploitation dial. Difficulty rises down the list.