Analysing crossover operators by search step size
Guangming Lin, Xin Yao · 2002
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. The paper analyses 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 are 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 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 optimisation problems.