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.