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 (&Tau;&subd;). Evolution proceeds with appearance, spread, and domination of the advantageous schema. The most important process determining &Tau;&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 &Tau;&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 &Tau;&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.
Suzuki
H
H
ATR Human Information Processing Research Laboratories, 2-2 Hikaridai Seika-cho Soraku-gun, Kyoto 619-0288, Japan. hsuzuki@hip. atr.co.jp.
Iwasa
Y
Y
D000465:Algorithms; D005075:Biological Evolution; D003198:Computer Simulation; D005828:Genetics, Population; D008433:Mathematics; D008957:Models, Genetic; D011995:Recombination, Genetic; D013997:Time Factors