Evolutionary algorithm

Evolutionary algorithm

In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the environment within which the solutions "live" (see also cost function). Evolution of the population then takes place after the repeated application of the above operators. "Artificial evolution" (AE) describes a process involving individual "evolutionary algorithm"s; EAs are individual components that participate in an AE.

Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape; this generality is shown by successes in fields as diverse as engineering, art, biology, economics, marketing, genetics, operations research, robotics, social sciences, physics, politics and chemistryFact|date=September 2008.

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 possible limitation of many 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 Fact|date=July 2008 to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve Fact|date=July 2008 the evolvability of the organism. Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns.

Implementation of biological processes

Usually, an initial population of randomly generated candidate solutions comprise the first generation. The fitness function is applied to the candidate solutions and any subsequent offspring. Two main classes of fitness functions exist: one where the fitness function does not change, as in optimizing a fixed function or testing with a fixed set of test cases; and one where the fitness function is mutable, as in using niche differentiation or co-evolving the set of test cases.

In selection, parents for the next generation are chosen with a bias towards higher fitness. The parents reproduce by copying with recombination and/or mutation. Recombination acts on the two selected parents (candidates) and results in one or two children (new candidates). Mutation acts on one candidate and results in a new candidate. These operators create the offspring (a set of new candidates). These new candidates compete with old candidates for their place in the next generation (survival of the fittest).

This process can be repeated until a candidate with sufficient quality (a solution) is found or a previously defined computational limit is reached.

Evolutionary algorithm techniques

Similar techniques differ in the implementation details and the nature of the particular applied problem.
*Genetic algorithm - This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary, although the best representations are usually those that reflect something about the problem being solved), by applying operators such as recombination and mutation (sometimes one, sometimes both). This type of EA is often used in optimization problems;
*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.
*Evolutionary programming - Like genetic programming, only the structure of the program is fixed and its numerical parameters are allowed to evolve;
*Evolution strategy - Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates;

Related techniques

*Differential evolution - Based on vector differences and is therefore primarily suited for numerical optimization problems.
*Particle swarm optimization - Based on the ideas of animal flocking behaviour. Also primarily suited for numerical optimization problems.
*Ant colony optimization - Based on the ideas of ant foraging by pheromone communication to form path. Primarily suited for combinatorial optimization problems.
*Invasive weed optimization algorithm - Based on the ideas of weed colony behavior in searching and finding a suitable place for growth and reproduction.
*Harmony search - Based on the ideas of musicians behavior in searching for better harmonies. This algorithm is suitable for combinatorial optimization as well as parameter optimization.
*Gaussian adaptation - Based on information theory. Used for maximization of manufacturing yield, mean fitness or average information. See for instance Entropy in thermodynamics and information theory.

Bibliography

* Ashlock, D. (2006), "Evolutionary Computation for Modeling and Optimization", Springer, ISBN 0-387-22196-4.
* Bäck, T. (1996), "Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms", Oxford Univ. Press.
* Bäck, T., Fogel, D., Michalewicz, Z. (1997), "Handbook of Evolutionary Computation", Oxford Univ. Press.
* Eiben, A.E., Smith, J.E. (2003), "Introduction to Evolutionary Computing", Springer.
* Holland, J. H. (1975), "Adaptation in Natural and Artificial Systems", The University of Michigan Press, Ann Arbor
*cite book | author=Poli, R., Langdon, W. B., McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming | publisher=Lulu.com, freely available from the internet | isbn = 978-1-4092-0073-4
* Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
* Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).

ee also

* Developmental biology
* Evolutionary computation
* Evolutionary robotics
* Fitness landscape
* Genetic operators
* Interactive evolutionary computation
* No free lunch in search and optimization
* Program synthesis

External links

* [http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming] by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.
* [http://www.dna-evolutions.com/dnaappletsample.html Demo applet of an evolutionary algorithm for solving TSP's and VRPTW problems]
* [http://www.isgec.org/ International Society for Genetic and Evolutionary Computation] - Home of the largest conference on the subject, GECCO (since January 1, 2005 reorganized to become [http://www.sigevo.org/ Special Interest Group for Genetic and Evolutionary Computation] of the ACM)
* [http://www-illigal.ge.uiuc.edu/ Illinois Genetic Algorithms Laboratory (IlliGAL)]
* [http://www.tik.ee.ethz.ch/sop/index.php The Systems Optimization Group (SOP)]
* [http://www.iitk.ac.in/kangal/ Kanpur Genetic Algorithms Laboratory (KanGAL)]
* [http://www.fmi.uni-stuttgart.de/fk/evolalg/ Evolutionary Computation Repository]
* [http://evonet.dcs.napier.ac.uk/ Evolutionary Computing European Network Of Excellence]
* [http://www.faqs.org/faqs/ai-faq/genetic/part1/ Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic)]
* [http://www.tuppas.com/Artificial-Intelligence/Artificial-Intelligence.htm Evolutionary computation in manufacturing scheduling]
* [http://www.talkorigins.org/faqs/genalg/genalg.html www.talkorigins.org: Genetic Algorithms and Evolutionary Computation]
* [http://cs.gmu.edu/~eclab/ Evolutionary Computation Lab at George Mason University (ECLab)]
* [http://cilib.sourceforge.net CILib] - GPLed computational intelligence simulation and research environment written in Java, includes various EC implementations
* [http://www.greythumb.org/wiki/Nanopond Nanopond (Grey Thumb)] - A very tiny (less than 1000 lines of C!) evolvable instruction set virtual machine that exhibits striking emergent behaviors.
* [http://eodev.sourceforge.net Evolving Objects] - GPLed C++ framework for evolutionary computation
* [http://www.it-weise.de/projects/book.pdf E-Book] - Global Optimization Algorithms - Theory and Application
* [http://www.economist.com/science/tq/displaystory.cfm?story_id=9896323 Economist article] - a showcase of real-world EA examples
* [http://www.softcomputing.es/en/home.php European Centre for Soft Computing]
* [http://dssg.cs.umb.edu/wiki/index.php/BiSNET/e BiSNET/e: A Cognitive Sensor Networking Architecture with Evolutionary Multiobjective Optimization]
* [http://dssg.cs.umb.edu/wiki/index.php/SymbioticSphere SymbioticSphere: A Biologically-inspired Architecture Network Systems with Evolutionary Multiobjective Optimization]

Implementations:
* [http://cs.gmu.edu/~eclab/projects/ecj/ ECJ] (Java), popular evolutionary computation toolkit.
* [http://eodev.sourceforge.net/ EO] (C++) another popular EC toolkit
* [http://www.ra.cs.uni-tuebingen.de/software/EvA2/ EvA2] (Java), a rich open source EA and heuristic optimization framework with GUI.
* [http://www.jaga.org JAGA] (Java) Open source API for implementing genetic algorithms and genetic programming applications
* [http://freshmeat.net/projects/openbeagle/ OpenBeagle] (C++) yet another popular EC toolkit.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Evolutionary music — is the audio counterpart to Evolutionary art, whereby algorithmic music is created using an evolutionary algorithm. The process begins with a population of individuals which by some means or other produce audio (e.g. a piece, melody, or loop),… …   Wikipedia

  • Evolutionary informatics — is a subfield of informatics addressing the practice of information processing in, and the engineering of information systems for, the study of biological evolution, as well as the study of information in evolutionary systems, natural and… …   Wikipedia

  • Evolutionary programming — is one of the four major evolutionary algorithm paradigms. It was first used by Lawrence J. Fogel in 1960 in order to use simulated evolution as a learning process aiming to generate artificial intelligence. Fogel used finite state machines as… …   Wikipedia

  • Evolutionary Acquisition of Neural Topologies — (EANT/EANT2) is an evolutionary reinforcement learning method that evolves both the topology and weights of neural networks. It is closely related to the works of Angeline et al. [Peter J Angeline, Gregory M Saunders, and Jordan B Pollack. An… …   Wikipedia

  • Evolutionary art — exploits the process of evolution to create an artwork which continually changes according to an evolutionary algorithm. In common with natural selection and animal husbandry, the members of a population undergoing artificial evolution modify… …   Wikipedia

  • Evolutionary computation — For the journal, see Evolutionary Computation (journal). In computer science, evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) that involves combinatorial optimization problems.… …   Wikipedia

  • Evolutionary robotics — (ER) is a methodology that uses evolutionary computation to develop controllers for autonomous robots. Algorithms in ER frequently operate on populations of candidate controllers,initially selected from some distribution. This population is then… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Memetic algorithm — Memetic algorithms (MA) represent one of the recent growing areas of research in evolutionary computation. The term MA is now widely used as a synergy of evolutionary or any population based approach with separate individual learning or local… …   Wikipedia

  • Genetic algorithm in economics — Genetic algorithms are used to model the learning behaviour of economic agents. The term genetic algorithm is often abbreviated as GA. The genetic algorithm is a particular class of evolutionary algorithm inspired by evolutionary biology. A… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”