What can Darwinian evolution evolve, and how fast?

5 November 2010

Leslie Valiant
School of Engineering and Applied Sciences
Harvard University


Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes within realistic time periods, and which are too complex.

We suggest such a theory. Evolution is treated as a form of computational learning from examples in which the course of learning is influenced only by the aggregate fitness of the current hypothesis on the examples, and not otherwise by specific examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. The dilemma is, say in the context of input functions for gene expression, that if the function class is too expressive then no evolution algorithm will exist to navigate it, and if it is too restrictive then it will not support biology.

It is shown, for example, that in any one phase of evolution, where selection is for one beneficial behavior, monotone Boolean conjunctions and disjunctions are demonstrably evolvable over the uniform distribution, while Boolean parity functions are demonstrably not. The framework also allows a wider range of issues in evolution to be quantified.

current theory lunch schedule