An analysis of Punctuated Equilibria in Simple Genetic Algorithms

Abstract

In the running of a genetic algorithm, the population is liable to be conned 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 dierential equation focusing on the population mean of a phenotype. Referring to the studies of dierential 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.