Genetic Algorithm Dynamics in Two-well Potentials
Jonathan Shapiro
University of Manchester
Manchester M13 9PL UK
Adam Pr\"{u}gel-Bennett
Nordita
Copenhagen, Dk-2100, Denmark.
ABSTRACT
The dynamics of a genetic algorithm is studied on fitness functions
consisting of two optima. The focus is on the following questions:
starting with a population in the local optimum, will the genetic
algorithm evolve to a population (primarily) in the global optimum,
and, if so, what is the time-scale for this to occur? The time-scale
of this process is compared with that of simulated annealing. The
system is studied by modelling the distribution of fitnesses as a sum
of two unimodal distributions, and, by using the statistical mechanics
formalism to derive equations for the mean change in the fraction of
the population in each well, and the variance in this change. It is
shown that in the infinite population limit, there is a phase
transition as the search parameters are changed. In one phase, the
population stays in the local optimum forever, and if the population
starts with some strings in the global optimum, the final state
consists of most of the strings in the local optimum. In the second
phase, the population evolves to one in which most or all strings are
the global optimum. In a finite population, the transition is not
abrupt and the increasing correlation of the population can change the
nature of the transition. In the first phase, a finite population
genetic algorithm finds the global optimum much more slowly than
simulated annealing, taking a time approximately exponential in the
population size to evolve to a population primarily in the global
optimum. In the second phase, the finite-population genetic algorithm
finds that population considerable faster than does simulated
annealing. Comparisons with simulations show that this prediction is
qualitatively correct.