SIMPLE GENETIC ALGORITHMS WITH LINEAR FITNESS

SIMPLE GENETIC ALGORITHMS WITH LINEAR FITNESS

Michael D. Vose
Computer Science Dept., 107 Ayres Hall
The University of Tennessee
Knoxville, TN 37996-1301
vose@cs.utk.edu  (615) 974-5067

Alden H. Wright
Computer Science Dept.
The University of Montana
Missoula, MT. 59812
wright@cs.umt.edu  (406) 243-2883

ABSTRACT

A general form of stochastic search is described ({\em random
heuristic search}) and some of its general properties are proved. This
provides a framework in which the simple genetic algorithm (SGA) is a
special case.  The framework is used to illuminate relationships
between seemingly different probabilistic perspectives on SGA
behavior.  Next the SGA is formalized as an instance of random
heuristic search.  The formalization is then used to show expected
population fitness is a Lyapunov function in the infinite population
model when mutation is zero and fitness is linear.  In particular, the
infinite population algorithm must converge, and average population
fitness increases from one generation to the next.  The consequence
for a finite population SGA is that the expected population fitness
increases from one generation to the next.  Moreover, the only stable
fixed point of the expected next population operator corresponds to
the population consisting entirely of the optimal string.  This result
is extended by way of a perturbation argument to allow nonzero
mutation.