Crossover (genetic algorithm)

From HandWiki
Short description: Operator used to vary the programming of chromosomes from one generation to the next
Part of a series on the
Evolutionary algorithm
Genetic algorithm
Genetic programming

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. 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. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions may be mutated before being added to the population.

Different algorithms in evolutionary computation may use different data structures to store genetic information, and each genetic representation can be recombined with different crossover operators. Typical data structures that can be recombined with crossover are bit arrays, vectors of real numbers, or trees.

The list of operators presented below is by no means complete and serves mainly as an exemplary illustration of this dyadic genetic operator type. More operators and more details can be found in the literature.[1][2][3][4][5]

Crossover for binary arrays

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.

OnePointCrossover.svg

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.

TwoPointCrossover.svg

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

Crossover for integer or real-valued genomes

Example of a discrete recombination in the three-dimensional case. The two possible offspring lie on the corners of the cuboid marked in blue.

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 [math]\displaystyle{ P_1=(1.5, 6, 8) }[/math] and [math]\displaystyle{ P_2=(7, 2, 1) }[/math], 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.[7]

Intermediate recombination

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 [math]\displaystyle{ a_i }[/math] are generated by mixing the alleles of the two parent genomes [math]\displaystyle{ a_{i,P_1} }[/math] and [math]\displaystyle{ a_{i,P_2} }[/math]:[7]

[math]\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 ] }[/math] randomly equally distributed per gene [math]\displaystyle{ i }[/math]

The choice of the interval [math]\displaystyle{ [-d, 1+d] }[/math] 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 [math]\displaystyle{ 0.25 }[/math] is recommended for [math]\displaystyle{ d }[/math] to counteract the tendency to reduce the allele values that otherwise exists at [math]\displaystyle{ d=0 }[/math].[8]

The adjacent figure shows for the two-dimensional case the range of possible new alleles of the two exemplary parents [math]\displaystyle{ P_1=(2,6) }[/math] and [math]\displaystyle{ P_2=(9,2) }[/math] in intermediate recombination. The offspring of discrete recombination [math]\displaystyle{ C_1 }[/math] and [math]\displaystyle{ C_2 }[/math] 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]

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 [math]\displaystyle{ \mathbb{N} }[/math] or [math]\displaystyle{ \mathbb{N}_0 }[/math]. 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[12] 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.[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.   [math]\displaystyle{ P_0 = \left( A,B,C,D,E,F,G,H \right) }[/math] and [math]\displaystyle{ P_1 = \left( C,G,E,A,F,H,B,D \right) }[/math]
Randomly select two crossover points forming a gene segment in [math]\displaystyle{ P_0 }[/math].   Here from gene position 4 to 6.   [math]\displaystyle{ P_0 = \left( A,B,C,\underline {D,E,F},G,H \right) }[/math]
The selected section is copied to the child chromosome in the same position.   The open positions are indicated by question marks.   [math]\displaystyle{ P_C = \left( ?,?,?,\underline {D,E,F},?,? \right) }[/math]
Look for genes that have not been copied in the corresponding segment of [math]\displaystyle{ P_1 }[/math] starting at the first crossover point. For each gene found (called [math]\displaystyle{ m }[/math]), look up in the offspring which element (called [math]\displaystyle{ n }[/math]) was copied in its place from [math]\displaystyle{ P_0 }[/math]. Copy [math]\displaystyle{ m }[/math] to the position held by [math]\displaystyle{ n }[/math] in [math]\displaystyle{ P_1 }[/math] if it is not occupied. Otherwise, continue with the next step.   Gene [math]\displaystyle{ A }[/math] is the first uncopied gene in the corresponding segment of [math]\displaystyle{ P_1 }[/math]: [math]\displaystyle{ \left(..., A,F,H,... \right) }[/math]. Gene [math]\displaystyle{ D }[/math] was copied from [math]\displaystyle{ P_0 }[/math] in its place in [math]\displaystyle{ P_C }[/math].   [math]\displaystyle{ P_C = \left( ?,?,?,\underline {\bold{D},E,F},?,? \right) }[/math]
  The position of [math]\displaystyle{ D }[/math] in [math]\displaystyle{ P_1 }[/math] is the furthest right position and [math]\displaystyle{ A }[/math] will be placed there in [math]\displaystyle{ P_C }[/math].   [math]\displaystyle{ P_C = \left( ?,?,?,\underline {D,E,F},?,A \right) }[/math]
If the place taken by [math]\displaystyle{ n }[/math] in [math]\displaystyle{ P_1 }[/math] is already occupied by an element [math]\displaystyle{ k }[/math] in the descendant, [math]\displaystyle{ m }[/math] is put in the place taken by [math]\displaystyle{ k }[/math] in [math]\displaystyle{ P_1 }[/math].   The next gene in [math]\displaystyle{ \left(..., A,F,H,... \right) }[/math] is [math]\displaystyle{ F }[/math] and this has already been copied into the child chromosome. Thus, the next gene to be handled is [math]\displaystyle{ H }[/math]. Its position in the offspring would be the position of [math]\displaystyle{ F }[/math] in [math]\displaystyle{ P_1 }[/math]. However, this place is already occupied by gene [math]\displaystyle{ E }[/math]. So [math]\displaystyle{ H }[/math] is copied to the position of [math]\displaystyle{ E }[/math] in [math]\displaystyle{ P_1 }[/math].   [math]\displaystyle{ P_C = \left( ?,?,H,\underline {D,E,F},?,A \right) }[/math]
After processing the genes from the selected segment in [math]\displaystyle{ P_1 }[/math], the remaining positions in the offspring are filled with the genes from [math]\displaystyle{ P_1 }[/math] that have not yet been copied, in the order of their appearance. This results in the finished child genome.   The genes copied from [math]\displaystyle{ P_1 }[/math] are [math]\displaystyle{ C, G }[/math] and [math]\displaystyle{ B }[/math].   [math]\displaystyle{ P_C = \left( C,G,H,\underline {D,E,F},B,A \right) }[/math]

Order crossover (OX1)

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.   [math]\displaystyle{ P_0 = \left( A,B,C,D,E,F,G,H,I,J \right) }[/math] and [math]\displaystyle{ P_1 = \left( B,D,A,H,J,C,E,G,F,I \right) }[/math]
Randomly select gene segments in [math]\displaystyle{ P_0 }[/math].   Here two segments from gene position 1 to 2 and from 6 to 8.   [math]\displaystyle{ P_0 = \left( \underline {A,B},C,D,E,\underline {F,G,H},I,J \right) }[/math]
As a child permutation, a permutation is generated that contains the selected gene segments of [math]\displaystyle{ P_0 }[/math] in the same position.   The open positions are indicated by question marks.   [math]\displaystyle{ P_C = \left( A,B,?,?,?,F,G,H,?,? \right) }[/math]
The remaining missing genes are now also transferred, but in the order in which they appear in [math]\displaystyle{ P_1 }[/math].   The missing genes of [math]\displaystyle{ P_0 }[/math] in the example are:   [math]\displaystyle{ P_\text{missing} = \left\{ C,D,E,I,J \right\} }[/math]

[math]\displaystyle{ P_{\text{in order from } P_1} = \left( D,J,C,E,I \right) }[/math]

This results in the completed child genome.   The transferred genes are underlined:   [math]\displaystyle{ P_C = \left( A,B,\underline {D,J,C},F,G,H,\underline {E,I} \right) }[/math]

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

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

See also

Bibliography

References

  1. ↑ 1.0 1.1 1.2 Davis, Lawrence (1991). Handbook of genetic algorithms. New York: Van Nostrand Reinhold. ISBN 0-442-00173-8. OCLC 23081440. 
  2. ↑ Eiben, A.E.; Smith, J.E. (2015). "Representation, Mutation, and Recombination" (in en). Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 49–78. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. http://link.springer.com/10.1007/978-3-662-44874-8. 
  3. ↑ Yu, Xinjie; Gen, Mitsuo (2010). "Encoding and Operators" (in en). Introduction to evolutionary algorithms. Decision Engineering. London: Springer. pp. 40–63. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-129-5. OCLC 654380156. https://www.worldcat.org/oclc/654380156. 
  4. ↑ Yu, Xinjie; Gen, Mitsuo (2010). "Variation Operators for Permutation Code". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 285–299. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8. http://link.springer.com/10.1007/978-1-84996-129-5. 
  5. ↑ 5.0 5.1 5.2 5.3 5.4 5.5 Booker, Lashon B.; Fogel, David B.; Whitley, Darrell; Angeline, Peter J.; Eiben, A.E. (2000). "Recombination". in Bäck, Thomas (in en). Evolutionary computation. Vol. 1, Basic algorithms and operators. Bristol: Institute of Physics Pub. pp. 256–307. ISBN 0-585-30560-9. OCLC 45730387. https://www.worldcat.org/oclc/45730387. 
  6. ↑ Syswerda, Gilbert (1989), Schaffer, J.D., ed., "Uniform crossover in genetic algorithms", Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA) (San Francisco: Morgan Kaufmann): pp. 2–9, ISBN 1558600663 
  7. ↑ 7.0 7.1 Eiben, A.E.; Smith, J.E. (2015). "Recombination Operators for Real-Valued Representation". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 65–67. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. http://link.springer.com/10.1007/978-3-662-44874-8. 
  8. ↑ Mühlenbein, Heinz; Schlierkamp-Voosen, Dirk (1993). "Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter Optimization" (in en). Evolutionary Computation 1 (1): 25–49. doi:10.1162/evco.1993.1.1.25. ISSN 1063-6560. https://direct.mit.edu/evco/article/1/1/25-49/1093. 
  9. ↑ Goldberg, David E. (1991). "Real-coded Genetic Algorithms, Virtual Alphabets, and Blocking". Complex Syst. 5 (2): 139–167. https://www.complex-systems.com/abstracts/v05_i02_a02/. 
  10. ↑ Stender, J.; Hillebrand, E.; Kingdon, J. (1994) (in en). Genetic algorithms in optimisation, simulation, and modelling. Amsterdam: IOS Press. ISBN 90-5199-180-0. OCLC 47216370. 
  11. ↑ Schwefel, Hans-Paul (1995) (in en). Evolution and optimum seeking. New York: Wiley. ISBN 0-471-57148-2. OCLC 30701094. https://ls11-www.cs.tu-dortmund.de/lehre/wiley/. 
  12. ↑ 12.0 12.1 12.2 12.3 Larrañaga, P.; Kuijpers, C.M.H.; Murga, R.H.; Inza, I.; Dizdarevic, S. (1999). "Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators". Artificial Intelligence Review 13 (2): 129–170. doi:10.1023/A:1006529012972. http://link.springer.com/10.1023/A:1006529012972. 
  13. ↑ Goldberg, David E.; Lingle, R. (1985), Grefenstette, John J., ed., "Alleles, loci, and the traveling salesman problem" (in en), Proceedings of the First International Conference on Genetic Algorithms and Their Applications (ICGA) (Hillsdale, N.J.: Lawrence Erlbaum Associates): pp. 154–159, ISBN 0-8058-0426-9, OCLC 19702892 
  14. ↑ 14.0 14.1 14.2 14.3 Eiben, A.E.; Smith, J.E. (2015). "Recombination for Permutation Representation" (in en). Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 70–74. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. http://link.springer.com/10.1007/978-3-662-44874-8. 
  15. ↑ Jakob, Wilfried; Quinte, Alexander; Stucky, Karl-Uwe; Süß, Wolfgang (2008), Rudolph, Günter; Jansen, Thomas; Beume, Nicola et al., eds., "Fast Multi-objective Scheduling of Jobs to Constrained Resources Using a Hybrid Evolutionary Algorithm", Parallel Problem Solving from Nature – PPSN X (Berlin, Heidelberg: Springer) LNCS 5199: pp. 1031–1040, doi:10.1007/978-3-540-87700-4_102, ISBN 978-3-540-87699-1, http://link.springer.com/10.1007/978-3-540-87700-4_102, retrieved 2023-01-14 
  16. ↑ Oliver, I.M.; Smith, D.J.; Holland, J. (1987), Grefenstette, John J., ed., "A study of permutation crossover operators on the travelling salesman problem" (in en), Proceedings of the Second International Conference on Genetic Algorithms and Their Applications (ICGA) (Hillsdale, N.J.: Lawrence Erlbaum Associates): pp. 224–230, ISBN 978-0-8058-0158-3 
  17. ↑ 17.0 17.1 Syswerda, Gilbert (1991). "Schedule Optimization Using Genetic Algorithms". in Davis, Lawrence (in en). Handbook of genetic algorithms. New York: Van Nostrand Reinhold. pp. 332–349. ISBN 0-442-00173-8. OCLC 23081440. 
  18. ↑ Whitley, Darrell; Starkweather, Timothy; Fuquay, D'Ann (1989), Schaffer, J.D., ed., "Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator", Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA) (San Francisco: Morgan Kaufmann): pp. 133–140, ISBN 1558600663 
  19. ↑ Dzubera, John; Whitley, Darrell (1994), Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard, eds., "Advanced correlation analysis of operators for the traveling salesman problem", Parallel Problem Solving from Nature — PPSN III (Berlin, Heidelberg: Springer) 866: pp. 68–77, doi:10.1007/3-540-58484-6_251, ISBN 978-3-540-58484-1, http://link.springer.com/10.1007/3-540-58484-6_251, retrieved 2023-01-15 
  20. ↑ Blanton, Joe L.; Wainwright, Roger L. (1993), Forrest, Stephanie, ed., "Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms", Proceedings of the 5th International Conference on Genetic Algorithms (ICGA) (San Francisco: Morgan Kaufmann): pp. 452–459, ISBN 978-1-55860-299-1 
  21. ↑ Ahmed, Zakir Hussain (2000). Sequential Constructive Sampling and Related approaches to Combinatorial Optimization (PhD). Tezpur University, India.
  22. ↑ Riazi, Amin (14 October 2019). "Genetic algorithm and a double-chromosome implementation to the traveling salesman problem". SN Applied Sciences 1 (11). doi:10.1007/s42452-019-1469-1. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Crossover_(genetic_algorithm)&oldid=3365408"