Es gibt in der Theorie einige Problemstellungen, die in ihren Grundlagen leicht zu verstehen und nachzuvollziehen sind. Man denke z.B. an das Rucksackproblem1, an verschiedenste Problemstellungen der Ressourcenplanung oder auch das Problem des Handlungsreisenden2 (TSP), welches später noch genauer betrachtet wird3. In der Praxis sind solche Probleme durchaus anzutreffen, wie z.B. beim Beladen von Containern, der Stunden- und Raumplanung einer Schule oder Universität oder der Planung einer LKW-Tour4.
All diese Probleme weisen allerdings eine exponentielle Komplexität auf, d.h. sie können kaum durch vollständige Enumeration5 gelöst werden. Schon ein TSP mit 10 zu besuchenden Orten führt zu über 3,6 Mio. Lösungsmöglichkeiten. Auch andere exakte Verfahren wie das Branch & Bound-Verfahren, das auf einer unvollständigen, begrenzten Enumeration basiert6, führen schnell zu einem unökonomischen Aufwand, d.h. sie können kaum in einer vertretbaren Zeit gelöst werden.
Inhaltsverzeichnis
1 Einführung
1.1 Einordnung von Tabu Search
1.2 Geschichtlicher Überblick
2 Tabu Search
2.1 Grundlagen
2.1.1 Kombinatorisches Optimierungsproblem
2.1.2 Zug und Nachbarschaft
2.1.3 Nachbarschafts-Suchalgorithmus
2.2 Das eigentliche Verfahren
2.2.1 Tabuliste
2.2.2 Tabu Search Algorithmus
2.2.3 Anmerkungen und Erweiterungen
3 Ein Beispiel: Traveling Salesman Problem
3.1 Einführung
3.2 Tabu Search
4 Schlussbemerkung
Zielsetzung und Themen
Die vorliegende Arbeit zielt darauf ab, Tabu Search als Heuristik im Bereich der kombinatorischen Optimierung theoretisch fundiert einzuführen, deren Wirkungsweise zu erläutern und ihre Anwendung anhand des Traveling Salesman Problems zu verdeutlichen.
- Grundlagen der kombinatorischen Optimierung und Nachbarschaftssuche
- Mechanismen und algorithmische Struktur von Tabu Search
- Implementierungsaspekte wie Tabulisten und Aspirationskriterien
- Erweiterungen zur Steuerung der Suche mittels Gedächtnisfunktionen
- Praxisrelevanz und Effizienz von Metaheuristiken
Auszug aus dem Buch
2.2.1 Tabuliste
Erreicht wird dies über die Tabuliste, die damit elementarster Bestandteil einer jeden Form von TS ist. Beim einfachsten Ansatz „strict prohibition“ werden alle bisher besuchten Lösungen gespeichert. Sollte später ein Zug zu einer bereits in der Liste gespeicherten Lösung führen, so wird dieser Zug abgelehnt. Dies erfordert gleichwohl die Speicherung aller bisherigen Lösungen und die aktuelle Lösung muss mit all ihren Vorgängern verglichen werden, woraus sowohl ein hoher Speicher- als auch Rechenzeitbedarf resultieren. Es gibt noch einige Modifikationen an diesem Ansatz, die die Effizienz aber nicht wesentlich steigern können.
Erst mit einem Ansatz wie dem mittlerweile am weitesten verbreiteten „move prohibition approach“ ist die einfache und ressourcenschonende Implementierung am Rechner möglich. Dabei werden nicht die besuchten Lösungen gespeichert, sondern – wie der Name es bereits andeutet – die durchgeführten Züge bzw. ihre verbotenen Komplementäre. Außerdem ist die Listenlänge beschränkt auf eine bestimmte Anzahl t von Iterationen. Nach jedem ausgeführten Zug wird diese Liste dahingehend aktualisiert, dass der am längsten in der Vergangenheit liegende Zug aus der Tabuliste herausfällt und der zuletzt durchgeführte Zug an das Ende der Liste geschrieben wird.
Zusammenfassung der Kapitel
1 Einführung: Einordnung der Problematik der kombinatorischen Optimierung und ein kurzer historischer Abriss zur Entstehung von Tabu Search.
2 Tabu Search: Detaillierte theoretische Darstellung der Grundlagen, des eigentlichen Algorithmus und weiterführender Konzepte wie Tabulisten und Gedächtnistraining.
3 Ein Beispiel: Traveling Salesman Problem: Praktische Anwendung der zuvor eingeführten theoretischen Prinzipien auf das klassische Problem des Handlungsreisenden.
4 Schlussbemerkung: Resümee zur Qualität, Effizienz und zukünftigen Bedeutung von Tabu Search im Vergleich zu anderen Verfahren.
Schlüsselwörter
Tabu Search, Metaheuristik, kombinatorische Optimierung, Nachbarschaftssuche, Tabuliste, Traveling Salesman Problem, Algorithmus, Gedächtnisfunktionen, lokale Optima, Optimierung, lokale Suche, Aspirationskriterien, Diversifizierung, Intensivierung, Zielfunktionswert.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die Metaheuristik „Tabu Search“ als Verfahren zur Lösung komplexer kombinatorischer Optimierungsprobleme.
Was sind die zentralen Themenfelder der Arbeit?
Die zentralen Themen umfassen die theoretischen Grundlagen der Nachbarschaftssuche, die algorithmische Umsetzung mittels Tabulisten und Gedächtnismodellen sowie die praktische Demonstration am Traveling Salesman Problem.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel der Arbeit ist es, die Funktionsweise von Tabu Search als intelligentes Suchverfahren zu erklären und die Vorteile gegenüber einfacheren lokalen Suchverfahren aufzuzeigen.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine systematische Literaturanalyse durchgeführt, um die methodischen Prinzipien von Tabu Search (z. B. Kurzzeit- und Langzeitgedächtnis) zu definieren und diese anschließend auf ein konkretes Beispiel anzuwenden.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die Einführung der algorithmischen Grundlagen, die detaillierte Beschreibung der Tabu-Suche (inklusive Erweiterungen) und eine beispielhafte Anwendung auf das Traveling Salesman Problem.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich primär über Begriffe wie Tabu Search, Metaheuristik, kombinatorische Optimierung, Tabuliste und Nachbarschaftssuche definieren.
Welche Rolle spielt das Gedächtnis bei Tabu Search?
Das Gedächtnis, implementiert durch Tabulisten oder Frequenzlisten, verhindert das „Kreisen“ zwischen bereits besuchten Lösungen und steuert die Suche gezielt in neue, noch nicht explorierte Lösungsregionen.
Warum ist Tabu Search anderen heuristischen Verfahren häufig überlegen?
Tabu Search gilt als zielstrebiger und „aggressiver“ als rein stochastische Verfahren wie Simulated Annealing, da es durch seine gedächtnisgestützte Strategie systematischer aus lokalen Minima ausbrechen kann.
- Quote paper
- Jörg Heinicke (Author), 2002, Tabu Search, Munich, GRIN Verlag, https://www.grin.com/document/9288
