The Simple Genetic Algorithm and the Walsh Transform: part II, The Inverse

The Simple Genetic Algorithm and the Walsh Transform: part II, The Inverse

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

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


ABSTRACT

This paper continues the development, begun in part I, of the
relationship between the simple genetic algorithm and the Walsh
transform.  The mixing scheme (comprised of crossover and mutation) is
essentially ``triangularized'' when expressed in terms of the Walsh
basis.  This leads to a formulation of the inverse of the
expected next generation operator.  The fixed points of the mixing
scheme are also determined, and a formula is obtained giving the fixed
point corresponding to any starting population.  Geiringer's theorem
follows from these results in the special case corresponding to zero
mutation.