View Full Document

7 views

Unformatted text preview:

Evolvability Leslie G Valiant School of Engineering and Applied Sciences Harvard University valiant seas harvard edu Abstract Living organisms function according to complex mechanisms that operate in different ways depending on conditions Evolutionary theory suggests that such mechanisms evolved through random variation guided by 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 In this paper 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 fitness of the hypotheses on the examples and not otherwise by the specific examples We formulate a notion of evolvability that quantifies the evolvability of different classes of functions It is shown 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 We suggest that the overall mechanism that underlies biological evolution is evolvable target pursuit which consists of a series of evolutionary stages each one pursuing an evolvable target in our technical sense each target being rendered evolvable by the serendipitous combination of the environment and the outcome of previous evolutionary stages 1 Introduction We address the problem of quantifying how complex mechanisms such as those found in living cells can evolve into existence without any need for unlikely events to occur If evolution merely performed a random search it would require exponential time much too long to explain the complexity of existing biological structures Darwin suggested selection as the critical controlling principle beyond random variation He



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Evolvability and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Evolvability and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?