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
- Einführung
- Einordnung von Tabu Search
- Geschichtlicher Überblick
- Tabu Search
- Grundlagen
- Kombinatorisches Optimierungsproblem
- Zug und Nachbarschaft
- Nachbarschafts-Suchalgorithmus
- Das eigentliche Verfahren
- Tabuliste
- Tabu Search Algorithmus
- Anmerkungen und Erweiterungen
- Ein Beispiel: Traveling Salesman Problem
- Einführung
- Tabu Search
- Schlussbemerkung
Zielsetzung und Themenschwerpunkte
Diese Hauptseminararbeit befasst sich mit Tabu Search als einer Heuristik aus dem Bereich der kombinatorischen Optimierung. Zunächst wird Tabu Search allgemein vorgestellt und in den Kontext der kombinatorischen Optimierung eingeordnet. Anschließend werden die Grundlagen des Verfahrens erläutert, bevor auf das eigentliche Verfahren Tabu Search eingegangen wird.
- Grundlagen der kombinatorischen Optimierung
- Das Konzept von Tabu Search
- Anwendungen und Anwendungsbeispiele
- Vergleich von Tabu Search mit anderen Heuristiken
- Bewertung der Effizienz von Tabu Search
Zusammenfassung der Kapitel
Einführung
Dieses Kapitel bietet eine Einleitung zu Tabu Search und erläutert seine Bedeutung im Kontext der kombinatorischen Optimierung. Es werden Beispiele für Problemstellungen wie das Rucksackproblem und das Traveling Salesman Problem (TSP) genannt und deren Komplexität diskutiert. Schließlich wird ein kurzer historischer Überblick über die Entwicklung von Tabu Search gegeben.
Tabu Search
In diesem Kapitel werden die grundlegenden Konzepte von Tabu Search erläutert. Dazu gehört die Definition eines kombinatorischen Optimierungsproblems, die Begriffe „Zug“ und „Nachbarschaft“ sowie die Vorstellung eines Nachbarschafts-Suchalgorithmus. Schließlich wird das eigentliche Verfahren Tabu Search mit seinen Komponenten wie der Tabuliste und dem Tabu Search Algorithmus vorgestellt. Darüber hinaus werden Erweiterungen und Anmerkungen zu Tabu Search diskutiert.
Ein Beispiel: Traveling Salesman Problem
Das Kapitel behandelt das Traveling Salesman Problem (TSP) als ein Beispiel für ein kombinatorisches Optimierungsproblem, das mithilfe von Tabu Search gelöst werden kann. Es wird eine Einführung in das TSP gegeben und anschließend die Anwendung von Tabu Search auf dieses Problem erläutert.
Schlüsselwörter
Kombinatorische Optimierung, Heuristik, Tabu Search, Traveling Salesman Problem (TSP), Nachbarschaft, Tabuliste, Algorithmus, Effizienz, Komplexität.
- Quote paper
- Jörg Heinicke (Author), 2002, Tabu Search, Munich, GRIN Verlag, https://www.grin.com/document/9288
