The Simple Genetic Algorithm and the Walsh Transform: part I, Theory

The Simple Genetic Algorithm and the Walsh Transform: part I, Theory

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 is the first part of a two part series.  It proves a
number of direct relationships between the Fourier transform and the
simple genetic algorithm.  (For a binary representation, the Walsh 
transform is the Fourier transform.) The results are of a theoretical 
nature and are based on the analysis of mutation and crossover.  
The Fourier transform of the mixing matrix is shown to be sparse.  
An explicit formula is given for the spectrum of the differential of the
mixing transformation.  By using the Fourier representation and the
fast Fourier transform, one generation of the infinite population 
simple genetic algorithm can be computed in time $O(c^{\ell\log_2 3})$, 
where $c$ is arity of the alphabet and $\ell$ is the string length.  
This is in contrast to the time of $O(c^{3\ell})$ for the algorithm 
as represented in the standard basis.  There are two orthogonal 
decompositions of population space which are invariant under mixing.  
The sequel to this paper will apply the basic theoretical results 
obtained here to inverse problems and asymptotic behavior.