Fitness Landscape Characterization
by Variance of Decompositions
Akiko Aizawa
National Center for Science Information System
3-29-1 Otsuka, Bunkyo-ku
Tokyo 112, JAPAN
akiko@rd.nacsis.ac.jp
Abstract
In the present paper, we first present a new framework in which
crossover operators are formalized as a combination of probabilistic
linear decompositions and a randomized search. Then, as a means to
theoretically analyze the behavior of different crossover operators
for the infinite population case, we uniquely define crossover
correlation using the variance between decompositions, i.e., after
decomposing the solution space through a template of competing
schemata, the variance between the decompositions, being expressed as
variance coefficients, is used as a fundamental statistical measure.
First, the employed linear decomposition hypothesis and variance
coefficients are mathematically defined. Then, features and
implications of utilizing such variance coefficients are presented by
formulating relational equations describing the respective
relationship between variance coefficients and Walsh coefficients,
epistasis variance, and crossover correlation. An analysis of
representative crossover operators is subsequently carried out using
crossover correlation expressed as variance coefficients, after which
we compare the coding effects of these crossover operators
mathematically. Following this, a simulation is shown to evaluate
analytical results in comparison with actual GA performance for the
case in which the population size is large relative to the problem
size.