Mutation (evolutionary algorithm)
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.
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.
Some mutations are Gaussian, Uniform, Zigzag, Scramble, Insertion, Inversion, Swap, and so on.
[4][5][6] An overview and more operators than those presented below can be found in the introductory book by Eiben and Smith[7] or in.
Many EAs, such as the evolution strategy[10][11] or the real-coded genetic algorithms,[12][13][8] work with real numbers instead of bit strings.
This is due to the good experiences that have been made with this type of coding.
[8][14] The value of a real-valued gene can either be changed or redetermined.
In practical applications, the respective value range of the decision variables to be changed of the optimisation problem to be solved is usually limited.
In the case of genes with a restricted range of values, it is a good idea to choose the step size of the mutation
The step size can also be adjusted to the smaller permissible change range depending on the current value.
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.
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.
into account is the mutation relative parameter change of the evolutionary algorithm GLEAM (General Learning Evolutionary Algorithm and Method),[17] 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
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
sub-change intervals of different size are formed: Subsequently, one of the
sub-areas shown in the adjacent figure for the exemplary case of
, such as 10, is less well suited for tasks where the optimum lies on one of the value range boundaries.
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.
[8][18][19] In the two mutations presented, parts of the genome are rotated or inverted.
The presentation of the procedure[19] is illustrated by an example on the right: The presentation of the procedure[18] 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.
is determined randomly according to one of the two procedures for the mutation of real numbers from the interval
