zbMATH — the first resource for mathematics

Evolutionary algorithms. The role of mutation and recombination. (English) Zbl 0952.68151
Natural Computing Series. Berlin: Springer. xii, 239 p. (2000).
Summary: This book has a central theme with occasional excursions into related areas. The central theme proceeds as follows. First, the book will introduce a novel test-problem generator based on Boolean satisfiability problems, which will serve to further clarify the relative roles of mutation and recombination on epistatic and multimodal problems. After this the book will start to delve into the theoretical aspects of recombination, by generalizing the traditional static schema theory for recombination. The purpose of the theory is to compute the disruptive aspects that \(n\)-point recombination and \(P_0\) uniform recombination have on \(k\)th-order hyperplanes \(H_k\). Then the theory will be generalized further to include the constructive aspects of recombination. At this point a schema theory for mutation can be derived, which also takes into account the disruptive and constructive aspects of mutation. Population homogeneity and arbitrary cardinality alphabets will be taken into account in a natural fashion. Mutation and recombination can thus be fairly compared, and various general hypotheses will be made concerning the relative aspects of recombination and mutation. This comparison occurs in Chap. 8.
The book then introduces a complete dynamic model of an EA (Evolutionary Algorithms) which uses Markov chains. The experiments performed with the Markov chain model are inspired by the insights gained from the static schema theories from Chaps. 3-8. The results of the Markov chain approach yield further hypotheses concerning the role of mutation and recombination on simple test functions.
Finally, the book confirms those hypotheses by examining the performance of an actual EA on real functions. A test-problem generator is created, motivated by the results from the Markov chain approach. The results of the experiments validate the results from the schema and Markov chain theories, completing the central theme.
However, this book also takes a number of interesting excursions, which often help to clarify the roles of mutation and recombination in EAs. First, we use the mathematical technique for handling population homogeneity to generalize prior static analyses of the distributional and positional biases of recombination, and provide a comparison with mutation. Then we examine simple dynamic theories concerning the distribution of populations undergoing recombination and mutation (in the limit of large time) and connect these theories with the prior static schema theories. We also provide a simple dynamic model that includes selection and mutation, and illustrate that for certain classes of problems an expectation model of a simple EA (without recombination) can be built that handles realistically large problems. These excursions shed more insight into the roles of recombination and mutation, and provide new theoretical tools for examining simple EAs.
Finally, the book (in perhaps its most important excursion), gives an automatic algorithm for simplifying Markov chain theories in general. Although motivated by a study of EAs, the algorithm will work on arbitrary Markov chains that are derived from other complex systems, and hence has a scope well beyond that examined in this book.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science