📂Optimization

Tabu Search in Optimization Theory

Terminology

In optimization problems, tabu search is, literally, a meta-heuristic technique that imposes taboo restrictions to prevent repeated exploration.

Description

Tabu search was proposed by Glover in 1986 and is called a meta-heuristic because it can be applied to any optimization problem¹. Regardless of whether tabu search is actually useful for a given problem, the idea of tabu search can be applied—whatever the theoretical background or the particular algorithm—by defining a neighborhood and a tabu list.

For example, in a route optimization problem, the neighborhood of a given path $P$ can be defined as the set of paths that differ by only one edge. Applying tabu search to route exploration means computing the value of the objective function, exploring the neighborhood first, and adding those paths that do not aid optimization to the tabu list to avoid unnecessary evaluations. By investing the resources saved in this way into deeper and broader search, one ultimately pursues better optimization.

If we can assume the objective function is a continuous function in a Euclidean space, then it can be more efficient in the short term to search areas that are even slightly more promising rather than thoroughly exploring regions with poor function values. From an optimization standpoint, by adding poor solutions to the tabu list, if a new candidate solution is sufficiently close to one of the entries on the tabu list―in other words, if it lies in the neighborhood―there is no need to probe that solution further. Thus, tabu search can be applied anywhere—whether the problem is discrete or continuous, and regardless of the method used—so long as the concept of places “not worth further exploration” is clearly defined².