Editing Genetic algorithm (section)

== Variants ==

=== Chromosome representation ===
{{main | genetic representation }}
The simplest algorithm represents each chromosome as a [[Bit array|bit string]]. Typically, numeric parameters can be represented by [[integer]]s, though it is possible to use [[floating point]] representations. The floating point representation is natural to [[Evolution strategy|evolution strategies]] and [[evolutionary programming]]. The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by [[John Henry Holland]] in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a [[linked list]], [[associative array|hashes]], [[object (computer science)|objects]], or any other imaginable [[data structure]]. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

When bit-string representations of integers are used, [[Gray coding]] is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so-called ''Hamming walls'', in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real-valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a ''virtual alphabet'' (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation.<ref name=Goldberg1991>{{cite book|last=Goldberg|first=David E.|title=Parallel Problem Solving from Nature|chapter=The theory of virtual alphabets|journal=Parallel Problem Solving from Nature, Lecture Notes in Computer Science|year=1991|volume=496|pages=13–22|doi=10.1007/BFb0029726|series=Lecture Notes in Computer Science|isbn=978-3-540-54148-6}}</ref><ref name=Janikow1991>{{cite journal|last1=Janikow|first1=C. Z.|first2=Z. |last2=Michalewicz |title=An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms|journal=Proceedings of the Fourth International Conference on Genetic Algorithms|year=1991|pages=31–36|url=http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.cs.umsl.edu/~janikow/publications/1991/GAbin/text.pdf |archive-date=2022-10-09 |url-status=live|access-date=2 July 2013}}</ref>

An expansion of the Genetic Algorithm accessible problem domain can be obtained through more complex encoding of the solution pools by concatenating several types of heterogenously encoded genes into one chromosome.<ref name=Patrascu2014>{{cite journal|last1=Patrascu|first1=M.|last2=Stancu|first2=A.F.|last3=Pop|first3=F.|title=HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation|journal=Soft Computing|year=2014|volume=18|issue=12|pages=2565–2576|doi=10.1007/s00500-014-1401-y|s2cid=29821873}}</ref> This particular approach allows for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

Another important expansion of the Genetic Algorithm (GA) accessible solution space was driven by the need to make representations amenable to variable levels of knowledge about the solution states. Variable-length representations were inspired by the observation that, in nature, evolution tends to progress from simpler organisms to more complex ones—suggesting an underlying rationale for embracing flexible structures.<ref>Goldberg, D.E., Korb, B., & Deb, K. (1989). Messy Genetic Algorithms: Motivation, Analysis, and First Results. Complex Systems, 3(5), 493–530. ISSN 0891-2513.</ref> A second, more pragmatic motivation was that most real-world engineering and knowledge-based problems do not naturally conform to rigid knowledge structures.<ref>Davidor, Y. (1991). Genetic Algorithms and Robotics: A Heuristic Strategy for Optimization. World Scientific Series in Robotics and Intelligent Systems: Volume 1.</ref>

These early innovations in variable-length representations laid essential groundwork for the development of [[Genetic programming]], which further extended the classical GA paradigm. Such representations required enhancements to the simplistic genetic operators used for fixed-length chromosomes, enabling the emergence of more sophisticated and adaptive GA models.

=== Elitism ===
A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as ''elitist selection'' and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.<ref>{{cite conference |last1=Baluja |first1=Shumeet |first2=Rich |last2=Caruana |title=Removing the genetics from the standard genetic algorithm |conference=[[International Conference on Machine Learning|ICML]] |year=1995 |url=http://www.ri.cmu.edu/pub_files/pub2/baluja_shumeet_1995_1/baluja_shumeet_1995_1.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.ri.cmu.edu/pub_files/pub2/baluja_shumeet_1995_1/baluja_shumeet_1995_1.pdf |archive-date=2022-10-09 |url-status=live}}</ref>

=== Parallel implementations ===
[[parallel algorithm|Parallel]] implementations of genetic algorithms come in two flavors. Coarse-grained parallel genetic algorithms assume a population on each of the computer nodes and migration of individuals among the nodes. Fine-grained parallel genetic algorithms assume an individual on each processor node which acts with neighboring individuals for selection and reproduction.
Other variants, like genetic algorithms for [[online optimization]] problems, introduce time-dependence or noise in the fitness function.

=== Adaptive GAs ===
Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (pm) greatly determine the degree of solution accuracy and the convergence speed that genetic algorithms can obtain. Researchers have analyzed GA convergence analytically.<ref>{{Cite journal |last1=Stannat |first1=W. |title=On the convergence of genetic algorithms – a variational approach |journal=Probab. Theory Relat. Fields |volume=129 |pages=113–132 |year=2004 |doi=10.1007/s00440-003-0330-y|s2cid=121086772 |doi-access=free }}</ref><ref>{{Cite journal |last1=Sharapov |first1=R.R. |last2=Lapshin |first2=A.V. |title=Convergence of genetic algorithms |journal=Pattern Recognit. Image Anal. |volume=16 |pages=392–397 |year=2006 |issue=3 |doi=10.1134/S1054661806030084|s2cid=22890010 }}</ref>

Instead of using fixed values of ''pc'' and ''pm'', AGAs utilize the population information in each generation and adaptively adjust the ''pc'' and ''pm'' in order to maintain the population diversity as well as to sustain the convergence capacity. In AGA (adaptive genetic algorithm),<ref>{{Cite journal |last1=Srinivas |first1=M. |last2=Patnaik |first2=L. |title=Adaptive probabilities of crossover and mutation in genetic algorithms |journal=IEEE Transactions on Systems, Man, and Cybernetics |volume=24 |issue=4 |pages=656–667 |year=1994 |doi=10.1109/21.286385 |url=http://eprints.iisc.ac.in/6971/2/adaptive.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://eprints.iisc.ac.in/6971/2/adaptive.pdf |archive-date=2022-10-09 |url-status=live }}</ref> the adjustment of ''pc'' and ''pm'' depends on the fitness values of the solutions. There are more examples of AGA variants: Successive zooming method is an early example of improving convergence.<ref>{{Cite journal |last1=Kwon |first1=Y.D. |last2=Kwon |first2=S.B. |last3=Jin |first3=S.B. |last4=Kim |first4=J.Y. |title=Convergence enhanced genetic algorithm with successive zooming method for solving continuous optimization problems |journal=Computers & Structures |volume=81 |issue=17  |pages=1715–1725 |year=2003 |doi=10.1016/S0045-7949(03)00183-4}}</ref> In ''CAGA'' (clustering-based adaptive genetic algorithm),<ref>{{cite journal |last1=Zhang |first1=J. |last2=Chung |first2=H. |last3=Lo, W. L. |title=Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms |journal=IEEE Transactions on Evolutionary Computation |volume=11 |issue=3 |pages=326&ndash;335 |year=2007 |doi=10.1109/TEVC.2006.880727 |s2cid=2625150 }}</ref> through the use of clustering analysis to judge the optimization states of the population, the adjustment of ''pc'' and ''pm'' depends on these optimization states. Recent approaches use more abstract variables for deciding ''pc'' and ''pm''. Examples are dominance & co-dominance principles<ref>{{Cite journal |last1=Pavai |first1=G. |last2=Geetha |first2=T.V. |title= New crossover operators using dominance and co-dominance principles for faster convergence of genetic algorithms|journal=Soft Comput  |volume=23 |pages=3661–3686  |year=2019 |issue=11 |doi=10.1007/s00500-018-3016-1|s2cid=254028984 }}</ref> and LIGA (levelized interpolative genetic algorithm), which combines a flexible GA with modified A* search to tackle search space anisotropicity.<ref>{{Cite journal |last1=Li |first1=J.C.F. |last2=Zimmerle |first2=D. |last3=Young |first3=P. |title=Flexible networked rural electrification using levelized interpolative genetic algorithm |journal=Energy & AI |volume=10 |pages=100186 |year=2022 |doi=10.1016/j.egyai.2022.100186|s2cid=250972466 |doi-access=free |bibcode=2022EneAI..1000186L }}</ref>

It can be quite effective to combine GA with other optimization methods. A GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as [[Hill climbing|simple hill climbing]]) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA {{Citation needed|date=July 2016}} while overcoming the lack of robustness of hill climbing.

This means that the rules of genetic variation may have a different meaning in the natural case. For instance &ndash; provided that steps are stored in consecutive order &ndash; crossing over may sum a number of steps from maternal DNA adding a number of steps from paternal DNA and so on. This is like adding vectors that more probably may follow a ridge in the phenotypic landscape. Thus, the efficiency of the process may be increased by many orders of magnitude. Moreover, the [[Chromosomal inversion|inversion operator]] has the opportunity to place steps in consecutive order or any other suitable order in favour of survival or efficiency.<ref>See for instance [http://www.thisurlisfalse.com/evolution-in-a-nutshell/ Evolution-in-a-nutshell] {{Webarchive|url=https://web.archive.org/web/20160415193505/http://www.thisurlisfalse.com/evolution-in-a-nutshell/ |date=15 April 2016 }} or example in [[travelling salesman problem]], in particular the use of an [[edge recombination operator]].</ref>

A variation, where the population as a whole is evolved rather than its individual members, is known as gene pool recombination.

A number of variations have been developed to attempt to improve performance of GAs on problems with a high degree of fitness epistasis, i.e. where the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the Building Block Hypothesis in adaptively reducing disruptive recombination. Prominent examples of this approach include the mGA,<ref>{{cite journal |url=http://www.complex-systems.com/issues/03-5.html |first1=D. E. |last1=Goldberg |first2=B. |last2=Korb |first3=K. |last3=Deb |title=Messy Genetic Algorithms : Motivation Analysis, and First Results |journal=Complex Systems |volume=5 |issue=3 |pages=493–530 |year=1989 }}</ref> GEMGA<ref>[https://www.osti.gov/servlets/purl/524858 Gene expression: The missing link in evolutionary computation]</ref> and LLGA.<ref>{{cite thesis |last=Harik |first=G. |date=1997 |title=Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms |type=PhD |publisher=Dept. Computer Science, University of Michigan, Ann Arbour |url=http://portal.acm.org/citation.cfm?id=269517 }}</ref>