Editing Crossover (evolutionary algorithm) (section)

=== 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;">
|}