Glossar · method

Tabu-Suche

Speicherbasierte Metaheuristik, die zuletzt besuchte Lösungen oder Züge auf einer Tabu-Liste festhält, um Zyklen zu vermeiden, und mittels Intensivierung und Diversifikation den Suchraum durchläuft.

Tabu SearchTSSpeicherbasierte MetaheuristikAdaptive Memory ProgrammingReactive Tabu Search

Die Tabu-Suche ist eine speicherbasierte Metaheuristik, eingeführt von Glover (1986, 1989, 1990); eine verwandte Idee wurde unabhängig von Hansen (1986) vorgeschlagen. Ihr Alleinstellungsmerkmal ist der explizite Speicher: Während simuliertes Abkühlen auf Zufall und genetische Algorithmen auf einer Population beruhen, hält die Tabu-Suche eine Liste zuletzt ausgeführter Züge oder Lösungsattribute und verbietet deren Umkehrung. Kernkomponenten: (1) Nachbarschaftsstruktur und Zugbewertung; jede Iteration wechselt zum besten nicht tabuisierten Nachbarn, auch bei Verschlechterung (Ausbruch aus lokalen Optima); (2) Kurzzeitgedächtnis (Tabu-Liste) der Länge k, k ist die Tabu-Tenure; (3) Aspirationskriterium — ein tabuierter Zug wird zugelassen, wenn er die beste bekannte Lösung verbessert; (4) mittelfristiger Speicher zur Intensivierung — Vertiefung der Suche um häufig besuchte gute Lösungen; (5) langfristiger Speicher zur Diversifikation — Sprünge in unerforschte Regionen. Varianten umfassen granulare Tabu-Suche, reaktive Tabu-Suche (Battiti und Tecchiolli 1994, mit automatischer Tenure-Anpassung) und Adaptive Memory Programming. Bei VRP, Scheduling, Sequenzierung und Zuweisungsproblemen ist sie eine der stärksten Metaheuristiken; die VRP-Arbeiten von Cordeau und Laporte sind Industriereferenz. Gegenüber simuliertem Abkühlen deterministischer und speicherintensiver, bei vergleichbarer Lösungsqualität und geringerer Parameterempfindlichkeit. Literatur: Glover und Laguna (1997), Gendreau und Potvin (2010).

Örnek

Ein Kurierunternehmen optimiert die Tour eines Einzelfahrzeugs für 18 Tageskunden. Die Greedy-Anfangstour beträgt 184 km. Tabu-Suche mit 2-opt- und Or-opt-Nachbarschaften, Tabu-Tenure 7, Aspirationskriterium und Diversifikationssprüngen alle 50 Iterationen erreicht 151 km in 9 Minuten — 18 Prozent Verbesserung. Mehrfach werden vorübergehend schlechtere Touren akzeptiert, doch die Tabu-Liste verhindert die Rückkehr zu früheren Routen; der Algorithmus erkundet andere Topologien und intensiviert anschliessend um die beste gefundene Lösung.