The Simple Genetic Algorithm

The second major section is a review of the uses of GAs in chemical applications, stressing variants on the GA rather than the chemically relevant results. Because well over 100 papers have been published in the field in the last few years, only representative and especially illustrative work is reviewed in depth. 

The final section gives references and sources of more information and software, much of it on-line. 

This section provides an overview of what a GA is, why it works, and some of the reasons why it can fail. Many research groups are using GAs to solve a variety of problems. In almost all cases, however, the underlying GA is no more than a variant on Holland s original formulation which has come to be known as the simple GA (SGA). We start by describing this in detail and then discuss some of the variations. 

To make the ideas concrete, we illustrate them with a simple parameter estimation problem. For the model problem, assume that inhibition constants have been measured for a series of 10 compounds, and a quantitative struc-ture-aaivity relationship (QSAR) model has been developed of the form 

In the SGA, each individual is represented by a binary chromosome that is simply a string of Is and Os. This string can then be translated into parame- 

---

Fonseca and Fleming (1993) proposed a modification of the simple genetic algorithm (SGA) at the selection level. The basic concepts of the proposed MOGA are the ranking based on the Pareto dominance and sharing function. The Pareto dominance-based rank is the same as one plus the number that certain individual dominates... 

Vose, M.D. (1999). The Simple Genetic Algorithm Foundations and Theory, MIT Press, Cambridge (MA), 251 p. 

A similar approach as for mutation can be adopted for recombining genetic strings. In the simple genetic algorithm that we want to model here, we define the recombination operation symmetrically in the two children produced. 

Koehler, G. (1997) Diagonalizing the Simple Genetic Algorithm Mixing Matrix, in Belew, R.K., and Vose, M.D. (eds.). Foundations of Genetic Algorithms 4, MIT Press, Boston. 

In traditional simple genetic algorithm, the mutation/crossover operators are processed on the chromosome indiscriminately over the loci without making use of the loci statistics, which has been demonstrated to provide useful information on mutation operator [9]. In our mutation matrix formalism, the traditional genetic algorithm can... 

The following prescription allows a quick implementation of a simple genetic algorithm to a given optimization problem. 

To determine the optimal parameters, traditional methods, such as conjugate gradient and simplex are often not adequate, because they tend to get trapped in local minima. To overcome this difficulty, higher-order methods, such as the genetic algorithm (GA) can be employed [31,32]. The GA is a general purpose functional minimization procedure that requires as input an evaluation, or test function to express how well a particular laser pulse achieves the target. Tests have shown that several thousand evaluations of the test function may be required to determine the parameters of the optimal fields [17]. This presents no difficulty in the simple, pure-state model discussed above. 

The most distinctive feature of the algorithm is its use of a population of potential solutions, so it is reasonable to ask why it might be more effective to work with many potential solutions when conventional methods require only one. To answer this question, and to appreciate how the genetic algorithm works, we consider a simple example. 

---