About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
COLT 2009
Conference paper
Robustness of evolvability
Abstract
A framework for analyzing the computational capabilities and the limitations of the evolutionary process of random change guided by selection was recently introduced by Valiant [Val06]. In his framework the process of acquiring a complex functionality is viewed as a constrained form of PAC learning. In addition to the basic definition, a number of natural variants of the evolvability model were introduced by Valiant, and several others have been suggested since then [Val09, Mic07, Val08]. Understanding the relative power of these variants in terms of the efficiently evolvable function classes they define is one of the main open problems regarding the model [Val09, FV08]. We present several results that collectively demonstrate that the notion of evolvability is robust to a variety of reasonable modifications of the model. Our results show that the power of a model of evolv-ability essentially depends only on the fitness metric used in the model. In particular, we prove that the classes of functions evolvable in Valiant's original model are also evolvable with substantially weaker and simpler assumptions on the mutation algorithm and the selection rule and therefore a wide range of models of evolution are equivalent. Another consequence of our results if that evolv-ability with the quadratic loss fitness metric (or any other non-linear loss) is strictly stronger than evolvability with the linear loss fitness metric used in Valiant's basic definition.