Rekombination (evolutionärer Algorithmus)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Rekombination wird bei evolutionärer Algorithmen die Erzeugung eines neuen Genoms (auch als Filialgenom bezeichnet) aus (in der Regel) zwei Elterngenomen (Parentalgenomen) bezeichnet. Eine Funktion, die eine zulässige Menge von Parentalgenomen auf eine Menge von Filialgenomen abbildet, heißt Rekombinationsfunktion. Eine Rekombinationsfunktion ist ein genetischer Operator.

Ziel der Rekombination ist es, gute Eigenschaften zweier verschiedener Eltern auf ein Kind zu übertragen. Im Vergleich zu Algorithmen, die nur die Mutation zur Veränderung der Genome benutzen, können so möglicherweise schneller Individuen gefunden werden, die zwei gute Eigenschaften A und B in sich tragen, wenn es vorher nur Individuen gab, die entweder nur über A oder über B verfügten.

Gute Rekombinationsfunktionen zeichnen sich dadurch aus, dass sie zumindest die guten Eigenschaften der Eltern erhalten und nicht so rekombinieren, dass diese Eigenschaften zerstört werden.

Für verschiedene Genom- und Problemtypen eignen sich verschiedene Rekombinationstypen unterschiedlich gut:

Rekombination von binären Zahlen (Bitstrings)[Bearbeiten]

Bei der Rekombination binärer Zahlen werden die Parentalgenome an einer oder mehreren Stellen unterteilt und das Filialgenom aus diesen Teilen zusammengesetzt.

Ein Beispiel ist die Rekombination von zwei Elterngenomen, die an zwei Stellen unterteilt werden:

Verfahren Beispiel
* Gegeben seien zwei binäre Zahlen, P_0 = \left( 0,1,1,0,0,1,0 \right) und P_1 = \left( 1,0,0,0,1,0,0 \right)
* Wähle nun zufällig zwei Indizes, an denen die Genome unterteilt werden s_1 = 3, s_2 = 6,
* Für das Kindgenome werden aus P_1 werden alle Stellen übernommen, die zwischen s_1 und s_2 liegen, während alle restlichen Stellen aus P_0 Übernommen werden. P_C = \left( 0,1, \underline {0,0,1,0} ,0 \right)

Rekombination von Permutationen[Bearbeiten]

Die Rekombination von Permutationen ist speziell für Genome ausgelegt, die selbst Permutationen einer Menge sind.

Ein Beispiel für eine Rekombination von Permutationen ist folgendes Verfahren:

Verfahren Beispiel
* Gegeben seien 2 Permutationen derselben Menge, P_0 = \left( A,B,C,D,E,F,G \right) und P_1 = \left( E,\underline {B},G,A,\underline {F},D,\underline {C} \right)
* sowie eine zufällige Auswahl, welche Stellen direkt von der ersten Permutation übernommen werden sollen S = \left( 1,0,0,1,1,0,1 \right)
* Als Kind-Permutation wird eine Permutation generiert, die überall dort von P_0 kopiert ist, wo S eine 1 hat. P_C = \left( A,?,?,D,E,?,G \right)
* Die Stellen, die von P_0 nicht übernommen wurden, werden nun ebenfalls übernommen, aber in der Reihenfolge, wie sie in P_1 vorkommen. P_{nochNichtUebernommen} = \left\{ B,C,F \right\}

P_{inReihenfolgeVonB} = \left( B,F,C \right)

* Damit ergibt sich das fertige Kind-Genom. P_C = \left( A,\underline {B},\underline {F},D,E,\underline {C},G \right)

Man kann auf diese Weise ein zweites (in gewisser Weise inverses) Kind erzeugen, indem man die Liste S invertiert und das Verfahren erneut anwendet.

Edge-Rekombination[Bearbeiten]

Eine weitere Variante der Rekombination von Permutationen ist die Edge-Rekombination, bei der die Nachbarschaftsbeziehungen zwischen den Elementen der Elterngenome so gut wie möglich erhalten werden. Bei der Edge-2-Rekombination werden dabei Verbindungen bevorzugt, die in beiden Elterngenomen vorkommen. Die Edge-3- und Edge-4-Rekombination versuchen zusätzlich, durch Inversion der Genome noch zusätzliche Nachbarschaften auszunutzen, die bei der Edge-2-Rekombination verloren gingen. Dieses Verfahren ist besonders gut geeignet für kombinatorische Optimierungsprobleme wie das Traveling Salesman Problem.

Rekombination von Bäumen[Bearbeiten]

Die Rekombination von Bäumen ist speziell für Genome ausgelegt, die selbst Bäume sind.

Ein Beispiel für eine Rekombination von Bäumen ist folgendes Verfahren:

  • Gegeben seien zwei Eltern-Bäume (Eltern-Genome).
  • Wähle in jedem Eltern-Baum einen Teilbaum aus.
  • Vertausche diese zwei Teilbäume.

Die zwei so neu entstandenen Bäume sind nun die zwei Kind-Genome.

Literatur[Bearbeiten]