Mutation (genetic algorithm)

Mutation is understood in an evolutionary algorithm (EA ) to randomly alter a genome. It is the implementation of the biological mutation for EA. Such an assignment of an ancient genome (and possibly random numbers ) to a new genome is a function and is called mutation function. Each mutation function is a genetic operator.

A mutation ideally should cause only small changes, but in the sum so much that individuals cover over the term of an evolutionary algorithm almost the entire value system on which you want to optimize. At the beginning of running an EA, it is therefore convenient to allow major changes, while in the advanced stage, only minor changes should be allowed to not, mop individuals who already are close to one optimum of this optimum.

An evolutionary algorithm with a global mutation rate (percentage of total population that is subjected to the mutation) of 0 will produce very poor results, because once never to return to the population again by crossing functions fallen from the population alleles, and thus, if the part Building Blocks of the globally optimal solution, were to find this missing. If the mutation rate is too high, however, individuals are forced away again close to the optimum of this and the algorithm can not converge.

When using for the problem is not well-suited crossing functions or problem representations may lead to unwanted mutations in the intersection. This produces in some places of chromosome one occurrence of the allele that can be traced back to any of the parent individuals, even before it comes to the actual mutation step.

For different genome types, different mutation types are differently well:

• 2.1 Rotation to the right
• 2.2 Reflection

Mutation of binary numbers ( bit strings )

The mutation of bit strings is performed by bit - flips at random locations.

Example:

The probability of a mutation of a bit is, the length of the binary vector is. Characterized in cross-section is a mutation rate of one per mutation and selected for mutation individual achieved (see above, global mutation rate ).

Favor of the less significant bit

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

• Choose a location of the binary number, where the least significant digits are selected with an exponentially higher probability than the more significant.
• Invert the bit to at this point of the binary number.
• The newly formed in this way the number is, the mutated genome.

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

This method also works with floating point numbers, if this is written as a number without exponent information ( ie place ).

A wrong choice of the mutation probabilities can lead to only low-order bits are modified so that the mutations ultimately have no appreciable influence on the individuals or their dependents fitness function value.

Mutation of permutations

Mutation of permutations is special designed for genomes that are permutations of a set itself. Parts of the genome are moved or mirrored.

Rotation to the right

A variant of mutation of permutations is the following method:

Reflection

Another variant of mutation of permutations is the following method:

This version is suitable for solving the problem of the traveling salesman, since the change in the neighborhood should be kept to a minimum and the reflection part - way is simply gone in reverse order.

• Evolutionary algorithm