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.

source

List of the ES population recombination operations:

Evolutionary.averageMethod
average(population)

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

source
Evolutionary.marriageFunction
marriage(population)

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

source

Binary Crossovers

Evolutionary.SHFXFunction
SHFX(v1, v2)

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

source
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.

source

Real-valued Crossovers

Evolutionary.genopMethod
genop(v1, v2)

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

source
Evolutionary.DCFunction
DC(v1, v2)

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

source
Evolutionary.AXFunction
AX(v1, v2)

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

source
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.

source
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 y in the interval $[-d;d+1]$.

source
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]$.

source
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)$.

source
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].

source

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.

source
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.

source
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.

source
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.

source
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.

source
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.

source

Tree (expression) Crossovers

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.