Paper Info
Title
The simple genetic algorithm and the walsh transform: Part i, theory
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(cl log2 3), where c is arity of the alphabet and l is the string length. This is in contrast to the time of O(c3l) for the algorithm as represented in the standard basis. There are two orthogonal decompositions of population space that are invariant under mixing. The sequel to this paper will apply the basic theoretical results obtained here to inverse problems and asymptotic behavior.
Year
DOI
Venue
1998
10.1162/evco.1998.6.3.253
Evolutionary Computation
Keywords
Field
DocType
inverse problem,fourier transform,spectrum,asymptotic behavior,fast fourier transform,walsh transform
Applied mathematics,Non-uniform discrete Fourier transform,Mathematical optimization,Harmonic wavelet transform,Mathematical analysis,Short-time Fourier transform,Fourier transform,Discrete Fourier transform (general),Discrete Fourier transform,Fourier transform on finite groups,Fractional Fourier transform,Mathematics
Journal
Volume
Issue
ISSN
6
3
1063-6560
Citations 
PageRank 
References 
22
1.63
15
Authors
2
Name
Order
Citations
PageRank
Michael D. Vose1752215.67
Alden H. Wright233045.58