Statistical dynamics of the royal road genetic algorithm

van Nimwegen, Erik and Crutchfield, James P. and Mitchell, Melanie. (1999) Statistical dynamics of the royal road genetic algorithm. Theoretical Computer Science, 229 (1-2). pp. 41-102.

Full text not available from this repository.

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

Downloads: Statistics Overview


Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper an analytical model for the dynamics of a mutation-only genetic algorithm (GA) is introduced that identifies a new and general mechanism causing metastability in evolutionary dynamics. The GA's population dynamics is described in terms of flows in the space of fitness distributions. The trajectories through fitness distribution space are derived in closed form in the limit of infinite populations. We then show how finite populations induce metastability, even in regions where fitness does not exhibit a local optimum. In particular, the model predicts the occurrence of "fitness epochs" - periods of stasis in population fitness distributions - at finite population size and identifies the locations of these fitness epochs with the flow's hyperbolic fixed points. This enables exact predictions of the metastable fitness distributions during the fitness epochs, as well as giving insight into the nature of the periods of stasis and the innovations between them. All these results are obtained as closed-form expressions in terms of the GA's parameters.
An analysis of the Jacobian matrices in the neighborhood of an epoch's metastable fitness distribution allows for the calculation of its stable and unstable manifold dimensions and so reveals the state space's topological structure. More general quantitative features of the dynamics - fitness fluctuation amplitudes, epoch stability, and speed of the innovations - are also determined from the Jacobian eigenvalues. The analysis shows how quantitative predictions for a range of dynamical behaviors, that are specific to the finite-population dynamics, can be derived from the solution of the infinite-population dynamics. The theoretical predictions are shown to agree very well with statistics from GA simulations. We also discuss the connections of our results with those from population genetics and molecular evolution theory.
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
Note:Publication type according to Uni Basel Research Database: Journal article
Identification Number:
Last Modified:18 May 2021 09:08
Deposited On:18 May 2021 09:08

Repository Staff Only: item control page