Genetic algorithms in search, optimization and machine learning. (English) Zbl 0721.68056

Goldberg, David E.

Reading, MA: Addison-Wesley. XIII, 412 p. DM 104.00 (1989).

This book is about genetic algorithms (GAs) - particularly robust search procedures based on the mechanics of natural selection and natural genetics. GAs operate on populations of strings, with the string coded to represent some underlying parameter set. Genetic operators are applied to successive string populations in order to create new populations; they simulate well-known biological metaphors such as reproduction, crossover, and mutation with corresponding string operations which employ random number generation, string copying, and partial string exchanging as basic mechanisms. Despite the simplicity of their string manipulation strategies, GAs achieve high performance rates for various application domains under strict experimental conditions.
The first five chapters of the book are devoted to GAs in search and optimization. After an introduction to the topic of genetic search and a description of a simple genetic algorithm in chapter 1, chapter 2 introduces the mathematical foundations on which GAs are based, covering topics such as schemata (similarity templates) and the fundamental theorem of GAs that quantifies growth and decay rates in string populations precisely.
Chapter 3 introduces a computer implementation of GAs by way of an example. Specially, Pascal code for a simple genetic algorithm for optimizing a simple function of one variable is presented along with a number of extensions.
Chapter 4 presents an historical account of early GAs together with a survey of current applications drawn from engineering, medicine, and game theory (iterated prisoner’s dilemma).
Chapter 5 examines more advanced genetic operators (low-level operators operating at the chromosomal level, such as dominance, inversion, intrachromosomal duplication, deletion, translocation, and segregation, as well as higher level, population-oriented operators such as migration, marriage restriction, and sharing functions); it also contains of applications illustrating their use. In addition, hybrid techniques are discussed, i.e. GAs crossed with various problem-specific search techniques.
Chapters 6 and 7 consider the application of GAs in machine learning systems. Chapter 6 gives a generic description of the most common type of a genetics-based machine learning system, the classifier system; a system that learns syntactically simple string rules (classifiers) to guide its performance in an arbitrary environment. The theory of operation of such a system is briefly considered, and a Pascal implementation of a single classifier system is presented and applied to the learning of a boolean function. Finally, chapter 7 rounds out the picture of genetics-based learning systems by presenting an historical review together with a selective survey of systems and topics in the field.
Appendices contain a brief review of combinatorics and elementary probability theory on which GAs are based, an introduction to the essentials of the programming language Pascal, and the complete Pascal code for two GAs, a simple genetic algorithm and a simple classifier system.

Reviewer: U.Hahn (Freiburg i.Br.)

MSC:

68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W10	Parallel algorithms in computer science
68T05	Learning and adaptive systems in artificial intelligence
68-02	Research exposition (monographs, survey articles) pertaining to computer science

Keywords:

machine learning; control methods; genetic algorithms; search; optimization; classifier system