TABU SEARCH

Escaping local optima via memory-guided neighborhood exploration

8
8
0.6
4
Tabu Search (Glover 1986) is a metaheuristic that escapes local optima by maintaining a tabu list — a short-term memory of recently visited solutions that are temporarily forbidden. At each step, the best non-tabu neighbor is selected, even if it worsens the objective. The tenure controls how long a solution remains forbidden. An aspiration criterion overrides the tabu status if a candidate achieves a new global best. Tabu search excels on combinatorial problems like TSP, graph coloring, and scheduling where gradient methods fail. The visualization shows the search trajectory (gold path) navigating a multi-modal landscape — red cells are currently tabu, cyan marks the global best.