next up previous contents
Nächste Seite: Mutation Aufwärts: Genetische Algorithmen in der Vorherige Seite: Generation und Generationsformen   Inhalt


Kreuzungsoperator

Der Crossover ist ein Genrekombinationsoperator, welcher die Entstehung von Individuen mit neuen Merkmalen ermöglicht.

In der Biologie ist Crossover bei allen höheren Lebewesen und bei den meisten niederen die Regel. Ein Crossover geht immer einher mit der sexuellen Reproduktion von Lebewesen und ermöglicht eine Durchbrechung der Genkopplung bei der Vererbung von Merkmalen bei höheren Lebewesen. Auf molekularer Ebene homologe3.10Chromosomen legen sich dabei aneinander und an bestimmten Stellen erfolgt ein Bruch der Chromatiden und eine kreuzweise Wiedervereinigung dieser Teilstücke. Durch eine solche Überkreuzung werden die auf abgetrennten Teilstücken liegenden Gene aus ihrer bisherigen Kopplungsgruppe gelöst und gegeneinander ausgetauscht. Dadurch werden die genetischen Informationen der Eltern gemischt, um den entstehenden Kindern Merkmalen von beiden Eltern zu vererben.

Dieses Verfahren ermöglicht die Durchbrechung der Genkopplung auch bei haploiden Chromosomensätzen und somit eine Erweiterung des 'Suchspektrums' für solche Lebewesen (z.B. Bakterien). Die Suche nach einer besseren, d.h. überlebens- oder reproduktionsfähigeren Lösung - als Lebewesen - wird gegenüber einfacher Mutation beschleunigt, da bei zunehmender Anzahl an Genen die Wahrscheinlichkeit, dass ein Kind einem der beiden Elternteile vollständig gleicht, abnimmt.

Genetische Algorithmen implementieren den Crossover-Operator in vielen verschiedenen Variationen und Spielarten, die sich alle mehr oder weniger auf das Beispiel aus der Biologie zurückführen lassen. Im einfachsten Fall werden zwei Genome an einer jeweils homologen Stelle gebrochen und die entstehenden Teilstücke ausgetauscht (1-Point Crossover). Weitere Möglichkeiten bestehen zum Beispiel aus mehreren solcher Bruchstellen (N-Point Crossover), vordefinierten Bruchstellen oder Austausch einzelner Basen. Die Möglichkeiten sind quasi unbegrenzt, und dieser Operator wird typischerweise sehr oft angewandt.

Der Effekt des Crossover-Operators lässt so im Laufe der Zeit typischerweise nach, je mehr die Population zu einer Lösung hinkonvergiert. Dadurch steigt die Wahrscheinlichkeit, dass zwei gleiche oder fast gleiche gekreuzte Genome mindestens ein Kindgenom erzeugen, welches mit einem der beiden Elternteile identisch ist.

Aus einer mathematischen Betrachtungsweise heraus dient dieser Operator im Rahmen der Exploitation von Informationen zweierlei Zwecken [24]. Der erste ist ein ständig fortlaufender Korrelationstest zwischen einer Anzahl an Allelen im Genom eines Individuums und dessen Fitness. Wenn während einer Genrekombination eine Gruppe von Genen vererbt wird, dann testet der Operator implizit die Hypothese, dass die Allele dieser Gene (oder auch eine Teilgruppe davon) mit einem guten Ziel- und damit auch Fitnesswert korrelieren3.11. Der zweite Zweck der Genrekombination ist es, gefundene Gruppen von Genen mit ``guten'' Werten, d.h. Gruppen, die wahrscheinlich die Fitness eines jeden Genoms erhöhen würden, miteinander zu rekombinieren. Hier wird von der Annahme ausgegangen, dass viele kleine dieser Building-Blocks zusammen eine weitere Verbesserung der Fitness eines Genoms bewirken3.12.


next up previous contents
Nächste Seite: Mutation Aufwärts: Genetische Algorithmen in der Vorherige Seite: Generation und Generationsformen   Inhalt
2001-07-08