Watson, Richard A., and Thomas Jansen. “A building-block royal road where crossover is provably essential.” In Proceedings of the 9th annual conference on Genetic and evolutionary computation , pp. 1452-1459. 2007.
URL1 URL2
One of the most controversial yet enduring hypotheses about what genetic algorithms (GAs) are good for concerns the idea that GAs process building-blocks. More specifically, it has been suggested that crossover in GAs can assemble short low-order schemata of above average fitness (building blocks) to create higher-order higher-fitness schemata. However, there has been considerable difficulty in demonstrating this rigorously and intuitively. Here we provide a simple building-block function that a GA with two-point crossover can solve on average in polynomial time, whereas an asexual population or mutation hill-climber cannot.