Tabu-Suche

Tabu-Suche ist ein iteratives metaheuristisches Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde 1986 von Fred W. Glover in den USA erfunden^[1] und seither ständig weiterentwickelt.

So wie beispielsweise evolutionäre Algorithmen ist auch die Tabu-Suche ein heuristisches Optimierungsverfahren. Anders als bei evolutionären Algorithmen wird bei der klassischen Tabu-Suche in jedem Iterationsschritt von nur einer Lösung ausgegangen. Die Tabu-Suche ist also ein trajektionsbasiertes Verfahren, da dessen Ablauf einer Trajektorie im Suchraum folgt.

Grundidee

Um Zyklen beim Traversieren des Lösungsraumes zu vermeiden, wird bei der Tabu-Suche mit Hilfe während der Suche gesammelter 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

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.
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.
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).
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

↑ F. Glover and C. McMillan: The general employee scheduling problem: an integration of MS and AI. In: Computers and Operations Research. 1986 (englisch).

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.

Weblinks

Tabu Search Vignettes. Tabu-Suche auf Fred Glovers Homepage (englisch).

[glover86-1] F. Glover and C. McMillan: The general employee scheduling problem: an integration of MS and AI. In: Computers and Operations Research. 1986 (englisch).

[1]