Tabu search
The memory-based single-solution metaheuristic that completes the single-solution axis beside simulated-annealing. Created by Fred Glover (1986, formalized 1989) for combinatorial / discrete optimization (the name is Tongan for “things not to be touched”). Where most of the corpus is population-based and memoryless, tabu search is the corpus’s clearest case of explicit memory as the search driver.
Mechanism
It is local search with two upgrades that let it escape local optima:
- Accept worsening moves — when no improving move exists, take the least-bad one (shared with simulated-annealing; the two are the corpus’s downhill-move-accepting pair).
- Tabu list — record recently visited solutions/move-attributes and forbid returning to them for a tabu tenure, breaking cycles and pushing the search into new territory.
- Aspiration criteria override a move’s tabu status when warranted (e.g. it beats the best solution so far).
- Three memory horizons: short-term (recency/tabu list), intermediate-term (intensification toward promising regions), long-term (diversification to escape plateaus) — a structured take on exploration-vs-exploitation.
Where it sits in the field
- vs simulated-annealing: both single-solution and both accept worsening moves, but SA escapes local optima via a stochastic cooling schedule, while tabu search uses deterministic memory (the tabu list). They’re the two poles of single-solution escape strategy — randomness vs memory.
- vs population methods (genetic-algorithm, particle-swarm-optimization, ant-colony-optimization): those keep many candidates and diversify across the population; tabu search keeps one and diversifies over time via memory.
The No-Free-Lunch read
Tabu search’s strength is combinatorial problems (routing, scheduling) where its move-memory prunes revisits — a different niche from the continuous-space metaheuristics that dominate the population-optimization-benchmark, underscoring again that the binding constraint (discrete vs continuous, memory vs sampling) picks the winner (no-free-lunch-theorem).
Related
simulated-annealing · metaheuristic-optimization · exploration-vs-exploitation · genetic-algorithm · no-free-lunch-theorem