Mutation

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. Alle in einem EA zur Anwendung kommenden Mutationsoperatoren müssen in ihrer Gesamtheit 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 eines EA-Laufs 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: