Inhaltsverzeichnis

Inhaltsverzeichnis   

1  Einleitung  1

2  Tabu Search  2

2.1  Grundlegende Funktionsweise  2

2.2  Lösungsraum und Nachbarschaft  4

2.3  Tabus  5

2.4  Aspirationskriterium  6

2.5  Abbruchkriterium  7

3  Erweiternde Konzepte  8

3.1  Intensivierung  8

3.2  Diversifikation  8

3.3  Ersatz- und Hilfsziele  9

4  Anwendungen  10

4.1  Anwendungsbreite  10

4.2  Modellierung am Beispiel des öffentlichen Personenverkehrs  11

5  Zusammenfassung  15

Literaturverzeichnis   16

Literaturverzeichnis   16

Literaturverzeichnis   16

Literaturverzeichnis   16

Literaturverzeichnis   16

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.

1 

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.

den ich von meiner Lösung aus in einem Zug erreichen kann {2,3; 6; 4,1} nach dem bestmöglichen Wert x b (in dem Beispiel ist es die 6) absuche und wenn x 0 b habe ich eine neues Optimum x* gefunden und setze x*:=x b . 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.

2 

Ein allgemeiner Algorithmus für dieses Vorgehen kann folgendermaßen gegeben werden (Vergleich: Klein, Scholl, 2004, S. 470): 1. Start bei zulässiger Lösung x Speicherung als optimale Lösung x*

2. Suche aus NB(x) die nicht tabugesetzt und zulässig sind ein x‘ mit ZFW(x‘)≥ZFW(x‘‘), für alle x‘‘∈ {NB(x)} setzt x:=x‘ 3. Wenn ZFW(x)>ZFW(x*) x*:=x

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.

Beispiel 2: Ich wende nun Tabu Search auf mein

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:

3