Analysis of punctuated equilibria in simple genetic algorithms

Abstract

Parallel problem solving methods modeled from nature are introduced to solve these combinatorial optimization problems. Among these methods, genetic algorithms (GAs) are ones imitating Darwinian evolution. The GA deals with a population which is a set of individuals each of which corresponds to a point in the solution space. The goodness of an individual is measured by a fitness function and this can be visualized as a landscape on the solution space. In the fitness landscape, there can be a number of local optima which is surrounded by neighbor points with lower fitness. Like many heuristic algorithms, GAs have the problem of their population being trapped in a local optimum but, the population can escape from the local optimum thanks to phenomena called punctuated equilibria. According to the paleontological studies, the progress of the evolution is not linear but intermittent: a long duration of metastable state followed by a sudden jump into the other stable state. This phenomenon is the punctuated equilibrium and is understood as a transition of an ecosystem from a local optimum into another in the neighborhood. The punctuated equilibria can be explained using mathematical theory of diffusion processes within the framework of neo-Darwinian theory which is the most widely accepted evolution model. The mathematical theory deals with a bistable landscape which has one local and one global optima. If a system starts from the local optimum, it remains there for an exponentially long time and, suddenly, transits into the global optimum. On the other hand, punctuated equilibria are also observed in computational ecosystems (CEs) which are simplified models of real ecosystems. The punctuated equilibria in CEs can also be explained using the mathematical theory of diffusion processes and it is suggested that the duration of metastable state is exponential in the population size, which is the number of individuals in the population, and the height of the barrier be...