Optimizing epochal evolutionary search: Population-size dependent theory

Epochal dynamics, in which long periods of stasis in an evolving population are punctuated by a sudden burst of change, is a common behavior in both n atural and artificial evolutionary processes. We analyze the population dyn amics for a class of fitness functions that exhibit epochal behavior using a mathematical framework developed recently, which incorporates techniques from the fields of mathematical population genetics, molecular evolution th eory, and statistical mechanics. Our analysis predicts the total number of fitness function evaluations to reach the global optimum as a function of m utation rate, population size, and the parameters specifying the fitness fu nction. This allows us to determine the optimal evolutionary parameter sett ings for this class of fitness functions. We identify a generalized error threshold that smoothly bounds the two-dime nsional regime of mutation rates and population sizes for which epochal evo lutionary search operates most efficiently. Specifically, we analyze the dy namics of epoch destabilization under finite-population sampling fluctuatio ns and show how the evolutionary parameters effectively introduce a coarse graining of the fitness function. More generally, we find that the optimal parameter settings for epochal evolutionary search correspond to behavioral regimes in which the consecutive epochs are marginally stable against the sampling fluctuations. Our results suggest that in order to achieve optimal search, one should set evolutionary parameters such that the coarse graini ng of the fitness function induced by the sampling fluctuations is just lar ge enough to hide local optima.