Mutation (evolutionärer Algorithmus)

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.

Die Gesamtheit aller in einem EA zur Anwendung kommenden Mutationsoperatoren müssen folgenden Anforderungen genügen:

1. Kleine Änderungen müssen wahrscheinlicher sein als große.
2. Jeder Punkt im Suchraum muss durch eine oder mehrere Mutationen erreichbar sein.
3. Es darf keine Bevorzugung von Teilen oder Richtungen im Suchraum (keine Drift) geben.

Am Anfang des Laufens eines EA ist es günstiger, größere Änderungen zuzulassen, während im fortgeschritteneren Stadium nur noch kleine Änderungen bevorzugt sein sollten, um Individuen, die sich bereits nahe einem Optimum 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 (Building Blocks bei klassischen genetischen Algorithmen) 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 schlechter 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)

Die Mutation von Bitstrings der klassischen genetischen Algorithmen 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

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}XOR2^{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 reeller Zahlen

Viele EAs wie zum Beispiel die Evolutionsstrategie oder die reell-codierten genetischen Algorithmen arbeiten mit reellen Zahlen anstelle von Bitstrings. Dies liegt in den guten Erfahrung begründet, die mit dieser Codierungsart gemacht wurden und in der Theorie der virtuellen Alphabete von David E. Goldberg.

Beispiel einer normalverteilten Zufallsgröße. Man beachte, dass sich die angegebenen Anteile der Teilbereiche auf Grund der Rundungen zu 99,8% und nicht zu 100% addieren.

Eine reelle $x'$ Zahl kann mittels der Normalverteilung $N(0,\sigma )$ mutiert werden, wobei eine normalverteilte Zufallszahl bei dieser Verteilung bekanntlich mit rund 99,7 % Wahrscheinlichkeit im Intervall $[-3\cdot \sigma ,+3\cdot \sigma ]$ liegt. Der mutierte Wert ergibt sich dann folgendermaßen:
$x'=x+N(0;\sigma )$
Bei praktischen Anwendungen sind die zu mutierenden Werte in der Regel begrenzt und es bietet sich an, die Schrittweite der Mutation $\sigma$ so zu wählen, dass sie zum Werteintervall $[x_{min},x_{max}]$ einigermaßen passt, also z. B.:
$\sigma ={{x_{max}-x_{min}} \over 6}$
Natürlich kann auch stattdessen vom kleineren Intervall zwischen dem aktuellen Wert von x und den Grenzen ausgegangen werden. Es wird aber in jedem Fall mit einer gewissen Wahrscheinlichkeit vorkommen, dass sich der neue Wert des Gens $x'$ außerhalb des Wertebereichs befindet. In einem solchen Fall liegt eine Letalmutation vor, da die naheliegende Reparatur durch Verwendung der jeweils verletzten Grenze als neuen Wert des Gens zu einer Drift führen würde. Denn der Grenzwert würde dann mit der gesamten Wahrscheinlichkeit der Werte jenseits der Grenze des Wertebereichs ausgewählt werden. Im Bild ist dies z. B. der gesamte Bereich rechts von 1σ, wenn dies beispielhaft der Obergrenze des Wertebereichs des Gens entspräche. Das wäre immerhin eine Wahrscheinlichkeit von rund 15,8% nur für diesen einen Wert!

Die Evolutionsstrategie arbeitet mit reellen Zahlen und ebenfalls einer Mutation basierend auf der Normalverteilung. Die Schrittweiten sind dabei Bestandteil des Chromosoms und unterliegen zusammen mit den eigentlichen Entscheidungsvariablen der Evolution.

Mutation von Permutationen

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

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|-1$ 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=1$
* 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

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|-1$ 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=1$
* 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.