Gliederung:

1  Einleitung  3

2  Der Grundgedanke  4

3  Der Algorithmus von GRASP  6

4  Vorteile von GRASP  10

5  Erweiterungen von GRASP  11

6  Parameter und Variablendefinition  14

7  Literaturangaben  16

2

1 Einleitung

GRASP ist die Abkürzung für Greedy Randomized Adaptive Search Procedures. 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 m it 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].

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.

- Rando mized: 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.

3

- 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

4

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 α bestimmt. Für ein Minimierungsproblem gilt: Setzt man α=0, wird immer nur der beste Kandidat gewählt (=> Greedy-Algorithmus), während bei α=1 die Auswahl uneingeschränkt ist, da man alle Kandidaten - also auch die Schlechtestenwählen kann. Es ist daher sinnvoll, einen Wert für α zwischen 0 und 1 zu wählen, um eine Variation an möglichen Lösungen anzus treben.

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.

5