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
wright@cs.umt.edu
http://www.cs.umt.edu/u/wright/wright.htm

Jonathan E. Rowe 
School of Computer Science 
The University of Birmingham  
Edgbaston, Birmingham B15 2TT
UK
j.e.rowe@cs.bham.ac.uk 

Riccardo Poli 
Computer Science  
University of Essex
Wivenhoe Park, Colchester, CO4 3SQ, UK 
UK 
rpoli@essex.ac.uk

Christopher R. Stephens
Instituto de Ciencias Nucleares 
UNAM, Mexico  
stephens@nuclecu.unam.mx


Abstract

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.