Genetic Algorithms: The Design of Innovation

The first edition of this book (Goldberg, 2002) was welcomed as an important contribution to the understanding and design of scalable genetic algorithms. Goldberg's theory of facetwise models proves invaluable to GA understanding and design, and the core chapters of the book continue to make those important arguments; however, they are brought up to date with the most important recent results, including population timing and sizing results.The chapter on scalable GA design (Chapter 12) gets a thorough overhaul by introducing other key scalable GA techniques, including the DSMGA (Dependency Structure Matrix GA) and others, and discussing how they relate to earlier models. Although the literature tends to emphasize small differences between different methods, the chapter shows the common theoretical and methodological threads running through all scalable methods. The DSMGA results are particularly important because of the light the shed on probabilistic model builders such as the Bayesian Optimization Algorithm.In the first edition, the possibility of efficiency enhancement was discussed briefly, but since 2002, great strides have been made in the practical speedup of scalable genetic algorithms through parallelization, time continuation, problem relaxation, and hybridization. Individually these techniques have demonstrated surefooted effectiveness in speeding GA solutions; however, when used in combination with both structural and fitness model building techniques, genetic algorithms can often be speeded by two or more orders of magnitude in so-called supermultiplicative speedups. This exciting possibility enables the solution of hard problems that were formerly beyond the reach of GAs because solution times and costs were prohibitive.The first edition of the text emphasized the importance of both theory and implementation practice as being important to the solution of real-world problems. A new chapter, Chapter 14, A Billion Variables and Beyond, shows how to put together the ideas in the book toward the solution of problems with millions and billions of decision variables. Traditional operations research and optimization is limited in practice to problems with thousands of decision variables because of the double whammy of the curse of dimensionality and the serial bottlenecks inherent in many of the procedures in common use. This chapter presents recent results in demonstrating practical scalability of GAs on a problem with over a billion variables, and shows how these results can be used to obtain routine solutions on many important problems with millions and even billions of variables.Much of the book is devoted to understanding and applying useful, cool technology on increasingly difficult problems of science, technology, and commerce, but a new final chapter returns to the more philosophical tone of the early part of the text. Scalable genetic algorithms are cool technology, but GA practitioners can hardly help but have the way they think about the world permanently altered by the philosophical possibilities of "population thinking." In the narrow realm of technology, populations represent a disembodied set of solutions to some particular problem, but it does not require an act of great imagination to think of GA populations as groups of agents or organisms or firms or even people. In this way, the lessons learned from this book can be applied to philosophical reflection about a variety of innovative, inventive, or even creative systems. These ideas lead inexorably to wonder about whether computer programs might ever achieve a kind of computational consciousness, and the final chapter concludes with some thoughts on that possibility.The first edition was an important landmark in the theory and practice of genetic algorithms, and problem size and difficulty of problem tackled has progressed rapidly since its publication. Genetic Algorithms: The Design of Innovation (2nd edition) updates that text with important additions, new groundbreaking material, and important suggestions for key research directions and likely lines of successful inquiry.

David E. Goldberg (BSE, 1975, MSE, 1976, PhD, 1983 in Civil Engineering from the University of Michigan, Ann Arbor) is a Professor of General Engineering at the University of Illinois at Urbana-Champaign (UIUC) and director of the Illinois Genetic Algorithms Laboratory (IlliGAL, http://www-illigal.ge.uiuc.edu/). Between 1976 and 1980 he held a number of positions at Stoner Associates of Carlisle, PA, including Project Engineer and Marketing Manager. Following his doctoral studies he joined the Engineering Mechanics faculty at the University of Alabama, Tuscaloosa, in 1984 and he moved to the University of Illinois in 1990. Professor Goldberg was a 1985 recipient of a U.S. National Science Foundation Presidential Young Investigator Award, and in 1995 he was named an Associate of the Center for Advanced Study at UIUC. He was founding chairman of the International Society for Genetic and Evolutionary Computation (http://www.isgec.org/), and his book Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, 1989) is widely used and cited. His research focuses on the design, analysis, and application of genetic algorithms--computer procedures based on the mechanics of natural genetics and selection--and other innovating machines.