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 (Τ&subd;). Evolution proceeds with appearance, spread, and domination of the advantageous schema. The most important process determining Τ&subd; 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 Τ&subd; 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 Τ&subd; 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 larger order (the number of bits). From these observations, we can determine implementation criteria for GAs, which are useful when we are applying GAs to engineering problems having a conspicuously discontinuous fitness landscape.