Crossover (genetic algorithm)

A point on both parents' chromosomes is picked randomly, and designated a 'crossover point'. Bits to the right of that point are swapped between the two parent chromosomes. This results in two offspring, each carrying some genetic information from both parents.

In two-point crossover, two crossover points are picked randomly from the parent chromosomes. The bits in between the two points are swapped between the parent organisms.

Two-point crossover is equivalent to performing two single-point crossovers with different crossover points. This strategy can be generalized to k-point crossover for any positive integer k, picking k crossover points.

In uniform crossover, typically, each bit is chosen from either parent with equal probability.[6] Other mixing ratios are sometimes used, resulting in offspring which inherit more genetic information from one parent than the other. In a uniform crossover, we don’t divide the chromosome into segments, rather we treat each gene separately. In this, we essentially flip a coin for each chromosome to decide whether or not it will be included in the off-spring.

If the rules of the uniform crossover for bit strings are applied during the generation of the offspring, this is also called discrete recombination.[7]

In the two-dimensional case, the two offspring of discrete recombination lie on the corners marked in blue, while the entire gray area is in question for the offspring of intermediate recombination.

In this recombination operator, the allele values of the child genome ${\displaystyle a_{i}}$ are generated by mixing the alleles of the two parent genomes ${\displaystyle a_{i,P_{1}}}$ and ${\displaystyle a_{i,P_{2}}}$:[7]

${\displaystyle \alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i}\right)\quad {\mathsf {with}}\quad \beta _{i}\in \left[-d,1+d\right]}$ randomly equally distributed per gene ${\displaystyle i}$

The choice of the interval ${\displaystyle [-d,1+d]}$ causes that besides the interior of the hyperbody spanned by the allele values of the parent genes additionally a certain environment for the range of values of the offspring is in question. A value of ${\displaystyle 0.25}$ is recommended for ${\displaystyle d}$ to counteract the tendency to reduce the allele values that otherwise exists at ${\displaystyle d=0}$.[8]

The adjacent figure shows for the two-dimensional case the range of possible new alleles of the two exemplary parents ${\displaystyle P_{1}=(2,6)}$ and ${\displaystyle P_{2}=(9,2)}$ in intermediate recombination. The offspring of discrete recombination ${\displaystyle C_{1}}$ and ${\displaystyle C_{2}}$ are also plotted. Intermediate recombination satisfies the arithmetic calculation of the allele values of the child genome required by virtual alphabet theory.[9][10] Discrete and intermediate recombination are used as a standard in the evolution strategy.[11]

The PMX operator was designed as a recombination operator for TSP like Problems.[13][14] The explanation of the procedure is illustrated by an example:

Procedure		Example		Example Chromosome
		Let be given two permutations of the same set.		${\displaystyle P_{0}=\left(A,B,C,D,E,F,G,H\right)}$ and ${\displaystyle P_{1}=\left(C,G,E,A,F,H,B,D\right)}$
Randomly select two crossover points forming a gene segment in ${\displaystyle P_{0}}$.		Here from gene position 4 to 6.		${\displaystyle P_{0}=\left(A,B,C,{\underline {D,E,F}},G,H\right)}$
The selected section is copied to the child chromosome in the same position.		The open positions are indicated by question marks.		${\displaystyle P_{C}=\left(?,?,?,{\underline {D,E,F}},?,?\right)}$
Look for genes that have not been copied in the corresponding segment of ${\displaystyle P_{1}}$ starting at the first crossover point. For each gene found (called ${\displaystyle m}$), look up in the offspring which element (called ${\displaystyle n}$) was copied in its place from ${\displaystyle P_{0}}$. Copy ${\displaystyle m}$ to the position held by ${\displaystyle n}$ in ${\displaystyle P_{1}}$ if it is not occupied. Otherwise, continue with the next step.		Gene ${\displaystyle A}$ is the first uncopied gene in the corresponding segment of ${\displaystyle P_{1}}$: ${\displaystyle \left(...,A,F,H,...\right)}$. Gene ${\displaystyle D}$ was copied from ${\displaystyle P_{0}}$ in its place in ${\displaystyle P_{C}}$.		${\displaystyle P_{C}=\left(?,?,?,{\underline {{\mathbf {D}},E,F}},?,?\right)}$
		The position of ${\displaystyle D}$ in ${\displaystyle P_{1}}$ is the furthest right position and ${\displaystyle A}$ will be placed there in ${\displaystyle P_{C}}$.		${\displaystyle P_{C}=\left(?,?,?,{\underline {D,E,F}},?,A\right)}$
If the place taken by ${\displaystyle n}$ in ${\displaystyle P_{1}}$ is already occupied by an element ${\displaystyle k}$ in the descendant, ${\displaystyle m}$ is put in the place taken by ${\displaystyle k}$ in ${\displaystyle P_{1}}$.		The next gene in ${\displaystyle \left(...,A,F,H,...\right)}$ is ${\displaystyle F}$ and this has already been copied into the child chromosome. Thus, the next gene to be handled is ${\displaystyle H}$. Its position in the offspring would be the position of ${\displaystyle F}$ in ${\displaystyle P_{1}}$. However, this place is already occupied by gene ${\displaystyle E}$. So ${\displaystyle H}$ is copied to the position of ${\displaystyle E}$ in ${\displaystyle P_{1}}$.		${\displaystyle P_{C}=\left(?,?,H,{\underline {D,E,F}},?,A\right)}$
After processing the genes from the selected segment in ${\displaystyle P_{1}}$, the remaining positions in the offspring are filled with the genes from ${\displaystyle P_{1}}$ that have not yet been copied, in the order of their appearance. This results in the finished child genome.		The genes copied from ${\displaystyle P_{1}}$ are ${\displaystyle C,G}$ and ${\displaystyle B}$.		${\displaystyle P_{C}=\left(C,G,H,{\underline {D,E,F}},B,A\right)}$

The order crossover goes back to Davis[1] in its original form and is presented here in a slightly generalized version with more than two crossover points. It transfers information about the relative order from the second parent to the offspring. First, the number and position of the crossover points are determined randomly. The resulting gene sequences are then processed as described below:

Procedure		Example		Example Chromosome
		Let be given two permutations of the same set.		${\displaystyle P_{0}=\left(A,B,C,D,E,F,G,H,I,J\right)}$ and ${\displaystyle P_{1}=\left(B,D,A,H,J,C,E,G,F,I\right)}$
Randomly select gene segments in ${\displaystyle P_{0}}$.		Here two segments from gene position 1 to 2 and from 6 to 8.		${\displaystyle P_{0}=\left({\underline {A,B}},C,D,E,{\underline {F,G,H}},I,J\right)}$
As a child permutation, a permutation is generated that contains the selected gene segments of ${\displaystyle P_{0}}$ in the same position.		The open positions are indicated by question marks.		${\displaystyle P_{C}=\left(A,B,?,?,?,F,G,H,?,?\right)}$
The remaining missing genes are now also transferred, but in the order in which they appear in ${\displaystyle P_{1}}$.		The missing genes of ${\displaystyle P_{0}}$ in the example are:		${\displaystyle P_{\text{missing}}=\left\{C,D,E,I,J\right\}}$ ${\displaystyle P_{{\text{in order from }}P_{1}}=\left(D,J,C,E,I\right)}$
This results in the completed child genome.		The transferred genes are underlined:		${\displaystyle P_{C}=\left(A,B,{\underline {D,J,C}},F,G,H,{\underline {E,I}}\right)}$

Among other things, order crossover is well suited for scheduling multiple workflows, when used in conjunction with 1- and n-point crossover.[15]

Over time, a large number of crossover operators for permutations have been proposed, so the following list is only a small selection. For more information, the reader is referred to the literature.[1][5][14][12]

1. cycle crossover (CX)[16][14]
2. order-based crossover (OX2)[5][17]
3. position-based crossover (POS)[5][17]
4. edge recombination[18][14]
5. voting recombination (VR)[12]
6. alternating-positions crossover (AP)[12]
7. maximal preservative crossover (MPX)[5][19]
8. merge crossover (MX)[5][20]
9. sequential constructive crossover operator (SCX)[21]

The usual approach to solving TSP-like problems by genetic or, more generally, evolutionary algorithms, presented earlier, is either to repair illegal descendants or to adjust the operators appropriately so that illegal offspring do not arise in the first place. Alternatively, Riazi suggests the use of a double chromosome representation, which avoids illegal offspring.[22]