Editing Mutation (evolutionary algorithm) (section)

== Mutation of real numbers ==
Many EAs, such as the [[evolution strategy]]<ref>{{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}}</ref><ref>{{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}}</ref> or the real-coded [[Genetic algorithm|genetic algorithms]],<ref>{{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 }}</ref><ref>{{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 }}</ref><ref name=":0" /> work with real numbers instead of bit strings. This is due to the good experiences that have been made with this type of coding.<ref name=":0" /><ref>{{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 }}</ref>

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 [[Restriction (mathematics)|restricted]] to an interval <math>[x_{\min}, x_{\max}]</math>. Mutations may or may not take these restrictions into account. In the latter case, suitable post-treatment is then required as described below.

=== Mutation without consideration of restrictions ===
[[File:Standard deviation diagram (decimal comma).svg|thumb|Example of a normally distributed random variable. Note that the given proportions of the subranges add up to 99.8 % and not 100 % due to rounding.]]
A real number <math>x</math> can be mutated using [[normal distribution]] <math>\mathcal{N}(0,\sigma)</math> by adding the generated random value to the old value of the gene, resulting in the mutated value <math>x'</math>:<blockquote><math>x' = x + \mathcal{N}(0, \sigma)</math></blockquote>In the case of genes with a restricted range of values, it is a good idea to choose the step size of the mutation <math>\sigma</math> so that it reasonably fits the range <math>[x_{\min}, x_{\max}]</math> of the gene to be changed, e.g.:<blockquote><math>\sigma = \frac{x_\text{max} - x_\text{min}}{6}</math></blockquote>The step size can also be adjusted to the smaller permissible change range depending on the current value. In any case, however, it is likely that the new value <math>x'</math> of the gene will be outside the permissible range of values. Such a case must be considered a lethal mutation, since the obvious repair by using the respective violated limit as the new value of the gene would lead to a drift. This is because the limit value would then be selected with the entire probability of the values beyond the limit of the value range. 

The evolution strategy works with real numbers and mutation based on normal distribution. The step sizes are part of the [[Chromosome (genetic algorithm)|chromosome]] and are subject to evolution together with the actual decision variables.<ref>{{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}}</ref><ref>{{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.}}</ref>

=== Mutation with consideration of restrictions ===
One possible form of changing the value of a gene while taking its value range <math>[x_{\min}, x_{\max}]</math> into account is the mutation ''relative parameter change'' of the evolutionary algorithm GLEAM (General Learning Evolutionary Algorithm and Method),<ref>{{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 }}</ref> 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|thumb|264x264px|Distribution of probabilities for k=10 sub-areas of the total change interval. The sub-areas each cover 1/k of the width of the total change interval.]]
First, an equally distributed decision is made as to whether the current value <math>x</math> 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 <math>[x, x_\max]</math>. It is divided into <math>k</math> sub-areas of equal size with the width <math>\delta</math>, from which <math>k</math> sub-change intervals of different size are formed:
:<math>i</math>-th sub-change interval: <math>[x, x + \delta \cdot i]</math> with
:<math>\delta = \frac{(x_\text{max} - x)}{k}</math> and <math>i = 1, \dots, k</math>
Subsequently, one of the <math>k</math> sub-change intervals is selected in equal distribution and a random number, also equally distributed, is drawn from it as the new value <math>x'</math> of the gene. The resulting summed probabilities of the sub-change intervals result in the probability distribution of the <math>k</math> sub-areas shown in the adjacent figure for the exemplary case of <math>k=10</math>. 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 <math>k</math>, 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 <math>k</math> when a gene value approaches its limits very closely.

=== Common properties ===
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 programming|mixed-integer optimization]] problems, rounding is usually used.