A formal analysis of the role of multi-point crossover in genetic algorithms

On the basis of early theoretical and empirical studies, genetic algorithms have typically used 1 and 2-point crossover operators as the standard mechan- isms for implementing recombination. However, there have been a number of recent studies, primarily empirical in nature, which have shown the benefits of crossover operators involving a higher number of crossover points. From a trad- itional theoretical point of view, the most surprising of these new results relate to uniform crossover, which involves on the average L / 2 crossover points for strings of length L. In this paper we extend the existing theoretical results in an attempt to provide a broader explanatory and predictive theory of the role of multi-point crossover in genetic algorithms. In particular, we extend the tradi- tional disruption analysis to include two general forms of multi-point crossover: n-point crossover and uniform crossover. We also analyze two other aspects of multi-point crossover operators, namely, their recombination potential and exploratory power. The results of this analysis provide a much clearer view of the role of multi-point crossover in genetic algorithms. The implications of these results on implementation issues and performance are discussed, and several directions for further research are suggested.