Simulated Annealing and Tabu Search

Chapters 24 and 25 were population methods: a crowd of candidate solutions searched in parallel, and progress came from how members shared information. The two methods in this chapter are single-solution methods — also called trajectory methods, because the algorithm maintains exactly one current solution and traces a path through the search space, replacing that solution with a neighbour at each step. There is no crowd, no crossover, no swarm. There is one point, moving.

The natural way to move one point is local search: look at the neighbours of the current solution, step to the best one, and repeat. This is hill climbing (or, for a minimisation, steepest descent by trial). It is fast, simple, and greedy — and greed is exactly its downfall. The instant every neighbour is worse than where you stand, local search halts. It has found a local optimum, and it has no way to tell whether that is the best point in the whole space or merely the bottom of the nearest ditch.

Every escape mechanism must thread a needle. Accept uphill moves too freely and the walker never settles — the search is a random walk that finds nothing. Accept them too rarely and it re-freezes into the first local optimum, exactly as plain descent did. The two methods manage this trade-off by opposite means. Simulated annealing makes the decision stochastic and lets a temperature parameter slide it from generous to strict. Tabu search makes the decision deterministic — always take the best neighbour available — and uses memory to stop the walker from immediately undoing an uphill step and cycling forever.

Simulated annealing, introduced by Kirkpatrick, Gelatt and Vecchi in 1983, is a near-literal transcription of a metallurgical process. To anneal a metal, you heat it until its atoms are jostling freely, then cool it slowly. Given time at each temperature, the atoms drift into the low-energy, highly ordered arrangement of a crystal — the global minimum of the material's energy. Cool too fast — quench it — and the atoms freeze wherever they happen to be, locked into a brittle, high-energy amorphous solid. That is a local minimum, reached by moving too greedily toward the nearest low-energy state.

The bridge to optimization is a dictionary. The objective function \(f\) plays the role of energy \(E\); a candidate solution is a configuration of the system; and a fictitious temperature \(T\) becomes the algorithm's single control knob. Minimising \(f\) is then just annealing the system to its ground state.

Physics also hands us the acceptance rule. At thermal equilibrium a system occupies a state of energy \(E\) with probability proportional to the Boltzmann factor \(e^{-E/kT}\). The consequence that matters is the relative likelihood of two states differing in energy by \(\Delta E\):

Read what this says physically. When \(T\) is large, the exponent is near zero and the ratio is near one: a higher-energy state is almost as likely as a lower one, so the system roams freely across energy barriers. As \(T\) falls, the ratio collapses toward zero: high-energy states become vanishingly unlikely, and the system is confined to the lowest energies it can find. That single knob slides the system from free exploration to strict exploitation — and it is the whole idea we are about to borrow. Metropolis and colleagues had already, in 1953, turned this factor into a rule for sampling such a system; annealing simply cools that rule.

Drop the Boltzmann constant \(k\) — it only sets units — and the rule for whether to accept a proposed move becomes the heart of the method. From the current solution generate a neighbour, and let \(\Delta E = f(\mathbf{x}_{\text{new}}) - f(\mathbf{x}_{\text{current}})\) be the change in objective. For a minimisation:

Two limits reveal the whole character of the method. At high \(T\), \(e^{-\Delta E/T} \to 1\): nearly every move is accepted and the walker performs an almost unbiased random walk — pure exploration, oblivious to the landscape. At low \(T\), \(e^{-\Delta E/T} \to 0\) for any \(\Delta E > 0\): only improving moves survive, and simulated annealing degenerates into plain greedy descent — pure exploitation. The art is the transition between them, governed by the cooling schedule of the next section.

The complete procedure is short enough to state in full:

The cooling schedule — how \(T\) is lowered — is to simulated annealing what the inertia schedule is to PSO and the evaporation rate is to ACO: the single dial that trades speed of convergence against quality of solution. Cool too fast and you quench into a local optimum; cool too slowly and you waste an enormous evaluation budget on a search that is barely making progress. Three schedules dominate.

The geometric rule is what almost everyone actually runs. A typical setup takes \(\alpha = 0.95\), holds a fixed number of moves at each temperature, and starts \(T_0\) high enough that around 80% of moves are accepted initially. It is cheap, robust, and has one free parameter with an intuitive meaning: \(\alpha\) closer to 1 means slower cooling, more thorough search, and more evaluations.

The logarithmic schedule is the one the theory loves. Geman and Geman proved that if the temperature is lowered no faster than \(T_k \ge c/\ln(k+1)\) for a large enough constant \(c\), simulated annealing converges to the global optimum with probability one. This is a genuine and remarkable guarantee — no other metaheuristic in this book has one so clean.

Tabu search, developed by Fred Glover in 1986, escapes local optima by a completely different philosophy. Where annealing is stochastic and memoryless — the next move depends only on the current state, never on the path taken — tabu search is deterministic and built entirely around memory. Its guiding metaphor is not physics but a determined explorer with a notebook.

The core rule is bold: at every step, move to the best solution in the neighbourhood — even if it is worse than where you stand. Plain local search stops when all neighbours are worse; tabu search does not stop, it simply takes the least-bad neighbour and keeps walking. That single change lets the walker climb out of any local optimum on the very next step.

But it creates an obvious disaster. If you are at a local minimum and forced to step to the least-bad neighbour, the best move from that neighbour is usually to step straight back down into the minimum you just left. The walker oscillates between the two forever. The fix is the idea that names the method: forbid it. A tabu list records recently visited solutions (or, more commonly, the moves that produced them) and marks them tabu — off-limits — for a while, so the walker cannot immediately reverse itself and is driven onward into new territory.

The full loop mirrors local search with two additions — a memory, and the forced best-admissible move:

Three refinements turn the bare idea into a working algorithm, and each is a lesson in how memory should be used.

The first is tabu tenure: how many iterations a move stays forbidden. It is the direct analogue of temperature — the knob that balances exploration against exploitation. Too short a tenure and the search cycles, because a reversed move becomes legal again before the walker has left the neighbourhood. Too long a tenure and too many good moves are locked out, driving the search away from promising regions and stalling it. Typical tenures are small — often a handful of iterations, sometimes scaled to the problem size, sometimes drawn randomly from a range to avoid pathological cycles.

The second refinement fixes an obvious flaw in blind forbidding. Because the tabu list stores move attributes, not whole solutions, it sometimes forbids a move that would lead somewhere excellent — better than anything seen so far — merely because that move's attribute is currently tabu. Overriding the tabu status in that case is the aspiration criterion.

The first two refinements use short-term memory — the recency-based tabu list, concerned only with the last few iterations. Powerful implementations add long-term memory that records the whole history of the search and drives two strategic behaviours:

Simulated annealing and tabu search solve the same problem — how a single walker escapes a local optimum — and it is worth seeing them side by side before folding them into the larger picture of Part 6.

Now widen the lens to all five metaheuristics of Part 6. The deepest division is not physical or biological inspiration — it is how many solutions the algorithm carries at once.

The through-line of Part 6 now closes. Every method here — population or trajectory — lives or dies by one thing: its willingness to move away from what currently looks best. A population resists its own consensus through mutation, inertia or evaporation. A single walker resists its own greed through a random uphill die-roll or a memory that forbids retreat. Different vocabulary, one principle: an optimizer must be built to do the locally wrong thing, on purpose, so it can find the globally right one.

For the annealing problems, remember that only a positive \(\Delta E\) (a worsening move) needs the exponential — improving moves are automatic. For the tabu problems, always list the admissible neighbours first, then test any tabu move against aspiration. Difficulty rises down the list.