In artificial intelligence, an evolutionary algorithm is a subset of
evolutionary computation, a generic population-based metaheuristic
optimization algorithm. An EA uses mechanisms inspired by biological
evolution, such as 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 quality of the solutions.
Evolution of the population then takes place after the repeated application of
the above operators. Artificial evolution describes a process involving
individual evolutionary algorithms; 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 chemistry.
Techniques from evolutionary algorithms applied to the modeling of biological
evolution are generally limited to explorations of microevolutionary
processes and planning models based upon cellular processes. The computer
simulations Tierra and Avida attempt to model macroevolutionary dynamics.
In most real applications of EAs, computational complexity is a
prohibiting factor. In fact, this computational complexity is due to
fitness function evaluation. Fitness approximation is one of the solutions to
overcome this difficulty. However, seemingly simple EA can solve often
complex problems; therefore, there may be no direct link between algorithm
complexity and problem complexity. 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 to make the genetic search more robust, and also may improve the
evolvability of the organism. Such indirect encodings also enable evolution
to exploit the regularity in the environment. Recent work in the field of
artificial embryogeny, or artificial developmental systems, seeks to address
these concerns. And gene expression programming successfully explores a
genotype-phenotype system, where the genotype consists of linear multigenic
chromosomes of fixed length and the phenotype consists of multiple
expression trees or computer programs of different sizes and shapes.
Implementation of biological processes Generate the initial population of
individuals randomly - first generation Evaluate the fitness of each individual
in that population Repeat on this generation until
termination: Select the best-fit individuals for
reproduction - parents Breed new individuals through crossover
and mutation operations to give birth to offspring
Evaluate the individual fitness of new individuals
Replace least-fit population with new individuals
Evolutionary algorithm types 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, by applying
operators such as recombination and mutation. 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 - Similar to genetic programming, but the structure
of the program is fixed and its numerical parameters are allowed to
evolve. Gene expression programming - Like
genetic programming, GEP also evolves computer programs but it explores a
genotype-phenotype system, where computer programs of different sizes are
encoded in linear chromosomes of fixed length.
Evolution strategy - Works with vectors of real numbers as representations of
solutions, and typically uses self-adaptive mutation rates.
Differential evolution - Based on vector differences and is therefore primarily
suited for numerical optimization problems.
Neuroevolution - Similar to genetic programming but the genomes represent
artificial neural networks by describing structure and connection weights. The
genome encoding can be direct or indirect.
Learning classifier system - Here the solutions are classifiers. A
Michigan-LCS works with individual classifiers whereas a Pittsburgh-LCS
uses populations of classifier-sets. Initially, classifiers were only binary,
but now include real, neural net, or S-expression types. Fitness is
determined with either a strength or accuracy based reinforcement learning
approach. Related techniques
Swarm algorithms, including: Ant colony optimization - Based on the
ideas of ant foraging by pheromone communication to form paths. Primarily
suited for combinatorial optimization and graph problems.
The runner-root algorithm is inspired by the function of runners and roots of
plants in nature Artificial Bee Colony Algorithm - Based
on the honey bee foraging behaviour. Primarily proposed for numerical
optimization and extended to solve combinatorial, constrained and
multi-objective optimization problems. Bees algorithm is based on the foraging
behaviour of honey bees. It has been applied in many applications such as
routing and scheduling. Cuckoo search is inspired by the
brooding parasitism of the cuckoo species. It also uses Lévy flights, and
thus it suits for global optimization problems.
Particle swarm optimization - Based on the ideas of animal flocking behaviour.
Also primarily suited for numerical optimization problems.
Other population-based metaheuristic methods
Firefly algorithm is inspired by the behavior of fireflies, attracting each
other by flashing light. This is especially useful for multimodal
optimization. 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.
Memetic algorithm - It is the hybrid form of population based methods.
Inspired by Dawkins’ notion of a meme, it commonly takes the form of a
population-based algorithm coupled with individual learning procedures capable
of performing local refinements. Emphasizes the exploitation of
problem-specific knowledge, and tries to orchestrate local and global search in a
synergic way. See also
Artificial development Developmental biology
Digital organism Estimation of distribution algorithm
Evolutionary computation Evolutionary robotics
Fitness function Fitness landscape
Fitness approximation Genetic operators
Interactive evolutionary computation List of digital organism simulators
Map of Evolutionary Algorithms No free lunch in search and optimization
Program synthesis Test functions for optimization
Gallery References
^ G.S. Hornby and J.B. Pollack. Creating high-level components with a generative
representation for body-brain evolution. Artificial Life, 8(3):223–246, 2002.
^ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving
Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding".
Proceedings of the IEEE Congress on Evolutionary Computing Special Section
on Evolutionary Robotics, 2009. Trondheim, Norway.
^ J. Clune, C. Ofria, and R. T. Pennock, “How a generative encoding fares as
problem-regularity decreases,” in PPSN, vol. 5199 of Lecture Notes in Computer
Science, pp. 358–367, Springer, 2008. ^ Ferreira, C., 2001. Gene Expression
Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems,
Vol. 13, issue 2: 87-129. ^ F. Merrikh-Bayat, The runner-root
algorithm: A metaheuristic for solving unimodal and multimodal optimization
problems inspired by runners and roots of plants in nature, Applied Soft
Computing, Vol. 33, pp. 292–303, 2015 ^ Simionescu, P.A.. Computer Aided
Graphing and Simulation Tools for AutoCAD Users. Boca Raton, FL: CRC
Press. ISBN 9-781-48225290-3. Bibliography
Ashlock, D., Evolutionary Computation for Modeling and Optimization, Springer,
ISBN 0-387-22196-4. Bäck, T., Evolutionary Algorithms in
Theory and Practice: Evolution Strategies, Evolutionary Programming,
Genetic Algorithms, Oxford Univ. Press. Bäck, T., Fogel, D., Michalewicz, Z.,
Handbook of Evolutionary Computation, Oxford Univ. Press.
Banzhaf, W., Nordin, P., Keller, R., Francone, F., Genetic Programming - An
Introduction, Morgan Kaufmann, San Francisco
Eiben, A.E., Smith, J.E., Introduction to Evolutionary Computing, Springer.
Holland, J. H., Adaptation in Natural and Artificial Systems, The University
of Michigan Press, Ann Arbor Michalewicz Z., Fogel D.B.. How To Solve
It: Modern Heuristics, Springer. Poli, R., Langdon, W. B., McPhee, N. F..
A Field Guide to Genetic Programming. Lulu.com, freely available from the
internet. ISBN 978-1-4092-0073-4. Price, K., Storn, R.M., Lampinen, J.A.,.
"Differential Evolution: A Practical Approach to Global Optimization",
Springer. Ingo Rechenberg: Evolutionsstrategie -
Optimierung technischer Systeme nach Prinzipien der biologischen Evolution.
Reprinted by Fromman-Holzboog. Hans-Paul Schwefel: Numerische
Optimierung von Computer-Modellen. Reprinted by Birkhäuser.
Simon, D.: Evolutionary Optimization Algorithms, Wiley.
Computational Intelligence: A Methodological Introduction by Kruse,
Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 9781447150121