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 Zufallszahlen) zu einem neuen Genom ist eine Funktion und heißt Mutations-Funktion. Jede Mutations-Funktion ist ein genetischer Operator. Mutationsoperatoren dienen als Suchoperator dazu, sowohl die Umgebung eines Lösungskandidaten abzusuchen als auch die weitere Umgebung in die Suche mit einzubeziehen. Sie dienen also sowohl der „Feinabstimmung (engl. exploitation), um ausgehend von einem guten Lösungskandidaten das zugehörige lokale Optimum zu finden,“ als auch dem „stichprobenartigen Erforschen (engl. exploration) weiter entfernter Gebiete des Suchraums, um das Einzugsgebiet eines potentiell besseren lokalen Optimums zu identifizieren.“ Eine weitere Funktion besteht darin, im Verlauf der Evolution verloren gegangene Allele wieder in den Genpool einzuführen. Man unterscheidet außerdem zwischen Genmutationen und solchen, die das komplette Chromosom oder (größere) Teile davon betreffen.
Alle in einem EA zur Anwendung kommenden Mutationsoperatoren müssen in ihrer Gesamtheit folgenden Anforderungen genügen:
- Kleine Änderungen müssen wahrscheinlicher sein als große.
- Jeder Punkt im Suchraum muss durch eine oder mehrere Mutationen erreichbar sein.
- Es darf keine Bevorzugung von Teilen oder Richtungen im Suchraum (keine Drift) geben.
Am Anfang eines EA-Laufs ist es günstiger, größere Änderungen zuzulassen, während im fortgeschritteneren Stadium vermehrt kleine Änderungen bevorzugt sein sollten, um es Individuen, die sich bereits nahe an einem Optimum befinden, zu erleichtern sich diesem Optimum weiter anzunähern.
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.
Für die verschiedenen Genom-Typen eignen sich unterschiedliche Mutations-Typen unterschiedlich gut. Einen Überblick und mehr Operatoren als die hier vorgestellten können im einführenden Buch von Eiben und Smith oder in gefunden werden.