Crossover (evolutionary algorithm)
Crossover in evolutionary algorithms and evolutionary computation, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring.
It is one way to stochastically generate new solutions from an existing population, and is analogous to the crossover that happens during sexual reproduction in biology.
The aim of recombination is to transfer good characteristics from two different parents to one child.
Typical data structures that can be recombined with crossover are bit arrays, vectors of real numbers, or trees.
Crossover methods for bit arrays are popular and an illustrative example of genetic recombination.
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.
For the crossover operators presented above and for most other crossover operators for bit strings, it holds that they can also be applied accordingly to integer or real-valued genomes whose genes each consist of an integer or real-valued number.
Instead of individual bits, integer or real-valued numbers are then simply copied into the child genome.
The offspring lie on the remaining corners of the hyperbody spanned by the two parents
If the rules of the uniform crossover for bit strings are applied during the generation of the offspring, this is also called discrete recombination.
[9] The adjacent figure shows for the two-dimensional case the range of possible new alleles of the two exemplary parents
Intermediate recombination satisfies the arithmetic calculation of the allele values of the child genome required by virtual alphabet theory.
This can be remedied by genetic repair, e.g. by replacing the redundant genes in positional fidelity for missing ones from the other child genome.
A well-known representative of the first task type is the traveling salesman problem (TSP), where the goal is to visit a set of cities exactly once on the shortest tour.
An example of the constrained task type is the scheduling of multiple workflows.
Workflows involve sequence constraints on some of the individual work steps.
[14][15] The explanation of the procedure is illustrated by an example: 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.
[16] Over time, a large number of crossover operators for permutations have been proposed, so the following list is only a small selection.
[1][5][15][13] 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.
