Analysis of the Simple Genetic Algorithm on the Single-peak and Double-peak Landscapes

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812

Jonathan E. Rowe 
School of Computer Science 
The University of Birmingham  
Edgbaston, Birmingham B15 2TT

Riccardo Poli 
Computer Science  
University of Essex
Wivenhoe Park, Colchester, CO4 3SQ, UK 

Christopher R. Stephens
Instituto de Ciencias Nucleares 
UNAM, Mexico


This paper analyzes a recombination/mutation/selection genetic
algorithm that uses gene pool recombination.  For linear fitness
functions, the infinite population model can be described by
$\ell$ equations where $\ell$ is the string length.  For linear
fitness functions, we show that there is a single fixed point
and that this fixed point is stable.   For the ONEMAX fitness
function, the model reduces to a linear recurrence in a single
variable which can be explicitly solved.  The time-to-convergence
for ONEMAX is given.