Genetic Algorithms + Data Structures = Evolution Programs

The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera ready by author 45/3140-5 4 3 2 1 O-Printed on acid-free paper To the next generation: Matthew, Katherine, Michael, Thomas, and Irene X PrefaceI would like to acknowledge a series of grants from North Carolina Supercomputing Center (1990Center ( -1991)), which allowed me to run the hundreds of experiments described in this text. This book discusses a class of algorithms which rely on analogies to natural processes - algorithms based on the principle of evolution, i.e., survival of the fittest. In these algorithms, called evolution programs, a population of individuals undergo a sequence of transformations. The individuals strive for survival: a selection scheme biased towards fitter individuals selects the next generation. After some generations, the program converges and the best individual hopefully represents the optimum solution. Hence evolution programming techniques are applicable to various hard optimization problems. The book discusses constrained optimization problems in the areas of optimal control, operations research, and engineering. The problems include optimization of functions with linear constraints, the traveling salesman problem, scheduling and partitioning problems, etc. All methods are illustrated by results obtained from various experimental systems. The book collects, in a unified and comprehensive manner, the results of evolution programming techniques previously available only in widely scattered research papers. The importance of these techniques has been growing in the last decade, since evolution programs are parallel in nature, and parallelism is one of the most promising directions in computer science. The book is self-contained and the only prerequisite is basic undergraduate mathematics. It is aimed at researchers, practitioners, and graduate students in the areas of computer science (especially artificial intelligence), operations research, and engineering 'What does your Master teach?' asked a visitor. 'Nothing, ' said the disciple. 'Then why does he give discourses?' 'He only points the way - he teaches nothing.' Anthony de Mello, One Minute Wisdom During the last three decades there has been a growing interest in algorithms which rely on analogies to natural processes. The emergence of massively parƯ allel computers made these algorithms of practical interest. The best known algorithms in this class include evolutionary programming, genetic algorithms, evolution strategies, simulated annealing, classifier systems, and neural netƯ works. Recently (1-3 October 1990) the University of Dortmund, Germany, hosted the First Workshop on Parallel Problem Solving from Nature [164]. This book discusses a subclass of these algorithms - those which are based on the principle of evolution (survival of the fittest). In such algorithms a popuƯ lation of individuals (potential solutions) undergoes a sequence of unary (mutaƯ tion type) and higher order (crossover type) transformations. These individuals strive for survival: a selection scheme, biased towards fitter individuals, selects the next generation. After some number of generations, the program converges - the best individual hopefully represents the optimum solution. There are many different algorithms in this category. To underline the simƯ ilarities between them we use the common term "evolution programs." Genetic algorithms are founded upon the principle of evolution, i.e., survival of the fittest. Hence evolution programming techniques, based on genetic algorithms, are applicable to many hard optimization problems, such as optimization of functions with linear and nonlinear constraints, the traveling salesman problem, and problems of scheduling, partitioning, and control. The importance of these techniques has been growing in the last decade, since evolution programs are parallel in nature, and parallelism is one of the most promising directions in computer science. The book is self-contained and the only prerequisite is basic undergraduate mathematics. It is aimed at researchers, practitioners, and graduate students in computer science and artificial intelligence, operations research, and engineering. This second edition includes several new sections and many references to recent developments. A simple example of genetic code and an index are also added. Writing an evolution program for a given problem should be an enjoyable experience - this book may serve as a guide to this task. Front Matter....Pages I-XIV Introduction....Pages 1-10 Front Matter....Pages 11-11 GAs: What Are They?....Pages 13-30 GAs: How Do They Work?....Pages 31-42 GAs: Why Do They Work?....Pages 43-53 GAs: Selected Topics....Pages 55-72 Front Matter....Pages 73-73 Binary or Float?....Pages 75-82 Fine Local Tuning....Pages 83-96 Handling Constraints....Pages 97-126 Evolution Strategies and Other Methods....Pages 127-138 Front Matter....Pages 139-139 The Transportation Problem....Pages 141-163 The Traveling Salesman Problem....Pages 165-191 Drawing Graphs, Scheduling, and Partitioning....Pages 193-214 Machine Learning....Pages 215-229 Conclusions....Pages 231-239 Back Matter....Pages 241-252