Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Mutation (evolutionary algorithm)
Type of genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next

Mutation is a genetic operator used to maintain genetic diversity of the chromosomes of a population of an evolutionary algorithm (EA), including genetic algorithms in particular. It is analogous to biological mutation.

The classic example of a mutation operator of a binary coded genetic algorithm (GA) involves a probability that an arbitrary bit in a genetic sequence will be flipped from its original state. A common method of implementing the mutation operator involves generating a random variable for each bit in a sequence. This random variable tells whether or not a particular bit will be flipped. This mutation procedure, based on the biological point mutation, is called single point mutation. Other types of mutation operators are commonly used for representations other than binary, such as floating-point encodings or representations for combinatorial problems.

The purpose of mutation in EAs is to introduce diversity into the sampled population. Mutation operators are used in an attempt to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping convergence to the global optimum. This reasoning also leads most EAs to avoid only taking the fittest of the population in generating the next generation, but rather selecting a random (or semi-random) set with a weighting toward those that are fitter.

The following requirements apply to all mutation operators used in an EA:

  1. every point in the search space must be reachable by one or more mutations.
  2. there must be no preference for parts or directions in the search space (no drift).
  3. small mutations should be more probable than large ones.

For different genome types, different mutation types are suitable. Some mutations are Gaussian, Uniform, Zigzag, Scramble, Insertion, Inversion, Swap, and so on. An overview and more operators than those presented below can be found in the introductory book by Eiben and Smith or in.

Related Image Collections Add Image
We don't have any YouTube videos related to Mutation (evolutionary algorithm) yet.
We don't have any PDF documents related to Mutation (evolutionary algorithm) yet.
We don't have any Books related to Mutation (evolutionary algorithm) yet.
We don't have any archived web articles related to Mutation (evolutionary algorithm) yet.

Bit string mutation

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

Example:

1010010
1010110

The probability of a mutation of a bit is 1 l {\displaystyle {\frac {1}{l}}} , where l {\displaystyle l} is the length of the binary vector.10 Thus, a mutation rate of 1 {\displaystyle 1} per mutation and individual selected for mutation is reached.

Mutation of real numbers

Many EAs, such as the evolution strategy1112 or the real-coded genetic algorithms,131415 work with real numbers instead of bit strings. This is due to the good experiences that have been made with this type of coding.1617

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 min , x max ] {\displaystyle [x_{\min },x_{\max }]} . 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

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

x ′ = x + N ( 0 , σ ) {\displaystyle x'=x+{\mathcal {N}}(0,\sigma )}

In the case of genes with a restricted range of values, it is a good idea to choose the step size of the mutation σ {\displaystyle \sigma } so that it reasonably fits the range [ x min , x max ] {\displaystyle [x_{\min },x_{\max }]} of the gene to be changed, e.g.:

σ = x max − x min 6 {\displaystyle \sigma ={\frac {x_{\text{max}}-x_{\text{min}}}{6}}}

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 x ′ {\displaystyle x'} 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 and are subject to evolution together with the actual decision variables.1819

Mutation with consideration of restrictions

One possible form of changing the value of a gene while taking its value range [ x min , x max ] {\displaystyle [x_{\min },x_{\max }]} into account is the mutation relative parameter change of the evolutionary algorithm GLEAM (General Learning Evolutionary Algorithm and Method),20 in which, as with the mutation presented earlier, small changes are more likely than large ones.

First, an equally distributed decision is made as to whether the current value x {\displaystyle 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 max ] {\displaystyle [x,x_{\max }]} . It is divided into k {\displaystyle k} sub-areas of equal size with the width δ {\displaystyle \delta } , from which k {\displaystyle k} sub-change intervals of different size are formed:

i {\displaystyle i} -th sub-change interval: [ x , x + δ ⋅ i ] {\displaystyle [x,x+\delta \cdot i]} with δ = ( x max − x ) k {\displaystyle \delta ={\frac {(x_{\text{max}}-x)}{k}}} and i = 1 , … , k {\displaystyle i=1,\dots ,k}

Subsequently, one of the k {\displaystyle 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 ′ {\displaystyle x'} of the gene. The resulting summed probabilities of the sub-change intervals result in the probability distribution of the k {\displaystyle k} sub-areas shown in the adjacent figure for the exemplary case of k = 10 {\displaystyle 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 {\displaystyle 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 {\displaystyle k} 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 optimization problems, rounding is usually used.

Mutation of permutations

Mutations of permutations are specially designed for genomes that are themselves permutations of a set. These are often used to solve combinatorial tasks.212223 In the two mutations presented, parts of the genome are rotated or inverted.

Rotation to the right

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

Procedure  Example
* Let a permutation be given.   P 0 = ( A , B , C , D , E , F , G ) {\displaystyle P_{0}=\left(A,B,C,D,E,F,G\right)}
* Select a partial list, i.e. a start index i {\displaystyle i} and an end index j {\displaystyle j} in P 0 {\displaystyle P_{0}} , which are both natural numbers between 0 and | P 0 | − 1 {\displaystyle \left|P_{0}\right|-1} . Choose the number of positions k {\displaystyle k} by which the partial list should be rotated, where 0 < k < | P 0 | {\displaystyle 0<k<|P_{0}|} . The start index can also be after the end index. Then the partial list simply starts again from the beginning (periodic boundary condition). This is necessary so that the permutation probability in the genome is the same everywhere and is not greater in the middle than at the edges.   i = 5 {\displaystyle i=5} , j = 1 {\displaystyle j=1} , k = 1 {\displaystyle k=1}
* Copy P 0 {\displaystyle P_{0}} to P 1 {\displaystyle P_{1}} and rotate the partial list by k {\displaystyle k} positions to the right.   P 1 = ( G , A _ , C , D , E , B , F _ ) {\displaystyle P_{1}=\left({\underline {G,A}},C,D,E,{\underline {B,F}}\right)}
* P 1 {\displaystyle P_{1}} is then the mutated genome.   P 1 = ( G , A , C , D , E , B , F ) {\displaystyle P_{1}=\left(G,A,C,D,E,B,F\right)}

Inversion

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

Procedure  Example
* Let a permutation be given.   P 0 = ( A , B , C , D , E , F , G ) {\displaystyle P_{0}=\left(A,B,C,D,E,F,G\right)}
* Select a partial list, i.e. a start index i {\displaystyle i} and an end index j {\displaystyle j} in P 0 {\displaystyle P_{0}} , which are both natural numbers between 0 and | P 0 | − 1 {\displaystyle \left|P_{0}\right|-1} , where i ≠ j {\displaystyle i\neq j} . This condition causes the mutation to always produce a genotypically altered chromosome. The start index can also be after the end index. Then the partial list simply starts again from the beginning (periodic boundary condition). This is necessary so that the permutation probability in the genome is the same everywhere and is not greater in the middle than at the edges.   i = 5 {\displaystyle i=5} , j = 1 {\displaystyle j=1}
* Copy P 0 {\displaystyle P_{0}} to P 1 {\displaystyle P_{1}} and invert the partial list.   P 1 = ( G , F _ , C , D , E , B , A _ ) {\displaystyle P_{1}=\left({\underline {G,F}},C,D,E,{\underline {B,A}}\right)}
* P 1 {\displaystyle P_{1}} is then the mutated genome.   P 1 = ( G , F , C , D , E , B , A ) {\displaystyle P_{1}=\left(G,F,C,D,E,B,A\right)}

Variants with preference for smaller changes

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 {\displaystyle j} of the partial lists is determined as the distance d {\displaystyle d} to the start index i {\displaystyle i} :

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

where d {\displaystyle d} is determined randomly according to one of the two procedures for the mutation of real numbers from the interval [ 0 , | P 0 | − 1 ] {\displaystyle \left[0,\left|P_{0}\right|-1\right]} and rounded.

For the rotation, k {\displaystyle k} is determined similarly to the distance d {\displaystyle d} , but the value 0 {\displaystyle 0} is forbidden.

For the inversion, note that i ≠ j {\displaystyle i\neq j} must hold, so for d {\displaystyle d} the value 0 {\displaystyle 0} must be excluded.

See also

Bibliography

References

  1. "XI. Crossover and Mutation". Marek Obitko. Retrieved 2011-04-07. http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php

  2. Eiben, A.E.; Smith, J.E. (2015). "Variation Operators (Mutation and Recombination)". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 31–32. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932. 978-3-662-44873-1

  3. Bäck, Thomas; Fogel, David B.; Whitley, Darrell; Angeline, Peter J. (1999). "Mutation operators". In Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Evolutionary computation. Vol. 1, Basic algorithms and operators. Boca Racon: CRC Press. pp. 237–255. ISBN 0-585-30560-9. OCLC 45730387. 0-585-30560-9

  4. Mirjalili, Seyedali (2019), Mirjalili, Seyedali (ed.), "Genetic Algorithm", Evolutionary Algorithms and Neural Networks: Theory and Applications, Studies in Computational Intelligence, vol. 780, Cham: Springer International Publishing, pp. 43–55, doi:10.1007/978-3-319-93025-1_4, ISBN 978-3-319-93025-1, S2CID 242047607, retrieved 2023-05-26 978-3-319-93025-1

  5. Harifi, Sasan; Mohamaddoust, Reza (2023-05-01). "Zigzag mutation: a new mutation operator to improve the genetic algorithm". Multimedia Tools and Applications. 82 (29): 45411–45432. doi:10.1007/s11042-023-15518-3. ISSN 1573-7721. S2CID 258446829. https://doi.org/10.1007/s11042-023-15518-3

  6. Katoch, Sourabh; Chauhan, Sumit Singh; Kumar, Vijay (2021-02-01). "A review on genetic algorithm: past, present, and future". Multimedia Tools and Applications. 80 (5): 8091–8126. doi:10.1007/s11042-020-10139-6. ISSN 1573-7721. PMC 7599983. PMID 33162782. https://doi.org/10.1007/s11042-020-10139-6

  7. Eiben, A.E.; Smith, J.E. (2015). "Representation, Mutation, and Recombination". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 49–78. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932. 978-3-662-44873-1

  8. Bäck, Thomas; Fogel, David B.; Whitley, Darrell; Angeline, Peter J. (1999). "Mutation operators". In Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Evolutionary computation. Vol. 1, Basic algorithms and operators. Boca Racon: CRC Press. pp. 237–255. ISBN 0-585-30560-9. OCLC 45730387. 0-585-30560-9

  9. Michalewicz, Zbigniew (1992). Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. S2CID 33272042. 978-3-662-02832-2

  10. Eshelman, Larry J. (1999). "Mutation and Crossover". In Bäck, Thomas; Fogel, David B.; Michalewicz, Zbigniew (eds.). Evolutionary computation. Vol. 1, Basic algorithms and operators. Boca Racon: CRC Press. p. 68. ISBN 0-585-30560-9. OCLC 45730387. 0-585-30560-9

  11. Rechenberg, Ingo (1973). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis) (in German). Frommann-Holzboog. ISBN 3-7728-0373-3. 3-7728-0373-3

  12. Schwefel, Hans-Paul (1977). Numerische Optimierung von Computermodellen (PhD thesis) (in German). Basel: Birkhäuser Verlag. Translation: Numerical optimization of computer models, Wiley, Chichester, 1981. ISBN 0-471-09988-0. OCLC 8011455. 0-471-09988-0

  13. Wright, Alden H. (1991), Rawlins, Gregory J. E. (ed.), Genetic Algorithms for Real Parameter Optimization, Foundations of Genetic Algorithms, vol. 1, Elsevier, pp. 205–218, doi:10.1016/b978-0-08-050684-5.50016-1, ISBN 9780080506845, retrieved 2023-01-02 9780080506845

  14. Eshelman, Larry J.; Schaffer, J. David (1993), "Real-Coded Genetic Algorithms and Interval-Schemata", Foundations of Genetic Algorithms, vol. 2, Elsevier, pp. 187–202, doi:10.1016/b978-0-08-094832-4.50018-0, ISBN 978-0-08-094832-4, retrieved 2023-01-01 978-0-08-094832-4

  15. Michalewicz, Zbigniew (1992). Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. S2CID 33272042. 978-3-662-02832-2

  16. Michalewicz, Zbigniew (1992). Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. S2CID 33272042. 978-3-662-02832-2

  17. Herrera, F.; Lozano, M.; Verdegay, J.L. (1998). "Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis". Artificial Intelligence Review. 12 (4): 265–319. doi:10.1023/A:1006504901164. S2CID 6798965. http://link.springer.com/10.1023/A:1006504901164

  18. Schwefel, Hans-Paul (1995). "Evolution Strategies for Numerical Optimization". Evolution and optimum seeking. Sixth-generation computer technology series. New York: Wiley. pp. 105–151. ISBN 978-0-471-57148-3. 978-0-471-57148-3

  19. Schwefel, Hans-Paul; Rudolph, Günter (1995), Morán, F.; Moreno, A.; Merelo, J.J.; Chacón, P. (eds.), "Contemporary Evolution Strategies", Conf. Proc. of the Third European Conference on Artificial Life (ECAL'95), Berlin, New York: Springer, pp. 893–907, ISBN 978-3-540-59496-3 978-3-540-59496-3

  20. Blume, Christian; Jakob, Wilfried (2002), "GLEAM - An Evolutionary Algorithm for Planning and Control Based on Evolution Strategy", Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002), vol. Late Breaking Papers, pp. 31–38, retrieved 2023-01-01 https://publikationen.bibliothek.kit.edu/170053025/3814288

  21. Michalewicz, Zbigniew (1992). Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. S2CID 33272042. 978-3-662-02832-2

  22. Eiben, A.E.; Smith, J.E. (2015). "Mutation for Permutation Representation". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 69–70. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932. 978-3-662-44873-1

  23. Yu, Xinjie; Gen, Mitsuo (2010). "Mutation Operators". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 286–288. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8. 978-1-84996-128-8

  24. Yu, Xinjie; Gen, Mitsuo (2010). "Mutation Operators". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 286–288. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8. 978-1-84996-128-8

  25. Eiben, A.E.; Smith, J.E. (2015). "Mutation for Permutation Representation". Introduction to Evolutionary Computing. Natural Computing Series. Berlin, Heidelberg: Springer. pp. 69–70. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID 20912932. 978-3-662-44873-1