Tabu Search ist eine Metaheuristik zur näherungsweisen Lösung komplexer Optimierungsprobleme. Ausgehend von einer gegebenen Startlösung werden in einem iterativen Suchprozess modifizierte Lösungen erzeugt, wobei der Suchprozess durch Anwendung des Tabu Search (oder der Tabusuche) gesteuert wird.
Grundkonzept
Unter einer Heuristik versteht man ein Verfahren, welches effizient über die Anwendung als sinnvoll erachteter Vorgehensweisen systematisch gute, aber nicht notwendigerweise optimale Lösungen (im Sinne von Handlungsalternativen) für gegebene Optimierungsprobleme bestimmt. Metaheuristiken sind allgemeine, im Wesentlichen nicht problemspezifische und somit generische Prinzipien und Schemata zur Entwicklung und Steuerung heuristischer Verfahren [Voß 2009]. In der Literatur subsumiert man hierunter u.a. Verfahren, die im Rahmen eines Suchprozesses auf die sukzessive Ermittlung verbesserter Lösungen abzielen und auf dem Prinzip der lokalen Suche aufbauen.
Verfahren der lokalen Suche suchen den Lösungsraum eines Optimierungsproblems unter Beachtung einer gegebenen Zielsetzung sowie vorgegebener Restriktionen in einem iterativen Prozess ab. Sie gehen dabei von einer möglicherweise suboptimalen Lösung des Problems aus und versuchen, diese sukzessive durch geringfügige Veränderungen zu verbessern. Eine derartige Veränderung lässt sich auch als Transformation oder Zug auffassen, und die Menge aller in einem Zug erreichbaren Lösungen lässt sich als Nachbarschaft bezeichnen. Der Transformationsvorgang wird iterativ wiederholt, bis ein Abbruchkriterium erfüllt ist.
Das Grundkonzept des Tabu Search wurde von Glover zur Lösung von (insbesondere kombinatorischen) Optimierungsproblemen entwickelt [Glover 1986; Glover und Laguna 1997]. Das Prinzip besteht darin, ein lokales Suchverfahren unter expliziter Verwendung einer Gedächtnisstruktur zu steuern. Die Gedächtnisstruktur wird verwendet, um die Suchrichtung des Verfahrens einzuschränken bzw. das Verfahren auf intelligente Art durch den Lösungsraum zu steuern. In jeder Iteration wird ein Zug ausgewählt, der zur größten Verbesserung, oder, falls keine Verbesserung möglich ist, zur geringsten Verschlechterung des Zielfunktionswertes führt. Verschlechterungen werden dann akzeptiert, wenn unter allen Lösungen der Nachbarschaft keine Verbesserung realisiert werden kann. Damit das Verfahren nicht immer wieder zu bereits gefundenen Lösungen zurückkehrt, werden sogenannte Tabu-Restriktionen zur Akzeptanz von Lösungen bestimmt. Im einfachsten Fall werden bereits untersuchte Lösungen im Folgenden nicht wieder untersucht, d.h. ein Zug zu einer derartigen Lösung wird tabuisiert (verboten bzw. als nicht ausführbar charakterisiert). Immer wenn ein bestimmter Zug getätigt wird, werden Elemente der damit erreichten Lösung tabu gesetzt, was bewirkt, dass diese Lösung in späteren Iterationen unter Umständen verboten wird.
Spezifikationen von Tabu-Restriktionen
Die Verwendung von Tabu-Restriktionen betrifft Entscheidungen hinsichtlich der Auswahl der tabu zu setzenden Züge und der Dauer ihres Tabustatus. Die Definition und Verwaltung von Tabulisten kann auf unterschiedliche Art erfolgen.
Statisches Vorgehen: In jeder Iteration wird genau ein Zug, nämlich das Komplement des jeweils letzten Zuges, für eine feste Dauer, d.h. eine feste Anzahl von Iterationen, tabu gesetzt. Die Idee der Vorgehensweise besteht darin, den Zug so lange zu verbieten, bis die Wahrscheinlichkeit des Wiedererreichens einer Lösung durch den tabuisierten Zug gering ist. (Das Speichern entsprechender Elemente einer Lösung entspricht einem sogenannten Kurzzeitgedächtnis.) Gegebenenfalls sinnvoll ist eine Wahl der Dauer in Abhängigkeit von der Art und Größe der zu lösenden Probleminstanzen.
Dynamisches Vorgehen: In jeder Iteration wird eine im Vorhinein nicht vorgegebene Anzahl an Zügen verboten. Dies kann insbesondere auf Basis logischer problembezogener Überlegungen geschehen. Z.B. die Reverse Elimination Methode garantiert dabei, dass alle Züge tabu gesetzt werden, die zu einer bereits aufgesuchten Lösung führen würden.
In weiterführenden Ansätzen wird insbesondere auf ein geschicktes Zusammenspiel zwischen Intensivierung und Diversifikation der Suche geachtet. Hierbei kann u.a. ein Langzeitgedächtnis (z.B. zur Untersuchung der Frequenz von Elementen guter Lösungen) zur Steuerung der Suche verwendet werden, um z.B. bisher wenig betrachtete Bereiche des Lösungsraums zu untersuchen.
Reactive Tabu Search zielt auf eine automatisierte Adaptation der Tabu-Restriktionen ab [Battiti und Tecchiolli 1994]. Die Idee besteht darin, die Anzahl zu tabuisierender Züge zu erhöhen, wenn im Laufe der Suche vermehrt Lösungswiederholungen auftreten. Umgekehrt kann diese Zahl beim Nichtauftreten von Wiederholungen sukzessive verringert werden.
Literatur
Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA Journal on Computing, 6, 1994, S. 126-140
Glover, F.: Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 1986, S. 533-549.
Glover, F., Laguna, M.: Tabu Search. Dordrecht: Kluwer, 1997.
Voß, S.: Metaheuristics. In: C.A. Floudas and P.M. Pardalos (eds.) Encyclopedia of Optimization, 2nd ed., New York: Springer, 2009. [ISBN: 978-0-387-74758-3]
