An analysis of punctuated equilibria in simple genetic algorithms

Abstract

In the running of a genetic algorithm, the population is liable to be confined in the local optimum, that is the metastable state, making an equilibrium. It is known that, after a long time, the equilibrium is punctuated suddenly and the population transits into the better neighbor optimum. We adopt the formalization of Computational Ecosystems to show that the dynamics of the Simple Genetic Algorithm is represented by a differential equation focusing on the population mean of a phenotype. Referring to the studies of differential equations of this form, we show that the duration time of metastability is exponential in the population size and other parameters, on the one dimensional bistable fitness landscape which has one metastable and one stable state.