Information Technology Reference
In-Depth Information
5 214361
+ + +
3 1425 4 6
3 2443 41
5 112566
Abbildung 11.13: Beispiel eines uniformen Crossover. Für jedes Gen wird einzeln
bestimmt, ob es ausgetauscht wird (+)odernicht().
Mischen
Ein-Punkt-Crossover
Entmischen
5
214
36
123 4 56
3 1425 4
42
635
1
42651 3
214534
6
5
3
5
4
4
2
4
4
6
3
1
4
5
2
1
5
1
1
3
4
Abbildung 11.14: Beispiel eines Shuffle Crossover in Kombination mit einem Ein-
Punkt-Crossover
Das
Shuffle Crossover
mischt vor der Anwendung eines beliebigen Zwei-Eltern-
Operators die Gene zufällig. Nach der erfolgten Rekombination werden die Gene
durch das Shuffle Crossover wieder entmischt. Meistens wird das Shuffle Crosso-
ver mit dem Ein-Punkt-Crossover angewendet (siehe Abbildung 11.14). Man muss
beachten, dass das Shuffle Crossover nicht äquivalent ist zum uniformen Crossover.
Beim Shuffle Crossover ist jede Anzahl von Vertauschungen von Genen zwischen
den Chromosomen gleichwahrscheinlich, während beim uniformen Crossover die
Anzahl binomialverteilt mit dem Parameter
p
x
ist. Das Shuffle Crossover ist eines
der empfehlenswertesten Verfahren.
Sollten Chromosomen aus dem Raum der Permutationen sein, so bieten sich per-
mutationserhaltende Rekombinationsoperatoren an. Zwei dieser Verfahren werden
wir hier nun kurz beleuchten. Das
uniforme ordnungsbasierte Crossover
ähnelt dem
normalen uniformen Crossover, da man für jedes Gen mit der Wahrscheinlichkeit
p
k
einzeln entscheidet, ob es erhalten bleibt oder nicht. Die Lücken füllt man durch
die fehlenden Allele auf, und zwar in der Reihenfolge, in der sie im anderen Chro-
mosom vorkommen. Ein Beispiel einer Anwendung dieses Verfahrens befindet sich
in Abbildung 11.15. Dieses Verfahren erhält Reihenfolgeinformation, was u. U. für
gewisse Kodierungen vom Vorteil sein kann.
Ein weiteres permutationserhaltendes Rekombinationsverfahren ist die
Kantenre-
kombination
.SiewurdespeziellfürdasProblemdesHandlungsreisendenentwickelt
(siehe Abschnitt 11.1.2 für weiteres Details zu diesem Problem). Man fasst das Chro-
mosom als Graph (genauer gesagt als Kette oder Ring) auf. D. h., jedes Gen besitzt
5 724631
+ +++
423 1 5 7 6
5 24
1
532476 1
+ +++
4 531726
+
+++
4
3 1
6
Abbildung 11.15: Beispiel eines uniformen ordnungsbasierten Crossover
