Evolutionäre Basisalgorithmen - Computational Intelligence - page 191

So gilt z. B. dl ( ** 0 * 11 * 10 * )= 9 3 = 6. Beim Ein-Punkt-Crossover liegt der
Schnittpunkt mit Wahrscheinlichkeit dl( h )

L 1 so, dass zwei Nicht-Jokerzeichen vonein-
ander getrennt werden. Die Erläuterung dafür ist, dass es bei Chromosomen der
Länge LL 1möglicheSchnittpunktegibtfürdasEin-Punkt-Crossover,diealle
gleichwahrscheinlich sind. dl( h ) dieser Schnittpunkte liegen so, dass im Schema
festgelegte Gene in verschiedene Nachkommen gelangen, wodurch die Passung ver-
lorengehen kann. Man muss allerdings beachten, dass die Passung verlorengehen
kann, jedoch nicht zwangsläufig verlorengehen muss. Für die Rechnung sind weite-
re Überlegungen nötig, die wir später durchführen werden.
Um die folgenden Rechnungen zu erleichtern und um den Ablauf des Algorith-
mus Schritt für Schritt zu analysieren, geben wir verschiedene Definitionen des Er-
wartungswerts der Anzahl der Chromosomen, die noch zu einem Schema passen.
Definition 12.6 (Erwartungswert passender Chromosomen) Der Wert N ( h , t ) ist de-
finiert als der Erwartungswert der Anzahl Chromosomen, die in der t-ten Generation zum
Schema h passen.
Definition 12.7 (Erwartungswert nach Selektion) N ( h , t + t s ) ist definiert als der Er-
wartungswert der Anzahl Chromosomen, die in der t-ten Generation nach Selektion zum
Schema h passen.
Definition 12.8 (Erwartungswert nach Crossover) N ( h , t + t s + t x ) ist definiert als
der Erwartungswert der Anzahl Chromosomen, die in der t-ten Generation nach Selektion
und Crossover zum Schema h passen.
Definition 12.9 (Erwartungswert nach Mutation)
N ( h , t + t s + t x + t m )= N ( h , t + 1 )
ist definiert als der Erwartungswert der Anzahl Chromosomen, die in der t-ten Generation
nach Selektion, Crossover und Mutation (und damit in der ( t + 1 ) -ten Generation) zum
Schema h passen.

Bei der Untersuchung verschiedener Schemata suchen wir nach dem Zusammen-
hang zwischen N ( h , t ) und N ( h , t + 1).WirbetrachtendaherschrittweisedieAus-
wirkungen der Selektion, des Crossover und der Mutation mit Hilfe der mittleren
Fitness, der Ordnung und der definierenden Länge eines Schemas.
Wir beschreiben die Auswirkungen der Selektion durch die mittlere Fitness
N ( h , t + t s )= N ( h , t ) · f rel ( h ) ·|pop|,
wobei N ( h , t ) · f rel ( h ) die Wahrscheinlichkeit ist, dass ein zum Schema h passendes
Chromosom ausgewählt wird und f rel ( h ) ·|pop| die durchschnittliche Anzahl Nach-
kommen eines zu einem Schema h passenden Chromosoms ist. Hierbei muss man
wissen, dass wir die relative Fitness f rel ( h ) nicht exakt bestimmen können, da die
zum Schema h passenden Chromosomen nur als Erwartungswert bekannt sind.
Die Auswirkungen des Crossover beschreibt man durch
N ( h , t + t s + t x )=( 1 p x ) · N ( h , t + t s )

A

+

p x

· N ( h , t + t s ) · ( 1 p loss ) + C ,

B