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:

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

Mutation von binären Zahlen (Bitstrings)

Die 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 $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).

Bevorzugung der niederwertigeren Bits

Eine Variante der Mutation von binären Zahlen ist folgendes Verfahren:

• Wähle eine Stelle $i$ der binären Zahl $Z_{0}$, 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: $Z_{1}=Z_{0}XOR2^{i}$.
• Die auf diese Weise neu entstandene Zahl $Z_{1}$ 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 $1100110000{,}00$ statt $1{,}10011\cdot 2^{9}$).

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

Viele EAs wie zum Beispiel die Evolutionsstrategie oder die reell-codierten genetischen Algorithmen arbeiten mit reellen Zahlen anstelle von Bitstrings. Dies liegt in den guten Erfahrungen begründet, die mit dieser Codierungsart gemacht wurden.

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 sind die zu verändernden Entscheidungsvariablen des zu bearbeitenden Optimierungsproblems in der Regel begrenzt. Dementsprechend sind die Werte der zugehörigen Gene jeweils auf ein Werteintervall $[x_{\text{min}},x_{\text{max}}]$ 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

Beispiel einer normalverteilten Zufallsgröße. Man beachte, dass sich die angegebenen Anteile der Teilbereiche auf Grund der Rundungen zu 99,8 % und nicht zu 100 % addieren.

Eine reelle Zahl $x$ kann mittels der Normalverteilung $N(0,\sigma )$ mutiert werden, wobei eine normalverteilte Zufallszahl bei dieser Verteilung bekanntlich mit rund 99,7 % Wahrscheinlichkeit im Intervall $\left[-3\cdot \sigma ,+3\cdot \sigma \right]$ liegt. Der mutierte Wert $x'$ ergibt sich dann folgendermaßen:

$x'=x+N(0;\sigma )$

Bei Genen mit eingeschränktem Wertebereich bietet es sich an, die Schrittweite der Mutation $\sigma$ so zu wählen, dass sie zum Werteintervall $[x_{\text{min}},x_{\text{max}}]$ des zu verändernden Gens einigermaßen passt, also z. B.:

$\sigma ={\frac {x_{\text{max}}-x_{\text{min}}}{6}}$

Natürlich kann auch stattdessen vom kleineren Intervall zwischen dem aktuellen Wert von $x$ 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 $x'$ 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

Verteilung der Wahrscheinlichkeiten der 10 Teilbereiche des Gesamtänderungsintervalls. Die Teilbereiche decken jeweils 10 % der Breite des Gesamtänderungsintervalls ab.

Eine mögliche Form der Werteänderung eines Gens unter Berücksichtigung seines Wertebereichs $[x_{\text{min}},x_{\text{max}}]$ ist die Mutation „relative Parameteränderung“ des evolutionären Algorithmus GLEAM (General Learning Evolutionary Algorithm and Method), bei der wie bei der zuvor vorgestellten Mutation kleine Veränderungen wahrscheinlicher sind als große.

Zuerst wird gleichverteilt entschieden, ob der aktuelle Wert $x$ 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 $[x,x_{\text{max}}]$. Es wird in zehn gleich große Teilbereiche mit der Breite $\delta$ eingeteilt, aus denen zehn unterschiedlich große Teiländerungsintervalle gebildet werden:

$i$-tes Teiländerungsintervall: $[x,x+\delta \cdot i]$ mit $\delta ={\frac {(x_{\text{max}}-x)}{10}}$ und $i=1,\dots ,10$

Anschließend wird gleichverteilt eines der zehn Teiländerungsintervalle ausgewählt und daraus eine ebenfalls gleichverteilte Zufallszahl als neuer Wert $x'$ für das Gen gezogen. Die sich daraus ergebenden summierten Wahrscheinlichkeiten der zehn Teiländerungsintervalle ergeben die im Bild dargestellte Verteilung für die zehn Teilbereiche. Dies ist zwar keine Normalverteilung wie zuvor, aber auch diese Verteilung bevorzugt deutlich kleine Änderungen vor größeren.

Verteilung der Wahrscheinlichkeiten für die beispielhafte Änderung des aktuellen Wertes x eines Gens.

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

Bei 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

Die 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.

Rotation nach rechts

Eine Variante von Mutation von Permutationen ist folgendes Verfahren, siehe auch :

Verfahren	Beispiel
Gegeben ist eine Permutation,	$P_{0}=\left(A,B,C,D,E,F,G\right)$
* Wähle eine Teil-Liste aus, also einen Start-Index $i$ und einen End-Index $j$ in $P_{0}$, die beide natürliche Zahlen zwischen 0 und $\left|P_{0}\right|-1$ sind. Wähle die Anzahl der Positionen $k$ aus, um die die Teil-Liste rotiert werden soll, wobei gilt $0<k<|P_{0}|$. 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.	$i=5$, $j=1$, $k=1$
* Kopiere $P_{0}$ nach $P_{1}$ und rotiere die Teil-Liste um $k$ Positionen nach rechts.	$P_{1}=\left({\underline {G,A{,}}}C,D,E,{\underline {B,F}}\right)$
* $P_{1}$ ist dann das mutierte Genom.	$P_{1}=\left(G,A,C,D,E,B,F\right)$

Spiegelung

Eine weitere Variante von Mutation von Permutationen ist folgendes Verfahren:

Verfahren	Beispiel
* Gegeben ist eine Permutation,	$P_{0}=\left(A,B,C,D,E,F,G\right)$
* Wähle eine Teil-Liste aus, also einen Start-Index $i$ und einen End-Index $j$ in $P_{0}$, die beide natürliche Zahlen zwischen 0 und $\left|P_{0}\right|-1$ sind und $i\neq j$ 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.	$i=5$, $j=1$
* Kopiere $P_{0}$ nach $P_{1}$ und spiegele die Teil-Liste.	$P_{1}=\left({\underline {G,F{,}}}C,D,E,{\underline {B,A}}\right)$
* $P_{1}$ ist dann das mutierte Genom.	$P_{1}=\left(G,F,C,D,E,B,A\right)$

Varianten mit Bevorzugung kleiner Änderungen

Die 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 $j$ der Teillisten wird als Distanz $d$ zum Startindex $i$ bestimmt:

$j=(i+d){\bmod {\left|P_{0}\right|}}$

wobei $d$ zufällig nach einem der beiden Verfahren für die Mutation reeller Zahlen aus dem Intervall $\left[0,\left|P_{0}\right|-1\right]$ bestimmt wird. Legt man die Mutation ohne Berücksichtigung von Restriktionen zu Grunde, so kann das $\sigma$ 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 $d$ auf ganze Zahlen zu runden.

Bei der Rotation wird $k$ ähnlich wie die Distanz $d$ bestimmt, wobei jedoch der Wert $0$ verboten ist.

Bei der Spiegelung ist zu beachten, dass $i\neq j$ sein muss, also ist für $d$ der Wert $0$ 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

• 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