Was ist die Tabu-Suche?
Die Tabu-Suche ist eine Metaheuristik für Kombinatorik-Optimierung, entwickelt von Fred Glover (1986). Sie verbessert die klassische lokale Suche, indem sie ein Gedächtnis einsetzt: Züge oder Lösungen, die kürzlich ausgeführt wurden, landen auf einer Tabu-Liste und sind vorübergehend verboten. Das verhindert Zyklen – also das Oszillieren zwischen denselben lokalen Optima – und zwingt die Suche, neue Regionen des Suchraums zu erkunden.
Wie funktioniert sie?
Ausgehend von einer Startlösung werden in jedem Schritt alle Nachbarlösungen betrachtet. Die beste nicht-verbotene Nachbarlösung wird übernommen – auch wenn sie schlechter ist als die aktuelle. Die Tabu-Liste speichert die letzten Züge (Tabu-Länge typisch 7–15), das Aspirationskriterium erlaubt eine Ausnahme: Ist eine verbotene Lösung besser als die bisher beste gefundene, darf sie trotzdem gewählt werden. Dazu kommen mittel- und langfristige Gedächtnisstrukturen, die eine Diversifikation steuern (z. B. selten benutzte Züge belohnen), während die kurzfristige Liste für Intensivierung sorgt.
Wo wird sie eingesetzt?
Die Tabu-Suche gehört zu den erfolgreichsten Verfahren für NP-vollständige Probleme in der Praxis: Job-Shop-Scheduling, Tourenplanung (Vehicle Routing), Telekommunikationsnetze und Layout-Optimierung. Anders als Simulated Annealing ist sie im Kern deterministisch – sie verlässt sich auf das Gedächtnis statt auf Zufall, ist aber eng mit dem Genetischen Algorithmus verwandt (beide sind Metaheuristiken über einfachen Heuristiken). Eine Optimum-Garantie gibt es nicht, die praktische Leistung ist aber bei vielen Problemklassen exzellent; die Laufzeit lässt sich wie bei jedem Algorithmus mit der Big-O-Notation einordnen.