Genetic algorithms as a combination of probabilistic solution-space decomposition and randomized search
Akiko Aizawa · Systems and Computers in Japan · 1998
In this paper, genetic algorithms are interpreted as a combination of probabilistic solution-space decomposition and randomized search. We study a method for characterization of the solution space from this point of view. Initially, a statistical measure called the variance coefficient is defined as an index to characterize the solution space. Next, three parameters that are commonly used to characterize a solution space are expressed in terms of the defined variance coefficients. The three parameters are the Walsh coefficient, epistasis variance, and correlation coefficient between generations. In particular, the generation correlation, which used to be known only empirically as an effective performance measure for genetic algorithms, is clearly expressed in terms of the variance coefficients. Based on the definition, the theoretical values of the generation correlations are compared for representative crossover operator; namely uniform crossover and one-point crossover. In addition, the correspondence between the theory and the performance of actual genetic algorithms are demonstrated by simple simulation experiments. © 1998 Scripta Technica, Syst Comp Jpn, 29(5): 1–10, 1998