Browse Books

Reviewer: Robert Goldberg

The authors introduce the concepts and applications of genetic algorithms. The perspective is that of a mathematician or physicist who is interested in optimizing a computationally intensive and difficult equation over all possible values (globally). In such a situation, standard numerical analysis root-finding techniques may be overwhelmed by the landscape of the output values, and could converge to a local optimal point that is not the global optimum. Genetic algorithms instead provide an alternative that dares to try directions of search in random areas of the domain. By combining information from more successful candidates, the genetic algorithm hopes to create a better solution to the problem. Although the perspective of the book is that of solving mathematical equations, the concepts clearly described can easily be applied to other applications as well. In fact, chapter 6 is dedicated to the discussion of advanced applications. The book is organized into seven chapters plus an appendix of pseudocode that outlines an implementation for the major operations involved in a genetic algorithm. Chapter 1 provides the background of optimization problems and describes how they are traditionally solved by minimum-seeking algorithms. Section 1.1.3 categorizes the various types of optimization problems in the literature, and provides the basis for the applications that will be discussed later (summarized in figure 1.2). Does solving the problem depend on whether there is prior knowledge of the function/process that is being optimized, or will trial and error adjust the parameters How many parameters are involved in the function (single versus multiple) Does the function model the situation at all times (static) or is it a dynamic function that changes with time (such as a shortest path involving traffic and weather conditions) Will the domain of acceptable values be discrete or continuous Are there any external constraints for the cost function and, if so, will they be linear or nonlinear in evaluation Finally, does obtaining the solution allow for a straightforward minimum-seeking search from some initial set of parameters, or does the system require random methods to find parameter sets These categories are discussed in detail. Chapter 1 concludes with an introduction of the genetic algorithm and its relationship to biological concepts. This relationship is further explored in chapter 2. Chapter 2 concentrates on the binary genetic algorithm, where the parameters are encoded by strings of binary digits (as opposed to real numbers, which are dealt with in chapter 3). The authors stress that choosing an appropriate cost function is directly linked to deciding which parameters to use. The chapter, like the rest of the book, is replete with mathematical formulas that help the reader understand the concepts. Coupled with the theory is a series of tables and, where appropriate, worked-out examples that further elucidate the material. On a smaller scale, this chapter discusses the relationship between the genetic algorithms and the biological processes on which they are based. Chapter 3 adapts the genetic algorithm to the case of real (continuous) parameters. This is not a simple task. For example, should crossover still exchange pieces of the underlying binary-encoded genome (chromosome), or should the parameters be treated on a phenome level where the parameters are swapped during crossover The book opts to treat these parameters as atoms, that is, indivisible pieces of information. Thus, crossover points occur between different parameters, but not within the binary representation of a given parameter. In section 3.1.6, other possible approaches are presented. For mutation (discussed in section 3.1.7), the case of continuous parameters is not much more complicated than the discrete case, although the authors point out that sophisticated approaches do exist. Chapters 4 and 6 deal with basic and advanced applications, respectively. The basic applications of chapter 4 are chosen because their implementation is “straightforward,” starting from the outline of the genetic algorithm developed in chapters 2 and 3. Basic applications include computer-generated music, word-guessing games, antenna design, and locating an emergency response unit that has to be directed to an emergency site. Section 4.1 deals with computer-generated music. This discussion is fascinating because fitness is based on a user's response, not just on pure mathematical evaluations. The more the user likes the music, the higher its fitness. The word guessing game of section 4.2 has to have its cost function (fitness) carefully chosen, but the overall structure of the genetic algorithm is identical to that of typical cases. For these applications, genetic algorithms perform quite well. The last two applications in chapter 4 are more advanced (dispatching emergency response units and setting an antenna in a proper position), but again use typical genetic algorithm structures. Chapter 6 presents more advanced applications, including the traveling salesman problem, robot trajectory planning, and solving high-order nonlinear partial differential equations. Solutions for these problems are based on genetic algorithms that incorporate the tricks of the trade presented in chapter 5, which gives details of each of the operators and discusses various alternatives. Finally, chapter 7 discusses the trends in the current literature and presents references to useful literature and software. The appendix includes pseudocode for the major operations involved in the genetic algorithm in the style of MATLAB code. This book is easy and sometimes humorous reading, and serves both novices and practitioners interested in variations on the basic theme well.