Einleitung
Gegenstand der vorliegenden Arbeit ist die Auseinandersetzung mit Tabu Search, einem heuristischen Verfahren. Es werden zunächst die heuristischen Verfahren für sich betrachtet, um dem Leser einen kurzen Einblick in die verschiedenen Lösungsverfahren zu ermöglichen.
In Kapitel 3 erfolgt eine ausführliche Beschreibung der Grundlagen von TS. Zunächst wird hier die geschichtliche Entwicklung dargestellt, um anschließend kurz das Konzept von Tabu Search zu erklären. In Hinblick auf die weiteren Ausführungen ist eine Erläuterung der wichtigsten Begriffe von TS unentbehrlich. Diese wird
in Kap. 3.3 vorgenommen. Daran schließt sich die ausführliche Darstellung der Funktionsweise von TS an, wobei auf die Probleme des Verfahrens und mögliche Lösungswege eingegangen wird. (Kap. 3.4.2 – 3.4.4) Danach werden einige Anwendungsbeispiele vorgestellt, welche die praktische Relevanz von TS erkennen lassen. Jedoch erfolgt eine Beschränkung auf die Grundprobleme, da ein weiteres Vordringen den Rahmen dieser Arbeit überschreiten würde.
In Kap. 5 wird ein Überblick über die bislang entwickelten Lösungsmethoden präsentiert, speziell in Hinblick auf die in Kap. 4.3 kurz eingeführte Tourenplanung. Im Weiteren erfolgt die Vorstellung neuerer Verfahren, welche die Mängel des ursprünglichen
TSV beseitigen sollen. Den Abschluss der Arbeit bilden die Zusammenfassung der Hauptergebnisse und ein kurzer Ausblick auf mögliche Weiterentwicklungen des vorgestellten Verfahrens.
[...]
Inhaltsverzeichnis
1 Einleitung
2 Heuristische Verfahren
3 Grundidee
3.1 Historischer Abriss
3.2 Was ist Tabu Search?
3.3 Erläuterung der wichtigsten Begriffe
3.3.1 Zug
3.3.2 Lokale und Globale Optima
3.3.3 Tabuliste
3.3.4 Tabudauer
3.3.5 Aspirationskriterien
3.4 Wie funktioniert Tabu Search?
3.4.1 Grundlegende Mechanismen
3.4.2 Speicheraufbau
3.4.3 Intensivierung
3.4.4 Diversifikation
4 Anwendungsbeispiele
4.1 Knapsackproblem
4.2 Reihenfolgeproblem bei der Isomattenentwicklung
4.3 Die Tourenplanung
5 Varianten
5.1 Entwicklungsrichtungen
5.2 Paralleles Tabu Search
5.3 Verteiltparalleles Tabu Search Verfahren
5.4 Reactive Tabu Search
6 Ausblick für die Zukunft & kritische Würdigung
Zielsetzung & Themen
Die vorliegende Arbeit setzt sich mit dem heuristischen Optimierungsverfahren "Tabu Search" (TS) auseinander. Ziel ist es, die theoretischen Grundlagen, die Funktionsweise sowie die verschiedenen Varianten und Anwendungsgebiete dieses Verfahrens im Kontext kombinatorischer Optimierungsprobleme wissenschaftlich darzulegen und kritisch zu bewerten.
- Historische Entwicklung und Einordnung von Tabu Search in die Künstliche Intelligenz.
- Systematische Erläuterung der zentralen Mechanismen wie Tabuliste, Speicherkonzept und Aspirationskriterien.
- Detaillierte Analyse der Suchphasen Intensivierung und Diversifikation zur Vermeidung lokaler Optima.
- Darstellung praktischer Anwendungsbeispiele, insbesondere im Bereich der Tourenplanung.
- Diskussion spezialisierter Verfahrensvarianten wie das parallele und das Reactive Tabu Search.
Auszug aus dem Buch
3.3.1 Zug
Ein Zug ist eine Funktion, die eine Lösung in eine andere Lösung transformiert. Jede von einer Lösung x durch Ausführung eines Zuges erreichbare andere Lösung x' wird als Nachbarlösung bezeichnet. Die Menge aller Nachbarn X' = {x'1, ... ,x'n} bildet die Nachbarschaft von x. In jeder Iteration wird ein solcher Zug ausgeführt, um von einer ermittelten Lösung x zu einer benachbarten Lösung x' zu wandern.
Ein Zug wird durch Vertauschen oder Verschieben von Elementen durchgeführt. Hat sich im Laufe der Iterationen z. B. der Vektor [1, 2, 3] für die Reihenfolge der Aufträge (Jobs) auf den Maschinen ergeben, so wird ein (mehrattributiver) Zug ausgeführt, indem die Reihenfolge zweier Variablen geändert wird. Durch einen Zug wird der Vektor [1, 2, 3] z.B. zum Vektor [1, 3, 2].
Bei einem Optimierungsproblem in Form des Knapsackproblems (Vgl. S.14) besteht ein Zug darin, Gegenstände in den Koffer einzupacken oder aus dem Koffer herauszunehmen. Hat sich im Laufe der Iterationen ergeben, dass die vier Gegenstände {A, B, C, D} in den Koffer gepackt werden, so kann ein Zug darin bestehen, dass Gegenstand A aus dem Koffer herausgenommen oder Gegenstand E in den Koffer eingepackt wird. So ergibt sich nach einem Zug beispielsweise die Kombination {B, C, D} oder {A, B, C, D, E}. Ein gleiches Ergebnis kann dadurch erzielt werden, dass die Problemformulierung mit Hilfe von Binärvariablen erfolgt. Beim Auspacken eines Gegenstandes erhält die Binärvariable den Wert 0 und beim Einpacken 1.
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung gibt einen Überblick über das Thema der Arbeit, die Zielsetzung sowie den strukturellen Aufbau der Untersuchung.
2 Heuristische Verfahren: Dieses Kapitel betrachtet allgemein die Bedeutung heuristischer Verfahren und deren Klassifizierung bei der Lösung von Optimierungsproblemen.
3 Grundidee: Die Grundlagen von Tabu Search werden erläutert, einschließlich historischer Hintergründe, wichtiger Fachbegriffe, der Funktionsweise und der zugrundeliegenden Speichermechanismen.
4 Anwendungsbeispiele: Anhand des Knapsackproblems, der Isomattenentwicklung und der Tourenplanung wird die praktische Relevanz und Anwendung von TS verdeutlicht.
5 Varianten: Hier werden weiterführende Entwicklungen und spezialisierte Ansätze wie das parallele und das Reactive Tabu Search vorgestellt.
6 Ausblick für die Zukunft & kritische Würdigung: Das Abschlusskapitel bietet eine kritische Reflexion des Verfahrens und einen Ausblick auf zukünftige Entwicklungen sowie Forschungspotenziale.
Schlüsselwörter
Tabu Search, Metaheuristik, kombinatorische Optimierung, Nachbarschaftssuche, Tabuliste, lokale Optima, Intensivierung, Diversifikation, Tourenplanung, Knapsackproblem, Zielfunktion, Algorithmus, Künstliche Intelligenz, Speicherverfahren, Iteration
Häufig gestellte Fragen
Worum geht es in der vorliegenden Arbeit grundsätzlich?
Die Arbeit behandelt das heuristische Verfahren "Tabu Search" als eine intelligente Methode zur Lösung komplexer kombinatorischer Optimierungsprobleme.
Welche zentralen Themenfelder werden in der Arbeit adressiert?
Die zentralen Felder sind die theoretische Fundierung des Verfahrens, die Funktionsweise der verschiedenen Suchmechanismen, der Einsatz von Speicherstrukturen sowie die Anwendung auf praktische Logistik- und Planungsprobleme.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist eine wissenschaftlich fundierte Darstellung, wie durch Tabu Search in einer Vielzahl von Problemstellungen optimale oder nahezu optimale Lösungen effizient gefunden werden können.
Welche wissenschaftliche Methode wird verwendet?
Es handelt sich um eine theoretische Arbeit, die auf einer umfassenden Literaturanalyse und der systematischer Beschreibung von Algorithmen sowie deren Anwendung in Fallbeispielen basiert.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Erläuterung der TS-Grundlagen (Begrifflichkeiten, Funktionen), die Darstellung konkreter Anwendungsbeispiele und die Analyse fortgeschrittener Varianten des Verfahrens.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die wichtigsten Begriffe umfassen Metaheuristik, Tabuliste, Intensivierung, Diversifikation, Optimierungsprobleme und Speicherstrategien.
Wie verhindert Tabu Search, dass der Suchprozess in lokalen Optima stecken bleibt?
Das Verfahren nutzt ein flexibles Gedächtnis, temporäre Zielfunktionsverschlechterungen und spezifische Strategien zur Diversifikation, um den Suchraum über lokale Maxima oder Minima hinaus zu erweitern.
Warum ist die Tabuliste für den Erfolg von Tabu Search entscheidend?
Die Tabuliste verhindert Zyklen und ein Steckenbleiben in bereits besuchten Lösungsräumen, indem sie bestimmte Züge für eine definierte Anzahl von Iterationen sperrt und so den Algorithmus zwingt, neue Wege zu erkunden.
- Quote paper
- Nicole Blechschmidt (Author), 2001, Tabu Search - Grundprinzip, Varianten und Anwendungen, Munich, GRIN Verlag, https://www.grin.com/document/3189