WikiDer > Tabu-Suche

Tabu-Suche ist ein metaheuristischOptimierungsalgorithmus entwickelt von Fred Glover. Es basiert auf Steilster Abstieg Algorithmus und die Tabu erklären zuvor besuchte Lösungen für das Problem. Der große Unterschied zum Steepest-Descent-Algorithmus besteht darin, dass die Tabu-Suche für die nächste Iteration nicht nur eine bessere, sondern auch eine schlechtere Lösung auswählen kann. Darüber hinaus kann die Tabu-Suche lokalen Minima umgehen, indem Lösungen tabuisiert werden.

Pseudocode

Wählen Sie eine Anfangslösung und bestimmen Sie, wie gut diese Lösung ist

Wiederholen

Bestimmen Sie die Nachbarlösungen, die nicht tabu sind und stellen Sie fest, wie gut sie sind

Wählen Sie die beste Nachbarlösung und platzieren Sie die vorherige Lösung in der Tabu-Liste

Wenn die neue Lösung besser ist, merken Sie sich die neue Lösung

Bis die Stoppbedingung erfüllt ist

Initialisierung

Die Anfangslösung wird zufällig gewählt oder eine spezifische Lösung, die bereits ein vernünftiges Ergebnis liefert, zum Beispiel die beste Lösung mit obtained genetischen Algorithmus oder simuliertes Glühen.

Tabu-Liste

Es gibt zwei verschiedene Möglichkeiten, eine bisherige Lösung für tabu zu erklären. Eine besteht darin, den Überblick zu behalten, welche Lösungen Tabu search bereits ausgewählt hat. Der große Nachteil dieser Methode ist, dass sie viel Speicherplatz benötigt und nur eine Lösung gleichzeitig tabuisiert.

Eine gängige Methode ist eine Tabu-Liste basierend auf den letzten Änderungen. Diese Tabu-Liste speichert die Unterschiede zwischen zwei aufeinanderfolgenden Lösungen für eine bestimmte Anzahl von Iterationen. Die Idee dahinter ist, dass, wenn der Algorithmus einen bestimmten Schritt im Lösungsraum gemacht hat, der (sehr) vorteilhaft war und dieser Schritt daher wahrscheinlich nicht in naher Zukunft rückgängig gemacht werden muss. Es ist daher nicht erforderlich, die durch einen der Schritte in der Tabu-Liste erhaltene Nachbarlösung in einer der folgenden Iterationen zu nehmen, was wiederum Rechenzeit spart. Der Nachteil dieser Methode ist jedoch, dass Sie einen zusätzlichen Parameter erhalten: die Länge der Tabu-Liste. Wenn zu lange gewählt, kann die Tabu-Suche keine benachbarten Lösungen finden und endet mit einer ziemlich schlechten Lösung. Wenn es jedoch zu kurz gewählt wird, hängt die Tabu-Suche um ein lokales Minimum herum.

Abbruchkriterium

Für die Beendigung können verschiedene Kriterien verwendet werden. Einige häufig verwendete Kündigungsbedingungen sind:

• Alle Nachbarlösungen wurden für tabu erklärt; Infolgedessen gibt es keine Reihe von Versuchslösungen mehr;
• Feste Anzahl von Iterationen;
• Die bisher beste gefundene Lösung wurde lange Zeit nicht verbessert;
• Budget: zugewiesene Computerzeit/verbrauchtes Geld;
• Eine Kombination der oben genannten Bedingungen.

Erweiterungen

Es gibt mehrere Erweiterungen der standardmäßigen Tabu-Suche, darunter:

• Diversifikation
• Intensivierung
• reaktive Tabu-Suche

Diversifikation

Der Hauptnachteil der standardmäßigen Tabu-Suche besteht darin, dass es sich um eine lokale Methode handelt. Dadurch kann ein großer Teil des Lösungsraums vernachlässigt werden. Bei der Diversifizierung wird nachverfolgt, welcher Teil des Lösungsraums besucht wurde. Bei Beendigung der Tabu-Suche wird eine neue Lösung in dem noch nicht durchsuchten Teil des Lösungsraums gewählt. Dies kann wiederholt wiederholt werden. Diversifikation macht die Tabu-Suche zu einem globalen Optimierungsalgorithmus.

Intensivierung

Bei der Intensivierung schauen wir uns an, welche Schritte die Tabu-Suche während verschiedener Iterationen oder Durchläufe macht. Wenn sich herausstellt, dass ein bestimmter Schritt im Lösungsraum häufig gemacht wird, kann dies darauf hinweisen, dass die durch diesen Schritt erhaltene Lösung im Allgemeinen gut ist. Wenn möglich, wird dieser Schritt von nun an früher erfolgen.

Reaktive Tabu-Suche

Tabu-Suche ist ein Algorithmus, bei dem sich der Lösungsraum im Laufe der Zeit nicht ändert. In der Praxis gibt es jedoch mehrere Probleme, bei denen sich der Lösungsraum mit der Zeit ändert. Die reaktive Tabu-Suche ist eine Erweiterung der Tabu-Suche, die es ermöglicht, die Tabu-Suche in wechselnden Lösungsräumen zu verwenden. Dies geschieht durch dynamisches Anpassen verschiedener Parameter, wie beispielsweise der Länge der Tabu-Liste, unter Verwendung eines einfachen Feedback-Schemas.