Optimizing epochal evolutionary search: Population-size dependent theory

van Nimwegen, Erik and Crutchfield, James P.. (2001) Optimizing epochal evolutionary search: Population-size dependent theory. Machine Learning, 45 (1). pp. 77-114.

Full text not available from this repository.

Official URL: https://edoc.unibas.ch/83042/

Downloads: Statistics Overview


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 natural and artificial evolutionary processes. We analyze the population dynamics 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 theory, and statistical mechanics. Our analysis predicts the total number of fitness function evaluations to reach the global optimum as a function of mutation rate, population size, and the parameters specifying the fitness function. This allows us to determine the optimal evolutionary parameter settings for this class of fitness functions.
We identify a generalized error threshold that smoothly bounds the two-dimensional regime of mutation rates and population sizes for which epochal evolutionary search operates most efficiently. Specifically, we analyze the dynamics of epoch destabilization under finite-population sampling fluctuations 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 graining of the fitness function induced by the sampling fluctuations is just large enough to hide local optima.
Faculties and Departments:05 Faculty of Science > Departement Biozentrum > Computational & Systems Biology > Bioinformatics (van Nimwegen)
UniBasel Contributors:van Nimwegen, Erik
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:Kluwer Academic
Note:Publication type according to Uni Basel Research Database: Journal article
Identification Number:
Last Modified:18 May 2021 08:57
Deposited On:18 May 2021 08:57

Repository Staff Only: item control page