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

Ein „Heiratsschema“ wäre beispielsweise: Wähle die drei besten Vektoren aus, also c, a und d,
und „kreuze“ den besten mit dem zweitbesten und den besten mit dem drittbesten. Das ergibt
die Elternpaare (c,a) und (c,d). Ein Rekombinations- bzw. Crossoverschema, das sich hier
anbietet, ist z. B. die Ersetzung der jeweils ersten beiden Komponenten in einem Vektor durch
die letzten beiden Komponenten des jeweils anderen. In unserem Beispiel ergibt das die fol-
genden neuen vier Vektoren:
„Kinder“ von (c,a):
(1,0,1,1,1); (1,1,1,1,0);
„Kinder“ von (c,d):
(1,0,1,1,1); (1,1,0,1,0).
Bei der Festlegung eines Heiratsschemas ist insbesondere darauf zu achten, dass die Anzahl der
Nachkommen gleich der Anzahl der Vorgänger ist. Das ist zwar nicht logisch zwingend und
beim biologischen Vorbild ist natürlich bekannt, dass die Anzahl von Kindern größer oder
kleiner sein kann als die Anzahl der Eltern. Aus praktischen Gründen jedoch erweist es sich
meistens als zweckmäßig, bei der Reproduktion die Anzahl der jeweiligen Vektoren konstant
zu halten.
Eine häufig verwandte Form des Crossover basiert darauf, dass man nicht einzelne Komponen-
ten der Vektoren nach dem Zufallsprinzip vertauscht, sondern bestimmte Teile der Vektoren
(Subvektoren) vollständig von einem Vektor in den jeweils anderen überführt. Es werden also
in einem Vektor W bestimmte Subvektoren ersetzt durch Subvektoren aus einem Vektor V;
entsprechend geschieht das dann im Vektor V (das haben wir im obigen Beispiel im Grunde
auch schon gemacht). Derartige ausgetauschte Subvektoren werden auch häufig als „Building
Blocks“ bezeichnet. Der Grund dafür, das Verfahren von Building Blocks im Crossover zu
realisieren, besteht gewöhnlich darin, dass die Einheiten in derartigen Building Blocks bzw.
Subvektoren „inhaltlich“ miteinander zusammenhängen und deswegen auch nur komplett aus-
getauscht werden dürfen. Man kann sich dies z. B. vorstellen an verschiedenen Gruppen von
Genen im Genom, die jeweils gemeinsam den Aufbau eines bestimmten Organs steuern.
Bei Anwendungen des GA werden die Raten der Mutation gewöhnlich sehr gering gesetzt, da
das Crossover die wesentliche Rolle spielt. Um bei dem kleinen obigen Beispiel überhaupt eine
Mutation durchzuführen, setzen wir die Mutationsrate für die gesamte neue Population von
vier Vektoren auf 5 %, d. h., bei insgesamt 20 Komponenten wird per Zufall eine Komponente
mutiert. Das ist bei GA-Anwendungen schon ein ziemlich hoher Wert. Die zu mutierende
Komponente sei die dritte im ersten „Kind“ von (c,a), was die endgültigen Vektoren (1,0,0,1,1)
sowie die drei anderen „Kinder“ ergibt. Man sieht sofort, dass bereits die erste Nachfolgerge-
neration deutlich bessere Werte hat als die erste Generation; außerdem zeigt sich, dass die
Mutation das Ergebnis verschlechtert (und nicht etwa verbessert). Dies ist in der Natur durch-
aus bekannt: Die meisten Mutationen wirken sich ungünstig aus und nur in wirklich großen
Populationen verbessern Mutationen das Gesamtergebnis mittel- und langfristig (Dawkins
1987).
Man sieht an diesem einfachen Beispiel durch Nachrechnen, dass der GA die Vektoren sehr
rasch zu besseren Werten bringt und dass das globale Optimum, nämlich Vektoren der Form
(1,1,1,1,1), schnell erreicht wird. Nach Erreichen des Optimums können Mutationen das Er-
gebnis nur noch verschlechtern; dies wird dann durch eine entsprechende Abbruchbedingung
verhindert.
Eine Spezialform der Mutation, die vor allem bei binären und nichtnumerischen Codierungen
eingesetzt werden kann, ist die so genannte Inversion. Dabei werden nach dem Zufallsprinzip