Tabu Search

Term Paper (Advanced seminar) , 2002 , 20 Pages , Grade: 1,3

Business economics - Operations Research

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
• Literaturverzeichnis
  • Primärliteratur
  • Sekundärliteratur
• Abkürzungsverzeichnis

Zielsetzung und Themenschwerpunkte

Die vorliegende Hauptseminararbeit befasst sich mit Tabu Search als einer Heuristik aus dem Gebiet der kombinatorischen Optimierung. Die Arbeit bietet eine allgemeine Einleitung inklusive einer Einordnung von Tabu Search und beleuchtet die grundlegenden Prinzipien und Algorithmen der Methode.

• Einordnung von Tabu Search im Kontext der kombinatorischen Optimierung
• Grundlagen der Tabu Search-Methode
• Funktionsweise des Tabu Search-Algorithmus
• Anwendung von Tabu Search am Beispiel des Traveling Salesman Problems
• Bewertung und Vergleich von Tabu Search mit anderen Heuristiken

Zusammenfassung der Kapitel

Die Einleitung führt in das Thema Tabu Search ein und erläutert, warum Heuristiken für die Lösung komplexer Optimierungsprobleme notwendig sind. Der geschichtliche Überblick zeichnet die Entwicklung von Tabu Search von den 1970er Jahren bis zur Gegenwart nach.

Kapitel 2 beschäftigt sich mit den Grundlagen von Tabu Search. Es werden die Konzepte des kombinatorischen Optimierungsproblems, des Zugs und der Nachbarschaft sowie des Nachbarschafts-Suchalgorithmus vorgestellt.

Kapitel 2.2 beschreibt das eigentliche Verfahren der Tabu Search. Es wird die Tabuliste als zentrales Element der Methode erklärt und die Funktionsweise des Tabu Search-Algorithmus detailliert dargestellt.

Kapitel 2.2.3 geht auf verschiedene Erweiterungen und Anpassungen der Tabu Search-Methode ein, wie z.B. Abbruchkriterien, die Länge der Tabuliste, Aspirationskriterien und Gedächtnistraining.

Kapitel 3 verdeutlicht die Anwendung von Tabu Search am Beispiel des Traveling Salesman Problems. Es werden die grundlegenden Prinzipien und die Anwendung der Methode in diesem Kontext erläutert.

Schlüsselwörter

Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen Tabu Search, kombinatorische Optimierung, Heuristiken, Traveling Salesman Problem, Algorithmen, Tabuliste, Aspirationskriterien, Gedächtnistraining, Simulated Annealing, NP-schwere Probleme und Metaheuristiken.

• College: University of Leipzig (Institut für Empirische Wirtschaftsforschung)
• Course: HS Operations Research
• Grade: 1,3
• Author: Jörg Heinicke (Author)
• Publication Year: 2002
• Pages: 20
• Catalog Number: V9288
• ISBN (eBook): 9783638160261
• ISBN (Book): 9783656525332
• Language: German
• Tags: Optimierungsprobleme, Heuristik, Suchalgorithmus