Chromosome (evolutionary algorithm): Difference between revisions

Revision as of 10:07, 25 June 2023

Latest revision as of 18:55, 17 July 2025

(14 intermediate revisions by 6 users not shown)

Line 2:

{{Evolutionary algorithms}}

InA [[genetic algorithm]]s (GA),'''chromosome''' or more'''genotype''' general,in [[evolutionary algorithm]]s (EA), a '''chromosome''' (also sometimes called a '''[[genotype]]''') is a set of parameters which define a proposed solution of the problem that the evolutionary algorithm is trying to solve. The set of all solutions, also called ''individuals'' according to the biological model, is known as the ''[[Population model (evolutionary algorithm)|population]]''.<ref name=ga-description>{{cite web|title=Introduction to genetic algorithms: IV. Genetic Algorithm|url=http://www.obitko.com/tutorials/genetic-algorithms/ga-basic-description.php|accessdate=12 August 2015}}</ref><ref name=":0">{{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=28–34 |language=en |chapter=Components of Evolutionary Algorithms |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref> The genome of an individual consists of one, more rarely of several,<ref>{{Citation |last=Baine |first=Nicholas |title=A simple multi-chromosome genetic algorithm optimization of a Proportional-plus-Derivative Fuzzy Logic Controller |date=2008 |url=https://ieeexplore.ieee.org/document/4531273 |work=NAFIPS 2008 - 2008 Annual Meeting of the North American Fuzzy Information Processing Society |pages=1–5 |publisher=IEEE |doi=10.1109/NAFIPS.2008.4531273 |isbn=978-1-4244-2351-4 |s2cid=46591432 }}</ref><ref>{{Citation |last1=Peng |first1=Jin |last2=Chu |first2=Zhang Shu |title=A Hybrid Multi-chromosome Genetic Algorithm for the Cutting Stock Problem |date=2010 |url=https://ieeexplore.ieee.org/document/5694457 |work=3rd International Conference on Information Management, Innovation Management and Industrial Engineering |pages=508–511 |publisher=IEEE |doi=10.1109/ICIII.2010.128 |isbn=978-1-4244-8829-2 |s2cid=15608610 }}</ref> chromosomes and corresponds to the [[genetic representation]] of the task to be solved. A chromosome is composed of a set of genes, where a gene consists of one or more semantically connected [[Parameter|parameters]], which are often also called ''decision variables''. They determine one or more [[Phenotype|phenotypic]] characteristics of the individual or at least have an influence on them.<ref name=":0" /> In the basic form of genetic algorithms, the chromosome is represented as a binary [[string (computer science)|string]],<ref>{{Cite book |last=Holland |first=John H. |url= |title=Adaptation in natural and artificial systems |date=1992 |publisher=MIT Press |isbn=0-585-03844-9 |edition= |___location=Cambridge, Mass. |language=en |oclc=42854623}}</ref> while in later variants<ref>{{Citation |last1=Janikow |first1=C.Z. |title=An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms |date=1991 |url=http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |work=Proceedings of the Fourth International Conference on Genetic Algorithms |pages=31–36 |editor-last=Belew |editor-first=Richard K. |editor2-last=Booker |editor2-first=Lashon B. |place=San Francisco, CA |publisher=Morgan Kaufmann Publishers |isbn=1-55860-208-9 |last2=Michalewicz |first2=Z.}}</ref><ref name=ga-tutorial>{{cite journal |last1=Whitley |first1=Darrell |title=A genetic algorithm tutorial |journal=Statistics and Computing |date=June 1994 |volume=4 |issue=2 |doi=10.1007/BF00175354 |citeseerx=10.1.1.184.3999| s2cid=3447126}}<!--|accessdate=12 August 2015--></ref> and in EAs in general, a wide variety of other [[data structure]]s are used.<ref name=":1">{{Cite journal |last=Whitley |first=Darrell |date=2001 |title=An overview of evolutionary algorithms: practical issues and common pitfalls |url=https://linkinghub.elsevier.com/retrieve/pii/S0950584901001884 |journal=Information and Software Technology |language=en |volume=43 |issue=14 |pages=817–831 |doi=10.1016/S0950-5849(01)00188-4|s2cid=18637958 |url-access=subscription }}</ref><ref>{{Citation |last1=Bäck |first1=Thomas |last2=Hoffmeister |first2=Frank |last3=Schwefel |first3=Hans-Paul |title=A Survey of Evolution Strategies |date=1991 |url=https://www.academia.edu/27025389 |work=Proceedings of the Fourth International Conference on Genetic Algorithms |pages=2–9 |editor-last=Belew |editor-first=Richard K. |editor2-last=Booker |editor2-first=Lashon B. |place=San Francisco, CA |publisher=Morgan Kaufmann Publishers |isbn=1-55860-208-9 }}</ref><ref name=":5">{{Cite book |last=Koza |first=John R. |url=https://www.worldcat.org/oclc/26263956 |title=Genetic programming : on the programming of computers by means of natural selection |date=1992 |publisher=MIT Press |isbn=0-262-11170-5 |___location=Cambridge, Mass. |oclc=26263956}}</ref>

==Chromosome design==

When creating the [[genetic representation]] of a task, it is determined which decision variables and other degrees of freedom of the task should be improved by the EA and possible additional heuristics and how the [[Genetic representation#Distinction between search space and problem space|genotype-phenotype mapping]] should look like. The design of a chromosome translates these considerations into concrete data structures for which an EA then has to be selected, configured, extended, or, in the worst case, created. Finding a suitable [[Genetic representation|representation]] of the problem ___domain for a chromosome is an important consideration, as a good representation will make the search easier by limiting the [[Genetic representation#Distinction between search space and problem space|search space]]; similarly, a poorer representation will allow a larger search space.<ref name=ga-notes>{{cite web|title=Genetic algorithms|url=http://www.cse.unsw.edu.au/~billw/cs9414/notes/ml/05ga/05ga.html|accessdate=12 August 2015|archive-date=22 October 2019|archive-url=https://web.archive.org/web/20191022162416/http://www.cse.unsw.edu.au/~billw/cs9414/notes/ml/05ga/05ga.html|url-status=dead}}</ref> In this context, suitable [[mutation (genetic algorithm)|mutation]] and [[crossover (genetic algorithm)|crossover]] [[genetic operator|operators]]<ref name=":0" /> must also be found or newly defined to fit the chosen chromosome design. An important requirement for these operators is that they not only allow all points in the search space to be reached in principle, but also make this as easy as possible.<ref>{{Cite book |last=Rothlauf |first=Franz |url=http://link.springer.com/10.1007/978-3-642-88094-0 |title=Representations for Genetic and Evolutionary Algorithms |date=2002 |publisher=Physica-Verlag HD |isbn=978-3-642-88096-4 |series=Studies in Fuzziness and Soft Computing |volume=104 |___location=Heidelberg |pages=31 |doi=10.1007/978-3-642-88094-0}}</ref><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=49–51 |language=en |chapter=Representation and the Roles of Variation Operators |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref>

The following requirements must be met by a well-suited chromosome:

Line 12:

* Design of the chromosome in such a way that it covers only the search space and no additional areas. so that there is no [[Genetic representation#Redundancy|redundancy]] or only as little redundancy as possible.

* Observance of [[Causality conditions|strong causality]]: small changes in the chromosome should only lead to small changes in the phenotype.<ref>{{Cite journalbook |last1=Galván-López |first1=Edgar |last2=McDermott |first2=James |last3=O'Neill |first3=Michael |last4=Brabazon |first4=Anthony |datetitle=2010-07-07Proceedings of the 12th annual conference on Genetic and evolutionary computation |titlechapter=Towards an understanding of locality in genetic programming |date=2010-07-07 |chapter-url=https://dl.acm.org/doi/10.1145/1830483.1830646 |journal=Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation |language=en |___location=Portland Oregon USA |publisher=ACM |pages=901–908 |doi=10.1145/1830483.1830646 |isbn=978-1-4503-0072-8|s2cid=15348983 |url=https://mural.maynoothuniversity.ie/15390/1/EG_towards.pdf }}</ref> This is also called [[Genetic representation#Locality|locality]] of the relationship between search and problem space.

* Designing the chromosome in such a way that it excludes prohibited regions in the search space completely or as much as possible.

While the first requirement is indispensable, depending on the application and the EA used, one usually only has to be satisfied with fulfilling the remaining requirements as far as possible. It should be noted, however, that theThe evolutionary search is supported and possibly considerably accelerated by a fulfillment as complete as possible.

== Examples of chromosomes ==

=== Chromosomes for binary codings ===

In their classical form, GAs use bit strings and map the decision variables to be optimized onto them. An example for one booleanBoolean and three integer decision variables with the value ranges <math>0 \leq D_1 \leq 60</math>, <math>28 \leq D_2 \leq 30</math> and <math>-12 \leq D_3 \leq 14</math> may illustrate this:

{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none; text-align:center;"

Line 44:

=== Chromosomes with real-valued or integer genes ===

For the processing of tasks with real-valued or mixed-integer decision variables, EAs such as the [[evolution strategy]]<ref name=":3">{{Cite book |last=Schwefel |first=Hans-Paul |url=https://www.researchgate.net/publication/220690578 |title=Evolution and optimum seeking |date=1995 |publisher=John Wiley & Sons |isbn=0-471-57148-2 |___location=New York |oclc=30701094}}</ref> or the real-coded GAs<ref>{{Citation |last1=Eshelman |first1=Larry J. |title=Real-Coded Genetic Algorithms and Interval-Schemata |date=1993 |url=https://linkinghub.elsevier.com/retrieve/pii/B9780080948324500180 |work=Foundations of Genetic Algorithms |volume=2 |pages=187–202 |publisher=Elsevier |language=en |doi=10.1016/b978-0-08-094832-4.50018-0 |isbn=978-0-08-094832-4 |access-date=2023-01-26 |last2=Schaffer |first2=J. David|url-access=subscription }}</ref><ref>{{Cite book |last=Michalewicz |first=Zbigniew |url= |title=Genetic Algorithms + Data Structures = Evolution Programs |date=1996 |publisher=Springer |others=Third, revised and extended edition |isbn=978-3-662-03315-9 |edition= |___location=Berlin, Heidelberg |language=en |oclc=851375253}}</ref><ref>{{Cite journal |last1=Deep |first1=Kusum |last2=Singh |first2=Krishna Pratap |last3=Kansal |first3=M.L. |last4=Mohan |first4=C. |date=June 2009 |title=A real coded genetic algorithm for solving integer and mixed integer optimization problems |url=https://linkinghub.elsevier.com/retrieve/pii/S0096300309001830 |journal=Applied Mathematics and Computation |language=en |volume=212 |issue=2 |pages=505–518 |doi=10.1016/j.amc.2009.02.044|url-access=subscription }}</ref> are suited. In the case of mixed-integer values, rounding is often used, but this represents some violation of the [[Genetic representation#Relationships between search space and problem space|redundancy requirement]]. If the necessary precisions of the real values can be reasonably narrowed down, this violation can be remedied by using integer-coded GAs.<ref>{{Citation |last1=Wang |first1=Fuchang |title=Decimal-Integer-Coded Genetic Algorithm for Trimmed Estimator of the Multiple Linear Errors in Variables Model |date=2011 |url=http://link.springer.com/10.1007/978-3-642-25255-6_46 |work=Information Computing and Applications |pages=359–366 |editor-last=Liu |editor-first=Baoxiang |series=LNCS 7030 |place=Berlin, Heidelberg |publisher=Springer |doi=10.1007/978-3-642-25255-6_46 |isbn=978-3-642-25254-9 |access-date=2023-01-23 |last2=Cao |first2=Huirong |last3=Qian |first3=Xiaoshi |editor2-last=Chai |editor2-first=Chunlai|url-access=subscription }}</ref><ref>{{Cite journal |last1=Cheng |first1=Xueli |last2=An |first2=Linchao |last3=Zhang |first3=Zhenhua |date=2019 |title=Integer Encoding Genetic Algorithm for Optimizing Redundancy Allocation of Series-parallel Systems |url=https://pdfs.semanticscholar.org/3169/6663ab35e700aa21a748878b150adddc770f.pdf |journal=Journal of Engineering Science and Technology Review |volume=12 |issue=1 |pages=126–136|doi=10.25103/JESTR.121.15 |s2cid=149497992 |doi-access=free }}</ref> For this purpose, the valid digits of real values are mapped to integers by multiplication with a suitable factor. For example, 12.380 becomes the integer 12380 by multiplying by 1000. This must of course be taken into account in genotype-phenotype mapping for evaluation and result presentation. A common form is a chromosome consisting of a list or an array of integer or real values.

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

|-

Line 60:

=== Chromosomes for complex representations ===

The chromosomes presented above are well suited for processing tasks of continuous, mixed-integer, pure-integer or combinatorial optimization. For a combination of these optimization areas, on the other hand, it becomes increasingly difficult to map them to simple strings of values, depending on the task. The following extension of the gene concept is proposed by the EA GLEAM (General Learning Evolutionary Algorithm and Method) for this purpose:<ref name=":4">{{Citation |last1=Blume |first1=Christian |last2=Jakob |first2=Wilfried |title=GLEAM - An Evolutionary Algorithm for Planning and Control Based on Evolution Strategy |date=2002 |url=https://publikationen.bibliothek.kit.edu/170053025/3814288 |work=Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) |volume=Late Breaking Papers |pages=31–38 |access-date=2023-01-01 }}</ref> A gene is considered to be the description of an element or elementary trait of the phenotype, which may have multiple parameters. For this purpose, gene types are defined that contain as many parameters of the appropriate data type as are required to describe the particular element of the phenotype. A chromosome now consists of genes as data objects of the gene types, whereby, depending on the application, each gene type occurs exactly once as a gene or can be contained in the chromosome any number of times. The latter leads to chromosomes of dynamic length, as they are required for some problems.<ref>{{Cite journal |last1=Pawar |first1=Sunil Nilkanth |last2=Bichkar |first2=Rajankumar Sadashivrao |date=June 2015 |title=Genetic algorithm with variable length chromosomes for network intrusion detection |url=http://link.springer.com/10.1007/s11633-014-0870-x |journal=International Journal of Automation and Computing |language=en |volume=12 |issue=3 |pages=337–342 |doi=10.1007/s11633-014-0870-x |s2cid=255346767 |issn=1476-8186|doi-access=free }}</ref><ref>{{Citation |last=Blume |first=Christian |title=Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM |date=2000 |url=http://link.springer.com/10.1007/3-540-45561-2_32 |work=Real-World Applications of Evolutionary Computing |series=Lecture Notes in Computer Science |volume=1803 |pages=330–341 |editor-last=Cagnoni |editor-first=Stefano |access-date=2023-06-25 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/3-540-45561-2_32 |isbn=978-3-540-67353-8|url-access=subscription }}</ref> The gene type definitions also contain information on the permissible value ranges of the gene parameters, which are observed during chromosome generation and by corresponding mutations, so they cannot lead to lethal mutations. For tasks with a combinatorial part, there are suitable [[Genetic operator|genetic operators]] that can move or reposition genes as a whole, i.e. with their parameters.

[[File:Genmodell Chromosombeispiel.png|thumb|212x212px|Three exemplary genes matching the adjacent gene type definitions in a chromosome organized as a list]]

[[File:Gene model gene types.png|left|thumb|224x224px|Three exemplary genes matching the adjacent gene type definitions in a chromosome organized as a list]]

Line 67:

[[File:Genetic Program Tree.png|thumb|214x214px|Syntax tree of a formula example]]

=== Chromosomes for tree representations ===

Tree representations in a chromosome are used by [[genetic programming]], an EA type for generating [[Computer program|computer programs]] or [[Electronic circuit|circuits]].<ref name=":5" /> The trees correspond to the [[Parse tree|syntax trees]] generated by a [[compiler]] as internal representation when translating a computer program. The adjacent figure shows the syntax tree of a mathematical expression as an example. Mutation operators can rearrange, change or delete subtrees depending on the represented syntax structure. Recombination is performed by exchanging suitable subtrees.<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=75–78 |language=en |chapter=Tree Representation |doi=10.1007/978-3-662-44874-8|s2cid=20912932 }}</ref>

== Bibliography ==

Line 74:

* Kenneth A. de Jong (2006): ''Evolutionary Computation: A Unified Approach.'' MIT Press, Cambridge, MA. {{ISBN|0-262-04194-4}}

* Melanie Mitchell (1996): ''An Introduction to Genetic Algorithms.'' MIT Press, Cambridge MA. {{ISBN|978-0-262-63185-3}}

* Hans-Paul Schwefel (1995): ''[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking Evolution and Optimum Seeking]''. Wiley & Sons, New York. {{ISBN|0-471-57148-2}}

== References ==

Line 81:

{{DEFAULTSORT:Chromosome (Genetic Algorithm)}}

[[Category:Evolutionary algorithms]]

[[Category:Genetic algorithms]]