Genetic algorithms: Principles and perpectives. A guide to GA theory (Q1868000)

Anyone working in combinatorial optimization is aware of the proliferation of papers applying genetic algorithms (GA) to basically any problem one can imagine, to quote the authors: ``\dots sadly, too many of them have titles like 'A New Genetic Algorithm for the Multi-Resource Travelling Gravedigger Problem with Variable Coffin Size'''. However, theoretical investigations that help understand GAs are far less plentiful. This monograph is a first book-length description of the different theoretical perspectives on GAs that have been developed. These different streams of research provide the structure of the book. In Chapter 2 the basic principles of GAs are reviewed (representation, population, operators). Chapter 3 is an account of schema theory as developed mainly by Holland and Goldberg. It also includes the critique that schema theory has received in recent years (In Chapter 10, Reeves and Rowe refer to ``the demise of schema theory''). Chapter 4 considers the implications of the No-Free-Lunch Theorem (averaged over all possible functions, the performance of all search algorithms that satisfy certain conditions is the same) for GAs. Genetic Algorithms as Markov processes are the topic of Chapter 5, leading on to the dynamical systems model of GAs discussed in Chapter 6. While the aim of Markov process and dynamical systems models is to investigate the probability distribution over all possible populations in a single iteration, Chapter 7 takes a look at obtaining approximations of the trajectory of the population using methods of statistical mechanics. Is it possible to predict the performance of GAs on problem classes (and thus discriminate those where they work well from those where they do not)? Chapter 8 gives an account of work in that area. This is related to the concept of landscapes (Chapter 9). Landscapes allow comparison of GAs and other heuristic techniques. A main argument is that the behaviour of a GA cannot be predicted from the fitness landscape alone. Chapter 10 gives a summary of the key points of the previous chapters, the impact of theory on practice and future research directions. Each chapter is concluded with bibliographic notes and some exercises. An appendix of test functions and an extensive bibliography (350 entries) are provided. The main arguments are well illustrated with examples and while the mathematical treatment is rigorous, the book is written in an engaging and accessible style. With these features it may be used as a text for a course on GAs and should be essential reading for anyone interested in genetic algorithms.