Evolutionary Computation: A Unified Approach
Kenneth A. DeJong, The MIT Press, Cambridge, MA, 2006, 256 pages, 32.95 £UK, hardback (ISBN 0-262-04194-4).
‘Oh great’, you might think, glancing at the title, ‘another textbook on genetic algorithms’. Happily, this is emphatically not the case. Kenneth DeJong, a highly-respected researcher, has written a wonderful integrative text that treats all flavours of evolutionary computation as specific instances of a single general class of evolutionary algorithms (EAs)—neatly sidestepping the decades of in-fighting between the respective adherents of genetic algorithms, evolutionary programming and evolutionary strategies.
Right from the outset, the book makes its case. The first chapter demonstrates how a simple evolutionary algorithm—including the concepts of genetic encoding, populations, fitness and mutation—can search for maxima on simple one- and two-dimensional fitness landscapes. Only then, in the subsequent two chapters, does DeJong take a step back, providing a (mercifully short) historical background, followed by an insightful treatment of how his initial simple algorithm can be elaborated to describe all three of the dominant canonical algorithms mentioned above. In the process, the similarities and differences between those algorithms are made precise, leaving little room for disagreement.
In practice, many researchers (including myself), whether intentionally or otherwise, have mixed and matched aspects of all three canonical algorithms as the problem domain required. For most, then, the centrepiece of the book is a short yet comprehensive account of the integrative framework for EAs, turning an ad hoc mix-and-match strategy into a cohesive working method. Once in place, DeJong quickly turns to elaborating just why we ought to use this framework, by considering design issues across the application domains of EAs.
Throughout, the book is sprinkled with useful, practical advice on design choices that affect the performance of EAs. For example, DeJong points out that the 1- and 2-point crossover traditionally used in genetic algorithms introduces a distance bias, so that genes far apart on the genome are unlikely to be inherited together. To overcome this limitation, the simple but elegant ‘parameterized uniform crossover’ is suggested, wherein there is a fixed probability of inheritance for all genes, effectively creating a dynamic number of crossover points. In most cases, the lengthy treatment of the analysis of EA dynamics later in the book makes clear why these recommendations were made, neatly tying up the hanging question of ‘yes, but why?’ for the more incredulous among us.
This section on analyses of EA dynamics dominates the book, lengthwise, but is well constructed, allowing the reader to follow the overall flow of the arguments without much effort, or dip in at will to a relevant part of the analysis. The analyses presented are mostly numerical, avoiding the limited scope of an exact analytic approach. DeJong begins by considering selection-only and reproduction-only models in isolation, to tease apart the contributions of each process to EA behaviour. He starts with the simplest possible EA model, of uniformly random selection, to demonstrate how genetic drift—the tendency towards homogeneity of a population over time—is an inherent feature of the selection process. From there, he effectively charts how most other parts of an EA act to counter genetic drift, simultaneously shedding as much light on the effectiveness of biological reproduction via inheritance as on why EAs are good general problem solvers. These separate analyses make clear the trade-off built into any EA between selection operators that reduce diversity by favouring high-fitness individuals, and reproduction operators that generate diversity by creating individuals that are similar, but not identical, to their parents. He makes this explicit by combining the separate analyses, exploring how different forms of these operators achieve a balanced EA.
Much of the book is concerned with simple EA problems characterized by a single population, random mating, linear genomic representations and a static fitness landscape. This is sufficient to cover many applications, and is certainly enough to illustrate clearly the main theses of the book. Wisely, he has chosen just to touch on important advanced topics in this field, providing a brief background, a few suggestions and a few key references, before swiftly moving to the next. The prose avoids meandering into deep problems, each of which is worthy of a comprehensive treatment in its own right, retaining the lightness of touch that characterizes much of this book. Thus, we are treated to some interesting comments on, amongst others, the potential forms self-adapting EAs might take, the handling of dynamic fitness landscapes, and the use of multi-objective EAs.
Your reviewer is a user of EAs, rather than a researcher of their properties, and suspects that many of the design choices are well known to those who are more familiar with the theory. None the less, such a cohesive and practical treatment is a marvellous achievement in a surprisingly short book. If you need any insight into EAs, start here.