Optimizing epochal evolutionary search: Population-size dependent theory

DOI10.1023/A:1010928206141MaRDI QIDQ5952200zbMATH OpenFDO

Authors Erik Van Nimwegen, James P. Crutchfield

Publication date 4 March 2003

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/adap-org/9810004

zbMATH Keywords

epochal dynamicserror thresholdevolutionary searchmarginal stability

Mathematics Subject Classification ID

Searching and sorting (68P10) Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05)

Abstract: 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. In the latter the approximations employed led to a population-size independent theory that allowed us to determine optimal mutation rates. Here we extend this approach to include the destabilization of epochs due to finite-population fluctuations and show that this dynamical behavior often occurs around the optimal parameter settings for efficient search. The resulting, more accurate theory 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. We further identify a generalized error threshold, smoothly bounding the two-dimensional regime of mutation rates and population sizes for which evolutionary search operates efficiently.

Recommendations

• Optimizing epochal evolutionary search: population-size independent theory.
• Finite populations induce metastability in evolutionary search.
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Dynamics of information and optimal control of mutation in evolutionary systems
• scientific article; zbMATH DE number 1264261

Cited in

(11)

• Optimizing epochal evolutionary search: population-size independent theory.
• An optimizing principle of natural selection in evolutionary population genetics
• Population size versus runtime of a simple evolutionary algorithm
• Efficient search and responsiveness trade-offs in a Markov chain model of evolution in dynamic environments
• Evolutionary optimization: pitfalls and booby traps
• The quasispecies regime for the simple genetic algorithm with ranking selection
• Drift analysis and average time complexity of evolutionary algorithms
• Survival of the flexible: explaining the recent popularity of nature-inspired optimization within a rapidly evolving world
• Fourier analysis meets runtime analysis: precise runtimes on plateaus
• Necessary and sufficient conditions for the existence of an optimisation principle in evolution
• Global versus local search: the impact of population sizes on evolutionary algorithm performance

This page was built for publication: Optimizing epochal evolutionary search: Population-size dependent theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5952200)