Mutation (evolutionary algorithm)

In an evolutionary algorithm (EA), mutation is the random change in a genome . She is the implementation of the biological mutation for EA. Such an assignment of an old genome (and possibly random numbers ) to a new genome is a function and is called a mutation function . Every mutation function is a genetic operator .

A mutation should ideally only cause small changes, but in total enough that the individuals cover almost the entire value landscape over the duration of an evolutionary algorithm on which optimization is to be carried out. At the beginning of running a EA it is therefore permit cheaper, larger, increasing in advanced stage only small changes should be allowed to individuals who are already close to an optimum , not stir are from this optimum.

An evolutionary algorithm with a global mutation rate (proportion of the total population subjected to the mutation) of 0 will give very poor results, since alleles once dropped from the population by cross functions can never return to the population and thus, if they are part of the Building blocks of the globally optimal solution were missing to find this. If, on the other hand, the mutation rate is too high, individuals close to the optimum are pushed away from it again and the algorithm cannot converge.

If cross functions or problem representations are used that are not well suited to the problem, unwanted mutations can occur in the cross. At some points on the chromosome, an expression of the allele develops that cannot be traced back to any of the parent individuals, even before the actual mutation step takes place.

Different mutation types are differently suitable for different genome types:

Mutation of binary numbers (bit strings)

Bit strings are mutated by bit flips at random positions.

Example:

1	0	1	0	0	1	0
				↓
1	0	1	0	1	1	0

The probability of a bit being mutated is , where is the length of the binary vector. As a result, a mutation rate of 1 per mutation and the individual selected for mutation is achieved on average ( see above , global mutation rate). ${\displaystyle 1/l}$ ${\displaystyle l}$

Preference for the lower-order bits

A variant of the mutation of binary numbers is the following procedure:

• Choose a digit of the binary number , whereby the lower significant digits are selected with an exponentially higher probability than the higher significant ones. ${\displaystyle i}$ ${\displaystyle Z_{0}}$
• Invert the bit at this point of the binary number to: . ${\displaystyle Z_{1}=Z_{0}XOR2^{i}}$
• The new number created in this way is the mutated genome. ${\displaystyle Z_{1}}$

An example to illustrate - a mutation of an 8-bit number:

11001100 - the number before the mutation

11000100 - afterwards (a mutation in the 4th position)

This procedure also works with floating point numbers if they are written as a number without exponent information (i.e. instead of ). ${\displaystyle 1100110000{,}00}$ ${\displaystyle 1{,}10011\cdot 2^{9}}$

A wrong choice of the mutation probabilities can lead to the fact that only lower-valued places are modified, so that the mutations ultimately have no significant influence on the individuals or the fitness-function value that is dependent on them .

Mutation of permutations

The mutation of permutations is specially designed for genomes that are themselves permutations of a set . Parts of the genome are shifted or mirrored.

Rotation to the right

A variant of mutation of permutations is the following procedure:

Procedure	example
A permutation is given,	${\displaystyle P_{0}=\left(A,B,C,D,E,F,G\right)}$
* Select a partial list, i.e. a start index and an end index in , which are both natural numbers between 0 and . The start index can also come after the end index. Then the part 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. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle P_{0}}$ ${\displaystyle \left|P_{0}\right|}$	${\displaystyle i=5}$, ${\displaystyle j=2}$
* Copy to and rotate the parts list to the right. ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$	${\displaystyle P_{1}=\left({\underline {G,A{,}}}C,D,E,{\underline {B,F}}\right)}$
* is then the mutated genome. ${\displaystyle P_{1}}$	${\displaystyle P_{1}=\left(G,A,C,D,E,B,F\right)}$

reflection

Another variant of mutation of permutations is the following procedure:

Procedure	example
* A permutation is given,	${\displaystyle P_{0}=\left(A,B,C,D,E,F,G\right)}$
* Select a partial list, i.e. a start index and an end index in , which are both natural numbers between 0 and . The start index can also come after the end index. Then the part 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. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle P_{0}}$ ${\displaystyle \left|P_{0}\right|}$	${\displaystyle i=5}$, ${\displaystyle j=2}$
* Copy to and reflected the partial list. ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$	${\displaystyle P_{1}=\left({\underline {G,F{,}}}C,D,E,{\underline {B,A}}\right)}$
* is then the mutated genome. ${\displaystyle P_{1}}$	${\displaystyle P_{1}=\left(G,F,C,D,E,B,A\right)}$

This variant is suitable for solving the problem of the traveling salesman , since the change in the neighborhood should be kept to a minimum here and the mirroring simply takes part of the route in the reverse order.