Taboo search

from Wikipedia, the free encyclopedia

Taboo search is an iterative metaheuristic process for solving or approximating complex problems. The algorithm was invented by Fred W. Glover in the USA in 1986 and has been continuously developed since then.

Just like evolutionary algorithms , for example , the taboo search is a heuristic optimization process . In contrast to evolutionary algorithms, the classic taboo search assumes only one solution in each iteration step. The taboo search is therefore a trajectory-based process, since its sequence follows a trajectory in the search space.

Basic idea

In order to avoid cycles when traversing the solution space, a taboo list is created in the taboo search with the help of data collected during the search . The moves or solutions on this list may not be carried out in the current iteration or only when an aspiration criterion is additionally fulfilled .

A classic taboo strategy that can be implemented quickly is to save the complement of the move performed in one iteration in the taboo list for a certain taboo duration . Another approach prohibits changing certain parts of a solution for a certain period of time.

procedure

  1. In the input phase , an initial solution is generated (for example, randomly or after a suitable heuristic), starting from which the algorithm. Then the actual optimization begins.
  2. Starting from the current solution, one creates a neighborhood of solutions. This relies on the presence of a neighborhood function . The set of neighboring solutions to generated by this function should contain at least one element.
  3. A new solution is then selected. A solution is chosen as the current one if it represents the best solution in the neighborhood and has not been classified as taboo (taboo criterion).
  4. The taboo list is updated based on the move made. Depending on the taboo strategy chosen, for example, the complement of the move can be taboo for a certain number of iterations.

Pseudocode

aktuelleLösung = ErzeugeStartLösung()
SOLANGE (Abbruchkriterium nicht erfüllt)
   nachbarschaft = ErzeugeNachbarschaft(aktuelleLösung)
   Evaluiere(nachbarschaft)
   nachbarschaft = EntferneTabuZüge(nachbarschaft)
   aktuelleLösung = WähleBestenZug(nachbarschaft)
   Tabuisiere(AusgeführtenZug, TabuDauer) 
ENDE SOLANGE

swell

  1. ^ F. Glover and C. McMillan: The general employee scheduling problem: an integration of MS and AI . In: Computers and Operations Research . 1986.

literature

  • F. Glover: Future paths for integer programming and links to artificial intelligence. In: Comput. Opera. Res. 13, 1986, pp. 533-549.
  • F. Glover, M. Laguna: 1997. Tabu Search. Kluwer Academic Publishers, 1997.
  • R. Battiti, G. Tecchiolli: The reactive tabu search. In: ORSA J. Comput. 6, 2, 1994, pp. 126-140.
  • A. Heinrici: Performance comparison of neighborhood search procedures. VWF Verlag for Science and Research, Berlin, 1996, ISBN 3-930324-76-8 .

Web links