Mutation (evolutionärer Algorithmus)

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

Unter Mutation versteht man bei einem evolutionären Algorithmus (EA) die zufällige Änderung eines Genoms. Sie ist die Umsetzung der biologischen Mutation für EA. Eine solche Zuordnung von einem alten Genom (und eventuell Zufallszahlen) zu einem neuen Genom ist eine Funktion und heißt Mutations-Funktion. Jede Mutations-Funktion ist ein genetischer Operator.

Eine Mutation sollte idealerweise nur kleine Änderungen hervorrufen, jedoch in der Summe so viel, dass die Individuen über die Laufzeit eines evolutionären Algorithmus fast die gesamte Wertelandschaft abdecken, auf der optimiert werden soll. Am Anfang des Laufens eines EA ist es deswegen günstiger, größere Änderungen zuzulassen, während im fortgeschrittenerem Stadium nur noch kleine Änderungen erlaubt sein sollten, um Individuen, die sich bereits nahe eins Optimums befinden, nicht von diesem Optimum wegzubringen.

Ein evolutionärer Algorithmus mit einer globalen Mutationsrate (Anteil der Gesamtpopulation, die der Mutation unterzogen wird) von 0 wird sehr schlechte Ergebnisse liefern, da einmal durch Kreuzungsfunktionen aus der Population gefallene Allele niemals wieder in die Population zurückkehren können und somit, falls sie ein Teil des Building Blocks der global optimalen Lösung waren, zum Auffinden dieser fehlen. Ist die Mutationsrate hingegen zu hoch, werden Individuen nahe beim Optimum wieder von diesem weggedrängt und der Algorithmus kann nicht konvergieren.

Bei Verwendung von für das Problem nicht gut geeigneten Kreuzungsfunktionen oder Problemrepräsentationen kann es zu ungewollten Mutationen bei der Kreuzung kommen. Dabei entsteht an manchen Stellen des Chromosoms eine Ausprägung des Allels, die sich auf keinen der Elternindividuen zurückführen lassen, noch bevor es zum eigentlichen Mutationsschritt kommt.

Für unterschiedliche Genom-Typen eignen sich unterschiedliche Mutations-Typen unterschiedlich gut:

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

Die Mutation von Bitstrings erfolgt durch Bit-Flips an zufälligen Stellen.

Beispiel:

1 0 1 0 0 1 0
1 0 1 0 1 1 0

Die Wahrscheinlichkeit für eine Mutation eines Bits beträgt 1/l, wobei l die Länge des Binärvektors ist. Dadurch wird im Schnitt eine Mutationsrate von 1 je Mutation und zur Mutation gewählten Individuum erreicht (siehe oben, globale Mutationsrate) .

Bevorzugung der niederwertigeren Bit[Bearbeiten]

Eine Variante der Mutation von binären Zahlen ist folgendes Verfahren:

  • Wähle eine Stelle i der binären Zahl Z_0, wobei die niederwertigen Stellen mit einer exponentiell höheren Wahrscheinlichkeit ausgewählt werden als die höherwertigen.
  • Invertiere das Bit an dieser Stelle der binären Zahl um: Z_1 = Z_0 XOR 2^i.
  • Die auf diese Weise neu entstandene Zahl Z_1 ist das mutierte Genom.

Ein Beispiel zur Veranschaulichung - eine Mutation einer 8-Bit-Zahl:

11001100 - die Zahl vor der Mutation
11000100 - danach (eine Mutation an der 4. Stelle)

Dieses Verfahren funktioniert auch bei Gleitkommazahlen, wenn diese als Zahl ohne Exponenten-Information geschrieben wird (also 1100110000{,}00 statt 1{,}10011 \cdot 2^9).

Eine falsche Wahl der Mutationswahrscheinlichkeiten kann dazu führen, dass immer nur niederwertigen Stellen modifiziert werden, sodass die Mutationen letztendlich gar keinen nennenswerten Einfluss auf die Individuen oder den von ihnen abhängige Fitness-Funktions-Wert haben.

Mutation von Permutationen[Bearbeiten]

Die Mutation von Permutationen ist spezielle für Genome ausgelegt, die selbst Permutationen einer Menge sind. Dabei werden Teile des Genoms verschoben oder gespiegelt.

Rotation nach rechts[Bearbeiten]

Eine Variante von Mutation von Permutationen ist folgendes Verfahren:

Verfahren Beispiel
Gegeben ist eine Permutation, P_0 = \left( A,B,C,D,E,F,G \right)
* Wähle eine Teil-Liste aus, also einen Start-Index i und einen End-Index j in P_0, die beide natürliche Zahlen zwischen 0 und \left|P_0\right| sind. Der Start-Index kann dabei auch nach dem End-Index kommen. Dann fängt die Teil-Liste einfach von vorne wieder an (periodische Randbedingung). Dies ist notwendig, damit die Permutationswahrscheinlichkeit im Genom überall gleich ist und nicht in der Mitte größer ist als an den Rändern. i = 5, j = 2
* Kopiere P_0 nach P_1 und rotiere die Teil-Liste nach rechts. P_1 = \left( \underline {G,A{,}}C,D,E,\underline {B,F} \right)
* P_1 ist dann das mutierte Genom. P_1 = \left( G,A,C,D,E,B,F \right)

Spiegelung[Bearbeiten]

Eine weitere Variante von Mutation von Permutationen ist folgendes Verfahren:

Verfahren Beispiel
* Gegeben ist eine Permutation, P_0 = \left( A,B,C,D,E,F,G \right)
* Wähle eine Teil-Liste aus, also einen Start-Index i und einen End-Index j in P_0, die beide natürliche Zahlen zwischen 0 und \left|P_0\right| sind. Der Start-Index kann dabei auch nach dem End-Index kommen. Dann fängt die Teil-Liste einfach von vorne wieder an (periodische Randbedingung). Dies ist notwendig, damit die Permutationswahrscheinlichkeit im Genom überall gleich ist und nicht in der Mitte größer ist als an den Rändern. i = 5, j = 2
* Kopiere P_0 nach P_1 und spiegele die Teil-Liste. P_1 = \left( \underline {G,F{,}}C,D,E,\underline {B,A} \right)
* P_1 ist dann das mutierte Genom. P_1 = \left( G,F,C,D,E,B,A  \right)

Diese Variante ist geeignet zur Lösung vom Problem des Handlungsreisenden, da hier die Änderung der Nachbarschaft minimal gehalten werden sollte und durch die Spiegelung einfach ein Teil-Weg in umgekehrter Reihenfolge gegangen wird.