Mutation

In genetic algorithms and evolutionary computation, mutation is a genetic operator used to maintain a diversity from one generation of a population to the next. It is analogous to biological mutation. Mutation alters one or more gene values in a chromosome from its initial state. The purpose of mutation is to introduce diversity into the sampled population.

Mutation Interface

All mutation operations have following call interface mutation(individual) where individual is the member of population. The mutation function returns an in-place mutated individual.

Evolutionary Strategy

See Strategies section for detailed description of ES strategies.

List of ES mutation operations:

Evolutionary.nopMethod
nop(s::AbstractStrategy)

This is a dummy mutation operator that does not change the strategy.

source
Evolutionary.gaussianMethod
gaussian(x, s::IsotropicStrategy)

Performs Gaussian isotropic mutation of the recombinant x given the strategy s by adding Gaussian noise as follows:

  • $x_i^\prime = x_i + s.\sigma \mathcal{N}_i(0,1)$
source
Evolutionary.gaussianMethod
gaussian(x, s::AnisotropicStrategy)

Performs Gaussian anisotropic mutation of the recombinant x given the strategy s by adding Gaussian noise as follows:

  • $x_i^\prime = x_i + s.\sigma_i \mathcal{N}_i(0,1)$
source
Evolutionary.cauchyMethod
cauchy(x, s::IsotropicStrategy)

Performs isotropic mutation of the recombinant x given the strategy s by adding a noise from the Cauchy distribution as follows:

  • $x_i^\prime = x_i + s.\sigma_i \delta_i$

where $\delta$ is a Cauchy random variable with the scale parameter $t = 1$ [2].

source

List of ES strategy mutation operations:

Evolutionary.gaussianMethod
gaussian(s::IsotropicStrategy)

Performs in-place mutation of the isotropic strategy s modifying its mutated strategy parameter $\sigma$ with Gaussian noise as follows:

  • $\sigma^\prime = \sigma \exp(\tau_0 \mathcal{N}(0,1))$
source
Evolutionary.gaussianMethod
gaussian(s::AnisotropicStrategy)

Performs in-place mutation of the anisotropic strategy s modifying its mutated strategy parameter $\sigma$ with Gaussian noise as follows:

  • $\sigma_i^\prime = \sigma_i \exp(\tau_0 \mathcal{N}(0,1) + \tau_i \mathcal{N}(0,1))$
source

Genetic Algorithm

Binary Mutations

Evolutionary.flipFunction
flip(recombinant)

Returns an in-place mutated binary recombinant with a bit flips at random positions.

source

Real-valued Mutations

Evolutionary.uniformMethod
uniform(r = 1.0)

Returns an in-place real valued mutation function that performs the uniform distributed mutation [1].

The mutation operator randomly chooses a number $z$ in from the uniform distribution on the interval $[-r,r]$, the mutation range. The mutated individual is given by

  • $x_i^\prime = x_i + z_i$
source
Evolutionary.gaussianFunction
gaussian(x, s::IsotropicStrategy)

Performs Gaussian isotropic mutation of the recombinant x given the strategy s by adding Gaussian noise as follows:

  • $x_i^\prime = x_i + s.\sigma \mathcal{N}_i(0,1)$
source
gaussian(x, s::AnisotropicStrategy)

Performs Gaussian anisotropic mutation of the recombinant x given the strategy s by adding Gaussian noise as follows:

  • $x_i^\prime = x_i + s.\sigma_i \mathcal{N}_i(0,1)$
source
gaussian(s::IsotropicStrategy)

Performs in-place mutation of the isotropic strategy s modifying its mutated strategy parameter $\sigma$ with Gaussian noise as follows:

  • $\sigma^\prime = \sigma \exp(\tau_0 \mathcal{N}(0,1))$
source
gaussian(s::AnisotropicStrategy)

Performs in-place mutation of the anisotropic strategy s modifying its mutated strategy parameter $\sigma$ with Gaussian noise as follows:

  • $\sigma_i^\prime = \sigma_i \exp(\tau_0 \mathcal{N}(0,1) + \tau_i \mathcal{N}(0,1))$
source
gaussian(σ = 1.0)

Returns an in-place real valued mutation function that performs the normal distributed mutation [1].

The mutation operator randomly chooses a number $z$ in from the normal distribution $\mathcal{N}(0,\sigma)$ with standard deviation $\sigma$. The mutated individual is given by

  • $x_i^\prime = x_i + z_i$
source
Evolutionary.BGAFunction
BGA(valrange, m = 20)

Returns an in-place real valued mutation function that performs the BGA mutation scheme with the mutation range valrange and the mutation probability 1/m [1].

source
Evolutionary.PMFunction
PM(lower, upper, p = 2)

Returns an in-place real valued mutation function that performs the Power Mutation (PM) scheme within lower and upper bound, and an index of mutation p[3].

Note: The implementation is a degenerate case of Mixed Integer Power Mutation (MIPM)

source
Evolutionary.MIPMFunction
MIPM(lower, upper, p_real = 10, p_int = 4)

Returns an in-place real valued mutation function that performs the Mixed Integer Power Mutation (MI-PM) scheme within lower and upper bound, and an index of mutation p_real for real value and p_int for integer values[4].

source
Evolutionary.PLMFunction
PLM(lower, upper, η = 2)

Returns an in-place real valued mutation function that performs the Polynomial Mutation (PLM) scheme within lower and upper bounds, and a mutation distribution index η[9].

source

Combinatorial Mutations

Note: The combinatorial mutation operations are applicable to binary vectors.

Evolutionary.inversionFunction
inversion(recombinant)

Returns an in-place mutated individual with a random arbitrary length segment of the genome in the reverse order.

source
Evolutionary.insertionFunction
insertion(recombinant)

Returns an in-place mutated individual with an arbitrary element of the genome moved in a random position.

source
Evolutionary.swap2Function
swap2(recombinant)

Returns an in-place mutated individual with a two random elements of the genome are swapped.

source
Evolutionary.scrambleFunction
scramble(recombinant)

Returns an in-place mutated individual with elements, on a random arbitrary length segment of the genome, been scrambled.

source
Evolutionary.shiftingFunction
shifting(recombinant)

Returns an in-place mutated individual with a random arbitrary length segment of the genome been shifted to an arbitrary position.

source
Base.replaceFunction
replace(pool,[minchange=1])(recombinant)

Replacement mutation operator changes an arbitrary number, no smaller then minchange, of elements in the individual by replacing them with elements from the predefined pool that are not in the individual.

source

Differential Evolution

Evolutionary.differentiationFunction
differentiation(recombinant, mutators; F = 1.0)

Returns an in-place differently mutated individual $x^\prime$ from recombinant $x$ by mutators $\{\xi_1, \ldots, \xi_n \}$ as follows

  • $x^\prime = x + \sum_{i=1}^{n/2} F (\xi_{2i-1} - \xi_{2i})$
source

Genetic Programming

Evolutionary.subtreeFunction
subtree(method::TreeGP; growth::Real = 0.0)

Returns an in-place expression mutation function that performs mutation of an arbitrary expression subtree with a randomly generated one [5].

Parameters:

  • growth: Growth restriction on the offspring in comparison to the parent. The offspring cannot be more than growth% deeper than its parent. (default: 0.0)
source
Evolutionary.pointFunction
point(method::TreeGP)

Returns an in-place expression mutation function that replaces an arbitrary node in the tree by the randomly selected one. Node replacement mutation is similar to bit string mutation in that it randomly changes a point in the individual. To ensure the tree remains legal, the replacement node has the same number of arguments as the node it is replacing [6].

source
Evolutionary.hoistFunction
hoist(method::TreeGP)

Returns an in-place expression mutation function that creates a new offspring individual which is copy of a randomly chosen subtree of the parent. Thus, the offspring will be smaller than the parent and will have a different root node [7].

source
Evolutionary.shrinkFunction
shrink(method::TreeGP)

Returns an in-place expression mutation function that replaces a randomly chosen subtree with a randomly created terminal. This is a special case of subtree mutation where the replacement tree is a terminal. As with hoist mutation, it is motivated by the desire to reduce program size [8].

source

References

  • 1Mühlenbein, H. and Schlierkamp-Voosen, D., "Predictive Models for the Breeder Genetic Algorithm: I. Continuous Parameter Optimization", Evolutionary Computation, 1 (1), 25-49, 1993.
  • 2Yao, Xin, and Yong Liu, "Fast evolution strategies", In International Conference on Evolutionary Programming, 149-161, Springer, 1997.
  • 3K. Deep, M. Thakur, "A new crossover operator for real coded genetic algorithms", Applied Mathematics and Computation 188, 895-912, 2007.
  • 4K. Deep, K. P. Singh, M. L. Kansal, and C. Mohan, "A real coded genetic algorithm for solving integer and mixed integer optimization problems", Appl. Math. Comput. 212, 505-518, 2009
  • 5K. E. Kinnear, Jr., "Evolving a sort: Lessons in genetic programming", In Proceedings of the 1993 International Conference on Neural Networks, vol 2, 881-888, IEEE Press, 1993.
  • 6B. McKay, M. J. Willis, and G. W. Barton., "Using a tree structured genetic algorithm to perform symbolic regression", GALESIA, vol 414, 487-492, 1995.
  • 7K. E. Kinnear, Jr., "Fitness landscapes and difficulty in genetic programming", In Proceedings of the 1994 IEEE World Conference on Computational Intelligence, vol 1, 142-147, IEEE Press, 1994.
  • 8P. J. Angeline, "An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover", Genetic Programming 1996: Proceedings of the First Annual Conference, 21–29, 1996.
  • 9K. Deb, R. B. Agrawal, "Simulated Binary Crossover for Continuous Search Space", Complex Syst., 9., 1995