Tabu search

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: 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 [http://spot.colorado.edu/~glover/ Fred Glover] .

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.

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.

Related methods

*Simulated annealing
*Genetic algorithms
*GRASP, or greedy randomized adaptive search procedure
*Ant colony optimization
*Particle swarm optimization
*Cross-entropy method
*Guided Local Search
*Harmony search

More links

[http://www.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS_Gendreau.htm 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.

External links

* [http://paradiseo.gforge.inria.fr/ ParadisEO] is a powerful C++ framework dedicated to the reusable design of metaheuristics, included local search algorithms as the Tabu-Search, the Hill-Climbing...


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Tabu Search — Tabu Suche ist ein iteratives metaheuristisches Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde von Fred Glover in den USA erfunden und seither ständig weiterentwickelt. So wie Genetische Algorithmen (GA) ist… …   Deutsch Wikipedia

  • tabu search — noun A combinatorial search technique used to solve optimization problems by tracking and guiding the search. Compared to simulated annealing, the tabu search heuristic performed well …   Wiktionary

  • Tabu-Suche — ist ein iteratives metaheuristisches Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde von Fred Glover in den USA erfunden und seither ständig weiterentwickelt. So wie Genetische Algorithmen (GA) ist auch Tabu… …   Deutsch Wikipedia

  • Tabu Suche — ist ein iteratives metaheuristisches Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde von Fred Glover in den USA erfunden und seither ständig weiterentwickelt. So wie Genetische Algorithmen (GA) ist auch Tabu… …   Deutsch Wikipedia

  • Tabu — may refer to:*Tabu (also spelled tapu ), a Polynesian cultural concept, from which the word taboo derives * Tabu (film), a 1931 award winning film *Tabu (actress), an Indian actress *Tabu Ley, a Congolese musician *Tabu by Dana, a perfume and… …   Wikipedia

  • Search-based software engineering — (SBSE) is an approach to apply metaheuristic search techniques like genetic algorithms, simulated annealing and tabu search to software engineering problems. It is inspired by the observation that many activities in software engineering can be… …   Wikipedia

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • Búsqueda tabú — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de …   Wikipedia Español

  • Local search (constraint satisfaction) — In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms… …   Wikipedia

  • Guided Local Search — is a metaheuristic search method. A meta heuristic method is a method that sits on top of a local search algorithm to change its behaviour. Guided Local Search builds up penalties during a search. It uses penalties to help local search algorithms …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”