Tabu Search
- Definition
- Tabu Search enhances local search by keeping a short-term memory (the tabu list) of recently visited solutions or moves to avoid cycling back. This lets the search explore new areas and escape local optima. Imagine keeping a short "do not revisit" list while trying neighboring changes, which helps avoid loops. It differs from plain hill-climbing by actively forbidding recent moves, and from population-based methods by focusing on a single evolving solution rather than many candidates.
How does it work?
Tabu Search methods search a space of candidate solutions. They typically define neighbor moves or gradients, evaluate objective functions, and use schedules or memory to escape local optima or to converge reliably.
Examples
- Vehicle routing improvements — Use tabu lists to avoid recent routes and escape cycles in routing heuristics.
- Crew scheduling — Search large combinatorial schedules while forbidding recent swaps to diversify search.
- Combinatorial timetabling — Improve initial solutions with tabu-guided neighborhood moves to respect constraints.
Problems
- Choosing an appropriate tabu list size (too short cycles, too long over-restricts)
- Extra memory and bookkeeping overhead for tracking visited states
- Designing aspiration criteria correctly to avoid missing good solutions
- Still no formal convergence guarantee