Bistability in a Gene Pool GA with Mutation

posted 2/9/03

To be published in FOGA 7, Morgan Kaufmann, 2003

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

Jonathon E. Rowe
School of Computer Science
University of Birmingham
Egbaston, Birmingham
B15 2TT, UK
J.E.Rowe@cs.bham.ac.uk

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

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



Abstract

It is possible for a GA to have two stable fixed points
on a single-peak fitness landscape.  These can correspond
to meta-stable finite populations.  This phenomenon is
called {\em bistability}, and is only known to happen in the presence
of recombination, selection, and mutation.  This paper models the
bistability phenomenon using an infinite population model of a GA
based on gene pool recombination.  Fixed points and their
stability are explicitly calculated.   This is possible since
the infinite population model of the gene pool GA is much
more tractable than the infinite population model for the
standard simple GA.

For the needle-in-the-haystack fitness function, the fixed point
equations reduce to a single variable polynomial equation, and 
stability of fixed points can be determined from the derivative 
of the single variable equation.  We also show empirically that 
bistability can occur on a single-peak landscape where there is
selective pressure toward the optimum at every point of the search 
space.