Tabu search

Tabu search is a mathematical optimization method, belonging to the class of local search techniques. Tabu search enhances the performance of a local search method by using memory structures. Tabu search is generally attributed to Fred Glover.

Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution $x$ to a solution $x'$ in the neighbourhood of $x$, until some stopping criterion has been satisfied. To explore regions of the search space that would be left unexplored by the local search procedure and—by doing this—escape local optimality, tabu search modifies the neighbourhood structure of each solution as the search progresses. The solutions admitted to $N^{*}(x)$, the new neighbourhood, are determined through the use of special memory structures. The search then progresses by iteratively moving from a solution $x$ to a solution $x'$ in $N^{*}(x)$.

Perhaps the most important type of short-term memory to determine the solutions in $N^{*}(x)$, also the one that gives its name to tabu search, is the use of a tabu list. In its simplest form, a tabu list contains the solutions that have been visited in the recent past (less than $n$ moves ago, where $n$ is the tabu tenure). Solutions in the tabu list are excluded from $N^{*}(x)$. Other tabu list structures prohibit solutions that have certain attributes (e.g. traveling salesman problem (TSP) solutions that include certain arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next $n$ moves). Selected attributes in solutions recently visited are labelled tabu-active. Solutions that contain tabu-active elements are tabu. This type of short-term memory is also called recency-based memory.

Tabu lists containing attributes are much more effective, although they raise a new problem. When a single attribute is forbidden as tabu, typically more than one solution ends up being tabu. Some of these solutions that must now be avoided might be of excellent quality and might not have been visited. To overcome this problem, aspiration criteria are introduced which allow overriding the tabu state of a solution to include it in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently best known solution.

Related methods

Simulated annealing is a related global optimization technique which traverses the search space by generating neighbouring solutions of the current solution. A superior neighbour is always accepted. An inferior neighbour is accepted probabilistically based on the difference in quality and a temperature parameter. The temperature parameter is modified as the algorithm progresses to alter the nature of the search.

Genetic algorithms maintain a pool of solutions rather than just one. The process of finding superior solutions mimics that of evolution, with solutions being combined or mutated to alter the pool of solutions, with solutions of inferior quality being discarded.

GRASP or greedy randomized adaptive search procedure repeatedly generates a greedy randomized feasible solution and applies local search starting from that solution. The best locally optimal solution found over all GRASP iterations is returned as the GRASP solution.

Ant colony optimization uses many artificial ants (or agents) that incrementally build solutions. Artificial ants deposit artificial pheromones (to this ant-inspired behavior is due their name) that are used by later ants to guide their search. Ant colony optimization is particularly useful for problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied.

Particle swarm optimization maintains a population of solutions rather than a single solution. This algorithm is based on simplified model of social behavior. Here each particle can be thought of as a state of mind. This model simulates how our beliefs and attitudes are influenced by other humans: evaluation, comparison and imitation. Every particle improves its fitness using its experience and its companions' experience, and particles finally reach a, possibly local, optimum.

The Cross-entropy method generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.

The Guided Local Search uses penalties to discourage the search from revisiting local optimum. The penalties can be seen as a way to define the tabu list. A utility criteria is used to evaluate the usefulness of penalizing different features of the solution space.

Harmony search mimics musical improvization process. In the process, each musician plays a note to make a best harmony all together.

Basic Details

• One of the main problems of all methods based on Local Search approaches, and this includes TS in spite of the beneficial impact of tabus, is that they tend to be too “local” (as their name implies), i.e., they tend to spend most, if not all, of their time in a restricted portion of the search space. The negative consequence of this fact is that, although good solutions may be obtained, one may fail to explore the most interesting parts of the search space and thus end up with solutions that are still pretty far from the optimal ones.

• Sometimes Tabus may prohibit atractive moves, even when there is no danger of cycling, or they may lead to an overall stagnation of the searching process. A solution for this problem is the aspiration criteria. It accepts improving solution even if generated by a tabu move.

More links

An introduction to Tabu search

Bibliography

• Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer, Norwell, MA.
• Glover, F. "Tabu Search — Part I", ORSA Journal on Computing 1989 1: 3, 190-206.
• Glover, F. "Tabu Search — Part II", ORSA Journal on Computing 1990 2: 1, 4-32.
• Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.