Tabu Search: Short-Term Memory in AI Optimization

This article explores how Tabu Search, a powerful metaheuristic algorithm in artificial intelligence, solves complex combinatorial optimization problems by escaping local optima. We will examine the core mechanism of the algorithm: the Tabu List, which acts as a short-term memory structure that tracks and forbids recent moves to prevent infinite cycling. Finally, we will cover how tabu tenure and aspiration criteria balance this memory system to ensure the algorithm efficiently discovers global optima.

In combinatorial optimization, basic local search algorithms often fail because they get trapped in local optima—solutions that are better than their immediate neighbors but worse than the global best solution. To escape a local optimum, an algorithm must occasionally accept a worse move. However, doing so creates a new problem: cycling. If an algorithm moves from a local optimum to a slightly worse neighbor, its very next step might simply be to move right back to the local optimum it just left, resulting in an infinite loop.

Tabu Search prevents cycling by implementing a short-term memory structure known as the Tabu List. Instead of remembering only the current state, the algorithm remembers the recent history of the search. Whenever the algorithm makes a move from one solution to another, that move (or the specific attribute that changed) is recorded in the Tabu List and labeled as "tabu" (forbidden). During subsequent iterations, the algorithm is strictly prohibited from executing any move present on this list, forcing it to explore new regions of the solution space rather than retracing its steps.

Because storing complete solutions is computationally expensive and memory-intensive, the Tabu List typically stores move attributes rather than whole states. For example, in the Traveling Salesperson Problem, if the algorithm swaps the order of City A and City B, the Tabu List simply records the pair (A, B). For a set number of future iterations, the algorithm cannot swap City A and City B again, even if doing so would immediately improve the current tour's length.

The Tabu List operates as a First-In, First-Out (FIFO) queue governed by a parameter called "tabu tenure." Tabu tenure defines the exact number of iterations a move remains forbidden. Once a move has been on the list for the duration of the tenure, it expires, is removed from the list, and becomes an allowable move again.

Choosing the right tabu tenure is critical for search performance:

• Short Tenure: If the memory is too short, the algorithm may still fall into larger cycles and fail to escape deep local optima.
• Long Tenure: If the memory is too long, too many moves become forbidden, overly restricting the search space and potentially blocking the algorithm from finding the optimal path.

Storing move attributes rather than full solutions can sometimes be overly restrictive, accidentally forbidding moves that lead to unvisited, high-quality solutions. To counter this, Tabu Search uses "aspiration criteria." An aspiration criterion is a rule that overrides a move's tabu status. The most common criterion is simple: if a forbidden move yields a solution that is better than the best-known solution found so far in the entire search, the tabu restriction is ignored. Because this new solution is superior to anything seen before, it is guaranteed not to be a previously visited state, meaning there is zero risk of cycling.