Finiteness of the Fixed Point Set for the Simple Genetic Algorithm

Finiteness of the Fixed Point Set for the Simple Genetic Algorithm

Alden H. Wright
Computer Science Dept.   
The University of Montana   
Missoula, MT 59812-1008   
wright@cs.umt.edu 

Michael D. Vose
Computer Science Dept.
The University of Tennessee
Knoxville, TN 37996-1301 
vose@cs.utk.edu

ABSTRACT


The Infinite Population Simple Genetic Algorithm is a discrete
dynamical system model of a genetic algorithm.  Trajectories
in the model are conjectured to always converge to fixed points.
This paper shows that an arbitrarily small perturbation of
the fitness will result in a model with a finite number of fixed
points.  Moreover, every sufficiently small perturbation of fitness
preserves finiteness of the fixed point set.  These results enable
proofs and constructions that require finiteness of the fixed point
set.  For example, applying the stable manifold theorem to a fixed
point requires the hyperbolicity of the differential of the transition
map of the genetic algorithm, which requires (among other things)
that the fixed point be isolated.