Crossover (evolutionary algorithm)

Traditional genetic algorithms store genetic information in a chromosome represented by a bit array. Crossover methods for bit arrays are popular and an illustrative example of genetic recombination. One-point crossover 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. Two-point and k-point crossover 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. Uniform crossover In uniform crossover, typically, each bit is chosen from either parent with equal probability. 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. ==Crossover for integer or real-valued genomes==

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 P_1=(1.5, 6, 8) and P_2=(7, 2, 1), as exemplified in the accompanying image for the three-dimensional case. Discrete recombination If the rules of the uniform crossover for bit strings are applied during the generation of the offspring, this is also called discrete recombination. Intermediate recombination In this recombination operator, the allele values of the child genome a_i are generated by mixing the alleles of the two parent genomes a_{i,P_1} and a_{i,P_2}: :\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 i The choice of the interval [-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 0.25 is recommended for d to counteract the tendency to reduce the allele values that otherwise exists at d=0. The adjacent figure shows for the two-dimensional case the range of possible new alleles of the two exemplary parents P_1=(3,6) and P_2=(9,2) in intermediate recombination. The offspring of discrete recombination C_1 and C_2 are also plotted. Intermediate recombination satisfies the arithmetic calculation of the allele values of the child genome required by virtual alphabet theory. Discrete and intermediate recombination are used as a standard in the evolution strategy. == Crossover for permutations ==

For combinatorial tasks, permutations are usually used that are specifically designed for genomes that are themselves permutations of a set. The underlying set is usually a subset of \mathbb{N} or \mathbb{N}_0. If 1- or n-point or uniform crossover for integer genomes is used for such genomes, a child genome may contain some values twice and others may be missing. 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. In order to avoid the generation of invalid offspring, special crossover operators for permutations have been developed which fulfill the basic requirements of such operators for permutations, namely that all elements of the initial permutation are also present in the new one and only the order is changed. It can be distinguished between combinatorial tasks, where all sequences are admissible, and those where there are constraints in the form of inadmissible partial sequences. 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. For example, a thread cannot be cut until the corresponding hole has been drilled in a workpiece. Such problems are also called order-based permutations. In the following, two crossover operators are presented as examples, the partially mapped crossover (PMX) motivated by the TSP and the order crossover (OX1) designed for order-based permutations. A second offspring can be produced in each case by exchanging the parent chromosomes. Partially mapped crossover (PMX) The PMX operator was designed as a recombination operator for TSP like Problems. The explanation of the procedure is illustrated by an example: Order crossover (OX1) The order crossover goes back to Davis Further crossover operators for permutations 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. • position-based crossover (POS) • merge crossover (MX) • sequential constructive crossover operator (SCX) 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. == See also ==