next up previous

4.2 Genetic Algorithms

Kirkpatrick [40] has described SA as ``an example of an evolutionary process modeled accurately by purely stochastic means,'' but this is more literally true of another class of new optimization routines known collectively as Genetic Algorithms (GAs). These attempt to simulate the phenomenon of natural evolution first observed by Darwin [12] and recently elaborated by Dawkins [14].

In natural evolution each species searches for beneficial adaptations in an ever-changing environment. As species evolve these new attributes are encoded in the chromosomes of individual members. This information does change by random mutation, but the real driving force behind evolutionary development is the combination and exchange of chromosomal material during breeding.

Although sporadic attempts to incorporate these principles in optimization routines have been made since the early 1960s (see a review in Chapter 4 of Goldberg [31]), GAs were first established on a sound theoretical basis by Holland [37]. The two key axioms underlying this innovative work were that complicated nonbiological structures could be described by simple bit strings and that these structures could be improved by the application of simple transformations to these strings.