Tabu Search

Inhaltsverzeichnis

1 Einführung
1.1 Einordnung von Tabu Search
1.2 Geschichtlicher Überblick

2 Tabu Search
2.1 Grundlagen
2.1.1 Kombinatorisches Optimierungsproblem
2.1.2 Zug und Nachbarschaft
2.1.3 Nachbarschafts-Suchalgorithmus
2.2 Das eigentliche Verfahren
2.2.1 Tabuliste
2.2.2 Tabu Search Algorithmus
2.2.3 Anmerkungen und Erweiterungen

3 Ein Beispiel: Traveling Salesman Problem
3.1 Einführung
3.2 Tabu Search

4 Schlussbemerkung

Literaturverzeichnis
Primärliteratur
Sekundärliteratur

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einführung

1.1 Einordnung von Tabu Search

Es gibt in der Theorie einige Problemstellungen, die in ihren Grundlagen leicht zu verstehen und nachzuvollziehen sind. Man denke z.B. an das Rucksackproblem^[1], an verschiedenste Problemstellungen der Ressourcenplanung oder auch das Problem des Handlungsreisenden^[2] (TSP), welches später noch genauer betrachtet wird^[3]. 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-Tour^[4].

All diese Probleme weisen allerdings eine exponentielle Komplexität auf, d.h. sie können kaum durch vollständige Enumeration^[5] 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 basiert^[6], führen schnell zu einem unökonomischen Aufwand, d.h. sie können kaum in einer vertretbaren Zeit gelöst werden.

1.2 Geschichtlicher Überblick

Um Lösungen für solche Problemstellungen zu erhalten, wurden seit dem Ende der 1970er Jahre so genannte Heuristiken^[7] entwickelt. Diese näherungsweisen Lösungsverfahren „bieten keine Garantie, dass ein Optimum gefunden (bzw. als solches erkannt) wird“.^[8] Ihr Vorteil besteht eher darin, dass sie mit einem vertretbaren Ressourcenaufwand möglichst optimale Lösungsansätze ergeben. Tabu Search (TS) ist eine solche Heuristik und die Grundlagen wurden 1986 unabhängig voneinander von dem US-Amerikaner Fred Glover und dem Belgier Pierre Hansen gelegt.^[9] Vor allem ersterer hat die Entwicklung von TS auch in den Folgejahren stark vorangetrieben und beeinflusst.^[10] Glover beschreibt TS dabei als ein Rahmenwerk, das auf Prinzipien zum intelligenten Problemlösen basiert.^[11]

2 Tabu Search

2.1 Grundlagen

Im folgenden Abschnitt werden die für TS nötigen Grundbegriffe eingeführt und definiert. Auch wird ein Algorithmus vorgestellt, der später die Grundlage für TS bilden wird.

2.1.1 Kombinatorisches Optimierungsproblem

Für ein kombinatorisches Optimierungsproblem^[12] gelten die Gesetze der Kombinatorik. Es wird repräsentiert in der Form

Abbildung in dieser Leseprobe nicht enthalten

Dabei ist Abbildung in dieser Leseprobe nicht enthaltender Zielfunktionswert von x. x ist ein Lösungsvektor aus der Menge aller Lösungsvektoren S (auch Suchraum genannt), für die die Funktion Abbildung in dieser Leseprobe nicht enthaltenim n-dimensionalen Raum definiert ist.^[13] Die Formel setzt ein Minimierungsproblem voraus, eine Maximierung von c (x) ist natürlich ebenso zulässig.

Des Weiteren kann man die Menge der Lösungsmöglichkeiten noch weiter einschränken, indem man nur diese Werte aus S zu lässt, für die auch alle eventuellen Nebenbedingungen erfüllt sind.^[14] Man spricht dann vom zulässigen Suchraum.^[15]

Abbildung in dieser Leseprobe nicht enthalten

2.1.2 Zug und Nachbarschaft

Eine wichtige Eigenschaft eines Lösungsvektors x ist seine Nachbarschaft Abbildung in dieser Leseprobe nicht enthalten.^[16] Es handelt sich dabei um die Menge benachbarter Vektoren, die man durch eine Operation auf dem Vektor x erreichen kann. Eine solche Operation bezeichnet man als Zug m.^[17] Wie weit eine solche Operation reicht, wird vorher festgelegt; z.B. könnte es sich um eine paarweise Vertauschung von Elementen des Vektors handeln.^[18]

Mathematisch lässt sich das wie folgt ausdrücken:^[19]

Ein Zug

Abbildung in dieser Leseprobe nicht enthalten

führt zu einer neuen Lösung

Abbildung in dieser Leseprobe nicht enthalten

Wenn

Abbildung in dieser Leseprobe nicht enthalten\ F,

dann handelt es sich um eine unzulässige Lösung, in allen anderen Fällen um eine zulässige.

Die Nachbarschaft Abbildung in dieser Leseprobe nicht enthaltenist dann definiert als Menge aller erreichbaren x 1:

Abbildung in dieser Leseprobe nicht enthalten

Bezogen auf S wird wieder von einer zulässigen und einer unzulässigen Nachbarschaft gesprochen. Die zulässige ist die Schnittmenge aus Abbildung in dieser Leseprobe nicht enthaltenund F:

Abbildung in dieser Leseprobe nicht enthalten

Eine wichtige Kennzahl für die Nachbarschaft ist ihre Größe. Sie gibt die Zahl der möglichen Züge vom Lösungsvektor x aus an:

Abbildung in dieser Leseprobe nicht enthalten

Der Durchschnitt aller Nachbarschaftsgrößen ist ein wichtiger Indikator für die Festlegung von Parametern der Heuristiken, so z.B. der Länge der Tabuliste (ein Thema, das in den Abschnitten 2.2.1 Tabuliste und 2.2.3 Anmerkungen und Erweiterungen noch eingehender behandelt wird).

Zu beachten gilt: je komplexer und weitreichender die erlaubten Operationen auf x, desto größer wird auch die Nachbarschaft von x und damit der Aufwand diese zu untersuchen. Im Extremfall entspricht die Nachbarschaft N (x) dem gesamten Suchraum der Problemstellung S und man ist wieder am Anfang angelangt und müsste eine Vollenumeration durchführen.

2.1.3 Nachbarschafts-Suchalgorithmus

Es ist nun möglich einen allgemeingültigen Algorithmus aufzustellen, dessen Aufgabe es ist Lösungen zu finden und zu bewerten. Er ist so allgemein gehalten, dass Bewertungsfunktion und Abbruchkriterien vor einer Anwendung festgelegt werden müssen.^[20]

1. Startlösungsmöglichkeit xk mit k = 1 auswählen

Abbildung in dieser Leseprobe nicht enthalten

2. Abbildung in dieser Leseprobe nicht enthaltenberechnen

3. Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

4. Test, ob E (xk) eine bessere Bewertung erhält als Abbildung in dieser Leseprobe nicht enthalten

wenn ja: Abbildung in dieser Leseprobe nicht enthalten

5. Abbruchkriterium erfüllt?

wenn ja: STOP; Abbildung in dieser Leseprobe nicht enthaltenist beste Lösung

wenn nein: weiter mit Schritt 2

Im einfachsten Fall ist E (x) mit der Kostenfunktion c (x) gleichzusetzen und das Abbruchkriterium ist ein lokales Minimum, d.h. es gibt kein Abbildung in dieser Leseprobe nicht enthalten. Dieser spezielle Fall wird in der englischen Literatur „Hill Climbing Heuristic”^[21],^[22] genannt, auch wenn diese hier invers angewandt wird. Sie bildet die Grundlage für eine einfache Form von TS. Verwendeter Ansatz sei dabei „steepest descent“^[23], d.h. es wird E (x) ausgewählt, für das die größte Verbesserung eintritt.

Wie bereits erwähnt, lassen sich mit dem Algorithmus nur lokale Extrema finden, nur im Ausnahmefall wird man in einem globalen Extremwert enden. Abhilfe kann hier das wiederholte Starten des Algorithmus mit verschiedenen Startlösungen schaffen, was in der englischsprachigen Literatur auch „iterated hill-climbing algorithm“^[24] genannt wird. Wenn man Glück hat, startet man in der richtigen Region und findet das globale Optimum – die Abhängigkeit vom reinen Zufall ist allerdings offensichtlich.

[...]

^[1] engl.: Knapsack Problem

^[2] engl.: Traveling Salesman Problem

^[3] Domschke, Drexl, S. 112 ff.

^[4] ohne Beachtung von Kapazitätskriterien wie bei der Tourenplanung (engl.: Vehicle Routing Problem)

(http://www.itcomplete.de/software/winf/tabusearch.html, Abschnitt „Überblick“)

^[5] systematisches Prüfen aller Möglichkeiten

^[6] unter Ausschluss von Teilzweigen des Lösungsbaums, die keine bessere Lösung als die aktuell beste enthalten können

^[7] aus dem Griechischen: „Findungskunst“ – Lehre von den Wegen zur Gewinnung neuer Erkenntnisse; im Gegensatz zur Logik, nach der Lösungen geschlussfolgert werden

^[8] Domschke, Drexl, S. 117

^[9] Eiselt, Sandblom, S. 243

^[10] http://www.wissen24.de/rd/vorschau/3189.html

^[11] Eiselt, Sandblom, S. 243: „Glover describes the tabu search framework as being based on a set of ‚principles of intelligent problem solving’.“

^[12] siehe Beispiele aus der Einführung

^[13] Glover (1989), S. 190

^[14] Eiselt, Sandblom, S. 231

^[15] Michalewicz, Fogel, S. 39: „feasible part of the search space“

^[16] engl.: Neighborhood

^[17] engl.: move

^[18] Domschke, Drexl, S. 118

^[19] Eiselt, Sandblom, S. 231

^[20] Eiselt, Sandblom, S. 233, Neighborhood Search Algorithm

^[21] Glover (1989), S. 191

^[22] dt.: Heuristik zum Besteigen eines Hügel

^[23] dt.: steilster Abstieg

^[24] Michalewicz, Fogel, S. 43