## Evolutionary computation

*13 May 1998 18:20*

There are lots of ways of getting a computer to mimic evolution, but the one I like best, and has the cleanest conceptual lines, is the "genetic algorithm" invented by John Holland. Take a population of strings, and measure their "fitness" against some criterion. Each string has a random number of descendants, i.e. gets copied a random number of times; the expected number of descendants of a string is proportional to its fitness. These descendants can be mutants, or swap part of their length with another descendant string. (Oral tradition says that this "cross-over" is usually more useful than mutation; when and how much, nobody really knows.) Repeat as needed. For this basic version of the genetic algorithm, Holland proved what is called the "schema theorem", showing that, if certain patterns of strings are fitter than others, then, in the long run, the GA can't help but find them, and the average number of strings in the population matching those patterns will increase exponentially. (This result is a relative, and quite consciously so, of Fisher's "Fundamental Theorem of Natural Selection.") In retrospect, it's an almost obvious idea, and utter idiots can write a workable GA in Fortran. (I have.)

In the normal computer-science manner, this has of course been tweaked and
elaborated in hundreds, and by now probably literally thousands, of different
ways. John Koza's technique of "genetic programming" replaces the simple
strings with a clever technique for only encoding syntactically correct (though
possibly useless) programs. (It works best in languages with a very regular
syntax, like Lisp or, Heaven help us, Forth.) There are even variants where
the fitness is determined (more or less) endogenously, i.e. which use something
more like natural than artificial selection. (Obviously, though, artificial
selection is the way to go if you want to solve a particular problem.) It's
neat, it's significant, and if I here it described once more as "teaching
computers how to have sex" or "the merging of life and the machine," I believe
I'll scream. Of course it *is* used in artificial
life and machine learning,
but if Holland had just picked some dull, boring name, like "stochastic
combinatory optimization", nobody would babble about it at all.

See also: Optimization

- Recommended:
- John Holland, Adaptation in Natural and Artificial Systems [One of the best scientific books I've ever read]
- Melanie Mitchell,
Introduction to Genetic Algorithms [I read this and came to the
conclusion it's the best intro. book on GAs
*before*I went to work for Melanie, honest.]

- To read:
- J. Berard and A. Bienvenue, "Sharp Asymptotic Results for
Simplified Mutation-Selection Algorithms", The Annals of Applied
Probability
**13**(2003): 1534--1568 - Volkhard Buchholtz and Thorsten Poeschel, "Adaptive Evolutionary Optimization of Team Work," cond-mat/0203412
- Philippe Collard, Sebastien Verel, Manuel Clergue, "Local search heuristics: Fitness Cloud versus Fitness Landscape", arxiv:0709.4010
- Kenneth A. De Jong, Evolutionary Computation: A Unified Approach [Blurb]
- Fogel, Evolutionary Computation
- Goldberg, Genetic algorithms
- Hughes Juillé, Methods for Statistical Inference: Extending the Evolutionary Computation Paradigm [Ph.D. dissertation, Brandeis University, 1999; online]
- Hillol Kargupta, "Information Transmission in Genetic Algorithm and Shannon's Second Theorem", Proceedings of the 5th International Conference on Genetic Algorithms (1993) [Compressed Postscript]
- Koza, Genetic Programming
- Laura Landweber and Erik Winfree (ed.), Evolution as Computation [The dual subject, as were]
- Heinz Mühlenbein [Website for papers]
- HM, "The Equation for the Response to Selection and Its
Use for Prediction," Evolutionary Computation
**5**(1998): 303--346 - HM and Thilo Mahnig, "The Exact Equation for the Response to Selection for Multiple Alleles and Its Application"
- HM and Alberto Ochoa Rodriguez, "Schemata, Distributions and Graphical Models in Evolutionary Optimization"

- HM, "The Equation for the Response to Selection and Its
Use for Prediction," Evolutionary Computation
- Juan Pablo Neirotti and Nestor Caticha, "Dynamics of the evolution
of learning algorithms by selection", Physical Review
E
**67**(2003): 041912 - Luca Scrucca, "GA: A Package for Genetic Algorithms in R",
Journal of Statistical Software
**53:4**(2013) - David Shilane, Richard H. Liang and Sandrine Dudoit, "Loss-Based Estimation with Evolutionary Algorithms and Cross-Validation", UC Berkeley Biostatistics Working Paper 227 [Abstract, PDF]
- Wilhelm Stannat, "On the Convergence of Genetic Algorithms --- A
Variational Approach", Probability Theory
and Related Fields
**129**(2004): 113--132 - Joe Suzuki, "A Markov chain analysis of genetic algorithms: large deviation principle approach", Journal of Applied
Probability
**47**(2010): 967--975 - Marc Toussaint, "Self-adaptive exploration in evolutionary search," physics/0102009
- Sebastien Verel, Philippe Collard, Manuel Clergue, "Measuring the Evolvability Landscape to study Neutrality", arxiv:0709.4011