Die Modellierung adaptiver Prozesse durch Evolutionäre Algorithmen - Modellierung komplexer Prozesse durch naturanaloge Verfahren - page 71

Elterngeneration verschwindet vollständig (so genanntes nicht-elitistisches Ersetzungsschema).
Dies macht Sinn vor allem bei Simulationen von „adaptiven“ natürlichen oder auch sozialen
Systemen, d. h. Systemen, bei denen im Verlauf der Zeit bestimmte Formen auftauchen, sich
mehr oder weniger gut bewähren und mittel- bis langfristig wieder verschwinden. Wenn es
jedoch darum geht, relativ schnell praktikable Lösungen für spezielle Probleme zu finden, dann
ist es häufig nicht sinnvoll, auf die jeweiligen Elterngenerationen völlig zu verzichten, da
Nachfolgegenerationen aufgrund der stochastischen Aspekte des GA auch durchaus schlechter
als die Elterngeneration sein können. Deswegen sind schon bald verschiedene elitistische
Formen des Ersetzungsschemas eingeführt worden, von denen hier einige Varianten dargestellt
werden sollen.
Die übliche elitistische Variante des Standard-GA besteht einfach darin, dass nach Durch-
führung von Crossover und Mutation die Kindergeneration mit der Elterngeneration, also der
zum Crossover verwendeten Subpopulation der Anfangspopulation, verglichen wird. Sind alle
Vektoren der Nachfolgegeneration schlechter als die Eltern, dann werden die n schlechtesten
Kinder durch die n besten Eltern ersetzt; diese bilden dann mit den verbleibenden Kindern die
neue Generation. Hierdurch kann man erreichen, dass die Bewertungsfunktion monoton stei-
gend wird, d. h., für die besten Werte W N der Nachfolgegeneration und die Werte W E der
Elterngeneration gilt stets
W N W E . (3.1)

Praktisch hat sich gezeigt, dass es genügt, n = 1 oder geringfügig größer zu wählen, womit die
Monotonie der Bewertungsfunktion hinreichend gewährleistet ist. Allerdings gibt es bei dieser
standardisierten Form des elitistischen GA den Nachteil, dass die Population zu schnell homo-
gen werden und in einem Suboptimum landen kann. Dies kann man entweder durch Erhöhung
der Mutationsrate verhindern oder durch Einführung eines schwachen Elitismus. Dieser besteht
darin, die n beibehaltenen besten Eltern vor Einfügung in die Nachfolgegeneration selbst zu
mutieren - entweder mit der generellen Mutationsrate oder einer speziellen.
Ein zusätzlicher Weg, das Ersetzungsschema zu variieren, besteht darin, die Elterngeneration
„anzureichern“ (delete-n-last). Dies bedeutet, dass die n schlechtesten Elemente der Eltern-
generation durch n Elemente der Nachfolgegeneration ersetzt werden und mit den verbleiben-
den Eltern die neue Generation bilden. Dabei müssen es nicht unbedingt die n besten Elemente
der Nachfolgegeneration sein. Falls diese z. B. den besten Elternvektoren zu ähnlich sind,
könnte eine zu schnelle Konvergenz auf ein Suboptimum hin erfolgen. Auch hier sind zahlrei-
che Varianten möglich.
(2) Konvergenzverhalten: Von bestimmten GA lässt sich mathematisch streng zeigen, dass sie
unter bestimmten Bedingungen einen Konvergenzpunkt haben, also immer eine optimale Lö-
sung finden, auch wenn diese zuweilen kein globales Optimum darstellt. Der entsprechende
Beweis von Michalewicz (1994) basiert auf einem Theorem aus der metrischen Topologie,
d. h. der Theorie metrischer Räume. Dies sind Mengen, auf denen eine metrische „Distanz-
funktion“ d definiert ist. Diese Funktion wird definiert für alle Elemente x, y und z der Menge
durch

(1) d(x, x) = 0;
(2) d(x, y) = d(y, x);

(3) d(x, z) d d(x, y) + d(y, z), (3.2)
mit d(x, y) R , also der Menge der reellen Zahlen. Die Bedingung (3) wird gewöhnlich als so
genannte Dreiecksungleichung bezeichnet.