Tabu search

From Wikipedia, the free encyclopedia

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 now 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.

[edit] 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.

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.

[edit] Basic details

• Short term memory uses a recency based tabu list
• Long term memory uses a frequency based tabu list
• Aspiration criteria is basically a single solution, deterministic neighborhood search technique that uses memory (a “tabu list”) to prohibit certain moves, even if they are improving. This makes tabu search a global optimizer rather than a local optimizer.

[edit] 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.