Vose M D, Wright A H
Computer Science Dept., University of Tennessee, Knoxville 37996-1301, USA.
Evol Comput. 1998 Fall;6(3):253-73. doi: 10.1162/evco.1998.6.3.253.
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(cllog2(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.
本文是一个分为两部分系列的第一部分。它证明了傅里叶变换与简单遗传算法之间的一些直接关系。（对于二进制表示，沃尔什变换就是傅里叶变换）。这些结果具有理论性质，并且基于对变异和交叉的分析。混合矩阵的傅里叶变换被证明是稀疏的。给出了混合变换微分谱的显式公式。通过使用傅里叶表示和快速傅里叶变换，无限种群简单遗传算法的一代可以在时间O(cllog2(3))内计算出来，其中c是字母表的元数，l是字符串长度。这与标准基表示的算法的O(c3l)时间形成对比。种群空间有两种在混合下不变的正交分解。本文的续篇将把这里得到的基本理论结果应用于反问题和渐近行为。
