Spears W.M. Evolutionary Algorithms: The Role of Mutation and Recombination

Springer, 2000. — 223 p.The main theme of the book is as follows. First, a static, component-wise analysis of recombination and mutation is performed. This analysis highlights some of the strengths and weaknesses of both operators. For example, the analysis suggests that increasing the number of peaks in a fitness landscape (i.e., its multimodality) can have a highly deleterious effect on an EA with recombination. This suggestion is confirmed via a dynamic Markov chain analysis of an EA on very small problems. The dynamic analysis also suggests that the relative heights of the peaks can influence the utility of recombination. Finally, these results are empirically confirmed on real problems through the use of a novel multimodality problem generator that produces random problems with a controllable amount of multimodality. When all peaks have equal heights, increasing the number of peaks has an increasingly deleterious effect on the performance of an EA with recombination. However, gradually lowering the heights of the suboptimal peaks is beneficial to the performance of recombination. Interestingly, the EA with mutation (and no recombination) is almost completely unaffected by the number of peaks or their heights. As well as following the main theme, the book also takes occasional excursions into related theoretical areas, in order to unify the existing theoretical techniques more closely. Using a static analysis, a No Free Lunch theorem is proven for recombination, demonstrating a tight relationship between the disruptive and constructive aspects of recombination. An intriguing relationship is also demonstrated between uniform recombination and mutation when the cardinality of the representation is two and there is maximum population diversity. The book also shows a close relationship between the static analyses and a dynamic analysis of a population undergoing recombination and/or mutation by demonstrating that the more disruptive an operator is (a static concept), the faster the population approaches an equilibrium distribution (a dynamic concept).