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 (Td). Evolution proceeds with appearance, spread, and domination of the advantageous schema. The most important process determining Td 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 Td 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 Td 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 apply GAs to engineering problems having a conspicuously discontinuous fitness landscape.