Evolutionary algorithm
|
|
An evolutionary algorithm (also EA, evolutionary computation, artificial evolution) is a generic term used to indicate any population-based metaheuristic optimization algorithm that uses mechanisms inspired by biological evolution, such as reproduction, mutation and recombination (see genetic operators). Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions "live" (see also fitness function). Evolution of the population then takes place after the repeated application of the above operators.
Specific examples of EAs are given below. Most of these techniques are similar in spirit, but differ in the details of their implementation and the nature of the particular problem to which they have been applied.
- Genetic algorithms - This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary), virtually always applying recombination operators in addition to selection and mutation;
- Genetic programming - Here the solutions are in the form of computer programs, and their fitness is determined by their ability to solve a computational problem;
- Evolution strategy - Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates;
- Evolutionary programming - Like genetic programming, only the structure of the program is fixed and its numerical parameters are allowed to evolve.
Because they do not make any assumption about the underlying fitness landscape, it is generally believed that evolutionary algorithms perform consistently well across all types of problems (see, however, the no-free-lunch theorem). This is evidenced by their success in fields as diverse as engineering, art, biology, economics, genetics, operations research, robotics, social sciences, physics, chemistry, and others.
Apart from their use as mathematical optimizers, evolutionary computation and algorithms have also been used as an experimental framework within which to validate theories about biological evolution and natural selection, particularly through work in the field of artificial life. Techniques from evolutionary algorithms applied to the modelling of biological evolution are generally limited to explorations of microevolutionary processes, however some computer simulations, such as Tierra and Avida, attempt to model macroevolutionary dynamics.
A limitation of evolutionary algorithms is their lack of a clear genotype-phenotype distinction. In nature, the fertilized egg cell undergoes a complex process known as embryogenesis to become a mature phenotype. This indirect encoding is believed to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve the evolvability of the organism. Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns.
Bibliography
- Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
- Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
See also
External links
- International Society for Genetic and Evolutionary Computation (http://www.isgec.org/) - Home of the largest conference on the subject, GECCO
(since January 1, 2005 reorganized to become Special Interest Group for Genetic and Evolutionary Computation (http://www.sigevo.org/) of the ACM)
- Illinois Genetic Algorithms Laboratory (IlliGAL) (http://www-illigal.ge.uiuc.edu/)
- Evolutionary Computation Repository (http://www.fmi.uni-stuttgart.de/fk/evolalg/)
- Evolutionary Computing European Network Of Excellence (http://evonet.dcs.napier.ac.uk/)
- The Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic) (http://www.faqs.org/faqs/ai-faq/genetic/part1/)
- www.talkorigins.org: Genetic Algorithms and Evolutionary Computation (http://www.talkorigins.org/faqs/genalg/genalg.html)
- Evolutionary Computation Lab at George Mason University (ECLab) (http://cs.gmu.edu/~eclab/)de:Evolutionärer_Algorithmus