Editing Mutation (evolutionary algorithm) (section)

== Mutation of permutations ==
Mutations of permutations are specially designed for genomes that are themselves [[Permutation|permutations]] of a [[Set (mathematics)|set]]. These are often used to solve combinatorial tasks.<ref name=":0" /><ref name=":1">{{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 }}</ref><ref name=":2">{{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}}</ref> In the two mutations presented, parts of the genome are rotated or inverted.

=== Rotation to the right ===
The presentation of the procedure<ref name=":2" /> is illustrated by an example on the right:
{|
|''Procedure'' 
| &nbsp;&nbsp;
| ''Example''
|-
| * Let a permutation be given.
| &nbsp;&nbsp;
| <math>P_0 = \left( A,B,C,D,E,F,G \right)</math>
|-
| * Select a partial list, i.e. a start index <math>i</math> and an end index <math>j</math> in <math>P_0</math>, which are both natural numbers between 0 and <math>\left|P_0\right|-1</math>. Choose the number of positions <math>k</math> by which the partial list should be rotated, where <math>0 < k < |P_0|</math>. The start index can also be after the end index.  Then the partial list simply starts again from the beginning ([[Periodic boundary conditions|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.
| &nbsp;&nbsp;
| <math>i = 5</math>, <math>j = 1</math>, <math>k = 1</math>
|-
| * Copy <math>P_0</math> to <math>P_1</math> and rotate the partial list by <math>k</math> positions to the right.
| &nbsp;&nbsp;
| <math>P_1 = \left( \underline {G,A},C,D,E,\underline {B,F} \right)</math>
|-
| * <math>P_1</math> is then the mutated genome.
| &nbsp;&nbsp;
| <math>P_1 = \left( G,A,C,D,E,B,F \right)</math>
|}

=== Inversion ===
The presentation of the procedure<ref name=":1" /> is illustrated by an example on the right:
{|
|''Procedure'' 
| &nbsp;&nbsp;
|''Example''
|-
| * Let a permutation be given.
| &nbsp;&nbsp;
| <math>P_0 = \left( A,B,C,D,E,F,G \right)</math>
|-
| * Select a partial list, i.e. a start index <math>i</math> and an end index <math>j</math> in <math>P_0</math>, which are both natural numbers between 0 and <math>\left|P_0\right|-1</math>, where <math>i \ne j</math>. 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 conditions|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.
| &nbsp;&nbsp;
| <math>i = 5</math>, <math>j = 1</math>
|-
| * Copy <math>P_0</math> to <math>P_1</math> and invert the partial list.
| &nbsp;&nbsp;
| <math>P_1 = \left( \underline {G,F},C,D,E,\underline {B,A} \right)</math>
|-
| * <math>P_1</math> is then the mutated genome.
| &nbsp;&nbsp;
| <math>P_1 = \left( G,F,C,D,E,B,A \right)</math>
|}

=== 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 <math>j</math> of the partial lists is determined as the distance <math>d</math> to the start index <math>i</math>:
:<math>j = (i+ d) \bmod \left|P_0\right|</math>
where <math>d</math> is determined randomly according to one of the two procedures for the mutation of real numbers from the interval <math>\left[0, \left|P_0\right| - 1\right]</math> and rounded.

For the ''rotation'', <math>k</math> is determined similarly to the distance <math>d</math>, but the value <math>0</math> is forbidden.

For the ''inversion'', note that <math>i \ne j</math> must hold, so for <math>d</math> the value <math>0</math> must be excluded.