Analyzing crossover operators by search step size

Crossover plays an important role in GA-based search. There have been many empirical comparisons of different crossover operators in the literature. However, analytical results are limited. No theory has explained the behaviours of different crossover operators satisfactorily. This paper analyzes crossover from quite a different point of view from the classical schema theorem. It explains the behaviours of different crossover operators through the investigation of crossover's search neighbourhood and search step size. It is shown that given the binary chromosome encoding scheme GAs with a large search step size is better than GAs with a small step size for most problems. Since uniform crossover's search step size is larger than that of either one-point or two-point crossover, uniform crossover is expected to perform better than the other two. Similarly, two-point crossover is expected to perform better than one-point crossover due to its larger search step size. It is also shown in this paper that increasing the number of crossover points will increase crossover's search step size. The analytical results are supported by the experimental studies on 12 benchmark function optimization problems.