Editing Crossover (evolutionary algorithm) (section)

== Crossover for permutations ==
For [[Combinatorial optimization|combinatorial tasks]], [[permutation]]s are usually used that are specifically designed for genomes that are themselves permutations of a [[Set (mathematics)|set]]. The underlying set is usually a subset of <math>\mathbb{N}</math> or <math>\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 ''[[Genotypic and phenotypic repair|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<ref name=":2">{{Cite journal |last1=Larrañaga |first1=P. |last2=Kuijpers |first2=C.M.H. |last3=Murga |first3=R.H. |last4=Inza |first4=I. |last5=Dizdarevic |first5=S. |date=1999 |title=Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators |url=http://link.springer.com/10.1023/A:1006529012972 |journal=Artificial Intelligence Review |volume=13 |issue=2 |pages=129–170 |doi=10.1023/A:1006529012972|s2cid=10284682 |url-access=subscription }}</ref> 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 [[Travelling salesman problem|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 [[Schedule|scheduling]] of multiple [[Workflow|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.<ref>{{Citation |last1=Goldberg |first1=David E. |last2=Lingle |first2=R. |title=Alleles, loci, and the traveling salesman problem |work=Proceedings of the First International Conference on Genetic Algorithms and Their Applications (ICGA) |date=1985 |publisher=Lawrence Erlbaum Associates |editor-last=Grefenstette |editor-first=John J. |isbn=0-8058-0426-9 |location=Hillsdale, N.J. |pages=154–159 |language=en |oclc=19702892}}</ref><ref name=":3">{{Cite book |last1=Eiben |first1=A.E. |url=http://link.springer.com/10.1007/978-3-662-44874-8 |title=Introduction to Evolutionary Computing |last2=Smith |first2=J.E. |date=2015 |publisher=Springer |isbn=978-3-662-44873-1 |edition=2nd |series=Natural Computing Series |location=Berlin, Heidelberg |pages=70–74 |language=en |chapter=Recombination for Permutation Representation |doi=10.1007/978-3-662-44874-8 |s2cid=20912932}}</ref> The explanation of the procedure is illustrated by an example: 
{| 
|- 
| '''Procedure'''
|  &nbsp;
| '''''Example'''''
| &nbsp;
| '''''Example Chromosome'''''
|-
| colspan=5 | <hr style="background-color:black; height:2px;">
|- style="vertical-align: top; "
| &nbsp;
| &nbsp;
| ''Let be given two permutations of the same set.''
| &nbsp;
| <math>P_0 = \left( A,B,C,D,E,F,G,H \right)</math> and <math>P_1 = \left( C,G,E,A,F,H,B,D \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top; "
| Randomly select two crossover points forming a gene segment in <math>P_0</math>.
| &nbsp;
| ''Here from gene position 4 to 6.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_0 = \left( A,B,C,\underline {D,E,F},G,H \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top;"
| The selected section is copied to the child chromosome in the same position.
| &nbsp;
| ''The open positions are indicated by question marks.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_C = \left( ?,?,?,\underline {D,E,F},?,? \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top;"
| rowspan=2 | Look for genes that have not been copied in the corresponding segment of <math>P_1</math> starting at the first crossover point. For each gene found (called <math>m</math>), look up in the offspring which element (called <math>n</math>) was copied in its place from <math>P_0</math>. Copy <math>m</math> to the position held by <math>n</math> in <math>P_1</math> if it is not occupied. Otherwise, continue with the next step.
| &nbsp;
| ''Gene <math>A</math> is the first uncopied gene in the corresponding segment of <math>P_1</math>: <math>\left(..., A,F,H,... \right)</math>. Gene <math>D</math> was copied from <math>P_0</math> in its place in <math>P_C</math>.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_C = \left( ?,?,?,\underline {\bold{D},E,F},?,? \right)</math>
|- style="vertical-align: top;"
| &nbsp;
| ''The position of <math>D</math> in <math>P_1</math> is the furthest right position and <math>A</math> will be placed there in <math>P_C</math>.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_C = \left( ?,?,?,\underline {D,E,F},?,A \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top; "
| If the place taken by <math>n</math> in <math>P_1</math> is already occupied by an element <math>k</math> in the descendant, <math>m</math> is put in the place taken by <math>k</math> in <math>P_1</math>.
| &nbsp;
| ''The next gene in <math>\left(..., A,F,H,... \right)</math> is <math>F</math> and this has already been copied into the child chromosome. Thus, the next gene to be handled is <math>H</math>. Its position in the offspring would be the position of <math>F</math> in <math>P_1</math>. However, this place is already occupied by gene <math>E</math>. So <math>H</math> is copied to the position of <math>E</math> in <math>P_1</math>.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_C = \left( ?,?,H,\underline {D,E,F},?,A \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top; "
| After processing the genes from the selected segment in <math>P_1</math>, the remaining positions in the offspring are filled with the genes from <math>P_1</math> that have not yet been copied, in the order of their appearance. This results in the finished child genome.
| &nbsp;
| ''The genes copied from <math>P_1</math> are <math>C, G</math> and <math>B</math>.''
| &nbsp;
|style="vertical-align: top;" | <math>P_C = \left( C,G,H,\underline {D,E,F},B,A \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|}

=== Order crossover (OX1) ===
The order crossover goes back to Davis<ref name=":0" /> 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'''
|  &nbsp;
| '''''Example'''''
| &nbsp;
| '''''Example Chromosome'''''
|-
| colspan=5 | <hr style="background-color:black; height:2px;">
|- style="vertical-align: top; "
| style="width:38%;" | &nbsp;
| style="width:1%;"  | &nbsp;
| style="width:30%;" | ''Let be given two permutations of the same set.''
| style="width:1%;"  | &nbsp;
| style="width:30%;" | <math>P_0 = \left( A,B,C,D,E,F,G,H,I,J \right)</math> and <math>P_1 = \left( B,D,A,H,J,C,E,G,F,I \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top; "
| Randomly select gene segments in <math>P_0</math>.
| &nbsp;
| ''Here two segments from gene position 1 to 2 and from 6 to 8.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_0 = \left( \underline {A,B},C,D,E,\underline {F,G,H},I,J \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top;"
| As a child permutation, a permutation is generated that contains the selected gene segments of <math>P_0</math> in the same position.
| &nbsp;
| ''The open positions are indicated by question marks.''
| &nbsp;
| style="vertical-align: middle;" | <math>P_C = \left( A,B,?,?,?,F,G,H,?,? \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top;"
| The remaining missing genes are now also transferred, but in the order in which they appear in <math>P_1</math>.
| &nbsp;
| ''The missing genes of <math>P_0</math> in the example are:''
| &nbsp;
| <math>P_\text{missing} = \left\{ C,D,E,I,J \right\}</math>
<math>P_{\text{in order from } P_1} = \left( D,J,C,E,I \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|- style="vertical-align: top;"
| This results in the completed child genome.
| &nbsp;
| ''The transferred genes are underlined:''
| &nbsp;
| <math>P_C = \left( A,B,\underline {D,J,C},F,G,H,\underline {E,I} \right)</math>
|-
| colspan=5 | <hr style="background-color:gray;">
|}

Among other things, order crossover is well suited for scheduling multiple workflows, when used in conjunction with 1- and n-point crossover.<ref>{{Citation |last1=Jakob |first1=Wilfried |title=Fast Multi-objective Scheduling of Jobs to Constrained Resources Using a Hybrid Evolutionary Algorithm |date=2008 |url=http://link.springer.com/10.1007/978-3-540-87700-4_102 |work=Parallel Problem Solving from Nature – PPSN X |volume=LNCS 5199 |pages=1031–1040 |editor-last=Rudolph |editor-first=Günter |place=Berlin, Heidelberg |publisher=Springer |doi=10.1007/978-3-540-87700-4_102 |isbn=978-3-540-87699-1 |access-date=2023-01-14 |last2=Quinte |first2=Alexander |last3=Stucky |first3=Karl-Uwe |last4=Süß |first4=Wolfgang |editor2-last=Jansen |editor2-first=Thomas |editor3-last=Beume |editor3-first=Nicola |editor4-last=Lucas |editor4-first=Simon|url-access=subscription }}</ref>

=== 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.<ref name=":0" /><ref name=":5" /><ref name=":3" /><ref name=":2" />

# cycle crossover (CX)<ref>{{Citation |last1=Oliver |first1=I.M. |last2=Smith |first2=D.J. |last3=Holland |first3=J. |title=A study of permutation crossover operators on the travelling salesman problem |work=Proceedings of the Second International Conference on Genetic Algorithms and Their Applications (ICGA) |date=1987 |publisher=Lawrence Erlbaum Associates |editor-last=Grefenstette |editor-first=John J. |isbn=978-0-8058-0158-3 |location=Hillsdale, N.J. |pages=224–230 |language=en }}</ref><ref name=":3" />
# order-based crossover (OX2)<ref name=":5" /><ref name=":4">{{Cite book |last=Syswerda |first=Gilbert |title=Handbook of genetic algorithms |date=1991 |publisher=Van Nostrand Reinhold |isbn=0-442-00173-8 |editor-last=Davis |editor-first=Lawrence |location=New York |pages=332–349 |language=en |chapter=Schedule Optimization Using Genetic Algorithms |oclc=23081440 }}</ref>
# position-based crossover (POS)<ref name=":5" /><ref name=":4" />
# edge recombination<ref>{{Citation |last1=Whitley |first1=Darrell |last2=Starkweather |first2=Timothy |last3=Fuquay |first3=D'Ann |title=Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator |date=1989 |work=Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA) |pages=133–140 |editor-last=Schaffer |editor-first=J.D. |place=San Francisco |publisher=Morgan Kaufmann |isbn=1558600663 }}</ref><ref name=":3" />
# voting recombination (VR)<ref name=":2" />
# alternating-positions crossover (AP)<ref name=":2" />
# maximal preservative crossover (MPX)<ref name=":5" /><ref>{{Citation |last1=Dzubera |first1=John |title=Advanced correlation analysis of operators for the traveling salesman problem |date=1994 |url=http://link.springer.com/10.1007/3-540-58484-6_251 |work=Parallel Problem Solving from Nature — PPSN III |volume=866 |pages=68–77 |editor-last=Davidor |editor-first=Yuval |place=Berlin, Heidelberg |publisher=Springer |doi=10.1007/3-540-58484-6_251 |isbn=978-3-540-58484-1 |access-date=2023-01-15 |last2=Whitley |first2=Darrell |editor2-last=Schwefel |editor2-first=Hans-Paul |editor3-last=Männer |editor3-first=Reinhard|url-access=subscription }}</ref>
# merge crossover (MX)<ref name=":5" /><ref>{{Citation |last1=Blanton |first1=Joe L. |last2=Wainwright |first2=Roger L. |title=Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms |date=1993 |work=Proceedings of the 5th International Conference on Genetic Algorithms (ICGA) |pages=452–459 |editor-last=Forrest |editor-first=Stephanie |place=San Francisco |publisher=Morgan Kaufmann |isbn=978-1-55860-299-1 }}</ref>
# sequential constructive crossover operator (SCX)<ref>{{cite thesis |last=Ahmed |first=Zakir Hussain |date=2000 |title=Sequential Constructive Sampling and Related approaches to Combinatorial Optimization |type=PhD |publisher=Tezpur University, India }}</ref>

The usual approach to solving TSP-like problems by genetic or, more generally, evolutionary algorithms, presented earlier, is either to [[Genotypic and phenotypic repair|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.<ref>{{cite journal |last1=Riazi |first1=Amin |title=Genetic algorithm and a double-chromosome implementation to the traveling salesman problem |journal=SN Applied Sciences |date=14 October 2019 |volume=1 |issue=11 |doi=10.1007/s42452-019-1469-1|doi-access= }}</ref>