Mutation (genetischer Algorithmus)

Unter Mutation bei einem genetischen Algorithmus versteht man die zufällige Abänderung eines Genoms. Sie ist die Umsetzung der biologischen Mutation für genetische Algorithmen. 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 genetischen Algorithmus' fast die gesamte Wertelandschaft abdecken, auf der optimiert werden soll. Am Anfang des Laufens eines genetischen Algorithmus 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 genetischer 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 Bitstrings

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 $\frac{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) .

• Mutation von Permutationen