Bistability of the Needle Function in the Presence of Truncation Selection

posted 8/16/04


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

Greg Cripe
Spokane Falls Community College, Spokane WA USA

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