# Crossover

In genetic algorithms and evolutionary computation, **crossover**, also called **recombination**, is a genetic operator used to combine the genetic information of two parents to generate new offspring.

## Recombination Interface

All recombination operations have following call interface: `recombination(i1, i2)`

where `i1`

and `i2`

are the same type individuals that involved in recombination to produce an offspring. The recombination function returns pair of recombined individuals.

**Note:** Some of the selection algorithms implemented as function closures, in order to provide additional parameters for the specified above recombination interface.

## Operations

### ES Crossovers

List of the ES strategy recombination operations:

`Evolutionary.average`

— Method`average(ss::Vector{<:AbstractStrategy})`

Returns the average value of the mutation parameter $\sigma$ of strategies `ss`

.

List of the ES population recombination operations:

`Evolutionary.average`

— Method`average(population)`

Returns an *one* offspring individual of a multi-parent recombination by averaging `population`

.

`Evolutionary.marriage`

— Function`marriage(population)`

Returns an *one* offspring individual of a multi-parent recombination by random copying from `population`

.

### Binary Crossovers

`Evolutionary.SPX`

— Function`SPX(v1, v2)`

Single point crossover between `v1`

and `v2`

individuals.

`Evolutionary.TPX`

— Function`TPX(v1, v2)`

Two point crossover between `v1`

and `v2`

individuals.

`Evolutionary.SHFX`

— Function`SHFX(v1, v2)`

Shuffle crossover between the parents `v1`

and `v2`

that performs recombination similar to `SPX`

preliminary shuffling these parents.

`Evolutionary.UX`

— Function`UX(v1, v2)`

Uniform crossover between `v1`

and `v2`

individuals.

`Evolutionary.BINX`

— Function`BINX(Cr::Real=0.5)`

Returns a uniform (binomial) crossover function, see Recombination Interface, function with the probability `Cr`

^{[2]}.

The crossover probability value must be in unit interval, $Cr \in [0,1]$.

`Evolutionary.EXPX`

— Function`EXPX(Cr::Real=0.5)`

Returns an exponential crossover function, see Recombination Interface, function with the probability `Cr`

^{[2]}.

The crossover probability value must be in unit interval, $Cr \in [0,1]$.

`Evolutionary.BSX`

— Function`BSX(k::Int)`

Binary Subset Crossover^{[7]}. Produces an offspring by first pooling the unique items of the two parents, and then creating each offspring by sampling without replacement at most `k`

elements from the pool of items.

### Real-valued Crossovers

`Evolutionary.genop`

— Method`genop(v1, v2)`

Returns the same parameter individuals `v1`

and `v2`

as an offspring pair (GENetic No OPeration).

`Evolutionary.DC`

— Function`DC(v1, v2)`

Returns a randomly assembled offspring and its inverse from the elements of parents `v1`

and `v2`

.

`Evolutionary.AX`

— Function`AX(v1, v2)`

Average crossover generates an offspring by taking average of the parents `v1`

and `v2`

.

`Evolutionary.WAX`

— Function`WAX(w::Vector{<:Real})(v1, v2)`

Returns a weighted average recombination operation, see Recombination Interface, which generate an offspring as weighted average of the parents `v1`

and `v2`

with the weights `w`

.

`Evolutionary.IC`

— Function`IC(d::Real=0.0)`

Returns an extended intermediate recombination operation, see Recombination Interface, which generates offspring `u`

and `v`

as

- $u_i = x_i + \alpha_i (y_i - x_i)$
- $v_i = y_i + \alpha_i (x_i - y_i)$

where $\alpha_i$ is chosen uniform randomly in the interval $[-d;d+1]$.

`Evolutionary.LC`

— Function`LC(d::Real=0.0)`

Returns a extended line recombination operation, see Recombination Interface, which generates offspring `u`

and `v`

as

- $u_i = x_i + \alpha (y_i - x_i)$
- $v_i = y_i + \alpha (x_i - y_i)$

where $\alpha$ is chosen uniform randomly in the interval $[-d;d+1]$.

`Evolutionary.HX`

— Function`HX(x, y)`

Heuristic crossover (HX) recombination operation^{[3]} generates offspring `u`

and `v`

as

- $u = x + r (x - y)$
- $v = y + r (y - x)$

where $r$ is chosen uniform randomly in the interval $[0;1)$.

`Evolutionary.LX`

— Function`LX(μ::Real = 0.0, b::Real = 0.2)`

Returns a Laplace crossover (LX) recombination operation^{[4]}, see Recombination Interface.

`Evolutionary.MILX`

— Function`MILX(μ::Real = 0.0, b_real::Real = 0.15, b_int::Real = 0.35)`

Returns a mixed integer Laplace crossover (MI-LX) recombination operation^{[5]}, see Recombination Interface.

`Evolutionary.SBX`

— Function`SBX(pm::Real = 0.5, η::Integer = 2)`

Returns a Simulated Binary Crossover (SBX) recombination operation, see Recombination Interface, with the mutation probability `pm`

of the recombinant component, and is the crossover distribution index `η`

^{[6]}.

### Combinatorial Crossovers

`Evolutionary.PMX`

— Function`PMX(v1, v2)`

Partially mapped crossover which maps ordering and values information from the parents `v1`

and `v2`

to the offspring. A portion of one parent is mapped onto a portion of the other parent string and the remaining information is exchanged.

`Evolutionary.OX1`

— Function`OX1(v1, v2)`

Order crossover constructs an offspring by choosing a substring of one parent and preserving the relative order of the elements of the other parent.

`Evolutionary.CX`

— Function`CX(v1, v2)`

Cycle crossover creates an offspring from the parents `v1`

and `v2`

such that every position is occupied by a corresponding element from one of the parents.

`Evolutionary.OX2`

— Function`OX2(v1, v2)`

Order-based crossover selects at random several positions in the parent `v1`

, and the order of the elements in the selected positions of the parent `v1`

is imposed on the parent `v2`

.

`Evolutionary.POS`

— Function`POS(v1, v2)`

Position-based crossover is a modification of the `OX1`

operator. It selects a random set of positions in the parents `v1`

and `v2`

, then imposes the position of the selected elements of one parent on the corresponding elements of the other parent.

`Evolutionary.SSX`

— Function`SSX(v1, v2)`

Subset crossover operator creates new offspring by pooling the unique indices of the two parent vectors `v1`

and `v2`

, and then sampling a set of unique indices from this pool, uniformly at random.

### Tree (expression) Crossovers

`Evolutionary.crosstree`

— Function`crosstree(t1::Expr, t2::Expr)`

Perform an arbitrary subtree swap between the expressions `t1`

and `t2`

.

## References

- 1H. Mühlenbein, D. Schlierkamp-Voosen, "Predictive Models for the Breeder Genetic Algorithm: I. Continuous Parameter Optimization". Evolutionary Computation, 1 (1), pp. 25-49, 1993.
- 2K. V. Price and R. M. Storn and J. A. Lampinen, "Differential evolution: A practical approach to global optimization", Springer, 2005.
- 3Z. Michalewicz, T. Logan, S. Swaminathan. "Evolutionary operators for continuous convex parameter spaces." Proceedings of the 3rd Annual conference on Evolutionary Programming, 1994.
- 4K. Deep, M. Thakur, "A new crossover operator for real coded genetic algorithms", Applied Mathematics and Computation 188, 2007, 895–912
- 5K. 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
- 6K. Deb, R. B. Agrawal, "Simulated Binary Crossover for Continuous Search Space", Complex Syst., 9., 1995
- 7M. A. Wolters, “A Genetic Algorithm for Selection of Fixed-Size Subsets with Application to Design Problems”, J. Stat. Soft., vol. 68, no. 1, pp. 1–18, Nov. 2015.