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: once a potential solution has been determined, it is marked as "taboo" ("tabu" being a different spelling of the same word) so that the algorithm does not visit that possibility repeatedly. Tabu search is attributed to Fred Glover.

Contents

[edit] Basic details

Tabu search is a metaheuristic algorithm that can be used for solving combinatorial optimization problems, such as the traveling salesman problem (TSP). 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 (see 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 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 memory structure used to determine the solutions admitted to N * (x), is the tabu list. In its simplest form, a tabu list is a short-term memory which contains the solutions that have been visited in the recent past (less than n iterations ago, where n is the number of previous solutions to be stored (n is also called the tabu tenure)). Tabu search excludes solutions in the tabu list from N * (x). A variation of a tabu list prohibits solutions that have certain attributes (e.g., solutions to the traveling salesman problem (TSP) which include undesirable 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 labeled "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 can be more effective for some domains, although they raise a new problem. When a single attribute is marked as tabu, this typically results in more than one solution being tabu. Some of these solutions that must now be avoided could be of excellent quality and might not have been visited. To mitigate this problem, "aspiration criteria" are introduced: these override a solution's tabu state, thereby including the otherwise-excluded solution in the allowed set. A commonly used aspiration criterion is to allow solutions which are better than the currently-known best solution.

[edit] Example: Traveling salesman problem

The traveling salesman problem (TSP) is often used to show the functionality of tabu search. The TSP involves finding an ordering of travel between cities, such that the distance traveled is minimized. For example, if city A and city B are next to each other, while city C is farther away, the total distance traveled will be shorter if cities A and B are visited one after the other, before visiting city C. Since finding an optimal order of visiting cities in the TSP is NP-hard, heuristic-based approximation methods are useful for approaching optimality.

Tabu search can be used to find a satisficing solution for the TSP. First, tabu search starts with an initial solution, which can be generated according to the nearest neighbor algorithm. To create new solutions, the order that two cities are visited is swapped. The distance for the total travel between all the cities is used to judge how good one solution is over another. To prevent cycles and to get out of local optima, a solution is added to the tabu list if it is accepted into N * (x), the solution neighborhood. New solutions continue to be created until some stopping criteria, such as an arbitrary number of iterations, is met. Once tabu search stops, the best solution is the solution with the shortest distance for the total travel between all cities.

[edit] Related methods

[edit] More links

An introduction to Tabu search

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

[edit] External links

  • ParadisEO is a powerful C++ framework dedicated to the reusable design of metaheuristics, included local search algorithms as the Tabu-Search, the Hill-Climbing...