View source for Genetic algorithm

[[File:St 5-xband-antenna.jpg|thumb|The unusual form of this [[antenna]], developed by [[NASA]], was found using a genetic algorithm.]]A '''genetic algorithm''' is an [[algorithm]] that [[imitation|imitates]] the process of [[natural selection]]. They help solve [[Optimization (computer science)|optimization]] and search problems. Genetic algorithms are part of the bigger class of [[evolutionary algorithm]]s. Genetic algorithms imitate natural [[Biological process|biological processes]], such as [[Heredity|inheritance]], [[mutation]], [[Natural selection|selection]] and [[Crossing over|crossover]].

Genetic algorithms is a [[search technique]] often used in [[computer science]] to find complex, non-obvious solutions to algorithmic optimisation and search problems. Genetic algorithms are global search [[Heuristic|heuristics]].{{ref|cga}}
== What is it ==
Natural [[evolution]] can be modeled as a [[Game theory|game]], in which the rewards for an [[organism]] that plays a good game of life are the passing on of its [[DNA|genetic material]] to its [[successors]] and its continued [[Survival of the fittest|survival]].{{ref|kendell}} In natural evolution, how well an individual performs depends on who it works with and who it competes with, as well as the environment. Genetic algorithms are a [[simulation]] of natural selection on a population of candidate solutions to an [[Optimization (computer science)|optimization]] problem ([[chromosome]]s, individuals, [[Creature|creatures]], or [[Phenotype|phenotypes]]).

Candidates are [[Evaluation|evaluated]] and [[Crossbreed|crossbred]] in an attempt to make good solutions. Such solutions may take a lot of time and are not obvious to a human. An evolutionary phase is started with a [[population]] of [[Random generation|randomly generated]] beings. In each generation, the fitness of every individual in the population is evaluated. Some are [[Stochastic process|randomly]] selected from the current population (based on their fitness) and modified (recombined and possibly randomly [[Mutation|mutated]]) to form a new population. The cycle repeats with this new population. The algorithm ends either after a set number of [[Generation|generations]] have passed, or a good fitness level has been reached for the population. If the algorithm has ended due to reaching a maximum number of generations, it does not necessarily mean a good fitness level has been obtained.
== Programming this on a computer ==
The [[pseudocode]] is:

#Initialization: Some possible solutions are created; very often these will have random values
#[[Evaluation]]: A fitness function scores each solution; the score will be a number that tells how well this solution solves the problem.
#The following steps are run until the requirement to stop is met:
##Selection: Pick the solutions/individuals for the next iteration
##Recombination: Combine the solutions picked
##Mutation: Randomly change the newly created solutions
##Evaluation: Apply the fitness function, see step 2.
##If the requirement to stop is not met, re-start with the selection step.
== Example ==
The above description is abstract. A concrete example helps.
{{jargon|date=January 2024}}
== Applications ==

== In general ==
Genetic algorithms are good at solving problems that include [[Timeline|timetabling]] and scheduling. They have also been applied to [[engineering]].<ref>Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. [http://www.mdpi.com/1996-1073/6/3/1439/pdf Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II.] Energies. 2013; 6(3):1439-1455.</ref> They are often used to solve global [[Combinatorial optimization|optimization]] problems. They might be useful in problem domains that have a complex fitness landscape as mixing is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. Commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a [[Markov chain]]).

Examples of problems solved by genetic algorithms include: mirrors designed to funnel sunlight to a [[solar collector]],<ref>{{cite web|url=http://www.ted.com/talks/bill_gross_on_new_energy.html|title=A solar energy system that tracks the sun|last=Gross|first=Bill|work=TED|accessdate=20 November 2013}}</ref> [[Antenna|antennae]] designed to pick up radio signals in space,<ref>{{citation|first1=G. S.|last1=Hornby|first2=D. S.|last2=Linden|first3=J. D.|last3=Lohn|url=http://ti.arc.nasa.gov/m/pub-archive/1244h/1244%20(Hornby).pdf|title=Automated Antenna Design with Evolutionary Algorithms}}</ref> walking methods for computer figures,<ref>{{Cite web|url=http://goatstream.com/research/papers/SA2013/index.html|title=Flexible Muscle-Based Locomotion for Bipedal Creatures}}</ref> optimal design of [[Aerodynamics|aerodynamic]] bodies in complex flowfields <ref>{{Cite journal|last1=Evans|first1=B.|last2=Walton|first2=S.P.|date=December 2017|title=Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation|url=https://cronfa.swan.ac.uk/Record/cronfa34688|journal=Applied Mathematical Modelling|volume=52|pages=215–240|doi=10.1016/j.apm.2017.07.024|issn=0307-904X}}</ref>

In his ''Algorithm Design Manual'', Skiena advises against genetic algorithms for any task: ''"It is quite unnatural to model applications in terms of genetic operators like mutation and crossover on bit strings. The pseudobiology adds another level of complexity between you and your problem. Second, genetic algorithms take a very long time on nontrivial problems. [...] The analogy with evolution—where significant progress require [sic] millions of years—can be quite appropriate.
[...] I have never encountered any problem where genetic algorithms seemed to me the right way to attack it. Further, I have never seen any computational results reported using genetic algorithms that have favorably impressed me. Stick to [[simulated annealing]] for your heuristic search voodoo needs."''<ref>{{cite book |last=Skiena |first=Steven |title = The Algorithm Design Manual |url=https://archive.org/details/algorithmdesignm0000stev |publisher=Springer Science+Business Media|edition=2nd |year = 2010 |isbn=978-1-849-96720-4}}</ref>{{rp|267}}
== Board games ==
Board games are a very relevant part of the area of genetic algorithms as applied to [[game theory]] problems. Much of the early work on computational intelligence and games was directed toward classic board games, such as [[tic-tac-toe]],{{ref|yao}} [[chess]], and [[checkers]].{{ref|samuel}} Board games can now, in most cases, be played by a computer at a higher level than the best humans, even with blind exhaustive search techniques. [[Go]] is a noted exception to this tendency, and has so far resisted machine attack. The best Go computer players now play at the level of a good novice.{{ref|muller}}{{ref|bouzy}} Go strategy is said to rely heavily on [[pattern recognition]], and not just logical analysis as with chess and other more piece-independent games. The huge effective [[branching factor]] required for finding high quality solutions heavily restricts the look-ahead that can be used within a move sequence search.
== Computer games ==
The genetic algorithm can be used in [[computer games]] to create [[artificial intelligence]] (the computer plays against you). This allows for a more realistic game experience; if a human player can find a sequence of steps which always lead to success even when repeated in different games, there can be no challenge left. Conversely if a learning technique such as a genetic algorithm for a strategist can avoid repeating past mistakes, the game will have more playability.

Genetic algorithms require the following parts:

* A method for representing the challenge in terms of the solution (e.g. routing [[Soldier|soldiers]] in an attack in a strategy game)
* A fitness or evaluation function in order to determine the quality of an instance (e.g. a [[measurement]] of damage done to an opponent in such an attack).

The fitness function accepts a mutated instantiation of an entity and measures its quality. This function is customized to the problem domain. In many cases, particularly those involving code optimization, the fitness function may simply be a system timing function. Once a genetic representation and fitness function are defined, a genetic algorithm will instantiate initial candidates as described before, and then improve through repetitive application of mutation, crossover, inversion and selection operators (as defined according to the problem domain).
== Limitations ==
There are limitations of the use of a genetic algorithm compared to alternative optimization algorithms:

* Repeated fitness function evaluation for complex problems is often the most limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex problems often requires very expensive fitness function evaluations. In real world problems such as structural optimization problems, a single function evaluation may require several hours to several days of complete simulation. Typical optimization methods cannot deal with such types of problem. It is often necessary to use [[approximation]], as calculating the exact solution takes too long. Genetic algorithms sometimes combine different approximation models to solve complex real life problems.
* Genetic algorithms do not [[scale]] well. That is, where the number of elements which are exposed to mutation is large there is often an [[Exponential function|exponential]] increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or a plane. To use genetic algorithms with such problems,  they must be broken down into the simplest representation possible. For this reason, we see evolutionary algorithms encoding designs for fan blades instead of engines, building shapes instead of detailed construction plans, and airfoils instead of whole aircraft designs. The second problem of complexity is the issue of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.
* The "better" solution is only in comparison to other solutions. As a result, the stop criterion is not clear in every problem.
* In many problems, genetic algorithms have a tendency to converge towards local optima or even arbitrary points rather than the global optimum of the problem. This means that the algorithm does not "know how" to sacrifice short-term fitness to gain longer-term fitness. The likelihood of this occurring depends on the shape of the fitness function: certain problems make it easy to find the global optimum, others may make it easier for the function to find the local optima. This problem may be lessened by using a different fitness function, increasing the rate of mutation, or by using selection techniques that maintain a diverse population of solutions.<ref>{{cite journal|last1=Taherdangkoo|first1=Mohammad|last2=Paziresh|first2=Mahsa|last3=Yazdi|first3=Mehran|last4=Bagheri|first4=Mohammad Hadi|date=19 November 2012|title=An efficient algorithm for function optimization: modified stem cells algorithm|journal=Central European Journal of Engineering|volume=3|issue=1|pages=36–50|doi=10.2478/s13531-012-0047-8|s2cid=108711765}}</ref> A common technique to maintain diversity is to use a "niche penalty": any group of individuals of sufficient similarity (niche radius) have a penalty added, which will reduce the representation of that group in the following generations, permitting other (less similar) individuals to be kept in the population. This trick, however, may not be effective, depending on the landscape of the problem. Another possible technique would be to simply replace part of the population with randomly generated individuals, when most of the population is too similar to each other. Diversity is important in genetic algorithms (and [[genetic programming]]) because crossing over a homogeneous population does not yield new solutions. In [[Evolution strategy|evolution strategies]] and [[evolutionary programming]], diversity is not essential because of a greater reliance on mutation.
* Operating on dynamic data sets is difficult, as [[genome]]s begin to converge early on towards solutions which may no longer be valid for later data. Several methods have been proposed to fix this by increasing genetic diversity somehow and preventing early convergence, either by increasing the probability of mutation when the solution quality drops (called ''triggered hypermutation''), or by occasionally introducing entirely new, randomly generated elements into the [[gene pool]] (called ''random immigrants''). Again, [[Evolution strategy|evolution strategies]] and [[evolutionary programming]] can be implemented with a so-called "comma strategy" in which parents are not maintained and new parents are selected only from offspring. This can be more effective on dynamic problems.
* Genetic algorithms cannot effectively solve problems in which the only fitness measure is a single right/wrong measure (like decision problems), as there is no way to converge on the solution (no hill to climb). In these cases, a random search may find a solution as quickly as a GA. However, if the situation allows the success/failure trial to be repeated giving (possibly) different results, then the ratio of successes to failures provides a suitable fitness measure.
* For specific optimization problems and problem instances, other optimization algorithms may be more efficient than genetic algorithms in terms of speed of convergence. Alternative and complementary algorithms include [[Evolution strategy|evolution strategies]], [[evolutionary programming]], [[simulated annealing]], [[Gaussian adaptation]], [[hill climbing]], and [[swarm intelligence]] (e.g.: [[ant colony optimization]], [[particle swarm optimization]]) and methods based on integer [[linear programming]]. The suitability of genetic algorithms is dependent on the amount of knowledge of the problem; well known problems often have better, more specialized approaches.
== History ==
In 1950, [[Alan Turing]] proposed a "learning machine" which would parallel the principles of evolution.<ref name="mind.oxfordjournals.org">{{cite journal|last1=Turing|first1=Alan M.|title=Computing machinery and intelligence|journal=Mind|volume=LIX|issue=238|pages=433–460|doi=10.1093/mind/LIX.236.433|url=http://mind.oxfordjournals.org/content/LIX/236/433|date=October 1950}}</ref> Computer simulation of evolution started as early as in 1954 with the work of [[Nils Aall Barricelli]], who was using the computer at the [[Institute for Advanced Study]] in [[Princeton, New Jersey]].<ref name="Barricelli 1954 45–68">{{cite journal|last=Barricelli|first=Nils Aall|year=1954|authorlink=Nils Aall Barricelli|title=Esempi numerici di processi di evoluzione|journal=Methodos|pages=45–68}}</ref><ref name="Barricelli 1957 143–182">{{cite journal|last=Barricelli|first=Nils Aall|year=1957|authorlink=Nils Aall Barricelli|title=Symbiogenetic evolution processes realized by artificial methods|journal=Methodos|pages=143–182}}</ref>  His 1954 publication was not widely noticed. Starting in 1957,<ref name="Fraser 1957 484–491">{{cite journal|last=Fraser|first=Alex|authorlink=Alex Fraser (scientist)|year=1957|title=Simulation of genetic systems by automatic digital computers. I. Introduction|journal=Aust. J. Biol. Sci.|volume=10|issue=4|pages=484–491|doi=10.1071/BI9570484}}</ref>  the Australian quantitative geneticist [[Alex Fraser (scientist)|Alex Fraser]] published a series of papers on simulation of [[artificial selection]] of organisms with multiple [[loci]] controlling a measurable [[trait]]. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970)<ref name="Fraser 1970">{{cite book|last1=Fraser|first1=Alex|authorlink=Alex Fraser (scientist)|first2=Donald |last2=Burnell|year=1970|title=Computer Models in Genetics|url=https://archive.org/details/computermodelsin00unse|publisher=McGraw-Hill|location=New York|isbn=978-0-07-021904-5}}</ref> and Crosby (1973).<ref name="Crosby 1973">{{cite book|last=Crosby|first=Jack L.|year=1973|title=Computer Simulation in Genetics|url=https://archive.org/details/computersimulati0000cros|publisher=John Wiley & Sons|location=London|isbn=978-0-471-18880-3}}</ref> Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, [[Hans-Joachim Bremermann]] published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms.<ref>[http://berkeley.edu/news/media/releases/96legacy/releases.96/14319.html 02.27.96 - UC Berkeley's Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69<!-- Bot generated title -->]</ref> Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by [[David B. Fogel|Fogel]] (1998).<ref>{{cite book|editor-last=Fogel|editor-first=David B. |year=1998|title=Evolutionary Computation: The Fossil Record|url=https://archive.org/details/evolutionarycomp0000unse_w3y7|publisher=IEEE Press|location=New York|isbn=978-0-7803-3481-6}}</ref>

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game,<ref>{{cite journal|last=Barricelli|first=Nils Aall|year=1963|title=Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life|journal=Acta Biotheoretica|volume=16|issue=3–4|pages=99–126|doi=10.1007/BF01556602|s2cid=86717105}}</ref> [[artificial evolution]] became a widely recognized optimization method as a result of the work of [[Ingo Rechenberg]] and [[Hans-Paul Schwefel]] in the 1960s and early 1970s &ndash; Rechenberg's group was able to solve complex engineering problems through [[Evolution strategy|evolution strategies]].<ref>{{cite book|last=Rechenberg|first=Ingo|year=1973|title=Evolutionsstrategie|place=Stuttgart|publisher=Holzmann-Froboog|isbn=978-3-7728-0373-4}}</ref><ref>{{cite book|last=Schwefel|first=Hans-Paul|year=1974|title=Numerische Optimierung von Computer-Modellen (PhD thesis)}}</ref><ref>{{cite book|last=Schwefel|first=Hans-Paul|year=1977|title=Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie|place=Basel; Stuttgart | publisher=Birkhäuser| isbn=978-3-7643-0876-6}}</ref><ref>{{cite book|last=Schwefel|first=Hans-Paul|year=1981|title=Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie)|url=https://archive.org/details/numericaloptimiz0000schw|place=Chichester ; New York|publisher=Wiley|isbn=978-0-471-09988-8}}</ref>  Another approach was the evolutionary programming technique of [[Lawrence J. Fogel]], which was proposed for generating artificial intelligence. [[Evolutionary programming]] originally used [[Finite-state machine|finite state machines]] for predicting environments, and used [[variation]] and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of [[John Henry Holland|John Holland]] in the early 1970s, and particularly his book ''Adaptation in Natural and Artificial Systems'' (1975). His work originated with studies of [[cellular automata]], conducted by [[John Henry Holland|Holland]] and his students at the [[University of Michigan]]. Holland introduced a formalized [[framework]] for predicting the quality of the next generation, known as [[Holland's schema theorem]]. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in [[Pittsburgh, Pennsylvania]].
== References ==
# {{note|cga}} Herrera, F.; Lozano, M.; and Verdegay, J. L. 1998. Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis. Artif. Intell. Rev. 12(4):265–319.
# {{note|kendell}} Lucas, S., and Kendell, G. 2006. Evolutionary computation and games. In IEEE Comput Intell Mag. February, 10–18. IEEE.
# {{note|yao}} Yao, X. Recent new development in evolutionary programming.
# {{note|samuel}} Samuel, A. L. 1995. Some studies in machine learning using the game of checkers. 71–105.
# {{note|muller}} Muller, M. 2002. Computer go. Artif. Intell. 134(1-2):145–179.
# {{note|bouzy}} Bouzy, B., and Cazenave, T. 2001. Computer go: an AI oriented survey. Artificial Intelligence 132:39–103.
== Sources ==
{{reflist}}

[[Category:Artificial intelligence]]