Book Review: Evolutionary Computation: A Unified Approach

by Amit


My background: I am currently working full time on research problems in Genetic Algorithms. My current work is in using GAs for multi-modal optimization. My experience in this field is 6 months, my interest infinite :)

Evolutionary Computation: A Unified Approach brings together a summarized view of three distinct fields of Evolutionary Computing (EC)- Evolutionary Strategies (ES), pioneered by Rechenberg and Schwefel, Evolutionary Programming (EP), pioneered by Fogel and Genetic Algorithms (GA) pioneered by John Holland. A fundamental book such as this one helps the EA researcher to sit back and identify the fundamental principles of these different algorithms. Throughout the book, a unified view of the fields is presented and thus this book is a must read for the evolutionary computing researcher- novice, like me or the experienced. This book explores a very experimental approach to the study of these algorithms and is thus easy to follow, almost like reading a novel for the EA researcher.

In Chapter 1, fundamental characteristics of a simple evolutionary system are presented. EV, a simple evolutionary system is presented and sample runs over a 1-dimensional and 2-dimensional landscape is presented. First ideas of evolutionary systems as problem solvers are presented in this chapter. A key idea presented in this chapter is that simulated evolutionary systems try to draw inspiration from the biological evolutionary system to design better algorithms to solve complex computational problems, and not mimic them. The graphical plots of the results demonstrates the ideas of convergence, and though not explicitly mentioned, the EC researcher easily identifies this as a useful way to demonstrate the progress of a Evolutionary algorithm.

In Chapter 2, a step is taken back to look at the historical development of the three fields of ES, EP and GA. This chapter puts the three research communities into perspective of their historical development.

In Chapter 3, the simple EV system introduced in Chapter 1 is extended to the generic EV(m,n) system of m parent population, and an offspring population of size n. What this generalization does is that it allows talking about the canonical EP, ES and GA in one common framework.

Chapter 4 presents a first detailed unified treatment of the three algorithms. The following common pattern of evolutionary dynamics are presented:

  1. a fixed size population, m is evolved over time,
  2. the current population is used as a parent population to produce n offspring, and
  3. the expanded population size is reduced from m+n to m

Its apparent that the EA researchers have several design choices to make: a correct value of m and n, the selection of the parent population that takes part in the process to generate offspring, and selecting the m population size from the m+n population. These questions are addresses in the rest of this chapter by the discussions on population sizing, selection mechanisms, reproductive mechanism and representation issues.

So far, the book has addressed the ideas of simulating simple evolutionary systems and their temporal dynamics. How can such systems be used to solve computational and engineering problems is addressed in chapter 5. Using EAs for search, optimization-single objective and multi-objective, machine learning and automatic programming are discussed here. This is a chapter that will be useful to readers beyond the EA research community, since they provide insights into using EA for practical problem solving, which can be useful in complex, high-dimensional search spaces and not much information is available about the problem at hand.

Chapter 6 is of utmost importance and interest for the EA researcher as it describes some of the ways that EAs can be theoretical analyzed. Depending on the property of a EA you are analyzing, the tools for analysis also vary:

  • EA population dynamics -> dynamical systems tools
  • Stochastic properties of EAs -> Markov processes
  • Aggregate properties of EAs -> Statistical mechanics tools
  • Computational complexity¬† of EAs -> Algorithmic Analysis tools
  • Optimization properties of EAs -> Mathematical tools

I am yet to grok this chapter in its full capacity and power, so I shall get back to it after a detailed reading.

The second last chapter of the book, Chapter 7 takes a look at some of the advanced EA topics such as self-adaptive EAs, Multi-objective EAs, memetic EAs, EAs applied to dynamic landscapes and others.

The book concludes in Chapter 8 by urging more work in the quest the book started with- more unification of the different fields in Evolutionary computation.

Advertisements