Editing Chromosome (evolutionary algorithm) (section)

=== Chromosomes for permutations ===
[[Combinatorial optimization|Combinatorial problems]] are mainly concerned with finding an optimal sequence of a set of elementary items. As an example, consider the problem of the [[Travelling salesman problem|traveling salesman]] who wants to visit a given number of cities exactly once on the shortest possible tour. The simplest and most obvious mapping onto a chromosome is to number the cities consecutively, to interpret a resulting sequence as [[permutation]] and to store it directly in a chromosome, where one gene corresponds to the ordinal number of a city.<ref>{{Cite book |last1=Eiben |first1=A.E. |url=https://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 |series=Natural Computing Series |location=Berlin, Heidelberg |pages=67–74 |language=en |chapter=Permutation Representation |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref> Then, however, the [[Genetic operator|variation operators]] may only change the gene order and not remove or duplicate any genes.<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> The chromosome thus contains the path of a possible tour to the cities. As an example the sequence <math>3,5,7,1,4,2,9,6,8</math> of nine cities may serve, to which the following chromosome corresponds:
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align:center;"
|-
|| 3 || 5 || 7 || 1 || 4 || 2 || 9 || 6 || 8 
|} 
In addition to this encoding frequently called ''path representation'', there are several other ways of representing a permutation, for example the ''ordinal representation'' or the ''matrix representation''.<ref name=":2" /><ref>{{Cite book |last=Whitley |first=Darrell |url= |title=Evolutionary computation. Vol. 1, Basic algorithms and operators |date=2000 |publisher=Institute of Physics Pub |isbn=0-585-30560-9 |editor-last=Fogel |editor-first=David B. |location=Bristol |pages=139–150 |language=en |chapter=Permutations |oclc=45730387 |editor-last2=Bäck |editor-first2=Thomas |editor-last3=Michalewicz |editor-first3=Zbigniew}}</ref>