Tabu Search

Tabu search is a meta-heuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality. One of the main components of tabu search is its use of adaptive memory, which creates an intelligent search pattern based on strategic choices, as opposed to random selections that are widely applied in other methodologies. Tabu search has connections with other memory-based methodologies, namely, scatter search and path relinking, and they have been extensively applied to many combinatorial optimization problems in general and in particular to several diversity models. Memory-based strategies are the hallmark of tabu search approaches, founded on a quest for “integrating principles,” by which alternative forms of memory are appropriately combined with effective strategies for exploiting them. They are based on principles designed to cross boundaries of feasibility or local optimality, which were usually treated as barriers. The methods based on these principles constitute nowadays the area called adaptive memory programming. Over a wide range of problem settings, the strategic use of memory in these methods has proved to make dramatic differences in the ability to solve challenging problems.