# 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`

— Method`nop(s::AbstractStrategy)`

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

`Evolutionary.gaussian`

— Method`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)$

`Evolutionary.gaussian`

— Method`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)$

`Evolutionary.cauchy`

— Method`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]}.

List of ES strategy mutation operations:

`Evolutionary.gaussian`

— Method`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))$

`Evolutionary.gaussian`

— Method`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))$

## Genetic Algorithm

### Binary Mutations

`Evolutionary.flip`

— Function`flip(recombinant)`

Returns an in-place mutated binary `recombinant`

with a bit flips at random positions.

`Evolutionary.bitinversion`

— Function`bitinversion(recombinant)`

Returns an in-place mutated binary `recombinant`

with its bits inverted.

### Real-valued Mutations

`Evolutionary.uniform`

— Method`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$

`Evolutionary.gaussian`

— Function`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)$

`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`

— Function`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]}.

`Evolutionary.PM`

— Function`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`

)

`Evolutionary.MIPM`

— Function`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]}.

`Evolutionary.PLM`

— Function`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]}.

### Combinatorial Mutations

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

`Evolutionary.inversion`

— Function`inversion(recombinant)`

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

`Evolutionary.insertion`

— Function`insertion(recombinant)`

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

`Evolutionary.swap2`

— Function`swap2(recombinant)`

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

`Evolutionary.scramble`

— Function`scramble(recombinant)`

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

`Evolutionary.shifting`

— Function`shifting(recombinant)`

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

`Base.replace`

— Function`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.

## Differential Evolution

`Evolutionary.differentiation`

— Function`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})$

## Genetic Programming

`Evolutionary.subtree`

— Function`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`

)

`Evolutionary.point`

— Function`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]}.

`Evolutionary.hoist`

— Function`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]}.

`Evolutionary.shrink`

— Function`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]}.

## 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