Mutation (evolutionary algorithm)

The mutation of bit strings ensue through bit flips at random positions.

Example:

The probability of a mutation of a bit is $\backslash frac\{1\}\{l\}$, where $l$ is the length of the binary vector.{{Cite book |last1=Eshelman |first1=Larry J. |url=https://www.worldcat.org/oclc/45730387 |title=Evolutionary computation. Vol. 1, Basic algorithms and operators |publisher=CRC Press |year=1999 |isbn=0-585-30560-9 |editor-last=Bäck |editor-first=Thomas |location=Boca Racon |pages=68 |language=en |chapter=Mutation and Crossover |oclc=45730387 |editor-last2=Fogel |editor-first2=David B. |editor-last3=Michalewicz |editor-first3=Zbigniew}} Thus, a mutation rate of $1$ per mutation and individual selected for mutation is reached.

Many EAs, such as the evolution strategy{{Cite book |last=Rechenberg |first=Ingo |title=Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution |publisher=Frommann-Holzboog |year=1973 |isbn=3-7728-0373-3 |language=de |type=PhD thesis}}{{Cite book |last=Schwefel |first=Hans-Paul |title=Numerische Optimierung von Computermodellen |date=1977 |publisher=Birkhäuser Verlag. Translation: Numerical optimization of computer models, Wiley, Chichester, 1981 |isbn=0-471-09988-0 |location=Basel |language=de |trans-chapter= |type=PhD thesis |oclc=8011455}} or the real-coded genetic algorithms,{{Citation |last=Wright |first=Alden H. |title=Genetic Algorithms for Real Parameter Optimization |date=1991 |url=https://www.sciencedirect.com/science/article/pii/B9780080506845500161 |series=Foundations of Genetic Algorithms |volume=1 |pages=205–218 |editor-last=Rawlins |editor-first=Gregory J. E. |publisher=Elsevier |language=en |doi=10.1016/b978-0-08-050684-5.50016-1 |isbn=9780080506845 |access-date=2023-01-02|url-access=subscription }}{{Citation |last1=Eshelman |first1=Larry J. |title=Real-Coded Genetic Algorithms and Interval-Schemata |date=1993 |url=https://linkinghub.elsevier.com/retrieve/pii/B9780080948324500180 |work=Foundations of Genetic Algorithms |volume=2 |pages=187–202 |publisher=Elsevier |language=en |doi=10.1016/b978-0-08-094832-4.50018-0 |isbn=978-0-08-094832-4 |access-date=2023-01-01 |last2=Schaffer |first2=J. David|url-access=subscription }} work with real numbers instead of bit strings. This is due to the good experiences that have been made with this type of coding.{{Cite journal |last1=Herrera |first1=F. |last2=Lozano |first2=M. |last3=Verdegay |first3=J.L. |date=1998 |title=Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis. |url=http://link.springer.com/10.1023/A:1006504901164 |journal=Artificial Intelligence Review |volume=12 |issue=4 |pages=265–319 |doi=10.1023/A:1006504901164|s2cid=6798965 |url-access=subscription }}

The value of a real-valued gene can either be changed or redetermined. A mutation that implements the latter should only ever be used in conjunction with the value-changing mutations and then only with comparatively low probability, as it can lead to large changes.

In practical applications, the respective value range of the decision variables to be changed of the optimisation problem to be solved is usually limited. Accordingly, the values of the associated genes are each restricted to an interval $[x\_\{\backslash min\},\; x\_\{\backslash max\}]$. Mutations may or may not take these restrictions into account. In the latter case, suitable post-treatment is then required as described below.

File:Standard deviation diagram (decimal comma).svg

A real number $x$ can be mutated using normal distribution $\backslash mathcal\{N\}(0,\backslash sigma)$ by adding the generated random value to the old value of the gene, resulting in the mutated value $x\text{'}$:

$x\text{'}\; =\; x\; +\; \backslash mathcal\{N\}(0,\; \backslash sigma)$

$\backslash sigma\; =\; \backslash frac\{x\_\backslash text\{max\}\; -\; x\_\backslash text\{min\}\}\{6\}$

The evolution strategy works with real numbers and mutation based on normal distribution. The step sizes are part of the chromosome and are subject to evolution together with the actual decision variables.{{Cite book |last=Schwefel |first=Hans-Paul |url=https://www.researchgate.net/publication/220690578 |title=Evolution and optimum seeking |date=1995 |publisher=Wiley |isbn=978-0-471-57148-3 |series=Sixth-generation computer technology series |location=New York |pages=105–151 |language=en |chapter=Evolution Strategies for Numerical Optimization}}{{Citation |last1=Schwefel |first1=Hans-Paul |last2=Rudolph |first2=Günter |title=Contemporary Evolution Strategies |date=1995 |work=Conf. Proc. of the Third European Conference on Artificial Life (ECAL'95) |publisher=Springer |isbn=978-3-540-59496-3 |editor-last=Morán |editor-first=F. |location=Berlin, New York |pages=893–907 |url=https://www.researchgate.net/publication/221531222 |editor-last2=Moreno |editor-first2=A. |editor-last3=Merelo |editor-first3=J.J. |editor-last4=Chacón |editor-first4=P.}}

One possible form of changing the value of a gene while taking its value range $[x\_\{\backslash min\},\; x\_\{\backslash max\}]$ into account is the mutation relative parameter change of the evolutionary algorithm GLEAM (General Learning Evolutionary Algorithm and Method),{{Citation |last1=Blume |first1=Christian |last2=Jakob |first2=Wilfried |title=GLEAM - An Evolutionary Algorithm for Planning and Control Based on Evolution Strategy |date=2002 |url=https://publikationen.bibliothek.kit.edu/170053025/3814288 |work=Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) |volume=Late Breaking Papers |pages=31–38 |access-date=2023-01-01 }} in which, as with the mutation presented earlier, small changes are more likely than large ones.

File:Probabilty distribution of the muatation relative parameter change.png

First, an equally distributed decision is made as to whether the current value $x$ should be increased or decreased and then the corresponding total change interval is determined. Without loss of generality, an increase is assumed for the explanation and the total change interval is then $[x,\; x\_\backslash max]$. It is divided into $k$ sub-areas of equal size with the width $\backslash delta$, from which $k$ sub-change intervals of different size are formed:

:$i$-th sub-change interval: $[x,\; x\; +\; \backslash delta\; \backslash cdot\; i]$ with

:$\backslash delta\; =\; \backslash frac\{(x\_\backslash text\{max\}\; -\; x)\}\{k\}$ and $i\; =\; 1,\; \backslash dots,\; k$

Subsequently, one of the $k$ sub-change intervals is selected in equal distribution and a random number, also equally distributed, is drawn from it as the new value $x\text{'}$ of the gene. The resulting summed probabilities of the sub-change intervals result in the probability distribution of the $k$ sub-areas shown in the adjacent figure for the exemplary case of $k=10$. This is not a normal distribution as before, but this distribution also clearly favours small changes over larger ones.

This mutation for larger values of $k$, such as 10, is less well suited for tasks where the optimum lies on one of the value range boundaries. This can be remedied by significantly reducing $k$ when a gene value approaches its limits very closely.

For both mutation operators for real-valued numbers, the probability of an increase and decrease is independent of the current value and is 50% in each case. In addition, small changes are considerably more likely than large ones. For mixed-integer optimization problems, rounding is usually used.

Mutations of permutations are specially designed for genomes that are themselves permutations of a set. These are often used to solve combinatorial tasks.{{Cite book |last1=Eiben |first1=A.E. |url=https://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |series=Natural Computing Series |location=Berlin, Heidelberg |pages=69–70 |language=en |chapter=Mutation for Permutation Representation |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}{{Cite book |last1=Yu |first1=Xinjie |url=http://link.springer.com/10.1007/978-1-84996-129-5 |title=Introduction to Evolutionary Algorithms |last2=Gen |first2=Mitsuo |date=2010 |publisher=Springer |isbn=978-1-84996-128-8 |series=Decision Engineering |volume= |location=London |pages=286–288 |language=en |chapter=Mutation Operators |doi=10.1007/978-1-84996-129-5}} In the two mutations presented, parts of the genome are rotated or inverted.

The presentation of the procedure is illustrated by an example on the right:

The presentation of the procedure is illustrated by an example on the right:

The requirement raised at the beginning for mutations, according to which small changes should be more probable than large ones, is only inadequately fulfilled by the two permutation mutations presented, since the lengths of the partial lists and the number of shift positions are determined in an equally distributed manner. However, the longer the partial list and the shift, the greater the change in gene order.

This can be remedied by the following modifications. The end index $j$ of the partial lists is determined as the distance $d$ to the start index $i$:

:$j\; =\; (i+\; d)\; \backslash bmod\; \backslash left|P\_0\backslash right|$

where $d$ is determined randomly according to one of the two procedures for the mutation of real numbers from the interval $\backslash left[0,\; \backslash left|P\_0\backslash right|\; -\; 1\backslash right]$ and rounded.

For the rotation, $k$ is determined similarly to the distance $d$, but the value $0$ is forbidden.

For the inversion, note that $i\; \backslash ne\; j$ must hold, so for $d$ the value $0$ must be excluded.

• Evolutionary algorithms
• Genetic algorithms
• Evolution strategy
• Genetic programming
• Evolutionary programming

{{Reflist}}

• John Holland (1975). Adaptation in Natural and Artificial Systems, PhD thesis, University of Michigan Press, Ann Arbor, Michigan. {{ISBN|0-262-58111-6}}.
• {{Cite book |last=Schwefel |first=Hans-Paul |title=Evolution and Optimum Seeking |publisher=John Wiley & Sons |year=1995 |isbn=0-471-57148-2 |location=New York |language=en |url=https://www.researchgate.net/publication/220690578}}
• {{Cite book |last=Davis |first=Lawrence |title=Handbook of genetic algorithms |date=1991 |publisher=Van Nostrand Reinhold |isbn=0-442-00173-8 |location=New York |oclc=23081440}}
• {{Cite book |last1=Eiben |first1=A.E. |url=https://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |series=Natural Computing Series |location=Berlin, Heidelberg |language=en |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}
• {{Cite book |last1=Yu |first1=Xinjie |url=http://link.springer.com/10.1007/978-1-84996-129-5 |title=Introduction to Evolutionary Algorithms |last2=Gen |first2=Mitsuo |date=2010 |publisher=Springer |isbn=978-1-84996-128-8 |series=Decision Engineering |volume= |location=London |language=en |doi=10.1007/978-1-84996-129-5}}
• {{Cite book |last=De Jong |first=Kenneth A. |title=Evolutionary computation : a unified approach |date=2006 |publisher=MIT Press |isbn=978-0-262-25598-1 |location=Cambridge, Mass. |language=en |oclc=69652176}}
• {{Cite book |url=https://www.worldcat.org/oclc/45730387 |title=Evolutionary computation. Vol. 1, Basic algorithms and operators |date=1999 |publisher=Institute of Physics Pub |isbn=0-585-30560-9 |editor-last=Fogel |editor-first=David B. |location=Bristol |oclc=45730387 |editor-last2=Bäck |editor-first2=Thomas |editor-last3=Michalewicz |editor-first3=Zbigniew}}

{{DEFAULTSORT:Mutation (Genetic Algorithm)}}

{{Evolutionary computation}}

+