Information Technology Reference
In-Depth Information
1 5 2 3624
1 5 143 4 6
5 214361
5 2425 24
3 1425 4 6
3 123661
Abbildung 11.16: Beispiel eines Diagonal-Crossover
betrachtet grundlegend zwei Verzerrungen als Charakteristika, die nach einer Re-
kombination von Individuen auftreten können: die ortsabhängige Verzerrung und
die Verteilungsverzerrung.
Eine
ortsabhängige Verzerrung
(engl.
positional bias
)liegtdannvor,wenndieWahr-
scheinlichkeit, dass zwei Gene zusammen vererbt werden (also im gleichen Chromo-
som bleiben oder zusammen in das andere Chromosom wandern), von ihrer relati-
ven Lage im Chromosom abhängt. Diese Charakteristik ist unerwünscht, da dann
die Anordnung der Gene im Chromosom entscheidenden Einfluss auf den Erfolg
oder Misserfolg des evolutionären Algorithmus haben kann. Bestimmte Anordnun-
gen ließen sich so schwerer erreichen als anderen.
Wir wollen die ortsabhängige Verzerrung an einem Beispiel wie dem Ein-Punkt-
Crossover verdeutlichen. Zwei Gene werden voneinander getrennt (gelangen also in
verschiedene Nachkommen), wenn der Crossover-Punkt zwischen sie fällt. Je näher
zwei Gene im Chromosom beieinander liegen, desto weniger mögliche Crossover-
Punkte gibt es zwischen ihnen. Folglich werden nebeneinander liegende Gene mit
höherer Wahrscheinlichkeit als entfernt liegende in den gleichen Nachkommen ge-
langen. Das Ein-Punkt-Crossover hat daher eine hohe ortsabhängige Verzerrung.
Eine
Ve r t e i l ung sv e r z e r rung
(engl.
distributional bias
)istvorhanden,wenndieWahr-
scheinlichkeit, dass eine bestimmte Anzahl von Genen ausgetauscht wird, nicht für
alle Anzahlen gleich ist. Dies ist oft unerwünscht, da dann Teillösungen unterschied-
licher Größe unterschiedlich gute Chancen haben, in die nächste Generation zu ge-
langen. Die Verteilungsverzerrung ist meist weniger kritisch (d. h. eher tolerierbar)
als die ortabhängige Verzerrung. Ein Beispiel für die Verteilungsverzerrung ist das
uniforme Crossover. Da jedes Gen unabhängig von allen anderen mit der Wahr-
scheinlichkeit
p
x
ausgetauscht wird, ist die Anzahl
k
der ausgetauschten Gene bi-
nomialverteilt mit dem Parameter
p
x
:
L
k
p
x
(
1
p
x
)
L
k
P
(
K
=
k
)=
wobei
L
der Gesamtzahl der Gene entspricht. Folglich sind sehr kleine und sehr
große Anzahlen unwahrscheinlicher.
11.3.5
Interpolierende und extrapolierende Rekombination
Bisher haben wir nur kombinierende Operatoren zur Verknüpfung mehrerer Indivi-
duen behandelt. Sie sind alle stark abhängig von der Diversität der Population. Auch
erschaffen sie keine neuen Genbelegungen und können somit nur Teilbereiche des
Suchraums erreichen, die in Individuen der Population enthalten sind. Falls die
