Lade Inhalt...

Tabu Search und seine Variationen

Seminararbeit 2010 18 Seiten

BWL - Beschaffung, Produktion, Logistik

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Tabu Search
2.1 Grundlegende Funktionsweise
2.2 Lösungsraum und Nachbarschaft
2.3 Tabus
2.4 Aspirationskriterium
2.5 Abbruchkriterium

3 Erweiternde Konzepte
3.1 Intensivierung
3.2 Diversifikation
3.3 Ersatz- und Hilfsziele

4 Anwendungen
4.1 Anwendungsbreite
4.2 Modellierung am Beispiel des öffentlichen Personenverkehrs

5 Zusammenfassung

Literaturverzeichnis

1 Einleitung

Mit dem Aufkommen von kombinatorischen Problemen im Rahmen des Operation Research (z.B. Stunden-/Raumplanung einer Schule, Planung einer Lieferantentour) wurden sogenannte Heuristiken (= Lösungsstrategien) entwickelt um diese zu lösen. Da diese Problemstellungen jedoch immer komplexer und der damit verbundene Rechenaufwand zur Bewältigung immer höher wurde, suchte man Anfang der 70er Jahre nach möglichst effektiven Lösungsverfahren. Eine der populärsten ist die 1986 unabhängig voneinander von dem US-Amerikaner Fred Glover und dem Belgier Pierre Hansen (Eiselt und Sandblom, 2000, S. 243) entwickelte Metaheuristik Tabu Search, die in oft sehr effektiver Rechenzeit eine nahezu optimale Lösung findet. Vor allem Glover wurde durch seine Weiterentwicklung des Tabu Search (z.B. in seinem Buch „Tabu Search“ von Glover und Laguna, 1997) zu einem Vorreiter auf diesem Gebiet.

In dieser Seminararbeit liefere ich einen Einblick in die Metaheuristik Tabu Search, wobei ich neben der grundlegenden Funktionsweise auch Erweiterungen und Abwandlungen betrachte, sowie die praktische Umsetzung anhand von Beispielen aufzeige.

2 Tabu Search

2.1 Grundlegende Funktionsweise

Tabu Search ist durch die Nutzung eines Kurzzeitgedächtnisses eine Erweiterung der Heuristik Local Search. Local Search ist ein iteratives Verfahren in dem von einer Startlösung aus ein gegebener Lösungsraum durchsucht wird. Dabei wird in jedem Suchschritt die Lösung durch Verbesserungen, die durch direkten Austausch einzelner Komponenten erreicht werden können, geringfügig verändert. Da laut dieser Heuristik nur verbessernde Züge zugelassen werden kommt es schnell zu einem „Feststecken“ im lokalen Optimum. Das (oft unterschiedliche) globale Optimum kann so gegebenenfalls nicht erreicht werden.

Abbildung in dieser Leseprobe nicht enthalten

Beispiel 1: Mein Lösungsraum ist die rechts dargestellte Matrix mit Nutzenwerten. Meine Startlösung x0 ist die 3 .. und ich will meinen Nutzen maximieren. Local Search schreibt mir nun vor dass ich den Nachbarschaftsraum . .. den ich von meiner Lösung aus in einem Zug erreichen kann {2,3; 6; 4,1} nach dem bestmöglichen Wert xb (in dem Beispiel ist es die 6) absuche und wenn x0<xb habe ich eine neues Optimum x* gefunden und setze x*:=xb. Jetzt suche ich wieder die Nachbarschaft {1,1; 2,1; 2,2; 2,3; 5; 3; 4,1; 2} meines neuen x*=6 nach Verbesserungen ab. Da jedoch kein neues Optimum erreicht werden kann stoppt nach Local Search die Suche und gibt mir x*=6 als Optimum heraus. Wie an der Matrix leicht zu sehen ist handelt es sich hier jedoch nur um ein lokales Optimum, das globale Optimum beträgt 20.

Um diese Diskrepanz zu überwinden wurden bei der Metaheuristik Tabu Search einige Abwandlungen vorgenommen. So werden auch verschlechternde Züge zugelassen (und zwar die mit dem jeweils geringsten Regretwert). Dadurch ermöglicht die Heuristik ein weiteres Absuchen des Lösungsraumes und der damit verbundenen Überwindung des lokalen Optimums. Um ein Kreisen zu vermeiden (sonst würde die Heuristik immer vom lokalen Optimum zum nächstschlechteren „hin- und herspringen“) werden die bereits erhaltenen Züge für eine bestimmte Dauer (Tabudauer) „Tabu“ gesetzt. Dies erfolgt über ein Kurzzeitgedächtnis indem diese Tabus gespeichert werden.

Ein allgemeiner Algorithmus für dieses Vorgehen kann folgendermaßen gegeben werden (Vergleich: Klein, Scholl, 2004, S. 470):

Abbildung in dieser Leseprobe nicht enthalten

4. Aktualisierung der Tabuliste
5. Abbruch bei Erreichen eines Abbruchkriteriums

Wobei ZFW(x) den Zielfunktionswert ist und NB(x) die Nachbarn von x bestimmt. Die Starlösung kann entweder zufällig gewählt oder durch ein Eröffnungsverfahren bestimmt werden. Abbruchkriterien können dagegen die Anzahl der Iterationen oder die vergangene Rechenzeit sein.

Abbildung in dieser Leseprobe nicht enthalten

Beispiel 2: Ich wende nun Tabu Search auf mein Beispiel 1. Startlösung ist wieder die 3 und ich setze die Tabudauer auf 2 Züge. Wie beim Local Search ist die. .beste Nachbarlösung die 6. In meine Tabuliste TL wird .. .. . nun die 3 als schon besuchte Lösung aufgenommen. Damit ist nach dem ersten Zug mein x*=6 und TL=(3). Jetzt suche ich wieder meine Nachbarschaft nach besseren Lösungen ab. Bei Local Search würde ich wie in Beispiel 1 gezeigt keine Verbesserungen finden und die Suche wär damit beendet. Bei Tabu Search hingegen lasse ich auch schlechtere Lösungen als x*=6 zu. Hier suche ich die Lösung mit dem geringsten Regretwert. Hier wäre das die 5. Damit führe ich den Zug aus. Mein x* bleibt bei 6, meine aktuelle Position x ist 5 und TL=(3,6). Von der 5 finde ich nun 2 verbessernde Züge, den Schritt zur 6 und den zur 20. Davon mal abgesehen dass uns die 20 den besseren ZFW bringt dürfte ich auch nichtmehr zur 6 zurückkehren da diese in der TL tabugesetzt ist. Damit bleibt nur der Zug zur 20. Mein x* ist 20 und es gilt TL=(6,5) (die 3 aus dem ersten Schritt fällt heraus weil die Tabudauer auf 2 beschränkt ist). Ein neues lokales Optimum ist gefunden. Die Suche wird dadurch jedoch nicht beendet, sondern geht wie folgt weiter:

Abbildung in dieser Leseprobe nicht enthalten

Wie man sieht kommt es in Iteration fünf bis zehn zu einem Kreisen (sich wiederholende Werte mit gleicher Tabuliste) so dass keine bessere Lösung gefunden wird. Wir erhalten also unser Optimum bei x*=20, was in diesem Beispiel auch dem globalen Optimum entspricht.

[...]

Details

Seiten
18
Jahr
2010
ISBN (eBook)
9783640816545
ISBN (Buch)
9783656447481
Dateigröße
511 KB
Sprache
Deutsch
Katalognummer
v165893
Institution / Hochschule
Friedrich-Schiller-Universität Jena
Note
Schlagworte
Tabu Search Metaheuristik Heuristik Intensivierung Diversifikation Aspirationskriterium

Autor

Teilen

Zurück

Titel: Tabu Search und seine Variationen