Stochastische Tabu-Suche – Randomisierte Metaheuristik mit Gedächtnis
- Eingeführt von
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- Jahr
- 1990s
- Typ
- Stochastic metaheuristic optimizer
- Familie
- Simulation / optimization
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die Stochastische Tabu-Suche (STS) ist eine Erweiterung der klassischen Tabu-Suche, die Zufälligkeit in die Phasen der Nachbarschaftserkundung und der Zugauswahl einführt.
Durch die Kombination von Tabu-Gedächtnis – das kürzlich besuchte Lösungen verbietet – mit probabilistischer Akzeptanz oder zufälliger Kandidatenstichprobe entgeht die STS lokalen Optima effektiver und erkundet zerklüftete Lösungslandschaften, die eine deterministische TS möglicherweise nicht durchqueren kann.
Die Intuition hinter der Methode
Die klassische Tabu-Suche navigiert einen Lösungsraum, indem sie immer zum besten erlaubten Nachbarn wechselt und ein Kurzzeitgedächtnis (die Tabu-Liste) verwendet, um Zyklen zu verhindern. In der Praxis kann der beste erlaubte Zug den Algorithmus jedoch immer noch in einem Bereich der Landschaft gefangen halten. Die Stochastische Tabu-Suche injiziert kontrollierte Zufälligkeit: Der nächste Zug wird probabilistisch aus einer Menge von Kandidatennachbarn gewählt, anstatt gierig, und gelegentlich werden zufällige Störungen eingeführt, um die Suche zu diversifizieren. Dies bewahrt die gedächtnisgesteuerte Disziplin der TS und fügt gleichzeitig die Erkundungskraft hinzu, die einem rein deterministischen Abstieg fehlt.
Geschichte
Die Tabu-Suche wurde 1986 von Fred Glover formal eingeführt und in wegweisenden Arbeiten von 1989-1990 detailliert beschrieben. Stochastische Erweiterungen entstanden in den 1990er Jahren, als Forscher erkannten, dass die deterministische Nachbarschaftsevaluierung bei großen Problemen ein Engpass war. Zufällige Kandidatenstichproben, probabilistische Zugakzeptanz und Rauschinjektion wurden integriert, um die Diversifizierung zu verbessern, was zur Stochastischen Tabu-Suche führte. Die Technik wird in der Operations Research, im Ingenieurdesign und bei der Hyperparameteroptimierung im maschinellen Lernen weit verbreitet eingesetzt.
Wann wird sie eingesetzt?
Verwenden Sie die Stochastische Tabu-Suche, wenn Sie kombinatorische oder kontinuierliche Black-Box-Optimierungsprobleme mit zerklüfteten, multimodalen Landschaften lösen, bei denen die deterministische lokale Suche ständig stecken bleibt (z. B. Zeitplanung, Routing, Merkmalsauswahl). Sie ist besonders wertvoll, wenn die vollständige Nachbarschaftsevaluierung rechenintensiv ist und eine zufällige Stichprobenziehung erforderlich macht. Verwenden Sie STS NICHT, wenn das Problem konvex oder unimodal ist – gradientenbasierte oder exakte Methoden sind schneller und optimal. Vermeiden Sie sie, wenn Sie eine garantierte globale Optimalität benötigen, da STS über heuristisch gefundene beste Lösungen hinaus keine Konvergenzgarantie bietet. Vermeiden Sie sie auch, wenn die Zielfunktion kostengünstig vollständig zu evaluieren ist und eine deterministische TS mit erschöpfender Nachbarschaftssuche machbar ist.
Grenzen und Hinweise
- Keine theoretische Garantie für das Finden des globalen Optimums; die Lösungsqualität hängt stark von den Parametereinstellungen ab.
- Tabu-Dauer und Kandidatenlistengröße erfordern eine problemspezifische Abstimmung; schlechte Entscheidungen führen zu vorzeitiger Konvergenz oder langsamem Fortschritt.
- Stochastische Läufe sind ohne einen festen Zufalls-Seed nicht reproduzierbar, was das Benchmarking und die Überprüfung erschwert.
- Der Speicherbedarf wächst mit der Größe der Tabu-Liste; für große Lösungsräume sind attributbasierte Tabu-Repräsentationen erforderlich.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Entgeht lokalen Optima effektiver als die deterministische Tabu-Suche, indem Gedächtnis mit probabilistischer Exploration kombiniert wird.
- Skaliert auf große Nachbarschaftsstrukturen durch Stichprobenziehung von Kandidaten, wodurch die Rechenkosten pro Iteration reduziert werden.
- Das Tabu-Gedächtnis verhindert Zyklen, ein häufiger Fehler bei rein stochastischen Methoden wie dem Random-Restart-Hill-Climbing.
- Flexibles Framework: Perturbationswahrscheinlichkeit und Tabu-Dauer können abgestimmt werden, um Intensivierung und Diversifizierung auszugleichen.
- Anwendbar auf kombinatorische Probleme (TSP, Zeitplanung) und kontinuierliche Optimierung mit geringfügiger Anpassung.
Anwendungen
- Fahrzeugrouting und Logistikoptimierung unter unsicherer Nachfrage
- Job-Shop- und Open-Shop-Terminplanung mit stochastischen Bearbeitungszeiten
- Merkmalsauswahl in hochdimensionalen Machine-Learning-Datensätzen
- Netzwerkdesign und Topologieoptimierung
- Portfoliooptimierung mit kombinatorischen Asset-Selektionsbeschränkungen
- Hyperparameter-Tuning für komplexe Simulationsmodelle
So funktioniert es
So funktioniert es
Generieren Sie eine Startlösung x0 (zufällig oder heuristisch). Setzen Sie die Tabu-Liste T auf leer, definieren Sie die Tabu-Dauer tau, die Iterationsgrenze I_max und stochastische Parameter (z. B. Kandidatenlistengröße k, Perturbationswahrscheinlichkeit p_perturb).
In jeder Iteration wird eine Teilmenge N_s der vollständigen Nachbarschaft N(x_current) zufällig abgetastet, anstatt alle Nachbarn zu evaluieren. Dies reduziert die Kosten pro Iteration und führt Stochastizität in die Bereiche des Raumes ein, die erkundet werden.
Wählen Sie die nächste Lösung x_next aus N_s: entweder (a) wählen Sie den besten Nicht-Tabu-Kandidaten mit Wahrscheinlichkeit 1-p_perturb, oder (b) mit Wahrscheinlichkeit p_perturb wählen Sie einen zufälligen Nicht-Tabu-Kandidaten zur Diversifizierung. Aspirationskriterien können den Tabu-Status außer Kraft setzen, wenn x_next die beste bekannte Lösung verbessert.
Fügen Sie x_current (oder das Zugattribut) der Tabu-Liste T hinzu. Entfernen Sie den ältesten Eintrag, wenn |T| > tau. Aktualisieren Sie die beste bekannte Lösung x_best, wenn f(x_next) < f(x_best).
Wiederholen Sie die Schritte neighborhood_sampling bis tabu_update, bis I_max Iterationen erreicht sind, ein Zielwert erreicht ist oder innerhalb eines Geduldsfensters keine Verbesserung eingetreten ist. Geben Sie x_best als endgültige Lösung zurück.
Häufige Fallstricke
- Eine zu kurze Tabu-Dauer ermöglicht Zyklen trotz der Tabu-Liste; eine zu lange Dauer blockiert vielversprechende Regionen unnötig.
- Die Verwendung einer zu kleinen Kandidatenliste (aggressive Stichprobenziehung) kann dazu führen, dass die Suche gute Nachbarn konsequent verfehlt.
- Das Vernachlässigen von Aspirationskriterien führt dazu, dass der Algorithmus global verbessernde Züge ablehnt, die zufällig tabu sind.
- Das Berichten nur eines einzelnen Laufs ohne mehrere Neustarts oder Seeds vermittelt ein irreführendes Bild der typischen Lösungsqualität.
- Verwechslung der Stochastischen Tabu-Suche mit Simulated Annealing: Beide sind stochastisch, unterscheiden sich aber grundlegend – STS verwendet ein explizites Gedächtnis, während SA eine temperaturbasierte probabilistische Akzeptanz ohne Gedächtnis verwendet.
Häufig gestellte Fragen
Wie unterscheidet sich die Stochastische Tabu-Suche von Simulated Annealing?
Beide sind stochastische Metaheuristiken, aber STS verwendet ein explizites Tabu-Gedächtnis, um kürzlich besuchte Züge zu verbieten und so Zyklen zu verhindern. SA hat kein Gedächtnis – es akzeptiert schlechtere Lösungen mit einer Wahrscheinlichkeit, die mit der Zeit abnimmt (Temperaturplan). STS ist im Allgemeinen bei kombinatorischen Problemen stärker, bei denen das Wiederholen von Zügen eine klare Gefahr darstellt.
Wie viele Iterationen (I_max) sollte ich ausführen?
Es gibt keine universelle Regel. Eine gängige Praxis ist es, mehrere unabhängige Versuche (z. B. 10-30 Neustarts) mit einem Budget proportional zur Problemgröße durchzuführen und dann die besten und durchschnittlichen Ergebnisse zu berichten. Für das Benchmarking sollte das Gesamtbudget für Funktionsauswertungen dem der konkurrierenden Methoden entsprechen.
Kann die Stochastische Tabu-Suche kontinuierliche Variablen verarbeiten?
Ja, aber es erfordert die Definition einer kontinuierlichen Nachbarschaft (z. B. Gaußsche Störung um die aktuelle Lösung) und eines geeigneten Attributs für die Tabu-Liste (z. B. eine Region oder Richtung). Die meisten STS-Literatur konzentriert sich auf kombinatorische Probleme; für kontinuierliche Räume sind Differential Evolution oder CMA-ES oft natürlichere Alternativen.
Welche Rolle spielen Aspirationskriterien?
Aspirationskriterien setzen den Tabu-Status eines Zuges außer Kraft, wenn dessen Akzeptanz zu einer besseren Lösung führt als die bisher beste gefundene. Ohne Aspiration könnte der Algorithmus global verbessernde Züge, die zufällig tabu sind, dauerhaft ablehnen, was die Lösungsqualität stark einschränken würde.
Sollte ich den Zufalls-Seed für die Reproduzierbarkeit festlegen?
Ja, legen Sie den Seed fest, wenn Sie Forschungsergebnisse berichten, um die Reproduzierbarkeit zu gewährleisten. In der Praxis sollten Sie mehrere Seeds verwenden und Statistiken (Mittelwert, Bestwert, Standardabweichung) berichten, um ein zuverlässiges Bild der Algorithmusleistung über die stochastische Landschaft zu erhalten.
Verwandte Methoden
Quellen
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
DOI-Referenz öffnenKopiert.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
DOI-Referenz öffnenKopiert.