Helpful context:

Local search gets stuck at local optima. Simulated annealing escapes via randomness - accept worse solutions with some probability, then cool. Tabu search escapes via memory. Keep a list of recently visited solutions and forbid revisiting them. This forces exploration beyond local optima - and the memory itself becomes a sophisticated guide for where to search next.

Fred Glover introduced tabu search in 1986. For Job Shop Scheduling, a specific tabu search algorithm held the world record for benchmark instances for decades. Memory, it turns out, is a powerful optimization tool.

The Tabu List

The core idea: at each step, we’re willing to move to a worse neighbor, as long as we haven’t been there recently. We maintain a tabu list of recently performed moves (not full solutions - storing full solutions would be too expensive), and we forbid reversing those moves for the next $k$ iterations.

The integer $k$ is called the tabu tenure.

At each iteration:

  1. Generate the neighborhood $N(s)$ of the current solution.
  2. Remove any move that is tabu (subject to an aspiration criterion - see below).
  3. Move to the best non-tabu neighbor - even if it’s worse than the current solution.
  4. Add the just-executed move to the tabu list (as a FIFO queue of length $k$). Remove the oldest entry if the list is full.

The critical difference from hill climbing: we always move, even to worse neighbors. And we can’t immediately undo the move we just made (it’s on the tabu list). This forces the algorithm to keep moving, cycling through different parts of the solution space rather than oscillating between two neighbors.

Tabu tenure. If $k$ is too small (say $k = 1$), the algorithm can cycle among a small set of solutions. If $k$ is too large, too many moves are forbidden and the algorithm can’t move at all. Typical values are $k \in [5, 20]$, often set to roughly $\sqrt{n}$ where $n$ is the problem size.

The Aspiration Criterion

A tabu move might lead somewhere great - better than anything seen before. It would be counterproductive to forbid such a move. The aspiration criterion overrides tabu status: a tabu move is allowed if it produces a solution better than the best known solution so far.

Formally, accept a tabu move producing $s'$ if:

$$f(s') < f(s^*),$$

where $s^*$ is the best solution found during the entire run.

This keeps the algorithm from being overly rigid. The tabu list prevents short-term cycling; the aspiration criterion ensures we never pass up a genuinely good solution just because of a bookkeeping rule.

Three Layers of Memory

What makes tabu search distinctive - and powerful - is its layered memory structure. We can operate at three different timescales simultaneously.

Short-term memory (recency): the tabu list. Prevents immediate cycling by forbidding the recent past. This is the core mechanism.

Medium-term memory (intensification). Track which regions of the solution space have produced good solutions. Periodically restart from the best known solution, or bias the neighborhood evaluation toward attributes that appeared in previously good solutions. This focuses effort on promising areas.

Long-term memory (diversification). Track the frequency with which each attribute appears across all visited solutions. When the search has been concentrated in one region for too long, add a frequency penalty to the objective:

$$\tilde{f}(s') = f(s') + \lambda \sum_i p_i \cdot \mathbf{1}[\text{attribute } i \in s'],$$

where $p_i$ is the frequency of attribute $i$ and $\lambda$ controls the diversification strength. This pushes the search toward under-explored attributes and away from regions it’s visited repeatedly.

The interplay between these three memories is what makes sophisticated tabu search algorithms hard to tune but powerful when tuned well. Intensification says: stay here, this region is good. Diversification says: leave, you’ve been here too long. Short-term memory prevents the immediate backtracks that would make neither strategy effective.

Discomfort check. Tabu search has many parameters: tabu tenure, aspiration criterion, intensification triggers, diversification strength. Isn’t this just overfitting to the problem?

Yes, to some extent. Tabu search is a framework, not a single algorithm. Its strength is precisely that it can incorporate domain knowledge through its memory structures - the definition of a “move,” what gets put on the tabu list, how frequency is tracked, when to intensify versus diversify. Its weakness is that this flexibility requires careful problem-specific tuning. The world-record tabu search for Job Shop Scheduling uses a very specific neighborhood (swapping adjacent operations on the critical path) and a very specific tabu list (the pair of operations that were swapped). That specificity is what makes it so good. A generic tabu search without that structure would be mediocre.

Choosing the tabu tenure $k$ is the most sensitive design decision. Reactive tabu search adjusts $k$ automatically:

  • If a solution is visited that was also visited recently, increase $k$ (the search is cycling - force longer memory).
  • If solutions haven’t repeated for many iterations, decrease $k$ (the search is exploring well - allow more moves).

This makes the algorithm more robust across different problem instances and reduces the most critical tuning parameter.

Tabu Search vs. Simulated Annealing

Both are metaheuristics for escaping local optima. Their mechanisms are different in character:

Property Simulated annealing Tabu search
Escape mechanism Probabilistic acceptance of worse solutions Forbidden-move list forces exploration
Memory Memoryless (Markov) Explicit tabu list, frequency tracking
Determinism Stochastic Deterministic given tabu list
Theoretical basis MCMC, Boltzmann distribution No clean theoretical framework
Primary tuning Temperature schedule Tabu tenure, memory parameters
Best for Smooth landscapes, continuous problems Structured combinatorial problems

Tabu search is preferred when reproducibility matters (it’s deterministic), when the neighborhood can be evaluated efficiently with incremental updates, or when domain knowledge can be embedded in the memory structures. SA is preferred when the problem has a natural energy analogy and the landscape is smooth.

Applications

Job Shop Scheduling. Assign $n$ jobs to $m$ machines, each job requiring operations in a fixed order on specific machines, minimizing makespan. The TSAB algorithm (Nowicki and Smutnicki, 1996) uses tabu search on a neighborhood of swapping two adjacent operations on the critical path. It held the record for the classic Ft10 benchmark for many years and remains competitive with the best known algorithms.

Vehicle Routing Problem. Find minimum-cost delivery routes for a fleet of vehicles with capacity constraints. Tabu search moves that relocate a customer from one route to another, or swap customers between routes, are consistently near-optimal and appear in commercial logistics software.

Network Design. Decide which network links to build to minimize cost while satisfying connectivity requirements. Long-term diversification memory is especially important here - the search needs to explore radically different network topologies.

Summary

Memory layer Timescale Mechanism Purpose
Short-term (tabu list) Last $k$ moves Forbid reversing recent moves Prevent cycling
Aspiration criterion Per move Override tabu if solution is best-known Don’t miss great solutions
Medium-term (intensification) Occasional restarts Bias toward attributes of good solutions Exploit good regions
Long-term (diversification) Extended runs Penalize frequent attributes Escape over-visited regions

Tabu search turns memory into a search strategy. The tabu list prevents the immediate cycling that makes local search ineffective. The aspiration criterion keeps the algorithm from being overly rigid. And the long-term memory gives the algorithm a kind of institutional knowledge - a record of where it’s been and how good those places were - that guides exploration in a way that pure randomness cannot.

Read next: