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.