Zum Inhalt springen
Zurück zu den Suchergebnissen

Tabu Search — Lokale Such-Metaheuristik

Eingeführt von
Fred Glover
Jahr
1989
Typ
Local-search metaheuristic

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Tabu Search ist eine von Fred Glover 1989 eingeführte Metaheuristik für lokale Suche, die eine Tabu-Liste – ein Kurzzeitgedächtnis kürzlich besuchter Lösungen – verwendet, um Zyklen zu verhindern und lokale Optima zu verlassen.

Durch explizites Verbot von Zügen, die kürzliche Entscheidungen rückgängig machen, erkundet der Algorithmus den Suchraum breiter und zielt durch Langzeitgedächtnisstrukturen wie Aspirationskriterien darauf ab, sich dem globalen Optimum auch bei großen, komplexen kombinatorischen Problemen anzunähern.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie navigieren im Dunkeln durch eine bergige Landschaft und versuchen, den höchsten Gipfel zu finden. Ein einfacher lokaler Such-Kletterer steigt immer bergauf und bleibt am nächsten Hügel stecken, den er erreicht. Tabu Search trägt ein Notizbuch mit kürzlich besuchten Orten und weigert sich, dorthin zurückzukehren, selbst wenn ein Zurückgehen verlockend erscheint. Diese erzwungene Amnesie über kürzliche Züge zwingt die Suche aus Sackgassen und in unerforschtes Gebiet, wodurch sie schließlich viel höhere Höhen entdecken kann, als eine einfache lokale Suche jemals könnte.

Geschichte

Tabu Search wurde von Fred Glover in einem wegweisenden Artikel von 1989 im ORSA Journal on Computing vorgestellt, wo es als Strategie zur Steuerung lokaler Suche durch Nutzung des Gedächtnisses vergangener Züge präsentiert wurde. Die grundlegenden Ideen wurden in der Springer-Monografie von Glover und Laguna aus dem Jahr 1997 konsolidiert und erweitert, die die kanonische Kurzzeit-Tabu-Liste, Aspirationskriterien sowie Langzeit-Diversifizierungs- und Intensifizierungsstrategien etablierte, die bis heute zentral für die Methode sind. Seit seiner Einführung wurde Tabu Search ausgiebig in der Betriebswirtschaftslehre, Terminplanung, Logistik und kombinatorischen Design angewendet und bleibt neben Simulated Annealing und genetischen Algorithmen eine Standard-Benchmark-Metaheuristik.

Wann wird sie eingesetzt?

Tabu Search eignet sich gut für kombinatorische und diskrete Optimierungsprobleme, bei denen der Lösungsraum für exakte Methoden zu groß ist und die Problemstruktur eine sinnvolle Nachbarschaft definiert. Typische Anwendungen sind Terminierungs-, Routen-, Zuweisungs- und Sequenzierungsprobleme. Es ist besonders effektiv, wenn die Suchlandschaft viele lokale Optima aufweist, die einfachere Methoden gefangen halten. Es erfordert nicht, dass die Zielfunktion differenzierbar oder stetig ist. Die Nachbarschaftsdefinition und die Tabu-Tenure müssen sorgfältig an das spezifische Problem angepasst werden; eine schlecht gewählte Nachbarschaft oder eine zu kurze oder zu lange Tenure kann die Leistung erheblich beeinträchtigen. Mindestens mehrere hundert – und idealerweise mehr als tausend – Iterationen sind erforderlich, damit die Suche den Raum ausreichend erkunden kann.

Grenzen und Hinweise

  • Die Leistung ist empfindlich gegenüber der Nachbarschaftsdefinition und der Tabu-Tenure; schlechte Entscheidungen können die Suche gefangen halten oder sie trotz des Tabu-Mechanismus zum Zyklieren bringen.
  • Erfordert ein minimales Iterationsbudget – typischerweise mehr als 1.000 Iterationen –, um die Nachbarschaft ausreichend zu erkunden; bei zu wenigen Iterationen sind die Ergebnisse nicht besser als bei einfacher lokaler Suche.
  • Die Tabu-Liste speichert Zugmerkmale anstelle vollständiger Lösungen, daher ist das Aspirationskriterium erforderlich, um versehentlich wirklich gute Züge nicht zu blockieren.
  • Im Gegensatz zu exakten Lösungsfindern bietet Tabu Search keine Optimalitätsgarantie, und die Ergebnisqualität kann bei verschiedenen Durchläufen variieren, wenn die Anfangslösung oder die Nachbarschaft stochastisch ist.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Verlässt lokale Optima durch den Tabu-Mechanismus, ohne Gradienteninformationen zu benötigen.
  • Anwendbar auf kombinatorische, gemischte und sogar kontinuierliche Probleme – es nimmt keine Normalität oder irgendeine Verteilungseigenschaft an.
  • Integriert Gedächtnis auf mehreren Zeitskalen (Kurzzeit-Tabu-Liste, Langzeit-Diversifizierung/Intensivierung), was eine prinzipienfeste Erkundung des Suchraums ermöglicht.
  • Findet oft qualitativ hochwertige Lösungen mit relativ bescheidenen Rechenbudgets im Vergleich zu exakten Methoden bei großen Instanzen.

Anwendungen

  • Job-Shop- und Flow-Shop-Scheduling – Optimierung der Reihenfolge von Operationen zur Minimierung der Durchlaufzeit oder Verspätung.
  • Fahrzeugroutenplanung – Ermittlung effizienter Lieferrouten unter Berücksichtigung von Kapazitäts- und Zeitfensterbeschränkungen.
  • Zuweisungs- und Standortplanung – Zuweisung von Aufgaben zu Ressourcen oder Standortwahl von Einrichtungen zur Kostenminimierung.
  • Graphfärbung, Netzwerkdesign und Telekommunikation – Lösung diskreter struktureller Optimierungsprobleme.
  • Merkmalsauswahl und Hyperparameter-Suche – Erkundung diskreter Konfigurationsräume in Machine-Learning-Pipelines.

So funktioniert es

So funktioniert es

1

Die Suche beginnt mit einer anfänglichen Kandidatenlösung, die zufällig oder mit einer gierigen Heuristik konstruiert werden kann. Die Tabu-Liste wird als leere Warteschlange fester Länge eingerichtet, und die bisher beste gefundene Lösung wird aufgezeichnet. Die Nachbarschaftsstruktur – die Regel, die definiert, welche Lösungen einen Schritt von der aktuellen Lösung entfernt sind – muss so definiert werden, dass sie für das spezifische Problem sinnvoll ist.

2

Von der aktuellen Lösung aus werden alle Züge in der definierten Nachbarschaft generiert und anhand der Zielfunktion bewertet. Jeder Zug entspricht einer kleinen Perturbation, wie dem Vertauschen zweier Elemente in einer Sequenz oder dem Umkehren einer binären Variablen. Die Nachbarschaft muss reichhaltig genug sein, um eine sinnvolle Erkundung zu ermöglichen, aber klein genug, um in jeder Iteration handhabbar zu sein.

3

Jeder Kandidatenzug wird gegen die Tabu-Liste geprüft. Wenn der Zug – oder das ihn charakterisierende Merkmal – auf der Liste erscheint, wird er als tabu klassifiziert und ist verboten, es sei denn, er erfüllt ein Aspirationskriterium: Typischerweise, wenn die resultierende Lösung besser wäre als die bisher beste gefundene Lösung, wird der Tabu-Status aufgehoben und der Zug erlaubt. Dieser Aspirationsmechanismus gibt dem Algorithmus Flexibilität, ohne seine Anti-Zyklus-Disziplin aufzugeben.

4

Unter allen nicht-tabu Zügen (und allen tabu Zügen, die das Aspirationskriterium erfüllen) wird der am besten abschneidende Zug ausgewählt und ausgeführt, auch wenn er den Zielfunktionswert verschlechtert. Diese Bereitschaft, Verschlechterungen zu akzeptieren, ermöglicht es dem Algorithmus, lokale Optima zu verlassen, was das definierende Merkmal von Tabu Search im Vergleich zu einfachem Hill Climbing ist.

5

Nachdem der Zug ausgeführt wurde, wird die Tabu-Liste aktualisiert, indem die Umkehrung des gerade gemachten Zuges (oder sein charakterisierendes Merkmal) hinzugefügt wird, und der älteste Eintrag wird entfernt, wenn die Liste voll ist, wodurch ihre feste Länge – die Tabu-Tenure – beibehalten wird. Wenn die neue Lösung besser ist als die beste aufgezeichnete Lösung, wird die beste Lösung aktualisiert. Optionale Langzeitgedächtnisstrukturen können die Lösungsfrequenz oder -aktualität verfolgen, um die Diversifizierung in weniger besuchte Regionen oder die Intensivierung um vielversprechende herum zu steuern.

6

Der Algorithmus iteriert weiter, bis ein Stoppkriterium erfüllt ist: eine maximale Anzahl von Iterationen, ein Zielwert der Zielfunktion oder eine feste Anzahl von Iterationen ohne Verbesserung. Die während der gesamten Suche gefundene beste Lösung wird als Ergebnis zurückgegeben. Die Wahl eines angemessenen Iterationsbudgets ist entscheidend – zu wenige Iterationen verhindern eine ausreichende Nachbarschaftserkundung.

Häufige Fallstricke

  • Das Einstellen einer zu kurzen Tabu-Tenure erlaubt wiederholtes Zyklieren, was den Zweck des Tabu-Mechanismus zunichtemacht; die Tenure sollte für die Problemgröße abgestimmt werden.
  • Das Einstellen einer zu langen Tenure schränkt die Suche übermäßig ein und verhindert, dass der Algorithmus Regionen erneut besucht, die Verbesserungen enthalten könnten.
  • Weniger als etwa 1.000 Iterationen durchzuführen bedeutet, dass die Suche den Suchraum nicht ausreichend erkundet hat – wenn die Rechenleistung begrenzt ist, greifen Sie auf Simulated Annealing zurück, das mit weniger Iterationen schnell nützliche Ergebnisse liefern kann.
  • Die Verwendung einer zu engen Nachbarschaft (z. B. nur einzelne Tauschzüge bei einer komplexen Struktur) führt zu einer flachen Suche; stellen Sie sicher, dass die Nachbarschaft reichhaltig genug ist, um alle vielversprechenden Regionen des Lösungsraums zu verbinden.
  • Das Ignorieren des Aspirationskriteriums kann Züge zum globalen Optimum dauerhaft blockieren, wenn dieser Zug zufällig tabu ist; implementieren Sie immer mindestens die Standardüberschreibung der besten Lösung.

Häufig gestellte Fragen

Wie unterscheidet sich Tabu Search von Simulated Annealing?

Beide Methoden akzeptieren Verschlechterungszüge, um lokale Optima zu verlassen, unterscheiden sich aber im Mechanismus. Simulated Annealing akzeptiert schlechtere Züge probabilistisch, gesteuert durch einen Kühl-Temperaturparameter. Tabu Search akzeptiert den besten verfügbaren nicht-tabu Zug deterministisch, gesteuert durch explizites Gedächtnis über kürzliche Züge. Tabu Search ist im Allgemeinen effektiver bei strukturierten kombinatorischen Problemen; Simulated Annealing kann bei Problemen mit kontinuierlichen oder nahezu kontinuierlichen Landschaften einfacher zu tunen sein und ist vorzuziehen, wenn das Iterationsbudget klein ist (unter etwa 1.000 Iterationen).

Wie lang sollte die Tabu-Liste sein?

Die Tabu-Tenure – die Anzahl der Iterationen, für die ein Zug verboten bleibt – ist problemabhängig. Ein häufig genannter Ausgangspunkt ist eine Tenure, die proportional zur Quadratwurzel der Problemgröße ist, aber dies sollte empirisch abgestimmt werden. Eine zu kurze Tenure erlaubt Zyklieren; eine zu lange Tenure schränkt die Suche übermäßig ein. Adaptive oder randomisierte Tenure-Strategien können die Empfindlichkeit gegenüber dieser Wahl verringern.

Garantiert Tabu Search das Finden des globalen Optimums?

Nein. Tabu Search ist eine Metaheuristik und bietet keine Optimalitätsgarantie. Sie zielt darauf ab, effizient qualitativ hochwertige Lösungen zu finden, aber das Ergebnis hängt von der Nachbarschaftsstruktur, der Tenure, der Anzahl der Iterationen und der Anfangslösung ab. Für eine Optimalitätsgarantie ist eine exakte Methode wie ganzzahlige Programmierung erforderlich, obwohl exakte Methoden für große Instanzen rechnerisch nicht durchführbar sein können.

Was ist ein Aspirationskriterium und warum ist es notwendig?

Ein Aspirationskriterium ist eine Regel, die den Tabu-Status eines Zuges unter besonderen Bedingungen aufhebt. Das häufigste Kriterium ist: Wenn die Ausführung eines tabu Zuges eine Lösung ergeben würde, die besser ist als die bisher beste gefundene Lösung, wird die Tabu-Beschränkung aufgehoben und der Zug erlaubt. Ohne diese Überschreibung könnte der Tabu-Mechanismus den Weg zum globalen Optimum dauerhaft blockieren, wenn dieser Weg über einen kürzlich besuchten Zug führt.

Verwandte Methoden

Quellen

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Publikationsreferenz öffnen
    Kopiert.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Kopiert.