Crossover Accelerates Evolution in GAs with a Babel-like Fitness Landscape: Mathematical Analyses
The effectiveness of crossover in accelerating evolution in genetic algorithms (GAS) is studied with a haploid finite population of bit sequences. A Babel-like fitness landscape is assumed. There is a single bit sequence (schema) that is significantly more advantageous than all the others. We study the time until domination of the advantageous schema (T-d). Evolution proceeds with appearance, spread, and domination of the advantageous schema. The most important process determining T-d is the appearance (creation) of the advantageous schema. Crossover helps this creation process and enhances the rate of evolution. To study this effect, we first establish an analytical method to estimate T-d with or without crossover. Then, we conduct a numerical analysis using the frequency vector representation of the population with the recurrence relations formulated after GA operations. Finally, we carry out direct computer simulations with simple GAS operating on a population of binary strings directly prepared in the computer memory to examine the performance of the two analytical methods. It is shown that T-d is reduced greatly by crossover with a mildly high rate when the mutation rate is adjusted to a moderate value and that an advantageous schema has a fairly large order (the number of bits). From these observations, we can determine implementation criteria for GAS, which are useful when we applying GAS to engineering problems having a conspicuously discontinuous fitness landscape.
genetic algorithms genetic recombination (crossover) epistasis population genetics building block hypothesis machine language genetic programming