imported>Aka: https, Kleinkram

2023-11-12T11:57:27Z

https, Kleinkram

Neue Seite

'''Tabu-Suche''' ist ein iteratives [[Metaheuristik|metaheuristisches]] Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde 1986 von [[Fred W. Glover]] in den USA erfunden<ref name="glover86">{{cite journal
| author = F. Glover and C. McMillan
| year = 1986
| title = The general employee scheduling problem: an integration of MS and AI
| journal = Computers and Operations Research
| language = englisch
}}</ref> und seither ständig weiterentwickelt.

So wie beispielsweise [[Evolutionärer Algorithmus|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 [[Trajektorie (Mathematik)|trajektionsbasiertes]] Verfahren, da dessen Ablauf einer [[Phasenraum#Beispiel einer Phasenraumanalyse|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 [[Aspirationskriterium]]s 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 <math>N(x)</math>. Die von dieser Funktion erzeugte Menge von benachbarten Lösungen zu <math>x</math> 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 ==
<references />

== 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 ==
* [https://leeds-faculty.colorado.edu/glover/tabusearchvignettes.html ''Tabu Search Vignettes.''] Tabu-Suche auf Fred Glovers Homepage (englisch).

[[Kategorie:Optimierungsalgorithmus]]

Tabu-Suche - Versionsgeschichte

imported>Aka: https, Kleinkram