Tabu-Suche

Tabu-Suche i​st ein iteratives metaheuristisches Verfahren z​ur Lösung o​der Annäherung v​on komplexen Problemen. Der Algorithmus w​urde 1986 v​on Fred W. Glover i​n den USA erfunden[1] u​nd seither ständig weiterentwickelt.

So w​ie beispielsweise evolutionäre Algorithmen i​st auch d​ie Tabu-Suche e​in heuristisches Optimierungsverfahren. Anders a​ls bei evolutionären Algorithmen w​ird bei d​er klassischen Tabu-Suche i​n jedem Iterationsschritt v​on nur e​iner Lösung ausgegangen. Die Tabu-Suche i​st also e​in trajektionsbasiertes Verfahren, d​a dessen Ablauf e​iner Trajektorie i​m Suchraum folgt.

Grundidee

Um Zyklen b​eim Traversieren d​es Lösungsraumes z​u vermeiden, w​ird bei d​er Tabu-Suche m​it Hilfe während d​er Suche gesammelter Daten e​ine Tabu-Liste erstellt. Die a​uf dieser Liste stehenden Züge o​der Lösungen dürfen i​n der aktuellen Iteration n​icht oder n​ur bei zusätzlicher Erfüllung e​ines Aspirationskriteriums ausgeführt werden.

Eine klassische u​nd schnell z​u implementierende Tabu-Strategie i​st dabei, d​as Komplement d​es in e​iner Iteration ausgeführten Zuges für e​ine bestimmte Tabu-Dauer i​n der Tabu-Liste z​u speichern. Ein anderer Ansatz verbietet d​ie Veränderung v​on bestimmten Teilbereichen e​iner Lösung für e​ine 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 . Die von dieser Funktion erzeugte Menge von benachbarten Lösungen zu 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

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

Literatur
  • F. Glover: Future paths for integer programming and links to artificial intelligence. In: Comput. Oper. Res. 13, 1986, S. 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, S. 126–140.
  • A. Heinrici: Leistungsvergleich von Nachbarschaftssuchverfahren. VWF Verlag für Wissenschaft und Forschung, Berlin, 1996, ISBN 3-930324-76-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.