Quelltext der Seite Mutation (evolutionärer Algorithmus)

Unter '''Mutation''' versteht man bei einem [[Evolutionärer Algorithmus|evolutionären Algorithmus]] (EA) die zufällige Änderung eines [[Genom (evolutionärer Algorithmus)|Genoms]]. Sie ist die Umsetzung der biologischen [[Mutation]] für EAs. Eine solche Zuordnung von einem alten Genom (und [[Zufallszahl]]en) zu einem neuen Genom ist eine [[Funktion (Mathematik)|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.''“<ref name=":3">{{Literatur |Autor=Karsten Weicker |Titel=Evolutionäre Algorithmen |Auflage=3. |Verlag=Springer Fachmedien |Ort=Wiesbaden |Datum=2015 |ISBN=978-3-658-09957-2 |DOI=10.1007/978-3-658-09958-9 |Kapitel=Rollen der Mutation |Seiten=59-62}}</ref> Eine weitere Funktion besteht darin, im Verlauf der Evolution verloren gegangene [[Allel]]e wieder in den [[Genpool]] einzuführen.<ref name=":5">{{Literatur |Autor=Darrell Whitley |Titel=A genetic algorithm tutorial |Sammelwerk=Statistics and Computing |Band=4 |Nummer=2 |Datum=1994-06 |ISSN=0960-3174 |DOI=10.1007/BF00175354 |Seiten=65-85 |Fundstelle=Abschn. 4.1, S. 73}}</ref> 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:<ref name=":4" details="Variation Operators (Mutation and Recombination), S. 31–32">{{Literatur |Autor=A.E. Eiben, J.E. Smith |Titel=Introduction to Evolutionary Computing |Reihe=Natural Computing Series |Auflage=2. |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2015 |ISBN=978-3-662-44873-1 |DOI=10.1007/978-3-662-44874-8}}</ref>
# 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 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.<ref name="EC-1" details="S. 238" />

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 ([[Schematheorem|Building Blocks]] bei [[Evolutionärer Algorithmus#Genetische Algorithmen (GA)|klassischen genetischen Algorithmen]]).<ref name=":5" /> 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.<ref>{{Literatur |Autor=Hartmut Pohlheim |Titel=Evolutionäre Algorithmen |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2000 |ISBN=978-3-642-63052-1 |DOI=10.1007/978-3-642-57137-4 |Kapitel=Mutation |Seiten=46-56}}</ref> Einen Überblick und mehr Operatoren als die hier vorgestellten können im einführenden Buch von Eiben und Smith<ref name=":4" details="Representation, Mutation, and Recombination, S. 49–78" /> oder in <ref name="EC-1">{{Literatur |Autor=Thomas Bäck, David B. Fogel, Darrel Whitley, Peter Angeline |Titel=Mutation operators |Hrsg=Thomas Bäck, David B. Fogel, Zbigniew Michalewicz |Sammelwerk=Evolutionary computation |Band=Vol. 1: ''Basic algorithms and operators'' |Verlag=Institute of Physics Pub |Ort=Bristol |Datum=1999 |Sprache=en |ISBN=978-0750306645 |DOI=10.1201/978148226871 |Seiten=237–255}}</ref> gefunden werden.

== Mutation von binären Zahlen (Bitstrings) ==
Die Mutation von Bitstrings der [[Evolutionärer Algorithmus|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 optimale Wahrscheinlichkeit für die Mutation eines Bits beträgt <math>1/l</math>, wobei <math>l</math> die Länge des Binärvektors ist.<ref>{{Literatur |Autor=Volker Nissen |Titel=Einführung in Evolutionäre Algorithmen |Verlag=Vieweg+Teubner Verlag |Ort=Wiesbaden |Datum=1997 |ISBN=978-3-528-05499-1 |DOI=10.1007/978-3-322-93861-9 |Kapitel=Mutation |Seiten=49}}</ref> 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 <math>i</math> der binären Zahl <math>Z_0</math>, 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: <math>Z_1 = Z_0\ XOR\ 2^i</math>.
* Die auf diese Weise neu entstandene Zahl <math>Z_1</math> 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 [[Gleitkommazahl]]en, wenn diese als Zahl ohne Exponenten-Information geschrieben wird (also <math>1100110000{,}00</math> statt <math>1{,}10011 \cdot 2^9</math>).

Eine falsche Wahl der Mutationswahrscheinlichkeiten kann bei dieser Mutationsvariante dazu führen, dass häufig nur niederwertigen Stellen modifiziert werden, sodass die Mutationen letztendlich gar keinen nennenswerten Einfluss auf die Individuen oder den von ihnen abhängige [[Fitness-Funktion]]s-Wert haben.

== Mutation reeller Zahlen ==
Viele EAs wie zum Beispiel die [[Evolutionärer Algorithmus|Evolutionsstrategie]]<ref>{{Literatur |Autor=Ingo Rechenberg |Titel=Evolutionsstrategie; Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. |Verlag=Frommann-Holzboog |Ort=Stuttgart-Bad Cannstatt |Datum=1973 |ISBN=3-7728-0373-3}}</ref><ref>{{Literatur |Autor=Hans-Paul Schwefel |Titel=Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie |Verlag=Birkhäuser |Ort=Basel |Datum=1977 |ISBN=3-7643-0876-1}}</ref> oder die reell-codierten [[Evolutionärer Algorithmus|genetischen Algorithmen]]<ref>{{Literatur |Autor=Larry J. Eshelman, J. David Schaffer |Titel=Real-Coded Genetic Algorithms and Interval-Schemata |Sammelwerk=Foundations of Genetic Algorithms |Band=2 |Verlag=Elsevier |Datum=1993 |ISBN=0-08-094832-4 |Seiten=187–202 |Online=https://linkinghub.elsevier.com/retrieve/pii/B9780080948324500180 |Abruf=2022-01-15 |DOI=10.1016/b978-0-08-094832-4.50018-0}}</ref><ref>{{Literatur |Autor=Cesary Janikow, Zbigniew Michalewicz |Titel=An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms |Sammelwerk=Conf. Proc of the Fourth Int. Conf. on Genetic Algorithms (ICGA'91) |Datum=1991 |Seiten=31-36 |Online=http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |Format=PDF |KBytes=}}</ref> arbeiten mit [[Reelle Zahl|reellen Zahlen]] anstelle von Bitstrings. Dies liegt in den guten Erfahrungen begründet, die mit dieser Codierungsart gemacht wurden<ref name=":1">{{Literatur |Autor=Zbigniew Michalewicz |Titel=Genetic Algorithms + Data Structures = Evolution Programs |Auflage=Third, revised and Extended edition |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=1996 |ISBN=3-662-03315-1}}</ref><ref>{{Literatur |Autor=F. Herrera, M. Lozano, J.L. Verdegay |Titel=Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis |Sammelwerk=Artificial Intelligence Review |Band=12 |Nummer=4 |Datum=1998 |Seiten=265–319 |DOI=10.1023/A:1006504901164}}</ref><ref name=":0" />.

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 [[Optimierungsproblem#Mathematische Definition und Begriffe|Entscheidungsvariablen]] des zu bearbeitenden Optimierungsproblems in der Regel begrenzt. Dementsprechend sind die Werte der zugehörigen Gene jeweils auf ein Werteintervall <math>[x_\text{min}, x_\text{max}]</math> [[Einschränkung|eingeschränkt]]. Mutationen können diese Restriktionen berücksichtigen oder nicht. Im letzten Fall ist dann eine geeignete [[Genotypische und phänotypische Reparatur|Nachbehandlung]] erforderlich.

=== Mutation ohne Berücksichtigung von Restriktionen ===
[[Datei:Standard deviation diagram (decimal comma).svg|mini|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 <math>x</math> kann mittels der [[Normalverteilung]] <math>N(0,\sigma)</math> mutiert werden, wobei eine normalverteilte Zufallszahl bei dieser Verteilung bekanntlich mit rund 99,7 % Wahrscheinlichkeit im Intervall <math>\left[ -3 \cdot \sigma, +3 \cdot \sigma \right]</math> liegt. Der mutierte Wert <math>x'</math> ergibt sich dann folgendermaßen:<ref name=":3" />

:<math>x' = x + N(0; \sigma)</math>

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

:<math>\sigma = \frac{x_\text{max} - x_\text{min}}{6}</math>

Natürlich kann auch stattdessen vom kleineren Intervall zwischen dem aktuellen Wert von <math>x</math> 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 <math>x'</math> 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 [[Genom (evolutionärer Algorithmus)#Genome für Koevolution|Bestandteil des Chromosoms]] und unterliegen zusammen mit den eigentlichen Entscheidungsvariablen der Evolution.<ref>{{Literatur |Autor=Hans-Paul Schwefel |Titel=Evolution and Optimum Seeking |Auflage=1. print |Verlag=Wiley |Ort=New York |Datum=1995 |Reihe=Sixth-generation computer technology series |ISBN=978-0-471-57148-3 |Kapitel=Evolution Strategies for Numerical Optimization |Seiten=105-151 |Online=https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking}}</ref><ref>{{Literatur |Autor=Hans-Paul Schwefel, Günter Rudolph |Titel=Contemporary Evolution Strategies |Hrsg=F.Morán, A.Moreno, J.J.Merelo, P.Chacón |Sammelwerk=Proceedings of the Third European Conference on Advances in Artificial Life (ECAL'95) |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=1995 |ISBN=978-3-540-59496-3 |Seiten=893-907 |Online=https://www.researchgate.net/publication/221531222_Contemporary_Evolution_Strategies}}</ref>

=== Mutation mit Berücksichtigung von Restriktionen ===
[[Datei:Mutation Relative Parameteränderung Teilansicht.png|mini|Verteilung der Wahrscheinlichkeiten der <math>k=10</math> 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 <math>[x_\text{min}, x_\text{max}]</math> ist die Mutation „relative Parameteränderung“ des evolutionären Algorithmus GLEAM (General Learning Evolutionary Algorithm and Method),<ref name=":0">{{Literatur |Autor=Christian Blume, Wilfried Jakob |Titel=GLEAM - General Learning Evolutionary Algorithm and Method : ein Evolutionärer Algorithmus und seine Anwendungen |Verlag=KIT Scientific Publishing |Datum=2009 |DOI=10.5445/ksp/1000013553}}</ref><ref>{{Literatur |Autor=Christian Blume, Wilfried Jakob |Titel=GLEAM - An Evolutionary Algorithm for Planning and Control Based on Evolution Strategy |Sammelwerk=Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) |Band=vol. Late Breaking Papers |Datum=2002 |Seiten=31-38 |Online=https://publikationen.bibliothek.kit.edu/170053025/3814288}}</ref> bei der wie bei der zuvor vorgestellten Mutation kleine Veränderungen wahrscheinlicher sind als große.

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

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

Anschließend wird gleichverteilt eines der <math>k</math> Teiländerungsintervalle ausgewählt und daraus eine ebenfalls gleichverteilte Zufallszahl als neuer Wert <math>x'</math> für das Gen gezogen. Die sich daraus ergebenden summierten Wahrscheinlichkeiten der <math>k</math> Teiländerungsintervalle ergeben die im Bild dargestellte Verteilung für <math>k=10</math> Teilbereiche. Dies ist zwar keine Normalverteilung wie zuvor, aber auch diese Verteilung bevorzugt deutlich kleine Änderungen vor größeren.
[[Datei:Mutation Relative Parameteränderung gesamter Wertebereich.png|mini|Verteilung der Wahrscheinlichkeiten für die beispielhafte Änderung des aktuellen Wertes x eines Gens bei jeweils <math>k=10</math> Teilbereiche.]]
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-ganzzahlige Optimierung|gemischt-ganzzahligen Optimierungsproblemen]] wird üblicherweise gerundet.

== Mutation von Permutationen ==
Die Mutation von Permutationen ist spezielle für [[Genom (evolutionärer Algorithmus)|Genome]] ausgelegt, die selbst [[Permutation]]en einer [[Menge (Mathematik)|Menge]] sind. Dabei werden Teile des Genoms verschoben, neu gemischt oder gespiegelt.<ref name=":1" /><ref name=":2">{{Literatur |Autor=Xinjie Yu, Mitsuo Gen |Titel=Introduction to Evolutionary Algorithms |Reihe=Decision Engineering |Verlag=Springer |Ort=London |Datum=2010 |ISBN=978-1-84996-128-8 |Kapitel=Mutation Operators |Seiten=286–288 |DOI=10.1007/978-1-84996-129-5}}</ref>

=== Rotation nach rechts ===
Eine Variante von Mutation von Permutationen ist folgendes Verfahren, siehe auch <ref name=":2" />:
{|
|''Verfahren'' ||''Beispiel''
|-
| Gegeben ist eine Permutation,
|| <math>P_0 = \left( A,B,C,D,E,F,G \right)</math>
|-
| * Wähle eine Teil-Liste aus, also einen Start-Index <math>i</math> und einen End-Index <math>j</math> in <math>P_0</math>, die beide natürliche Zahlen zwischen 0 und <math>\left|P_0\right|-1</math> sind. Wähle die Anzahl der Positionen <math>k</math> aus, um die die Teil-Liste rotiert werden soll, wobei gilt <math>0 < k < |P_0|</math>. 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.
|| <math>i = 5</math>, <math>j = 1</math>, <math>k = 1</math>
|-
| * Kopiere <math>P_0</math> nach <math>P_1</math> und rotiere die Teil-Liste um <math>k</math> Positionen nach rechts.
|| <math>P_1 = \left( \underline {G,A{,}}C,D,E,\underline {B,F} \right)</math>
|-
| * <math>P_1</math> ist dann das mutierte Genom.
|| <math>P_1 = \left( G,A,C,D,E,B,F \right)</math>
|}

=== Spiegelung ===
Eine weitere Variante von Mutation von Permutationen ist folgendes Verfahren:<ref name=":4" details="Mutation for Permutation Representation, S. 69–70" />
{|
|''Verfahren'' ||''Beispiel''
|-
| * Gegeben ist eine Permutation,
|| <math>P_0 = \left( A,B,C,D,E,F,G \right)</math>
|-
| * Wähle eine Teil-Liste aus, also einen Start-Index <math>i</math> und einen End-Index <math>j</math> in <math>P_0</math>, die beide natürliche Zahlen zwischen 0 und <math>\left|P_0\right|-1</math> sind und <math>i \ne j</math> 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.
|| <math>i = 5</math>, <math>j = 1</math>
|-
| * Kopiere <math>P_0</math> nach <math>P_1</math> und spiegele die Teil-Liste.
|| <math>P_1 = \left( \underline {G,F{,}}C,D,E,\underline {B,A} \right)</math>
|-
| * <math>P_1</math> ist dann das mutierte Genom.
|| <math>P_1 = \left( G,F,C,D,E,B,A \right)</math>
|}

=== 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 <math>j</math> der Teillisten wird als Distanz <math>d</math> zum Startindex <math>i</math> bestimmt:
:<math>j = (i+ d) \bmod \left|P_0\right|</math>
wobei <math>d</math> zufällig nach einem der beiden Verfahren für die Mutation reeller Zahlen aus dem Intervall <math>\left[0, \left|P_0\right| - 1\right]</math> bestimmt wird. Legt man die Mutation ohne Berücksichtigung von Restriktionen zu Grunde, so kann das <math>\sigma</math> 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 <math>d</math> auf ganze Zahlen zu runden.

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

Bei der Spiegelung ist zu beachten, dass <math>i \ne j</math> sein muss, also ist für <math>d</math> der Wert <math>0</math> auszuschließen.

Diese Varianten sind z.&nbsp;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.
* {{Literatur
   |Autor=A.E. Eiben, J.E. Smith
   |Titel=Introduction to Evolutionary Computing
   |Reihe=Natural Computing Series
   |Verlag=Springer
   |Ort=Berlin, Heidelberg
   |Datum=2015
   |ISBN=978-3-662-44873-1
   |DOI=10.1007/978-3-662-44874-8}}
* [[Hans-Paul Schwefel]]: ''[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking 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 ==
<references>
</references>

[[Kategorie:Evolutionärer Algorithmus]]