# 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.averageMethod
average(ss::Vector{<:AbstractStrategy})

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

List of the ES population recombination operations:

Evolutionary.averageMethod
average(population)

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

Evolutionary.marriageFunction
marriage(population)

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

### Binary Crossovers

Evolutionary.SPXFunction
SPX(v1, v2)

Single point crossover between v1 and v2 individuals.

Evolutionary.TPXFunction
TPX(v1, v2)

Two point crossover between v1 and v2 individuals.

Evolutionary.SHFXFunction
SHFX(v1, v2)

Shuffle crossover between the parents v1 and v2 that performs recombination similar to SPX preliminary shuffling these parents.

Evolutionary.UXFunction
UX(v1, v2)

Uniform crossover between v1 and v2 individuals.

Evolutionary.BINXFunction
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.EXPXFunction
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.BSXFunction
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.genopMethod
genop(v1, v2)

Returns the same parameter individuals v1 and v2 as an offspring pair (GENetic No OPeration).

Evolutionary.DCFunction
DC(v1, v2)

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

Evolutionary.AXFunction
AX(v1, v2)

Average crossover generates an offspring by taking average of the parents v1 and v2.

Evolutionary.WAXFunction
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.ICFunction
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.LCFunction
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.HXFunction
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.SBXFunction
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.PMXFunction
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.OX1Function
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.CXFunction
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.OX2Function
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.POSFunction
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.SSXFunction
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.crosstreeFunction
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.