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

   And

Alden H. Wright 
(This work was done while visiting the computer science department 
of the University of Tennessee.)
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 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.