Tabu-Suche

Tabu-Suche

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 (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 Auswahl einer neuen Lösung. Eine 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 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 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 (Begriffsklärung) — Tabu steht für: Tabu, eine Handlung oder Verhaltensweise, die durch Sitte verboten ist Tabu (Spiel), ein Gesellschaftsspiel Tabu (1931), ein Film aus dem Jahr 1931 von Friedrich Wilhelm Murnau Tabu (1999), der deutsche Titel des japanischen Films …   Deutsch Wikipedia

  • Lokale Suche — Die lokale Suche ist ein Oberbegriff für eine Reihe von metaheuristischen Suchverfahren der kombinatorischen Optimierung. Die Verfahren werden in vielen Variationen dafür genutzt, komplizierte Optimierungsprobleme näherungsweise zu lösen… …   Deutsch Wikipedia

  • Tabusuche — 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

  • Diskrete Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Programmierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige lineare Programmierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Meta-Heuristik — Eine Metaheuristik ist in der Mathematik ein Algorithmus zur näherungsweisen Lösung eines kombinatorischen Optimierungsproblems. Im Gegensatz zu problemspezifischen Heuristiken, die nur auf ein bestimmtes Optimierungsproblem angewendet werden… …   Deutsch Wikipedia

Share the article and excerpts

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