Greedy Randomized Adaptive Search Procedure (GRASP)

Gliederung

1 Einleitung

2 Der Grundgedanke

3 Der Algorithmus von GRASP

4 Vorteile von GRASP

5 Erweiterungen von GRASP

6 Parameter und Variablendefinition

7 Literaturangaben

1 Einleitung

GRASP ist die Abkürzung für G reedy R andomized A daptive S earch P rocedures. Dieser Suchvorgang wird durch die drei folgenden Begriffe charakterisiert:

- Greedy: Greedy heißt wörtlich übersetzt „gierig“ oder „gefräßig“. Damit ist ein Algorithmus gemeint, der sich z. B. durch einen Graphen „frisst“. Es wird eine Teillösung konstruiert und in jedem Schritt eine neue Komponente hinzugefügt [res99]. Dabei wird immer die Komponente mit dem größten „greedy“-Wert einer greedy-Funktion hinzugefügt. Ist man schließlich am Endknoten des Graphen angekommen, hat man eine mögliche, jedoch nicht unbedingt die beste Lösung gefunden [meg02].

Abbildung in dieser Leseprobe nicht enthalten

Abb.1

In Abb.1 ist ein Beispiel für die Anwendung eines Greedy-Algorithmus‘ dargestellt. Als Problemstellung dient hier die Aufgabe, den kürzesten Weg vom Startpunkt zum Endknoten zu finden. Bei Erreichung eines neuen Knoten, werden die möglichen weiterführenden Kanten bewertet. Es wird stets die Kante gewählt, die den höchsten Greedy Wert (hier: niedrigste Kosten) hat [res01]. Die Knoten der anderen weiterführenden Kanten sowie andere mögliche Wege (gestrichelte Pfeile) werden hier nicht beachtet.

- Randomized: Diese Eigenschaft greift Überlegungen von Semi-greedy Konstruktionsheuristiken auf [har87]. Es wird eine Kandidatenliste (RCL) erschaffen, in der einige der Lösungskomponenten mit den geringsten Kosten stehen. Aus dieser Liste wird zufällig eine Komponente entnommen und zu der bisherigen Teillösung gegeben. Somit besteht die Möglichkeit, über einen anderen Weg zu gehen als bei dem herkömmlichen Greedy-Algorithmus, wodurch eine Verbesserung der Lösung erreicht werden kann.

- Adaptive: Wird ein Element aus der Kandidatenliste ausgewählt und in die Teillösung mit aufgenommen, wird die Kandidatenliste mitsamt Kosten der restlichen Kandidaten aktualisiert, da einige Kandidaten nun nicht mehr zur Auswahl stehen [res01]. Die sich ergebende Lösung wird als vorläufige Lösung behalten, um sie mit weiteren möglichen Lösungen vergleichen zu können.

2 Der Grundgedanke

GRASP ist eine Mateheuristik, die systematisch Greedy-Konstruktionsheuristiken randomisiert, um relativ viele gute voneinander unabhängige Startlösungen für eine nachfolgende Suche zu generieren [stü01]. Demnach versucht man die Vorteile von Greedy Heuristiken und Semi-greedy Heuristiken zu verknüpfen, die Nachteile hingegen zu minimieren [res99]. Dadurch erhält man in vielen Fällen eine recht gute Annäherung an die optimale Lösung, die auch häufig in kurzer Zeit zu realisieren ist.

GRASP ist ein iterativer Prozess, der aus zwei Phasen besteht:

- Konstruktionsphase
- Lokale Suche

Anschließend erfolgt stets eine Aktualisierung der Lösung. Die beste gefundene Lösung wird als Endresultat festgehalten [res01]. Bei der lokalen Suche ist die Effektivität der Optimierung abhängig von der Struktur der Nachbarschaft, der Suchtechnik, dem Startpunkt (Seed) und wie schnell die Kostenfunktion der Nachbarn ansteigt [res99]. Eine qualitativ durchschnittliche Lösung ist bei GRASP oft schlechter als eine greedy-Lösung, während die beste Lösung durch GRASP oft besser ist als die mittels greedy-Algorithmus erhaltene Lösung [stü01].

Daraus ergeben sich drei mögliche Stellgrößen, die das Endresultat beeinflussen können [res98]:

- Qualität der Elemente in der RCL: Die Auswahl der Kandidaten für eine mögliche Lösung kann entweder numerisch festgesetzt werden, d. h. durch die Aufnahme in die RCL von den maximal n besten Kandidaten (wobei n fixer Parameter ist), oder durch qualitative Einschränkung. Die qualitative Einschränkung wird durch die Festsetzung von einem Parameter a bestimmt. Für ein Minimierungsproblem gilt: Setzt man a=0, wird immer nur der beste Kandidat gewählt (=> Greedy-Algorithmus), während bei a=1 die Auswahl uneingeschränkt ist, da man alle Kandidaten - also auch die Schlechtesten - wählen kann. Es ist daher sinnvoll, einen Wert für a zwischen 0 und 1 zu wählen, um eine Variation an möglichen Lösungen anzustreben.

Abbildung in dieser Leseprobe nicht enthalten

Anzahl der Iterationen: Bei jeder Iteration ergibt sich eine weitere, möglicherweise neue Lösung (mit einem neuen ZF-Wert). Je mehr Iterationen durchgeführt werden, desto größer ist die Wahrscheinlichkeit, eine gute Annäherung an die optimale Lösung oder sogar die optimale Lösung selbst zu erreichen. Jedoch benötigt jede Iteration eine gewisse Zeit, so dass die Dauer proportional zur Erhöhung der Iterationen ansteigt. Auch hier muss man deshalb einen Kompromiss zwischen der Schnelligkeit und der Optimalität der Lösung finden.

- Suchverfahren: Bei der lokalen Suche wird eine gefundene Lösung lokal optimiert, d. h. die Nachbarschaft der Lösung wird nach besseren Lösungen durchsucht. Dabei ist die Definierung der Nachbarschaft von großer Bedeutung. Je größer man diese wählt, umso stärker kann die Lösung noch verbessert werden. Doch auch hier ist eine größere Nachbarschaft und demnach eine intensivere lokale Suche mit mehr Zeitaufwand verbunden.

3 Der Algorithmus von GRASP

Es sei gegeben [res01]:

- Menge von Kanten E, mit einer Kante e Î E
- Kosten der Kanten c(e)
- Optimale Lösung S, optimale Kanten e Î S
- Mögliche Lösungen F mit f(S) = åeÎS c(e) , mit S Í E
- Der Beschränkungsparameter a sei zunächst fix (0<a<1)
- Die Kandidatenliste RCL sei qualitativ beschränkt durch a
- cmin und cmax seien der beste bzw. schlechteste greedy-Funktionswert (= Kosten) der jeweiligen Kanten in der RCL
- Es seien c‘(e) die Kosten der nächsten Lösungskomponente mit
c‘(e) Î [cmin, cmin + a(cmax – cmin)], wobei es die beiden Spezialfälle a = 0 (=> greedy- Konstruktionsheuristik) und a = 1 (=> zufällige Lösungskonstruktion) gibt

Abbildung in dieser Leseprobe nicht enthalten

In Abb. 2 ist eine neue mögliche Lösung dargestellt, hier ein weiterer Ausschnitt für das Min.-Problem aus Kapitel 1. Die roten Pfeile markieren jeweils die Kandidaten, die in die Kandidatenliste (RCL) aufgenommen wurden. Als Beschränkungskriterium dient, ebenso zunächst im weiteren Verlauf, eine qualitative Begrenzung, die durch den Parameter a bestimmt wird. In diesem Fall ist 0<a<1, so dass die anderen (dicker gestrichelten) Pfeile aufgrund zu schlechter Qualität nicht betrachtet werden. Die blauen Pfeile markieren die Kandidaten aus der RCL, aus denen die mögliche Lösung besteht. Im Vergleich zu Abb.1 wird am 2. blauen Knoten zufällig eine andere Kante aus der RCL gewählt als in Abb.1. Dadurch ist eine neue mögliche Lösung (mit gleichem ZF-Wert) entstanden, die mit weiteren Lösungen verglichen werden kann.

[...]