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.“[1] Eine weitere Funktion besteht darin, im Verlauf der Evolution verloren gegangene Allele wieder in den Genpool einzuführen.[2] 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:[3]
- 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.[4]
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.[5] Einen Überblick und mehr Operatoren als die hier vorgestellten können im einführenden Buch von Eiben und Smith[6] oder in [7] gefunden werden.
Mutation von binären Zahlen (Bitstrings)
BearbeitenDie 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 , wobei die Länge des Binärvektors ist.[8] Dadurch wird im Schnitt eine Mutationsrate von 1 je Mutation und zur Mutation gewählten Individuum erreicht (siehe oben, globale Mutationsrate).
Bevorzugung der niederwertigeren Bits
BearbeitenEine Variante der Mutation von binären Zahlen ist folgendes Verfahren:
- Wähle eine Stelle der binären Zahl , 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: .
- Die auf diese Weise neu entstandene Zahl 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 statt ).
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
BearbeitenViele EAs wie zum Beispiel die Evolutionsstrategie[9][10] oder die reell-codierten genetischen Algorithmen[11][12] arbeiten mit reellen Zahlen anstelle von Bitstrings. Dies liegt in den guten Erfahrungen begründet, die mit dieser Codierungsart gemacht wurden[13][14][15].
Der Wert eines reellwertigen Gens kann entweder verändert oder neu bestimmt werden. Eine Mutation, die letzteres umsetzt, sollte immer nur in Verbindung mit den Wert ändernden Mutationen eingesetzt werden und dann auch nur mit vergleichsweise geringer Wahrscheinlichkeit, da sie zu großen Änderungen führen kann.
Bei praktischen Anwendungen ist der jeweilige Wertebereich der zu verändernden Entscheidungsvariablen des zu bearbeitenden Optimierungsproblems in der Regel begrenzt. Dementsprechend sind die Werte der zugehörigen Gene jeweils auf ein Werteintervall eingeschränkt. Mutationen können diese Restriktionen berücksichtigen oder nicht. Im letzten Fall ist dann eine geeignete Nachbehandlung erforderlich.
Mutation ohne Berücksichtigung von Restriktionen
BearbeitenEine reelle Zahl kann mittels der Normalverteilung mutiert werden, wobei eine normalverteilte Zufallszahl bei dieser Verteilung bekanntlich mit rund 99,7 % Wahrscheinlichkeit im Intervall liegt. Der mutierte Wert ergibt sich dann folgendermaßen:[16]
Bei Genen mit eingeschränktem Wertebereich bietet es sich an, die Schrittweite der Mutation so zu wählen, dass sie zum Werteintervall des zu verändernden Gens einigermaßen passt, also z. B.:
Natürlich kann auch stattdessen vom kleineren Intervall zwischen dem aktuellen Wert von und den Grenzen ausgegangen werden, solange dies nicht zu klein im Vergleich zum gesamten Wertebereich ist. Es wird aber in jedem Fall mit einer gewissen Wahrscheinlichkeit vorkommen, dass sich der neue Wert des Gens 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 ergäbe dann 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 mit Berücksichtigung von Restriktionen
BearbeitenEine mögliche Form der Werteänderung eines Gens unter Berücksichtigung seines Wertebereichs ist die Mutation „relative Parameteränderung“ des evolutionären Algorithmus GLEAM (General Learning Evolutionary Algorithm and Method),[15][17] bei der wie bei der zuvor vorgestellten Mutation kleine Veränderungen wahrscheinlicher sind als große.
Zuerst wird gleichverteilt entschieden, ob der aktuelle Wert vergrößert oder verkleinert werden soll und dann das zugehörige Gesamtänderungsintervall bestimmt. Ohne Beschränkung der Allgemeinheit wird für die Erklärung von einer Vergrößerung ausgegangen und das Gesamtänderungsintervall lautet dann . Es wird in gleich große Teilbereiche mit der Breite eingeteilt, aus denen unterschiedlich große Teiländerungsintervalle gebildet werden:
- -tes Teiländerungsintervall: mit und
Anschließend wird gleichverteilt eines der Teiländerungsintervalle ausgewählt und daraus eine ebenfalls gleichverteilte Zufallszahl als neuer Wert für das Gen gezogen. Die sich daraus ergebenden summierten Wahrscheinlichkeiten der Teiländerungsintervalle ergeben die im Bild dargestellte Verteilung für Teilbereiche. Dies ist zwar keine Normalverteilung wie zuvor, aber auch diese Verteilung bevorzugt deutlich kleine Änderungen vor größeren.
Die Wahrscheinlichkeiten der Teilbereiche eines Gens, für die Änderung ausgewählt zu werden, gibt das nebenstehende Bild für seinen gesamten Wertebereich wieder. Man beachte, dass die Flächen nur jeweils rechts oder links vom aktuellen Wert proportional zur jeweiligen Änderungswahrscheinlichkeit sind, da die Entscheidung, ob eine Vergrößerung oder Verkleinerung stattfindet, gleichverteilt und unabhängig vom aktuellen Wert des Gens gefällt wird.
Es sei angemerkt, dass diese Mutation weniger gut für Aufgabenstellungen geeignet ist, bei denen das Optimum auf einer Grenze des zulässigen Wertebereichs liegt. Im Fall großer Annäherung eines Genwertes an seine Grenzen kann aber die Mutation leicht geeignet verändert werden, z. B. indem dann einfach der neue Wert aus dem kleinen Restbereich gleichverteilt ausgewürfelt wird.
Gemeinsame Eigenschaften
BearbeitenBei beiden Mutationsoperatoren für reellwertige Zahlen ist die Wahrscheinlichkeit für eine Vergrößerung und Verkleinerung unabhängig vom aktuellen Wert und beträgt jeweils 50 %. Außerdem sind kleine Änderungen erheblich wahrscheinlicher als große. Bei gemischt-ganzzahligen Optimierungsproblemen wird üblicherweise gerundet.
Mutation von Permutationen
BearbeitenDie Mutation von Permutationen ist spezielle für Genome ausgelegt, die selbst Permutationen einer Menge sind. Dabei werden Teile des Genoms verschoben, neu gemischt oder gespiegelt.[13][18]
Rotation nach rechts
BearbeitenEine Variante von Mutation von Permutationen ist folgendes Verfahren, siehe auch [18]:
Verfahren | Beispiel |
Gegeben ist eine Permutation, | |
* Wähle eine Teil-Liste aus, also einen Start-Index und einen End-Index in , die beide natürliche Zahlen zwischen 0 und sind. Wähle die Anzahl der Positionen aus, um die die Teil-Liste rotiert werden soll, wobei gilt . 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. | , , |
* Kopiere nach und rotiere die Teil-Liste um Positionen nach rechts. | |
* ist dann das mutierte Genom. |
Spiegelung
BearbeitenEine weitere Variante von Mutation von Permutationen ist folgendes Verfahren:[19]
Verfahren | Beispiel |
* Gegeben ist eine Permutation, | |
* Wähle eine Teil-Liste aus, also einen Start-Index und einen End-Index in , die beide natürliche Zahlen zwischen 0 und sind und gilt. Diese Bedingung bewirkt, dass die Mutation immer ein genotypisch verändertes Chromosom erzeugt. 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. | , |
* Kopiere nach und spiegele die Teil-Liste. | |
* ist dann das mutierte Genom. |
Varianten mit Bevorzugung kleiner Änderungen
BearbeitenDie eingangs erhobene Anforderung an Mutationen, wonach kleine Änderungen wahrscheinlicher sein sollen als große, wird durch die beiden Permutationsmutationen nur unzureichend erfüllt, da die Längen der Teillisten und die Anzahl der Verschiebungspositionen gleichverteilt bestimmt werden. Je länger aber die Teilliste und die Verschiebung ausfallen, desto größer ist die Änderung an der Genreihenfolge.
Dem kann durch folgende Modifikationen abgeholfen werden. Der Endindex der Teillisten wird als Distanz zum Startindex bestimmt:
wobei zufällig nach einem der beiden Verfahren für die Mutation reeller Zahlen aus dem Intervall bestimmt wird. Legt man die Mutation ohne Berücksichtigung von Restriktionen zu Grunde, so kann das so gewählt werden, dass es einem Drittel der Intervallbreite entspricht, und von der sich ergebenden normalverteilten Zufallszahl wird der Betrag genommen. Bei beiden Verfahren ist die resultierende reelle Zahl für auf ganze Zahlen zu runden.
Bei der Rotation wird ähnlich wie die Distanz bestimmt, wobei jedoch der Wert verboten ist.
Bei der Spiegelung ist zu beachten, dass sein muss, also ist für der Wert auszuschließen.
Diese Varianten sind z. B. zur Lösung vom Problem des Handlungsreisenden geeignet, da hier die Änderung der Nachbarschaft minimal gehalten werden sollte und durch die Spiegelung einfach ein Teil-Weg in umgekehrter Reihenfolge gegangen wird.
Literatur
Bearbeiten- Hartmut Pohlheim: Evolutionäre Algorithmen. Verfahren, Operatoren und Hinweise für die Praxis. Springer, Berlin 1999, ISBN 3-540-66413-0.
- Karsten Weicker: Evolutionäre Algorithmen. Teubner, Stuttgart 2002, ISBN 3-519-00362-7.
- A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, doi:10.1007/978-3-662-44874-8.
- Hans-Paul Schwefel: Evolution and Optimum Seeking. Wiley & Sons, New York 1995, ISBN 0-471-57148-2.
- Keshav P. Dahal, Kay Chen Tan, Peter I. Cowling (Hrsg.): Evolutionary Scheduling. Studies in Computational Intelligence, Bd. 49, Springer, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-48584-1, ISBN 978-3-642-08017-3
- Amir H. Gandomi, Ali Emrouznejad, Mo M. Jamshidi, Kalyanmoy Deb, Iman Rahimi (Hrsg.): Evolutionary Computation in Scheduling. John Wiley & Sons, 2020. ISBN 978-1-119-57387-6
Einzelnachweise
Bearbeiten- ↑ Karsten Weicker: Evolutionäre Algorithmen. Springer Fachmedien, Wiesbaden 2015, ISBN 978-3-658-09957-2, Rollen der Mutation, S. 59–62, doi:10.1007/978-3-658-09958-9.
- ↑ 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.
- ↑ 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, Variation Operators (Mutation and Recombination), S. 31–32, doi:10.1007/978-3-662-44874-8 (englisch).
- ↑ 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. 238, doi:10.1201/978148226871 (englisch).
- ↑ 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.
- ↑ 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, Representation, Mutation, and Recombination, S. 49–78, doi:10.1007/978-3-662-44874-8 (englisch).
- ↑ 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).
- ↑ Volker Nissen: Einführung in Evolutionäre Algorithmen. Vieweg+Teubner Verlag, Wiesbaden 1997, ISBN 978-3-528-05499-1, Mutation, S. 49, doi:10.1007/978-3-322-93861-9.
- ↑ Ingo Rechenberg: Evolutionsstrategie; Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart-Bad Cannstatt 1973, ISBN 3-7728-0373-3.
- ↑ Hans-Paul Schwefel: Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie. Birkhäuser, Basel 1977, ISBN 3-7643-0876-1.
- ↑ Larry J. Eshelman, J. David Schaffer: Real-Coded Genetic Algorithms and Interval-Schemata. In: Foundations of Genetic Algorithms. Band 2. Elsevier, 1993, ISBN 0-08-094832-4, S. 187–202, doi:10.1016/b978-0-08-094832-4.50018-0 (elsevier.com [abgerufen am 15. Januar 2022]).
- ↑ Cesary Janikow, Zbigniew Michalewicz: An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms. In: Conf. Proc of the Fourth Int. Conf. on Genetic Algorithms (ICGA'91). 1991, S. 31–36 (umsl.edu [PDF]).
- ↑ a b Zbigniew Michalewicz: Genetic Algorithms + Data Structures = Evolution Programs. Third, revised and Extended edition Auflage. Springer, Berlin, Heidelberg 1996, ISBN 3-662-03315-1.
- ↑ F. Herrera, M. Lozano, J.L. Verdegay: Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis. In: Artificial Intelligence Review. Band 12, Nr. 4, 1998, S. 265–319, doi:10.1023/A:1006504901164.
- ↑ a b Christian Blume, Wilfried Jakob: GLEAM - General Learning Evolutionary Algorithm and Method : ein Evolutionärer Algorithmus und seine Anwendungen. KIT Scientific Publishing, 2009, doi:10.5445/ksp/1000013553.
- ↑ 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.
- ↑ Christian Blume, Wilfried Jakob: GLEAM - An Evolutionary Algorithm for Planning and Control Based on Evolution Strategy. In: Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002). vol. Late Breaking Papers, 2002, S. 31–38 (kit.edu).
- ↑ a b Xinjie Yu, Mitsuo Gen: Introduction to Evolutionary Algorithms (= Decision Engineering). Springer, London 2010, ISBN 978-1-84996-128-8, Mutation Operators, S. 286–288, doi:10.1007/978-1-84996-129-5.
- ↑ 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, Mutation for Permutation Representation, S. 69–70, doi:10.1007/978-3-662-44874-8.