Information Technology Reference
In-Depth Information
Abbildung 13.2: Problem des VEGA-Verfahrens
große Herausforderung hierbei ist, ohne eine vorab bestimmte Gewichtung, dieses
Problem zu lösen. Immerhin existieren meistens viele verschiedene und dennoch
gleichwertige Lösungen auf der Pareto-Front.
Der einfachste Ansatz ist die Verwendung einer gewichteten Summe der einzel-
nen Zielfunktionen als Fitnessfunktion. Dies hat einige Nachteile, die wir bereits
im Abschnitt 13.2.1 erwähnt haben. Dieser Ansatz führt zu einer Pareto-optimalen
Lösung, aber eben einer durch die Gewichtungen ausgezeichneten. Eine nahelie-
gende Alternative stellt der sogenannte
Ve c t o r Ev a l ua t ed Gene t i c Al g o r i t hm
(VEGA)
dar [Schaffer 1985]. Gegeben seien
k
Kriterien, denen die Zielfunktionen
f
i
mit
i
=
1, . . . ,
k
zugeordnet sind. Für jedes
i
{1, . . . ,
k
} werden
|pop|
k
Individuen auf Grund-
lage der Fitnessfunktion
f
i
gewählt. Der Vorteil liegt in der Einfachheit dieses Verfah-
rens, durch den geringen Rechenaufwand. Der Nachteil ist, dass Lösungen, die alle
Kriterien recht gut, aber keines maximal erfüllen, einen deutlichen Selektionsnach-
teil haben. Die Folge ist, dass sich die Suche auf Randlösungen konzentriert. Dies ist
in Abbildung 13.2 verdeutlicht. Es kommt also zu einem Gendrift, sodass die Indivi-
duen auf der Pareto-Front an beliebigen Punkten durch Zufallseffekte konvergieren.
Ein besserer Ansatz ist, den Dominanzbegriff für die Selektion zu nutzen. Dafür
bauen wir eine
Rangskala
der Individuen einer Population wie folgt auf:
1. Finde alle nicht dominierten Lösungskandidaten der Population.
2. Ordne diesen Lösungskandidaten den höchsten Rang zu und entferne sie aus
der Population.
3. Wiederhole das Bestimmen und Entfernen der nicht dominierten Lösungskan-
didaten für die weiteren Ränge, bis die Population leer ist.
Mit Hilfe der Rangskala wird dann eine Rangauswahl durchgeführt. Meistens wird
dieser Ansatz mit Nischentechniken (siehe Abschnitt 11.2.7) kombiniert, um zwi-
schen Individuen mit gleichem Rang zu unterscheiden. Beispielsweise kann das
Power Law Sharing
verwendet werden: Individuen mit einer häufigen Kombination
von Funktionswerten erhalten eine geringere Fitness. Dadurch sind einzeln auftre-
tende Kombinationen genauso wahrscheinlich wie Individuen mit gehäuft vorkom-
menden Kombinationen. Dies entspricht einem
Sharing
wie für eine Fitnessfunktion,
nur mit einem Abstandsmaß von Funktionswerten. Lediglich die aufwändige Be-
rechnung der Rangskala stellt hier ein Problem dar.
