Tabu Search - Grundprinzip, Varianten und Anwendungen

Inhaltsverzeichnis

Abkürzungsverzeichnis

1 Einleitung

2 Heuristische Verfahren

3 Grundidee
3.1 Historischer Abriss
3.2 Was ist Tabu Search?
3.3 Erläuterung der wichtigsten Begriffe
3.3.1 Zug
3.3.2 Lokale und Globale Optima
3.3.3 Tabuliste
3.3.4 Tabudauer
3.3.5 Aspirationskriterien
3.4 Wie funktioniert Tabu Search?
3.4.1 Grundlegende Mechanismen
3.4.2 Speicheraufbau
3.4.3 Intensivierung
3.4.4 Diversifikation

4 Anwendungsbeispiele
4.1 Knapsackproblem
4.2 Reihenfolgeproblem bei der Isomattenentwicklung
4.3 Die Tourenplanung

5 Varianten
5.1 Entwicklungsrichtungen
5.2 Paralleles Tabu Search
5.3 Verteiltparalleles Tabu Search Verfahren
5.4 Reactive Tabu Search

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

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

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.

2 Heuristische Verfahren

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 Entscheidungsoperatoren, die potentielle Lösungen vom Suchprozess ausschließen können. Für heuristische Verfahren charakteristisch und zugleich Abgrenzungsmö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.

Abbildung in dieser Leseprobe nicht enthalten

Diese Mängel können durch lokale Suchverfahren, sogenannte Metastrategien, beseitigt werden. Unter Metaheuristiken versteht man übergeordnete heuristische Lösungsstrategien, die den Ablauf untergeordneter Heuristiken steuern.^[1] Da die hier genannten metaheuristischen Ansätze lokale Informationen über die Alternativenmenge zur Steuerung 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^[3], 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 Problemstellungen 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.

3 Grundidee

3.1 Historischer Abriss

Das Grundprinzip des TS geht auf die Publikationen von F. Glover^[4] aus den Jahren 1977 und 1986 sowie auf die Ausarbeitungen von P. Hansen und B. Jaumard^[5] 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 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.

3.2 Was ist Tabu Search?

Tabu Search (TS)^[6] 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^[7].

Aufgrund des Einsatzes eines flexiblen Gedächtnisses, das menschlichen Verhaltensweisen ähnelt, ordnet Glover TS dem Bereich der Künstlichen Intelligenz zu^[8]. Daraus ergeben sich für den Computereinsatz zwei Ablaufmechanismen, um quantitative Entscheidungsmodelle zu lösen (Tabelle 1).

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Lösungsmethoden für quantitative Entscheidungen

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 Varianten 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.

3.3 Erläuterung der wichtigsten Begriffe

3.3.1 Zug

Ein Zug ist eine Funktion, die eine Lösung in eine andere Lösung transformiert. Jede von einer Lösung x durch Ausführung eines Zuges erreichbare andere Lösung x’ wird als Nachbarlösung bezeichnet. Die Menge aller Nachbarn X’ = {x’₁, ... ,x’_n } bildet die Nachbarschaft von x. In jeder Iteration wird ein solcher Zug ausgeführt, um von einer ermittelten Lösung x zu einer benachbarten Lösung x’ zu wandern.

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

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 {A, B, C, D} 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 Kombination {B, C, D} oder {A, B, C, D, E}. Ein gleiches Ergebnis kann dadurch erzielt werden, dass die Problemformulierung mit Hilfe von Binärvariablen erfolgt. Beim Auspacken eines Gegenstandes erhält die Binärvariable den Wert 0 und beim Einpacken 1.

Ein Zug, der die Wirkung eines Zuges rückgängig macht, wird als dessen Komplement bezeichnet.

3.3.2 Lokale und Globale Optima

Ein lokales Optimum ist dann gegeben, wenn kein Nachbar einen besseren Zielfunktionswert aufweist als die betrachtete Lösung. Ein globales Optimum ist die insgesamt beste Lösung der gesamten Optimierungsaufgabe.

Die Strategie ist darauf ausgerichtet, von einem lokalen Optimum zum nächsten zu gelangen, da sich unter diesen Lösungen auch die gesuchte (global optimale) Lösung befinden muss (Vgl. Abbildung 16, S. 24). Um diese Lösung möglichst schnell zu finden, wird der jeweils bestmögliche Zug gewählt. Jedoch kann durch Verschlechterungen und anschließende Verbesserungen wieder zu einem bereits besuchten lokalen Optimum zurückgekehrt werden. Wird das Verfahren unverändert fortgesetzt, besteht die Gefahr in eine Endlosschleife zu geraten. Die Folge wären, eine zyklische Abfolge derselben Lösungssequenz. Somit würde die Betrachtung neuer Lösungen ausgeschlossen werden. Die Suche gelangt ins Kreisen.

Eine einfache Regel zur Vermeidung von Zyklen zwischen benachbarten Lösungen ist das Verbot, einen vorher durchgeführten Zug unmittelbar wieder umzukehren. Es werden also grundsätzlich solche Züge verboten, die komplementär zueinander sind. Diese Maßnahme allein reicht jedoch nicht aus, um ein Kreisen zu verhindern.

Um nicht wie die klassische Nachbarschaftssuche in einem lokalen Optimum stecken zu bleiben, lässt Tabu Search temporäre Zielfunktionsverschlechterungen zu.

3.3.3 Tabuliste

Die Tabuliste speichert den Suchverlauf des Algorithmus. Sie beinhaltet entgegengesetzte Aktionen von früheren Zügen. Die Leistung von TS wird hauptsächlich durch die Länge der Tabuliste und die Operatoren, die die Liste verändern bestimmt. Operatoren legen das Hinzufügen bzw. das Entfernen von Tabuzügen fest. Bei komplexeren Aufgaben besteht das Problem darin, dass der Umfang der bereits besuchten Lösungen mit der Anzahl der durchgeführten Iterationen steigt. Ein Speichern aller Lösungen erfordert also hohe Speicherkapazitäten. Um dem entgegen zu wirken, setzt man die Züge für eine bestimmte Zeit (Tabudauer), d. h. für eine gewisse Anzahl von Iterationen, tabu. Nach Ablauf der definierten Tabudauer wird dieser Zug wieder aus der Tabuliste gelöscht bzw. überschrieben.

[...]

^[1] Vgl. De Werra und Hertz (1989, S. 131).

^[2] Vgl. Morton und Pentico (1993).

^[3] Vgl. Domschke (1990, S.140).

^[4] Vgl. Glover (1977), Glover (1986).

^[5] Vgl. Hansen und Jaumard (1987, S. 43-87).

^[6] „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“.

^[7] Vgl. Glover (1990b, S. 74).

^[8] Vgl. Glover (1990a).