Tabu Search

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 auch Tabu-Suche ein heuristisches Optimierungsverfahren. Jedoch anders als bei Genetischen Algorithmen geht man beim klassischen Tabu Search in jedem Iterationsschritt von nur einer Lösung aus. Tabu-Suche ist also ein trajektions-basiertes Verfahren, da dessen Ablauf einer Trajektorie im Suchraum folgt.

Inhaltsverzeichnis

Grundidee

Um Zyklen beim Traversieren des Lösungsraumes zu vermeiden, wird bei der Tabu-Suche mithilfe von während der Suche gesammelten Daten eine Tabu-Liste erstellt. Die auf dieser Liste stehenden Züge oder Lösungen dürfen in der aktuellen Iteration nicht oder nur bei zusätzlicher Erfüllung eines Aspirationskriteriums ausgeführt werden.

Eine klassische und schnell zu implementierende Tabu-Strategie ist dabei, das Komplement des in einer Iteration ausgeführten Zuges für eine bestimmte Tabu-Dauer in der Tabu-Liste zu speichern. Ein anderer Ansatz verbietet die Veränderung von bestimmten Teilbereichen einer Lösung für eine bestimmte Zeit.

Ablauf

  1. In der Eingangsphase wird eine zum Beispiel zufällig oder nach einer geeigneten Heuristik eine Initial-Lösung erzeugt, von der aus der Algorithmus startet. Danach beginnt die eigentliche Optimierung.
  2. Von der aktuellen Lösung ausgehend, erzeugt man eine Nachbarschaft von Lösungen. Dies stützt sich auf das Vorhandensein einer Nachbarschaftsfunktion N(x). Die von dieser Funktion erzeugte Menge von benachbarten Lösungen zu x sollte zumindest ein Element beinhalten.
  3. Danach erfolgt die Selektion. Eine neue Lösung wird als die Aktuelle gewählt, wenn sie die beste Lösung der Nachbarschaft darstellt und nicht als Tabu klassifiziert worden ist (Tabu-Kriterium).
  4. Ausgehend vom ausgeführten Zug wird die Tabu-Liste aktualisiert. Je nach gewählter Tabu-Strategie kann zum Beispiel das Komplement des Zuges für eine bestimmte Anzahl an Iterationen tabuisiert werden.

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

Literatur

  • GLOVER, F. 1986. Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549.
  • GLOVER, F., and LAGUNA, M. 1997. Tabu Search. Kluwer Academic Publishers.
  • BATTITI, R., and TECCHIOLLI, G. 1994. The reactive tabu search. ORSA J. Comput. 6, 2, 126–140.
  • HEINRICI, A. 1996. Leistungsvergleich von Nachbarschaftssuchverfahren. VWF Verlag für Wissenschaft und Forschung, Berlin, ISBN 3-930324-76-8

Links


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   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”