Inhaltsverzeichnis

Abk  ürzungsverzeichnis.  1

1  Einleitung.  2

2  Heuristische Verfahren  2

3  Grundidee.  4

3.1  Historischer Abriss  4

3.2  Was ist Tabu Search?  5

3.3  Erläuterung der wichtigsten Begriffe.  6

3.3.1  Zug  6

3.3.2  Lokale und Globale Optima.  7

3.3.3  Tabuliste.  7

3.3.4  Tabudauer.  8

3.3.5  Aspirationskriterien.  9

3.4  Wie funktioniert Tabu Search?  9

3.4.1  Grundlegende Mechanismen  9

3.4.2  Speicheraufbau  10

3.4.3  Intensivierung.  12

3.4.4  Diversifikation.  13

4  Anwendungsbeispiele.  14

4.1  Knapsackproblem.  14

4.2  Reihenfolgeproblem bei der Isomattenentwicklung  15

4.3  Die Tourenplanung.  19

5  Varianten  21

5.1  Entwicklungsrichtungen.  21

5.2  Paralleles Tabu Search  23

5.3  Verteiltparalleles Tabu Search Verfahren.  24

5.4  Reactive Tabu Search  25

6  Ausblick für die Zukunft kritische Würdigung  26

Literaturverzeichnis   28

Abkürzungsverzeichnis

EDV .......................... Elektronische Datenverarbeitung GA ............................ Genetische Algorithmen LAN........................... Local Area Network MBMS....................... Multiple Balls, Multiple Strategies MBSS ....................... Multiple Balls, Single Strategy QAP .......................... Quadratic Assignment Problem RTS .......................... Reactive Tabu Search SA............................. Simulated Annealing SBMS ....................... Single Ball, Multiple Strategies SBSS ........................ Single Ball, Single Strategy TD............................. Tabudauer TS ............................. Tabu Search TSP........................... Travelling Salesman Problem TSV........................... Tabu Search Verfahren

1

(LQOHLWXQJ

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.

+HXULVWLVFKH9HUIDKUHQ

Durch den schnellen Wandel in allen Lebensbereichen haben Optimierungsprobleme gegenwärtig eine besondere Relevanz. Deshalb wird nach immer besseren Lösungsmethoden gesucht. Verwandt werden dabei hauptsächlich die heuristischen Verfahren, die jedoch in der Literatur nicht einheitlich definiert sind. Auf eine dieser Definitionen wird im Folgenden kurz eingegangen. Wie Abbildung 1 zeigt, verwenden heuristische Verfahren nichtwillkürliche Ent-scheidungsoperatoren, die potentielle Lösungen vom Suchprozess ausschließen können. Für heuristische Verfahren charakteristisch und zugleich Abgrenzungs-

2

möglichkeit in Bezug auf exakte Verfahren ist die Tatsache, dass für sie kein Konvergenzbeweis geführt werden kann. Das heißt, nach einer endlichen Anzahl von Iterationen muss das Optimum nicht erreicht werden. Deshalb müssen bei einfachen Heuristiken oft schlechte Lösungen genügen.

$EELOGXQJ.ODVVLIL]LHUXQJYRQ/|VXQJVYHUIDKUHQ

4XHOOH,Q$QOHKQXQJDQ6WUHLP6

rung des Lösungsprozesses verwenden, bezeichnet man sie auch als „lokale Suchverfahren“. 2

Vorteile dieser Art von Heuristiken sind zum einen die leichte Programmierbarkeit und zum anderen der geringe Rechenaufwand. Dabei werden oft externe Abbruchkriterien vorgegeben, so dass für den Anwender die Möglichkeit besteht, selbst in den Ablauf einzugreifen.

Konstruktions- und Eröffnungsverfahren, wie z.B. Sweep- und Savingsverfahren für knotenorientierte Standardprobleme ³ , finden schnell gute Ausgangslösungen. Da meist dieses erste Ergebnis nicht zufriedenstellend ist, werden Verbesserungsverfahren, wie das r-opt-Verfahren oder TS, angewandt. Optimierungsprobleme kombinatorischer Art, wie im Bereich der Tourenplanung, der Investitionsplanung oder der Maschinenbelegungsplanung, sind zumeist leicht verständlich und erklärbar. Sie weisen jedoch schon bei einfachen Problemstel-

¹ Vgl.De Werra und Hertz (1989, S. 131).

² Vgl. Morton und Pentico (1993).

³ Vgl. Domschke (1990, S.140).

3

lungen mit wenigen Restriktionen eine große Anzahl möglicher Ergebnisse auf. Für die Lösung solcher komplexer Optimierungsprobleme wurden seit Anfang der achtziger Jahre verschiedene Metastrategien entwickelt, von denen hier einige genannt werden sollen.

Es gibt eine Reihe von metaheuristischen Verfahren aus unterschiedlichsten Bereichen der Wissenschaft. Das Simulated Annealing (SA) ist eine der Physik entlehnte Modellvorstellung zur Kristallisation von Körpern aus der Schmelze. Weitere Verfahren sind das Threshold Accepting und der Sintflut-Algorithmus. Der biologischen Evolution hat man den Genetischen Algorithmus nachempfunden. Lösungen und Zielfunktionswerte werden auf Genotypen und Fitnesswerten von Individuen abgebildet. Durch den Prozess der Erbgutskreuzung und Mutation sollen besonders “fitte” Individuen erzeugt werden. Das über Generationen hinweg ermittelte beste Individuum lässt sich dann auf eine i.a. sehr gute Lösung des Optimierungsproblems rücktransformieren. Das Ameisensystem ist die aus der künstlichen Intelligenz entlehnte Bestensuche A*. Sie ist je nach Ausgestaltung exakt oder heuristisch. Ursprünglich wurde die Bestensuche für Spielprogramme (z. B. Schachprogramme) und regelbasierte Expertensysteme entwickelt. Die Methode sucht z.B. vom aktuellen Spielzustand einen Pfad von Zügen bis zum Endzustand “Sieg” unter vorausschauender Bewertung zukünftiger Zustände. Ein weiteres metaheuristisches Verfahren, Tabu Search, soll im Rahmen dieser Arbeit ausführlich dargestellt werden.

*UXQGLGHH

+LVWRULVFKHU$EULVV

Das Grundprinzip des TS geht auf die Publikationen von F. Glover ⁴ aus den Jahren 1977 und 1986 sowie auf die Ausarbeitungen von P. Hansen und B. Jaumard ⁵ von 1987 zurück.

Eine vollständige Beschreibung von TS ist kaum möglich, da das Erfolgspotential der vielfältigen möglichen Elemente aufgrund theoretischer Überlegungen plausibel erscheint, jedoch noch nicht hinreichend ausgelotet worden ist. Traditionell

⁴ Vgl. Glover (1977), Glover (1986).

⁵ Vgl. Hansen und Jaumard (1987, S. 43-87).

4

wird TS für das Lösen kombinatorischer Optimierungsprobleme genutzt. Die Entwicklung von Tabu Search wurde von Skorin-Kapov (1994) und Widmer/Hertz (1989) entscheidend beeinflusst. Die gegenwärtige Entwicklung wird vor allem von Voß, Glover und Laguna vorangetrieben.

Die Grundlagen zum Lösen praktischer Probleme übersteigen die früheren Fähigkeiten bei weitem. Obwohl bisher viele Gebiete für TS erschlossen wurden, ist die Fülle der möglichen Anwendungen noch nicht ausgereizt.

:DVLVW7DEX6HDUFK"

Tabu Search (TS) ⁶ ist eine „intelligente“ Metaheuristik zur Lösung kombinatorischer Optimierungsprobleme. Es hat sich als sehr erfolgreich im Lösen einer Reihe von klassischen und praktischen Problemen erwiesen ⁷ . Aufgrund des Einsatzes eines flexiblen Gedächtnisses, das menschlichen Verhaltensweisen ähnelt, ordnet Glover TS dem Bereich der Künstlichen Intelligenz zu ⁸ . Daraus ergeben sich für den Computereinsatz zwei Ablaufmechanismen, um quantitative Entscheidungsmodelle zu lösen (Tabelle 1).

7DEHOOH/|VXQJVPHWKRGHQIUTXDQWLWDWLYH(QWVFKHLGXQJHQ

Auch für heutige Computer ist es fast unmöglich, komplexere Probleme in einem annehmbaren Zeitrahmen zu lösen, da mit der Anzahl der Ausgangswerte die Va- ⁶ „Tabu“ist ein Wort aus dem Polynesischen für Dinge, die man aufgrund deren Heiligkeit nicht berühren darf. Außerdem bedeutet es in der englischen Sprache „ein Risiko erkennen“.

⁷ Vgl. Glover (1990b, S. 74).

5

rianten der Durchführung exponentiell ansteigen. Es wurden jedoch intelligente Suchprozeduren gefunden, die die beste oder fast beste Lösung eines komplexen Entscheidungsproblems finden können, obwohl sie nur einen kleinen Teil der möglichen Alternativen untersuchen. 1986 schlug Fred Glover Tabu Search in seiner Urform als Lösungsverfahren vor. Ziel war es, durch Diversifikation (Vgl. S.13) das weiträumige Absuchen der Lösungsmenge zu erreichen. Daran anschließend sollte die Suche nach dem lokalen Optimum (Vgl. S.12) intensiviert werden. Um das Verständnis hierfür im Voraus zu erleichtern, sollte vorausschauend Abbildung 15 (S. 21) betrachtet werden.

Die Grundbegriffe, die für das Verstehen des Ablaufs von TS nötig sind, werden im Folgenden aufgeführt.

(UOlXWHUXQJGHUZLFKWLJVWHQ%HJULIIH

3.3.1 Zug

Ein Zug ist eine Funktion, die eine Lösung in eine andere Lösung transformiert. Jede von einer Lösung [ durch Ausführung eines Zuges erreichbare andere Lösung [¶ wird als Nachbarlösung bezeichnet. Die Menge aller Nachbarn

;¶ {[¶ [¶¡ } bildet die Nachbarschaft von [. In jeder Iteration wird ein solcher  

Zug ausgeführt, um von einer ermittelten Lösung [ zu einer benachbarten Lösung [¶ zu wandern.

Ein Zug wird durch Vertauschen oder Verschieben von Elementen durchgeführt. Hat sich im Laufe der Iterationen z. B. der Vektor > @ 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 >@ z.B. zum Vektor >@.

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 ^$ % & '` 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

⁸ Vgl. Glover (1990a).

6