Clever Algorithms: Nature-Inspired Programming Recipes

A book by Jason Brownlee

Evolutionary Algorithms

Overview

This chapter describes Evolutionary Algorithms.

Evolutionary Algorithms belong to the Evolutionary Computation field of study concerned with computational methods inspired by the process and mechanisms of biological evolution. The process of evolution by means of natural selection (descent with modification) was proposed by Darwin to account for the variety of life and its suitability (adaptive fit) for its environment. The mechanisms of evolution describe how evolution actually takes place through the modification and propagation of genetic material (proteins). Evolutionary Algorithms are concerned with investigating computational systems that resemble simplified versions of the processes and mechanisms of evolution toward achieving the effects of these processes and mechanisms, namely the development of adaptive systems. Additional subject areas that fall within the realm of Evolutionary Computation are algorithms that seek to exploit the properties from the related fields of Population Genetics, Population Ecology, Coevolutionary Biology, and Developmental Biology.

References

Evolutionary Algorithms share properties of adaptation through an iterative process that accumulates and amplifies beneficial variation through trial and error. Candidate solutions represent members of a virtual population striving to survive in an environment defined by a problem specific objective function. In each case, the evolutionary process refines the adaptive fit of the population of candidate solutions in the environment, typically using surrogates for the mechanisms of evolution such as genetic recombination and mutation.

There are many excellent texts on the theory of evolution, although Darwin's original source can be an interesting and surprisingly enjoyable read [Darwin1859]. Huxley's book defined the modern synthesis in evolutionary biology that combined Darwin's natural selection with Mendel's genetic mechanisms [Huxley1942], although any good textbook on evolution will suffice (such as Futuyma's "Evolution" [Futuyma2009]). Popular science books on evolution are an easy place to start, such as Dawkins' "The Selfish Gene" that presents a gene-centric perspective on evolution [Dawkins1976], and Dennett's "Darwin's Dangerous Idea" that considers the algorithmic properties of the process [Dennett1995].

Goldberg's classic text is still a valuable resource for the Genetic Algorithm [Goldberg1989], and Holland's text is interesting for those looking to learn about the research into adaptive systems that became the Genetic Algorithm [Holland1975]. Additionally, the seminal work by Koza should be considered for those interested in Genetic Programming [Koza1992], and Schwefel's seminal work should be considered for those with an interest in Evolution Strategies [Schwefel1981]. For an in-depth review of the history of research into the use of simulated evolutionary processed for problem solving, see Fogel [Fogel1998] For a rounded and modern review of the field of Evolutionary Computation, Bäck, Fogel, and Michalewicz's two volumes of "Evolutionary Computation" are an excellent resource covering the major techniques, theory, and application specific concerns [Baeck2000] [Baeck2000a]. For some additional modern books on the unified field of Evolutionary Computation and Evolutionary Algorithms, see De Jong [Jong2006], a recent edition of Fogel [Fogel1995], and Eiben and Smith [Eiben2003].

Algorithms

Extensions

There are many other algorithms and classes of algorithm that were not described from the field of Evolutionary Computation, not limited to:

Distributed Evolutionary Computation: that are designed to partition a population across computer networks or computational units such as the Distributed or 'Island Population' Genetic Algorithm [Tanese1989] [Cantu-Paz2000] and Diffusion Genetic Algorithms (also known as Cellular Genetic Algorithms) [Alba2008].
Niching Genetic Algorithms: that form groups or sub-populations automatically within a population such as the Deterministic Crowding Genetic Algorithm [Mahfoud1992] [Mahfoud1995], Restricted Tournament Selection [Harik1994] [Harik1995], and Fitness Sharing Genetic Algorithm [Goldberg1987] [Deb1989].
Evolutionary Multiple Objective Optimization Algorithms: such as Vector-Evaluated Genetic Algorithm (VEGA) [Schaffer1984], Pareto Archived Evolution Strategy (PAES) [Knowles1999] [Knowles1999a], and the Niched Pareto Genetic Algorithm (NPGA) [Horn1994].
Classical Techniques: such as GENITOR [Whitley1989], and the CHC Genetic Algorithm [Eshelman1991].
Competent Genetic Algorithms: (so-called [Goldberg2002]) such as the Messy Genetic Algorithm [Goldberg1989a] [Goldberg1990], Fast Messy Genetic Algorithm [Goldberg1993], Gene Expression Messy Genetic Algorithm [Kargupta1996], and the Linkage-Learning Genetic Algorithm [Harik1996].

Bibliography

[Alba2008]	E. Alba and B. Dorronsoro, "Cellular Genetic Algorithms", Springer, 2008.
[Baeck2000]	T. B\äck and D. B. Fogel and Z. Michalewicz (editors), "Evolutionary Computation 1: Basic Algorithms and Operators", IoP, 2000.
[Baeck2000a]	T. B\äck and D. B. Fogel and Z. Michalewicz (editors), "Evolutionary Computation 2: Advanced Algorithms and Operations", IoP, 2000.
[Cantu-Paz2000]	E. Cantú–Paz, "Efficient and Accurate Parallel Genetic Algorithms", Kluwer Academic Publishers (Springer), 2000.
[Darwin1859]	C. Darwin, "On the Origin of Species by Means of Natural Selection, or the Preservation\n\tof Favoured Races in the Struggle for Life", John Murray, 1859.
[Dawkins1976]	R. Dawkins, "The selfish gene", Oxford University Press, 1976.
[Deb1989]	K. Deb and D. E. Goldberg, "An investigation of niche and species formation in genetic function\n\toptimization", in Proceedings of the Second International Conference on Genetic Algorithms, 1989.
[Dennett1995]	D. C. Dennett, "Darwin's Dangerous Idea", Simon \& Schuster, 1995.
[Eiben2003]	A. E. Eiben and J. E. Smith, "Introduction to evolutionary computing", Springer, 2003.
[Eshelman1991]	L. J. Eshelman, "The CHC adaptive search algorithm: How to do safe search when engaging\n\tin nontraditional genetic recombination", in Proceedings Foundations of Genetic Algorithms Conf., 1991.
[Fogel1995]	D. B. Fogel, "Evolutionary computation: Toward a new philosophy of machine intelligence", IEEE Press, 1995.
[Fogel1998]	D. B. Fogel, "Evolutionary Computation: The Fossil Record", Wiley-IEEE Press, 1998.
[Futuyma2009]	D. Futuyma, "Evolution", Sinauer Associates Inc., 2009.
[Goldberg1987]	D. E. Goldberg and J. Richardson, "Genetic algorithms with sharing for multimodal function optimization", in Proceedings of the 2nd Internaltional Conference on Genetic Algorithms, 1987.
[Goldberg1989]	D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Wesley, 1989.
[Goldberg1989a]	D. E. Goldberg and B. Korb and K. Deb, "Messy genetic algorithms: Motivation, analysis, and first results", Complex Systems, 1989.
[Goldberg1990]	D. E. Goldberg and K. Deb and B. Korb, "Messy genetic algorithms revisited: studies in mixed size and scale", Complex Systems, 1990.
[Goldberg1993]	D. E. Goldberg and K. Deb and H. Kargupta and G. Harik, "Rapid, Accurate Optimization of Difficult Problems Using Fast Messy\n\tGenetic Algorithms", in Proceedings of the Fifth International Conference on Genetic Algorithms, 1993.
[Goldberg2002]	D. E. Goldberg, "The design of innovation: Lessons from and for competent genetic\n\talgorithms", Springer, 2002.
[Harik1994]	G. Harik, "Finding Multiple Solutions in Problems of Bounded Difficulty", Technical Report IlliGAL Report No. 94002, University of Illinois at Urbana–Champaign, 1994.
[Harik1995]	G. Harik, "Finding Multimodal Solutions Using Restricted Tournament Selection", in Proceedings of the Sixth International Conference on Genetic Algorithms, 1995.
[Harik1996]	G. R. Harik and D. E. Goldberg, "Learning linkage", in Foundations of Genetic Algorithms 4, 1996.
[Holland1975]	J. H. Holland, "Adaptation in natural and artificial systems: An introductory analysis\n\twith applications to biology, control, and artificial intelligence", University of Michigan Press, 1975.
[Horn1994]	J. Horn and N. Nafpliotis and D. E. Goldberg, "A niched Pareto genetic algorithm for multiobjective optimization", in Proceedings of the First IEEE Conference on Evolutionary Computation,\n\tIEEE World Congress on Computational Intelligence, 1994.
[Huxley1942]	J. Huxley, "Evolution: The Modern Synthesis", Allen \& Unwin, 1942.
[Jong2006]	K. A. De Jong, "Evolutionary computation: A unified approach", MIT Press, 2006.
[Kargupta1996]	H. Kargupta, "The gene expression messy genetic algorithm", in Proceedings of the IEEE International Conference on Evolutionary\n\tComputation, 1996.
[Knowles1999]	J. D. Knowles and D. W. Corne, "Local Search, Multiobjective Optimization and the Pareto Archived\n\tEvolution Strategy", in Proceedings of the Third Australia–Japan Joint Workshop on Intelligent\n\tand Evolutionary Systems, 1999.
[Knowles1999a]	J. D. Knowles and D. W. Corne, "The Pareto Archived Evolution Strategy : A New Baseline Algorithm\n\tfor Pareto Multiobjective Optimisation", in Proceedings of the 1999 Congress on Evolutionary Computation, 1999.
[Koza1992]	J. R. Koza, "Genetic programming: On the programming of computers by means of\n\tnatural selection", MIT Press, 1992.
[Mahfoud1992]	S. W. Mahfoud, "Crowding and Preselection Revised", in Parallel Problem Solving from Nature 2, 1992.
[Mahfoud1995]	S. W. Mahfoud, "Niching Methods for Genetic Algorithms", [PhD Thesis] University of Illinois at Urbana–Champaign, 1995.
[Schaffer1984]	D. J. Schaffer, "Some experiments in machine learning using vector evaluated genetic\n\talgorithms", [PhD Thesis] Vanderbilt University, Tennessee, 1984.
[Schwefel1981]	H–P. Schwefel, "Numerical Optimization of Computer Models", John Wiley \& Sons, 1981.
[Tanese1989]	R. Tanese, "Distributed genetic algorithms", in Proceedings of the third international conference on Genetic algorithms, 1989.
[Whitley1989]	D. Whitley, "The GENITOR Algorithm and Selective Pressure: Why Rank-Based Allocation\n\tof Reproductive Trials is Best", in Proceedings of the 3rd International Conference on Genetic Algorithms, 1989.

Please Note: This content was automatically generated from the book content and may contain minor differences.