Evolvability Export

@incollection{citeulike:1904041, abstract = {Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as result of a random search 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.}, author = {Valiant, Leslie}, citeulike-article-id = {1904041}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-74456-6_5}, doi = {10.1007/978-3-540-74456-6_5}, journal = {Mathematical Foundations of Computer Science 2007}, keywords = {evolution, evolvability}, pages = {22--43}, posted-at = {2007-11-12 20:52:01}, priority = {3}, title = {Evolvability}, url = {http://dx.doi.org/10.1007/978-3-540-74456-6_5}, year = {2007} }

TY - CHAP ID - citeulike:1904041 L3 - citeulike-article-id:1904041 N2 - Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as result of a random search 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. JF - Mathematical Foundations of Computer Science 2007 EP - 43 TI - Evolvability SP - 22 KW - evolution KW - evolvability AU - Valiant, Leslie PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-74456-6_5 ER -