## Definition **Tabu Search** is a metaheuristic that augments local search with a **memory** of recently visited solutions (or recent moves) — marking them as "tabu" (forbidden) to avoid cycling. Introduced by Fred Glover (1986). ## The Idea Pure local search greedily picks the best neighbour and converges to a local optimum, then stops. Tabu Search: 1. Always picks the *best non-tabu* neighbour, even if it worsens the objective. 2. Maintains a tabu list of recent solutions / moves. 3. Allows aspiration criteria: a tabu move is allowed if it produces a better-than-best solution. This lets the search **walk out of basins** without random restarts. ## The Algorithm ``` x ← initial solution best ← x tabu_list ← empty while not done: neighbours ← N(x) candidates ← neighbours not in tabu_list (with aspiration overrides) x ← argmax fitness over candidates if f(x) > f(best): best ← x add x's move to tabu_list (remove oldest if at capacity) return best ``` ## Memory Structures ### Short-Term (Recency) The tabu list — fixed-length queue of recent moves. Prevents short cycles. ### Intermediate-Term (Intensification) Track "elite" solutions; periodically restart from them to refine promising regions. ### Long-Term (Diversification) Track which moves have been used heavily; penalise them to push the search into unexplored regions. The interplay of these memories is the algorithm's signature. ## Key Hyperparameters - **Tabu list length.** Too short = cycles; too long = stalls. Often dynamic. - **Aspiration criteria.** When to override the tabu list (typically: better than the global best). - **Diversification triggers.** When to escape stagnant regions. ## Where Tabu Search Wins - **Combinatorial problems** with known neighbourhood structures: scheduling, vehicle routing, graph colouring. - **Vehicle Routing Problem (VRP).** Tabu Search variants are competitive with the best specialised algorithms. - **Quadratic Assignment Problem (QAP).** Tabu Search has won multiple benchmarks. - **Job-shop scheduling.** ## Strengths - **Effective on combinatorial problems** with well-defined neighbourhoods. - **Memory-guided exploration** vs random restart's blind exploration. - **Often competitive with problem-specific algorithms.** ## Weaknesses - **Many hyperparameters.** Tuning is non-trivial. - **Memory overhead** — tabu list management adds bookkeeping. - **Less popular than GA / SA** despite often outperforming them — partially because GA is more pedagogically famous. ## Variants - **Adaptive Tabu Search.** Self-tuning list length. - **Reactive Tabu Search.** Detects cycles and adjusts dynamically. - **Granular Tabu Search.** Larger neighbourhoods explored efficiently. - **Scatter Search.** Population-based generalisation by Glover. ## Comparison | | Simulated Annealing | Genetic Algorithms | Tabu Search | |---|---|---|---| | Memory | None | Population | Explicit tabu list | | Escape from local optima | Stochastic (temperature) | Crossover diversity | Deterministic + memory | | Hyperparameter sensitivity | Medium | High | Medium-high | | Real-world combinatorial wins | Moderate | Some | Many | ## Related - [[Simulated Annealing]] - [[Genetic Algorithms]] - [[Hill Climbing]] - [[Combinatorial Optimization]]