Kurs:Genetische Algorithmen/Kapitel 4

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

In diesem Kapitel schauen wir uns die natürliche Rekombination aus der Sicht der DNS an. Es wird anhand von Beispielen gezeigt, wie diese allgemein auf Lösungen von Optimierungsproblemen angewendet werden kann.

Lernziele

• Nach dem Bearbeiten dieses Kapitels wissen Sie, wie die natürliche Rekombination funktioniert und wozu sie gut ist.
• Sie wissen, wie man die Rekombination auf beliebige Darstellungen einer Lösung verstehen kann.
• Sie können Rekombinationsoperatoren für verschiedene Optimierungsprobleme formulieren.

Die Rekombination

Wir erinnern uns: zwei Hasen verlieben sich. Er hat lange Ohren, sie hat kräftige Hinterbeine und zusammen haben sie viel Nachwuchs. Einige dieser Hasenbabys werden längere Ohren haben, andere kräftigere Hinterbeine, andere weder noch und zuletzt einige beide Merkmale. Wie funktioniert das eigentlich?

Bei Hasen ist, wie bei fast alle Lebewesen, die Erbinformation doppelt vorhanden. Jede Zelle enthält zwei Kopien der DNS, eine von jedem Elternteil. Diese zwei DNS Stränge müssen nicht zwangsläufig identisch sein, sie stammen ja schliesslich von zwei verschiedenen Individuen. Auch geschehen die Mutationen, die wir im letzten Kapitel gesehen haben, nicht automatisch auf beiden Kopien, sondern nur auf einer.

Paaren sich zwei Individuen, spenden sie je zufällig eine ihrer Kopien (vgl.~Abbildung~\ref{fig:paar}). Diese Kopien können auf vier verschiedene Arten verteilt werden\footnote{Diejenigen, die Geschwister haben, werden gemerkt haben, dass bei den Menschen mehr als nur vier Kombinationen möglich sind. Dies liegt daran, dass unser Erbgut auf 26 Chromosomenpaare verteilt ist. Wir haben von jedem Chromosom zwei Kopien, eines von jedem Elternteil. Bei 26 Chromosomen gibt es 4'503'599'627'370'496 Arten, wie sich diese auf den Nachwuchs verteilen können. Die Wahrscheinlichkeit also, dass zwei Geschwister identisch aussehen, ist so gut wie null.}.

Aufgabe:

Ein Hase, der auf einem seiner Chromosome ein Gen für längere Ohren trägt, paart sich mit einem Hasen, der dieses Gen auf keinem seiner Chromosome trägt. Wenn wir annehmen, dass alle Chromosome mit gleicher Wahrscheinlichkeit weitervererbt werden, wie gross ist die Wahrscheinlichkeit, dass ein Kind dieser zwei Hasen auch das Gen für längere Ohren hat?

Wir können also bei unseren sich liebenden Hasen davon ausgehen, dass der Vater auf einer seiner zwei DNS-Kopien die Mutation für längere Ohren trägt. Bei der Mutter trägt eine der beiden Kopien die Mutation für kräftigere Beine. Es wird also im Durchschnitt jedes vierte Kind dieser zwei Hasen beide Eigenschaften mit sich tragen. Es besteht aber noch ein Problem: Beide Mutationen sind nicht auf demselben DNS-Strang. Der Nachwuchs dieser doppelt mutierten Hasen wird also entweder längere Ohren oder kräftigere Beine haben. Bei zwei Eigenschaften -- längere Ohren und kräftigere Beine -- können wir immer noch Individuen mit beiden Eigenschaften erzeugen. Problematisch wird es aber, wenn weitere Eigenschaften, zum Beispiel das angepasste Fell, dazukommen. Die Eigenschaften sind, weil sie nicht auf dem gleichen DNS-Strang liegen, nicht wirklich vermischt.

Aufgabe:

Ein Hase, mit einem Gen für längere Ohren auf einer Kopie eines Chromosoms und einem Gen für kräftigere Beine auf der anderen Kopie, paart sich mit einem anderen Hasen ohne besondere Eigenschaften.

1. Wieviel Prozent des Nachwuchses werden längere Ohren haben?
2. Wieviel Prozent werden kräftigere Beine haben?
3. Wieviel Prozent werden beide Eigenschaften tragen?

Dies wird durch die Rekombination ermöglicht. Die Rekombination ist ein biologischer Vorgang, bei dem beide Kopien der DNS einer Zelle an der gleichen Stelle getrennt und vertauscht wieder zusammengefügt werden (vgl.~Abbildung~\ref{fig:recomb}). So können zwei Mutationen, die auf verschiedenen Kopien liegen, zusammengefügt werden.

Beispiel:

Bei unseren parametrisierten Hasen lässt sich die Rekombination sehr einfach ausführen. Wir trennen beide Parameterlisten an der gleichen Stelle und vertauschen die Hälften und erzeugen so eine neue Parameterliste

$h_{1}\quad =\quad [{\color {Blue}\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots }|{\color {Blue}\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,{\mbox{usw}}\dots }]$

$h_{2}\quad =\quad [{\color {Red}\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots }|{\color {Red}\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,{\mbox{usw}}\dots }]$

ergibt nach der Rekombination

$h_{\mathsf {neu}}\quad =\quad [{\color {Red}\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots }|{\color {Blue}\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,{\mbox{usw}}\dots }]$

$h_{\mathsf {neu}}\quad =\quad [{\color {Blue}\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots }|{\color {Red}\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,{\mbox{usw}}\dots }]$

Beide Eltern tragen je zwei Kopien ihres Erbgutes. Bei der Paarung werden dem Spross je eine der Kopien beider Elternteile gegeben. Es sind also 4 verschiedene Kombinationen möglich.

Bei der Rekombination werden beide Kopien der DNS an der gleichen Stelle durchtrennt und vertauscht wieder zusammengefügt.

Wie bei der Mutation ist es hier wichtig, dass die Rekombination an einer zufälligen Stelle ansetzt. Wieder weiss die Rekombination nichts über das zu lösende Problem und kann deswegen nicht gezielt operieren. Auch hier ist es wichtig, dass, wie bei der Mutation, ungeahnte und unkonventionelle Lösungen gefunden werden.

Definition:

Zusammenfassend kann man sagen, dass die Rekombination aus zwei Lösungen eine neue Lösung erzeugt, indem sie die Werte dieser zwei Lösungen zufällig mischt.

Im folgenden werden wir sehen, wie sich die Rekombination in unseren Beispielproblemen realisieren lässt.

Das Klassifikationsproblem

Da die Lösungen des Klassifikationsproblems aus nur zwei Unbekannten bestehen, ist die Rekombination ziemlich trivial. Aus zwei zufällig gewählten Lösungen erzeugen wir eine neue Lösung mit dem $a$ der ersten und dem $b$ der zweiten.

Natürlich gehts auch komplizierter. Anstatt die zwei Lösungen nur als Parameterpaare zu sehen können wir sie auch eben geometrisch betrachten und zum Beispiel die Winkelhalbierende zwischen beiden Geraden bilden. Wir können von den zwei Lösungen den Durchschnitt der Parametern $a$ und $b$ nehmen.

Das Problem des Handelsreisenden

Da es sich beim Problem des Handelsreisenden bei den Lösungen um Reihenfolgen handelt, ist der Rekombinationsoperator nicht trivial. Wenn wir zwei Lösungen nehmen und an einer zufällig gewählten Stelle rekombinieren kann es sein, dass gewisse Städte dann doppelt oder eben gar nicht mehr vorkommen.

Um dem vorzubeugen können wir folgenden Rekombinationsoperator benutzen: Wir wählen zufällig zwei Lösungen und eine Zahl $i$ zwischen 1 und 6. Die neue Lösung setzen wir dann aus der ersten bis zur $(i-1)$-ten Stadt aus der ersten Lösung und den restlichen Städten in der Reihenfolge, in der sie in der zweiten Lösung vorkommen zusammen (vgl.~Abbildung~\ref{fig:rekhr}).

Rekombinationsoperator für das Problem des Handelsreisenden. Von der ersten Lösung werden die erste bis zur $(i-1)$-ten Stadt genommen. Die restlichen Städte werden in der Reihenfolge wie sie in der zweiten Lösung stehen in der neuen Lösung eingetragen.

Lernkontrolle

1. Erklären Sie mit Ihren eigenen Worten, wie die Rekombination in der Natur funktioniert. Sie können dazu auch eine Skizze anfertigen.
2. Wenn unsere Bevölkerung aus fünf parametrisierten Hasen besteht, wieviele Paare sind für die Rekombination möglich?
3. Erklären Sie in Ihren eigenen Worten, wozu die Rekombination gut ist.
4. Benutzen Sie den Rekombinationsoperator für das Problem des Handelsreisenden, um folgende zwei Lösungen an der Stelle $i=3$ zu rekombinieren:
   1. BDAFEC
   2. AEDFBC
5. Sowohl der Mutationsoperator als auch der Rekombinationsoperator erzeugen neue Lösungen.
   1. Worin unterscheiden sich die neuen Lösungen beider Operatoren?
   2. Was kann die Rekombination, was die Mutation nicht kann?
   3. Was kann die Mutation, was die Rekombination nicht kann?

Kapiteltest

Beschreiben Sie einen möglichen Rekombinationsoperator für das Damenproblem.

Lösungen

Lernkontrolle

1. Wichtig ist, dass zwei DNS-Stränge an einer Stelle geschnitten und vertauscht werden.
2. Es gibt $5\times 4/2=10$ mögliche Kombinationen von zwei Hasen aus fünf.
3. Wichtig ist, dass gute Eigenschaften von zwei Lösungen vermischt werden. Geschieht dies nicht, dann dürfen neue Ansätze nicht gleichzeitig entstehen, sonst geht eine davon zwangsläufig verloren.
4. BDAEFC
5. Der Mutationsoperator erzeugt zufällige neue Werte für die Parameter während der Rekombinationsoperator alte Werte der Parameter neu vermischt. Der Mutationsoperator erzeugt somit neue Parameterwerte und der Rekombinationoperator neue Kombinationen von Parameterwerten. Die Rekombination kann "alte" Information nutzen, was der Mutationsoperator nicht kann. Der Mutationsoperator kann eine völlig neue Lösung erzeugen, was der Rekombinationsoperator nicht kann.

Kapiteltest

Eine einfach Art, zwei Lösungen des Damenproblems zu rekombinieren ist es, eine zufällige Zahl $i$ zwischen 1 und 6 zu wählen und die Spalten 1 bis $i-1$ der ersten Lösung mit den Spalten $i$ bis 6 der zweiten Lösung zu vermischen. Wir können aber auch einzelne Spalten aus der einen Lösung mit der der anderen Lösung vermischen, anstatt sie blockweise zu nehmen.