Rekombination (evolutionärer Algorithmus) - LinkFang.de





Rekombination (evolutionärer Algorithmus)


Als Rekombination wird bei evolutionären 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 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)

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,
[math]P_0 = \left( 0,1,1,0,0,1,0 \right)[/math] und [math]P_1 = \left( 1,0,0,0,1,0,0 \right)[/math]
  • Wähle nun zufällig zwei Indizes, an denen die Genome unterteilt werden
[math]s_1 = 3[/math], [math]s_2 = 6[/math],
  • Für das Kindgenom werden aus [math]P_1[/math] alle Stellen übernommen, die zwischen [math]s_1[/math] und [math]s_2[/math] liegen, während alle restlichen Stellen aus [math]P_0[/math] übernommen werden.
[math]P_C = \left( 0,1, \underline {0,0,1,0} ,0 \right)[/math]

Rekombination von Permutationen

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,
[math]P_0 = \left( A,B,C,D,E,F,G \right)[/math] und [math]P_1 = \left( E,\underline {B},G,A,\underline {F},D,\underline {C} \right)[/math]
  • sowie eine zufällige Auswahl, welche Stellen direkt von der ersten Permutation übernommen werden sollen
[math]S = \left( 1,0,0,1,1,0,1 \right)[/math]
  • Als Kind-Permutation wird eine Permutation generiert, die überall dort von [math]P_0[/math] kopiert ist, wo [math]S[/math] eine [math]1[/math] hat.
[math]P_C = \left( A,?,?,D,E,?,G \right)[/math]
  • Die Stellen, die von [math]P_0[/math] nicht übernommen wurden, werden nun ebenfalls übernommen, aber in der Reihenfolge, wie sie in [math]P_1[/math] vorkommen.
[math]P_{nochNichtUebernommen} = \left\{ B,C,F \right\}[/math]

[math]P_{inReihenfolgeVonB} = \left( B,F,C \right)[/math]

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

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

Edge-Rekombination

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

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


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Rekombination (evolutionärer Algorithmus) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.