## 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.