SCHEMA ANALYSIS OF GENETIC ALGORITHMS ON MULTIPLICATIVE LANDSCAPE

摘要

A method has been developed to derive an evolution equation of schemata under the action of genetic operators. The method makes use of the fact that schema frequencies can be given by Walsh transformation of genotype frequencies. It is applied to genetic algorithms (GAs) on the multiplicative landscape. On this landscape, an exact evolution equation for the first order schemata can be derived within the framework of an infinite population model, and this makes it possible to carry out an analytical investigation of genetic operators. The theoretical results are compared with numerical experiments. The analysis of the experiments focuses on the interplay of mutation and crossover, and investigates the effect of linkage due to finite population size.