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.nop
— Methodnop(s::AbstractStrategy)
This is a dummy mutation operator that does not change the strategy.
Evolutionary.gaussian
— Methodgaussian(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)$
Evolutionary.gaussian
— Methodgaussian(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)$
Evolutionary.cauchy
— Methodcauchy(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].
List of ES strategy mutation operations:
Evolutionary.gaussian
— Methodgaussian(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))$
Evolutionary.gaussian
— Methodgaussian(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))$
Genetic Algorithm
Binary Mutations
Evolutionary.flip
— Functionflip(recombinant)
Returns an in-place mutated binary recombinant
with a bit flips at random positions.
Evolutionary.bitinversion
— Functionbitinversion(recombinant)
Returns an in-place mutated binary recombinant
with its bits inverted.
Real-valued Mutations
Evolutionary.uniform
— Methoduniform(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$
Evolutionary.gaussian
— Functiongaussian(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)$
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)$
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))$
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))$
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$
Evolutionary.BGA
— FunctionBGA(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].
Evolutionary.PM
— FunctionPM(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
)
Evolutionary.MIPM
— FunctionMIPM(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].
Evolutionary.PLM
— FunctionPLM(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].
Combinatorial Mutations
Note: The combinatorial mutation operations are applicable to binary vectors.
Evolutionary.inversion
— Functioninversion(recombinant)
Returns an in-place mutated individual with a random arbitrary length segment of the genome in the reverse order.
Evolutionary.insertion
— Functioninsertion(recombinant)
Returns an in-place mutated individual with an arbitrary element of the genome moved in a random position.
Evolutionary.swap2
— Functionswap2(recombinant)
Returns an in-place mutated individual with a two random elements of the genome are swapped.
Evolutionary.scramble
— Functionscramble(recombinant)
Returns an in-place mutated individual with elements, on a random arbitrary length segment of the genome, been scrambled.
Evolutionary.shifting
— Functionshifting(recombinant)
Returns an in-place mutated individual with a random arbitrary length segment of the genome been shifted to an arbitrary position.
Base.replace
— Functionreplace(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.
Differential Evolution
Evolutionary.differentiation
— Functiondifferentiation(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})$
Genetic Programming
Evolutionary.subtree
— Functionsubtree(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 thangrowth
% deeper than its parent. (default:0.0
)
Evolutionary.point
— Functionpoint(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].
Evolutionary.hoist
— Functionhoist(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].
Evolutionary.shrink
— Functionshrink(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].
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