Book Review

Genetic Algorithms in Search, Optimization, & Machine Learning

This is an academic textbook rather than an industrial handbook, (which, as an engineer I prefer). The early chapters present the theory of how and why genetic algorithms work. While covering the theory of why GAs work and the various dos and don'ts

relating to their application, there is little practical help in the book on how to implement a GA to solve real life problems. The textbook feel is continued by the presence of questions and programming tasks (without answers).

The book includes many examples of problems solved with GAs, however no details are given of the implementation and the examples are presented mainly to describe the evolution of GAs.

On the plus side, book includes the code, (in Pascal) for a Simple Genetic Algorithm, (SGA), and a Simple Classifier System, (SCS). The full code is presented in the appendices, but the key sections are developed and explained in the main body.

*4 Sep 2001*

Chap. 1.

The chapter introduces what GAs are, in terms of their mechanics, power, and differences from more conventional optimisation techniques.

A simple GA is presented and worked through by hand. The principles of schemata and the lingo

of GAs are also introduced.

Chap. 2.

Continues from chapter 1, giving a more rigorous appraisal of genetic algorithm performance using a more careful analysis of schemata (similarity templates). The primary result that **high-performance, short-defining-length, low order schemata are best suited to solving problems.**

Further insight of the workings of GAs is obtained through the analysis of the Minimal Deceptive Problem, the smallest problem that can possibly deceive or mislead a simple genetic algorithm. However it turns out that for many likely initial conditions the MDP is not GA-hard.

Chap. 3.

Contains a description of and the code (in Pascal) for a bare-bones genetic algorithm; a Simple Genetic Algorithm (SGA). The description discusses the details of implementation;

- object-to-fitness transformations, (which convert the normal objective function, whether a maximisation or minimisation problem, to proper fitness form);
- fitness scaling, (which maintains more careful control over the allocation of trials to the best strings);
- and the
*principle of minimal alphabets*and the*principle of effective building blocks*which help the GA user design effective codings.

The code listing contains;

- a data structure with a coding based on the above principles, and the author has found useful in a number of applications. The coding is a multi-parameter, mapped, fixed point one,
- three routines to perform a simple stochastic selection and replacement, (
roulette wheel selection

), crossover and mutation.

The topic of discretisation for the optimisation of functions over a continuum is introduced. As is the addition of exterior penalty functions to apply inequality constraints to a problem. *See Optimization for Engineering Design chapter 4.2.1. for further details of interior and exterior penalty functions for traditional optimisation techniques.*

Chap. 4.

Covers the rise of genetic algorithms and their establishment as a viable search and optimisation methods is described.

The five functions of De Jung's function minimisation problems are included.

The history of genetic algorithms saw the rise in popularity of stochastic remainder selection techniques, for which example code is included.

As well as providing a list of applications were genetic algorithms have been implemented, the author presents the results of his own work (gas pipeline optimisation and structural optimisation), as well as those of others including medical image registration and the iterated prisoner's dilemma problem, which is drawn from political science and game theory.

Chap. 5.

Covers the theory of some of the advanced operators and techniques available for improving simple genetic algorithms.

**Micro-operators** - genetic operators operating a chromosomal level - that are observed in nature; dominance and diploidy, reordering operators, segmentation, translocation, duplication and deletion.

Dominance and diploidy provide a method of implementing a long-term population memory and have been shown to be useful in stationary and especially cyclic functions. Code to implement the Holland-Hollstien trialletic dominance-diploidy scheme is given.

Chap. 6.

Provides details on the background, principles of operation, (that is a rule and message system, apportionment of credit system (**Bucket Brigade**), and genetic algorithm) implementation and performance of a classifier system.

A Simple Classifier System (SGS) is implemented in Pascal, the main aspects of which are described. To test the system it is interfaced to a six-bit multiplexer. The classifier's ability to learn to discount bad rules and promote good ones is demonstrated and the concept of default hierarchy is introduced.

Chap. 7.

Chap. 8.

A

B

C

D

E

Effective processing by genetic algorithms occurs **building blocks** - relatively short, low-order schemata with above average fitness values - combine to form optima or near optima.

The appendix presents a method of performing static schema analysis using Holland's method of partial coefficients. This can be used to identify appropriate functions, codings, and operators for better genetic algorithm performance.