Genetic algorithms + data structures = evolution programs. (English) Zbl 0763.68054

Artificial Intelligence. Berlin etc.: Springer-Verlag. XIV, 250 p. (1992).
Nearly three decades of research and applications have demonstrated that the search process of natural evolution can yield very robust, direct computer algorithms. The resulting evolutionary algorithms are based on simulation of a learning process within a population of individuals, each of which represents a point within the search space. The population evolves towards better regions (survival of the “fittest” by means of randomized processes of variations (mutuations) and selection (using quality information — “fittness” — of the search points). This book discusses a main stream of instances of evolutionary algorithms: Genetic algorithms (developed in the US), and includes a chapter about a second approach: the Evolution strategies (developed in Germany). The title of this book rephrases the famous expression used by N. Wirth for his book [Algorithms + Data Structures = Programs, Prentice-Hall (1976; Zbl 0375.68005)]. Both books share a common idea. To build a successful program, appropriate data structures must be used. In the case of an evolutionary algorithm or an evolution program the data structures correspond to the individual chromosome representation.
The coding of chromosomes has a long and controversial history in the community of evolutionary search. The author studies binary representations traditionally used in genetic algorithms and real-coded (or floating point) representations used in evolution strategies. The book is organized as follows.
Part I serves a survey of motivation of evolutionary algorithms, especially of genetic algorithms.
In part II the floating point representations are explored. Some experimental comparisons of binary and floating point representations are discussed. Evolution programs are presented to handle constrained problems, and various test cases are considered.
Part III discusses a collection of evolution programs to explore their applicability to a variety of problems: the transportation problem, the traveling salesman problem, drawing graphs, scheduling, and partitioning, machine learning.
The “artificial live” community will read this book with great interest. In general, the book will be of interest to the operations research community, and everyone who faces challenging optimization problems by means of simulation of “natural” evolutionary principles. College level mathematics and basic knowledge in programming are sufficient to understand the book.
Reviewer: J.Born (Berlin)


68T05 Learning and adaptive systems in artificial intelligence
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
68-02 Research exposition (monographs, survey articles) pertaining to computer science


Zbl 0375.68005