Book Review
Genetic Algorithms in Search, Optimization, & Machine Learning

Review

3 stars

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

Brief Description of Contents

Chap. 1.

A Gentle Introduction to Genetic Algorithms

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.

Genetic Algorithms Revisited: Mathematical Foundations

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.

Computer Implementation of a Genetic Algorithm

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.

Some Applications of Genetic Algorithms

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.

Advanced Operators and Techniques in Genetic Search

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.

Introduction to Genetics-Based Machine Learning

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.

Applications of Genetics-Based Machine Learning

Contains a number of examples of genetics based machine learning, starting with the first system CS-1. Also discussed is the CL-ONE system that is able to convert a traditional artificial intelligence knowledge base into classifier system representation. The use of classifier systems to implement sequential program learning is also briefly discussed. In this section the author describes how in 1985 Crammer simplified the Turing-equivalent language PL, and devised a simple language for the calculation of primitive recursive functions and in the search for a simple binary multiplication program.
Chap. 8.

A Look Back, a Glance Ahead

Briefly reflects on the style of the book and the future of genetic algorithms.

Appendices

A

Review of Combinations and Elementary Probability

Provides a short introduction or refresher course in finite sets, combination counting and elementary probability.
B

Pascal with Random Number Generation for Fortran, Basic, and Cobol Programmers

Aims to provide enough knowledge for an experienced programmer to understand the code in the book.
C

A Simple Genetic Algorithm (SGA) in Pascal


D

A Simple Classifier System (SCS) in Pascal


E

Partition Coefficient Transforms for Problem Coding Analysis

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.

Back