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 EAs. 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:

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 in stärkerem Maße 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.

Der Anteil der Nachkommen pro Generation, der mindestens einer Mutation unterzogen wird, ergibt die globale Mutationsrate. Diese darf nicht zu niedrig sein, da sonst aus der Population gefallene Allele schlecht wieder in die Population zurückkehren können und somit, falls sie ein Teil der global optimalen Lösung waren, zum Auffinden dieser fehlen (Building Blocks bei klassischen genetischen Algorithmen). 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.

1. ↑ Karsten Weicker: Evolutionäre Algorithmen. 3. Auflage. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-09957-2, Rollen der Mutation, S. 59–62, doi:10.1007/978-3-658-09958-9. 
2. 1 2 Darrell Whitley: A genetic algorithm tutorial. In: Statistics and Computing. Band 4, Nr. 2, Juni 1994, ISSN 0960-3174, S. 65–85, Abschn. 4.1, S. 73, doi:10.1007/BF00175354. 
3. A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, doi:10.1007/978-3-662-44874-8. 
   1. ↑ Variation Operators (Mutation and Recombination), S. 31–32
   2. ↑ Representation, Mutation, and Recombination, S. 49–78
4. ↑ Thomas Bäck, David B. Fogel, Darrel Whitley, Peter Angeline: Mutation operators. In: Thomas Bäck, David B. Fogel, Zbigniew Michalewicz (Hrsg.): Evolutionary computation. Vol. 1: Basic algorithms and operators. Institute of Physics Pub, Bristol 1999, ISBN 978-0-7503-0664-5, S. 237–255, doi:10.1201/978148226871 (englisch). 
   1. ↑ S. 238
5. ↑ Hartmut Pohlheim: Evolutionäre Algorithmen. Springer, Berlin, Heidelberg 2000, ISBN 978-3-642-63052-1, Mutation, S. 46–56, doi:10.1007/978-3-642-57137-4.