Chromosome (evolutionary algorithm): Difference between revisions

Revision as of 21:10, 20 March 2023

Revision as of 00:29, 24 May 2023

Line 47:

=== 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}}</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}}</ref> The chromosmchromosome 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;"

|-