Die Tabu-Suche (TS) ist eine metaheuristische Suchmethode, die lokale Suchverfahren zur mathematischen Optimierung einsetzt . Sie wurde 1986 von Fred W. Glover [ 1 ] entwickelt und 1989 formalisiert. [ 2 ] [ 3 ]

Lokale (Nachbarschafts-)Suchverfahren untersuchen eine mögliche Lösung eines Problems und prüfen deren unmittelbare Nachbarn (d. h. Lösungen, die sich nur in wenigen Details unterscheiden), um eine bessere Lösung zu finden. Lokale Suchverfahren neigen dazu, in suboptimalen Bereichen oder auf Plateaus stecken zu bleiben, auf denen viele Lösungen gleich gut geeignet sind.

Die Tabu-Suche verbessert die Leistung der lokalen Suche, indem sie deren Grundregel lockert. Erstens können in jedem Schritt auch sich verschlechternde Züge akzeptiert werden, wenn kein besserer Zug möglich ist (beispielsweise wenn die Suche in einem strikten lokalen Minimum feststeckt ). Zusätzlich werden Verbote (daher der Begriff Tabu ) eingeführt, um zu verhindern, dass die Suche zu bereits besuchten Lösungen zurückkehrt.

Die Implementierung der Tabu-Suche verwendet Speicherstrukturen, die die besuchten Lösungen oder benutzerdefinierte Regelsätze beschreiben. [ 2 ] Wurde eine potenzielle Lösung bereits innerhalb eines bestimmten kurzen Zeitraums besucht oder hat sie gegen eine Regel verstoßen, wird sie als „ Tabu “ (verboten) markiert, sodass der Algorithmus diese Möglichkeit nicht wiederholt in Betracht zieht.

Hintergrund

Das Wort Tabu stammt aus dem Tongaischen und bezeichnet Dinge, die nicht berührt werden dürfen, weil sie heilig sind. [ 4 ]

Die Tabu-Suche ist ein metaheuristischer Algorithmus, der zur Lösung kombinatorischer Optimierungsprobleme (Probleme, bei denen eine optimale Reihenfolge und Auswahl von Optionen gewünscht ist) verwendet werden kann .

Aktuelle Anwendungsgebiete der Tabu-Suche erstrecken sich über Ressourcenplanung , Telekommunikation, VLSI-Design , Finanzanalyse, Terminplanung, Raumplanung, Energieverteilung, Molekulartechnik, Logistik, Mustererkennung , flexible Fertigung, Abfallwirtschaft, Mineralexploration, biomedizinische Analytik, Umweltschutz und viele weitere. In den letzten Jahren haben Fachzeitschriften verschiedenster Disziplinen Einführungsartikel und computergestützte Studien veröffentlicht, die die Erfolge der Tabu-Suche bei der Erweiterung des Spektrums effektiv lösbarer Probleme dokumentieren – mit Lösungen, deren Qualität die von bisher angewandten Methoden oft deutlich übertrifft. Eine umfassende Liste der Anwendungen, einschließlich zusammenfassender Beschreibungen der durch praktische Implementierungen erzielten Vorteile, findet sich in [ 5 ].

Grundlegende Beschreibung

Die Tabu-Suche verwendet ein lokales oder Nachbarschaftssuchverfahren , um iterativ von einer potenziellen Lösung zu einer verbesserten Lösung in der Nachbarschaft zu gelangen , bis ein Abbruchkriterium erfüllt ist (in der Regel eine Versuchsbegrenzung oder ein Schwellenwert für die Punktzahl). Lokale Suchverfahren bleiben oft in Bereichen mit niedriger Punktzahl oder in Bereichen mit stagnierenden Punktzahlen stecken. Um diese Fallstricke zu vermeiden und Bereiche des Suchraums zu erkunden , die von anderen lokalen Suchverfahren unberücksichtigt blieben, untersucht die Tabu-Suche während des Suchvorgangs sorgfältig die Nachbarschaft jeder Lösung. Die in die neue Nachbarschaft aufgenommenen Lösungen werden mithilfe von Speicherstrukturen bestimmt. Mithilfe dieser Speicherstrukturen schreitet die Suche fort, indem sie iterativ von der aktuellen Lösung zu einer verbesserten Lösung in der Nachbarschaft gelangt .

Die Tabu-Suche weist mehrere Ähnlichkeiten mit dem simulierten Ausglühen auf , da beide mögliche Abwärtsbewegungen beinhalten. Tatsächlich kann das simulierte Ausglühen als eine spezielle Form der Tabu-Suche betrachtet werden, bei der wir eine Art „gestaffelte Gültigkeit“ verwenden, d. h. eine Bewegung wird mit einer festgelegten Wahrscheinlichkeit tabu.

Diese Speicherstrukturen bilden die sogenannte Tabuliste, eine Reihe von Regeln und verbotenen Lösungen, die dazu dienen, zu filtern, welche Lösungen in den Suchraum aufgenommen werden . Vereinfacht ausgedrückt ist eine Tabuliste eine Kurzzeitmenge der Lösungen, die in der jüngsten Vergangenheit besucht wurden (weniger als Iterationen zurückliegend, wobei die Anzahl der zu speichernden vorherigen Lösungen ist – dies wird auch als Tabu-Laufzeit bezeichnet). Üblicherweise besteht eine Tabuliste aus Attributen, die sich beim Übergang von einer Lösung zur nächsten geändert haben. Zur besseren Verständlichkeit ist es hilfreich, eine „Lösung“ als durch solche Attribute kodiert und repräsentiert zu verstehen.

Speicherarten

Die bei der Tabu-Suche verwendeten Speicherstrukturen können grob in drei Kategorien unterteilt werden: [ 6 ]

  • Kurzfristig: Die Liste der zuletzt in Betracht gezogenen Lösungen. Erscheint eine potenzielle Lösung auf der Tabuliste, kann sie erst wieder geprüft werden, wenn ihre Gültigkeitsdauer abgelaufen ist.
  • Mittelfristig: Intensivierungsregeln, die die Suche auf vielversprechende Bereiche des Suchraums ausrichten sollen.
  • Langfristig: Diversifizierungsregeln, die die Suche in neue Bereiche lenken (d. h. hinsichtlich Neustarts, wenn die Suche auf einem Plateau oder in einer suboptimalen Sackgasse stecken bleibt).

Kurzzeit-, Mittelzeit- und Langzeitgedächtnis können sich in der Praxis überschneiden. Innerhalb dieser Kategorien lässt sich das Gedächtnis weiter differenzieren, beispielsweise anhand der Häufigkeit und der Auswirkungen von Änderungen. Ein Beispiel für eine Struktur des Mittelzeitgedächtnisses ist eine, die Lösungen mit bestimmten Eigenschaften (z. B. unerwünschte oder erwünschte Werte für bestimmte Variablen) verbietet oder fördert, oder eine, die bestimmte Schritte verhindert oder auslöst (z. B. basierend auf der Häufigkeit, mit der Lösungen Merkmale gemeinsam haben mit unattraktiven oder attraktiven Lösungen aus der Vergangenheit). Im Kurzzeitgedächtnis werden ausgewählte Eigenschaften kürzlich besuchter Lösungen als „tabu-aktiv“ gekennzeichnet. Lösungen mit tabu-aktiven Elementen sind ausgeschlossen. Aspirationskriterien werden eingesetzt, um den Tabu-Status einer Lösung aufzuheben und sie so in die zulässige Menge aufzunehmen (vorausgesetzt, die Lösung ist nach einem Qualitäts- oder Diversitätsmaß „gut genug“). Ein einfaches und häufig verwendetes Aspirationskriterium ist die Zulassung von Lösungen, die besser sind als die aktuell beste bekannte Lösung.

Kurzzeitgedächtnis allein mag ausreichen, um Lösungen zu erzielen, die denen herkömmlicher lokaler Suchverfahren überlegen sind, doch sind mittel- und langfristige Strukturen oft notwendig, um komplexere Probleme zu lösen. [ 7 ] Die Tabu-Suche wird häufig mit anderen Metaheuristiken verglichen – wie beispielsweise Simulated Annealing , genetischen Algorithmen , Ameisenkolonie-Optimierungsalgorithmen , reaktiver Suchoptimierung, geführter lokaler Suche oder gieriger randomisierter adaptiver Suche . Darüber hinaus wird die Tabu-Suche mitunter mit anderen Metaheuristiken kombiniert, um Hybridmethoden zu entwickeln. Die gängigste Tabu-Suche-Hybridmethode entsteht durch die Kombination von Tabu Search (TS) mit Scatter Search [ 8 ] [ 9 ], einer Klasse populationsbasierter Verfahren, die gemeinsame Wurzeln mit der Tabu-Suche hat und häufig zur Lösung großer nichtlinearer Optimierungsprobleme eingesetzt wird.

Pseudocode

Der folgende Pseudocode stellt eine vereinfachte Version des oben beschriebenen Tabu-Suchalgorithmus dar. Diese Implementierung verfügt über ein rudimentäres Kurzzeitgedächtnis, enthält jedoch keine Strukturen für Zwischen- oder Langzeitgedächtnis. Der Begriff „Fitness“ bezieht sich auf die Bewertung der Kandidatenlösung, wie sie in einer Zielfunktion für die mathematische Optimierung zum Ausdruck kommt. 

sBest ← s0sCurr ← s0bestCandidate ← s0tabuList ← []tabuList.push ( s0 )​​while ( not stoppingCondition ())sNeighborhood ← getNeighbors ( sCurr )bestCandidateFitness ← - ∞für ( Kandidat in sNachbarschaft )if ( ( not tabuList . contains ( sCandidate ))und ( Fitness ( sCandidate ) > bestCandidateFitness ) )bestCandidate ← sCandidatebestCandidateFitness ← fitness ( bestCandidate )EndeEndeif ( bestCandidateFitness is - ∞ )brechen ;EndesCurr ← bestCandidateif ( bestCandidateFitness > fitness ( sBest ))sBest ← bestCandidateEndetabuList.push ( bestCandidate )​​if ( tabuList . size > maxTabuSize )tabuList.removeFirst ( )​EndeEndereturn sBest

Die Zeilen 1–5 stellen die anfängliche Einrichtung dar: Es wird eine (möglicherweise zufällig gewählte) Anfangslösung erstellt, diese als bisher beste Lösung festgelegt und eine Tabuliste mit dieser Anfangslösung initialisiert. In diesem Beispiel ist die Tabuliste lediglich eine Kurzzeitspeicherstruktur, die die Elemente der besuchten Zustände speichert.

Die zentrale algorithmische Schleife beginnt in Zeile 6. Diese Schleife sucht so lange nach einer optimalen Lösung, bis eine vom Benutzer festgelegte Abbruchbedingung erfüllt ist (beispielsweise ein einfaches Zeitlimit oder ein Schwellenwert für die Fitnessbewertung). In Zeile 10 werden die benachbarten Lösungen auf Tabu-Elemente geprüft. Zusätzlich speichert der Algorithmus die beste Lösung in der Nachbarschaft, die kein Tabu-Element enthält.

Die Fitnessfunktion ist im Allgemeinen eine mathematische Funktion, die einen Wert zurückgibt oder angibt, ob die Aspirationskriterien erfüllt sind – beispielsweise könnte ein Aspirationskriterium darin bestehen, dass ein neuer Suchraum gefunden wurde. [ 4 ] Wenn der beste lokale Kandidat einen höheren Fitnesswert als der aktuell beste hat (Zeile 20), wird er als neuer bester Kandidat festgelegt (Zeile 21). Der lokal beste Kandidat wird stets der Tabuliste hinzugefügt (Zeile 23). Ist die Tabuliste voll (Zeile 24), dürfen einige Elemente verfallen (Zeile 25). Im Allgemeinen verfallen Elemente in der Reihenfolge ihres Hinzufügens aus der Liste. Das Verfahren wählt den besten lokalen Kandidaten aus (auch wenn er einen schlechteren Fitnesswert als der aktuell beste hat), um das lokale Optimum zu verlassen.

Dieser Prozess wird fortgesetzt, bis das vom Benutzer festgelegte Abbruchkriterium erfüllt ist. Dann wird die während des Suchprozesses gefundene beste Lösung zurückgegeben (Zeile 28).

Beispiel: das Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (Traveling Salesman Problem , TSP) wird mitunter verwendet, um die Funktionalität der Tabu-Suche zu demonstrieren. [ 7 ] Dieses Problem stellt eine einfache Frage: Gegeben eine Liste von Städten, welche ist die kürzeste Route, die alle Städte besucht? Wenn beispielsweise Stadt A und Stadt B benachbart sind, Stadt C jedoch weiter entfernt liegt, ist die zurückgelegte Gesamtstrecke kürzer, wenn Stadt A und B nacheinander besucht werden, bevor Stadt C besucht wird. Da die Suche nach einer optimalen Lösung NP-schwer ist , eignen sich heuristische Approximationsverfahren (wie z. B. lokale Suchen) zur Entwicklung nahezu optimaler Lösungen. Um gute TSP-Lösungen zu erhalten, ist es unerlässlich, die Graphstruktur auszunutzen. Die Bedeutung der Ausnutzung der Problemstruktur ist ein wiederkehrendes Thema in Metaheuristiken, und die Tabu-Suche ist hierfür gut geeignet. Eine Klasse von Strategien, die mit der Tabu-Suche verwandt sind und als Auswurf-Ketten-Methoden bezeichnet werden, ermöglicht es, effizient hochwertige TSP-Lösungen zu finden. [ 10 ]

Andererseits kann eine einfache Tabu-Suche verwendet werden, um eine zufriedenstellende Lösung für das Problem des Handlungsreisenden zu finden (d. h. eine Lösung, die ein Adäquatheitskriterium erfüllt, jedoch nicht die hohe Qualität aufweist, die durch die Ausnutzung der Graphstruktur erzielt wird). Die Suche beginnt mit einer Startlösung, die zufällig oder mithilfe eines Nächste-Nachbarn-Algorithmus generiert werden kann . Um neue Lösungen zu erzeugen, wird die Reihenfolge der besuchten Städte in einer potenziellen Lösung vertauscht. Die gesamte Reisedistanz zwischen allen Städten dient als Kriterium, um die Idealität einer Lösung im Vergleich zu einer anderen zu bewerten. Um Zyklen – also das wiederholte Besuchen einer bestimmten Lösungsmenge – und das Festfahren in lokalen Optima zu vermeiden , wird eine Lösung der Tabu-Liste hinzugefügt, wenn sie als Lösungsnachbar akzeptiert wird .

Es werden so lange neue Lösungen generiert, bis ein Abbruchkriterium, beispielsweise eine beliebige Anzahl von Iterationen, erfüllt ist. Sobald die einfache Tabu-Suche beendet ist, gibt sie die beste während ihrer Ausführung gefundene Lösung zurück.

Referenzen

  1. ^ Fred Glover (1986). „Zukünftige Wege der ganzzahligen Programmierung und Verbindungen zur künstlichen Intelligenz“. Computers and Operations Research . 13 (5): 533–549 . doi : 10.1016/0305-0548(86)90048-1 .
  2. ^ a b Fred Glover (1989). "Tabu Search – Part 1". ORSA Journal on Computing . 1 (2): 190– 206. doi : 10.1287/ijoc.1.3.190 .
  3. ^ Fred Glover (1990). „Tabu Search – Part 2“. ORSA Journal on Computing . 2 (1): 4–32 . doi : 10.1287/ijoc.2.1.4 .
  4. ^ a b "Kurse" (PDF) .
  5. ^ F. Glover; M. Laguna (1997). Tabu Search . Kluwer Academic Publishers. ISBN 978-1-4613-7987-4Die
  6. ^ Fred Glover (1990). „Tabu Search: A Tutorial“. Interfaces .
  7. ^ a b M. Malek; M. Huruswamy; H. Owens; M. Pandya (1989). „Serielle und parallele Suchverfahren für das Problem des Handlungsreisenden“. Annals of OR: Linkages with Artificial Intelligence .
  8. ^ F. Glover, M. Laguna & R. Marti (2000). „Grundlagen der Streusuche und Pfadverknüpfung“. Control and Cybernetics . 29 (3): 653–684 .
  9. ^ M. Laguna & R. Marti (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers. ISBN 9781402073762Die
  10. ^ D. Gamboa, C. Rego & F. Glover (2005). „Datenstrukturen und Auswurfsketten zur Lösung großskaliger Probleme des Handlungsreisenden“. European Journal of Operational Research . 160 (1): 154–171 . CiteSeerX 10.1.1.417.9789 . doi : 10.1016/j.ejor.2004.04.023 .