Industrial Applications of Genetic Algorithms:Genetic Algorithms in the Engineer's Toolbox

Previous | Table of Contents | Next

A BRIEF HISTORY

As with most technologies, the specifics of GA history are open to debate. This is due in part to the difficulties associated with distinguishing the lines of demarcation between GAs and other evolutionary algorithms. Therefore, this section is intentionally not restricted strictly to a discussion of GAs, rather it attempts to credit early researchers who developed techniques that served as a foundation upon which today’s GAs have been built.

Perhaps the earliest instance of an evolution-based technique related to modern GAs was suggested in the 1960’s by Rechenberg [1]. This technique was called evolution strategies (Evolutionsstrategie in the original German), and was originally used primarily in an attempt to design airfoils. It provided a mechanism by which real-valued parameters were altered to optimize an airfoil shape based on an objective function. This work was continued by Schwefel [9, 10] who served as a focal point of a reasonably active community of researchers. However, the “populations” in evolution strategies consisted of but two candidate solutions: a parent and an offspring which was a mutated version of the parent. For the most part, GAs are thought to have developed independently from evolution strategies. It has not been until recently that the two research communities have begun to interact significantly.

Evolutionary programming is a technique developed by Fogel, Owens, and Walsh [2] which is actually quite similar to modern GAs. In evolutionary programming, candidate solutions to a problem are represented as finite-state machines. New solutions are evolved by mutating the candidate solutions (the evolution is accomplished by randomly altering the state-transition diagrams). The production of new candidate solutions is driven by a fitness function. Unlike GAs, evolutionary programming uses only a mutation operator to provide variation in the population of candidate solutions.

Several other researchers in the 1950s and 1960s developed evolution-inspired computer algorithms. These efforts have not received the attention or follow-up that evolutionary programming and GAs have, but are worthy of mention nonetheless because they addressed the main application focal point of GAs, that being optimization and machine learning. Box [11], Martin and Cockerham [12], and Bledsoe [13] all developed algorithms that were based on the search capabilities apparent in natural systems. Additionally, there were a number of natural biologists including Baricelli [14] and Fraser [15, 16] who used computers early on to simulate evolution in very controlled experiments. However, these efforts did not address the more general optimization and search goals of GAs.

John Holland is generally credited with the invention of GAs. Holland, his students, and his colleagues at the University of Michigan developed a detailed approach to modeling natural evolution in the form of computer algorithms. Holland’s 1975 monograph entitled Adaptation in Natural and Artificial Systems describes the basic approach to the population-based search characteristics of today’s GAs. His book presented most of the genetic operators used in GAs including selection, recombination, mutation, and inversion. Interestingly enough, Holland’s original motivation was not optimization, rather it was to formally study the mechanisms of adaptation found in nature and to incorporate those mechanisms into computer-simulated systems. One of the real appeals of Holland’s work is that it set forth a theory attempting to explain why and how GAs worked. Holland’s schema theorem is still the most popular theory used to explain the success of GAs. In the years following the publication of Holland’s book, his students struck the greatest blows for GA acceptance through the publication of empirical studies in which GAs were used to solve optimization and machine learning problems [17-20].

The publication of John Holland’s book on adaptation in artificial systems represented a high water mark in the history of GAs. His book was the first document in which anyone had set forth the idea of using a population of candidate solutions in conjunction with a suite of genetic operators. A second major milestone in the history of GAs came with the publication of David Goldberg’s 1989 book entitled Genetic Algorithms in Search, Optimization, and Machine Learning [21]. This landmark text presented the GA as a straightforward approach to solving search problems of various kinds. It presented the GA as a problem-solving tool, and cited numerous instances in which researchers had applied GAs in various problem domains. The book also provided a clear and concise explanation of the theory of GAs. Pascal source code for most of the routines presented in Goldberg’s book allowed other researchers to experiment with GAs with a minimum of difficulty.

The publication of Goldberg’s text accelerated the application of GAs. The extent to which GAs progressed in the application domain is evidenced by the publication in 1991 of The Handbook of Genetic Algorithms [5] by Dave Davis. The first several chapters in this book served as a tutorial on GAs, providing the reader with the basic tools of GA implementation, but neglected the theoretical details. The remainder of the book consisted of chapters outlining GA applications. These subsequent chapters were written by individual researchers who had successfully applied a GA in their particular fields of interest. This book served as a testimonial to the applicability and the effectiveness of GAs in a number of problem domains and represented the state-of-the-art in GA applications. However, it also noted a problem at that time: most of the chapter authors were from academia or research firms, or were otherwise GA specialists.

Previous | Table of Contents | Next

Copyright © CRC Press LLC