In addition to gamete diversity due to genetic crossover and chromosomal segregation into gametes, additional diversity is brought about because of mutation. Mutation arises from errors in copying DNA. In mitosis, or cell division, mutation often has little effect, since the mutated cell will often die. However, in meiosis, mutation can have a significant impact since the mutated genetic code will propagate into the genetic code of every cell in the child. Even then, many mutations are not noticeable because they are a part of the genetic code that is unused. When mutation has a noticeable effect, it is generally for the worse. However, occasionally beneficial mutations occur which improve the ability of an individual (and eventually a species) to survive.
A final concept from biology that will serve our needs for an optimization engine is the idea of natural selection and the survival of the fittest, an idea stemming from Charles Darwin’s voyages of the H.M.S Beagle, during a period of time roughly contemporary with the work of Mendel and the American Civil War. The idea that the most fit individuals of a population survive to reproduce is directly used in GAs. These algorithms are based on an explicit fitness function, which will be used to determine which individuals “survive” and will be placed into a mating pool.
Clearly, the discussion in this section is at a high level and has been greatly simplified. The interested reader is referred to Crow [2] for a more thorough introduction to the topic.
1.5 The Canonical Genetic Algorithm
A century after the work of Mendel and Darwin, but a mere decade after the work of Watson and Crick, John Holland, a professor at the University of Michigan, proposed using the principles of biological genetics as a computation algorithm for optimization, a concept instantiated by a GA [3]. In this section, we will begin our consideration of GAs with a canonical GA similar to Holland’s original vision.
GAs are quite different from traditional optimization algorithms. First of all, GAs operate not on the argument of the function being optimized, but rather on an encoding of the argument. Second, rather than iterating to improve an estimate for an optimizer, GAs iterate to improve a large number of different estimates of the optimizer. This collection of estimates will be referred to as a population. The use of a population of estimated solutions improves the chances of finding a global optimum. Third, GA operations are based only on the values of the objective function—gradients and Hessians are not used, nor even estimated. This property is useful in function with discontinuities or with a discrete or mixed search space. Finally, GA operations are based on probabilistic rather than deterministic computations.
The first concept that must be set forth in a GA is that it, like evolution, operates on a population, not on an individual. We will denote the population within the GA as P[k], where k is the generation number. The kth generation consists of a number of individuals, that is,
(1.5-1)
where θi is the genetic code for the ith individual in the kth generation of the population and where Np denotes the number of individuals in the population, which should be an even number. The genetic code for the ith individual may be organized as
where Nc is the number of chromosomes, Ng is the number of genes, and
The fact that the genes are encoded results in a limitation of the domain of the parameter vector. In other words, the domain of possible values of each element of the parameter vector is inherently limited. In some cases, this property is very convenient, but in other cases this limitation on the domain of the parameter vectors is disadvantageous.
Associated with the genetic code for each population member, we will have a decoding function that translates the genetic code into a parameter vector. In particular,
where xi is the parameter vector of the ith member of the population and is structured as
(1.5-4)
As can be seen, xi has one element (denoted with a subscript) for each gene. However, it is not partitioned into chromosomes.
Based on the parameter vector of ith population member, the objective function can be evaluated. In particular,
In the case of a GA, the objective function is referred to as a fitness function. It will be used in a “survival of the fittest” sense to determine which members of the population will mate to form the next generation. In the context of a GA, fitness is viewed in a positive sense, thus it is assumed that we wish to maximize the fitness function. Fortunately, it is a straightforward matter to convert between maximization of a function and the minimization of a function. At this point, we have enough background to discuss the computational aspects of a GA. However, before doing this, it is appropriate to briefly pause in our development and consider an example.
Suppose the 13th member of the population has the genetic code
The decoding algorithm is on a gene‐by‐gene basis and is of the form
where li is the number of bits of the ith gene, m is an index ranging from least significant (rightmost) bit to most significant (leftmost) bit for a given gene, bm is the value of that bit (0 or 1), and xmn,i and xmx,i are the minimum and maximum values of the ith element of the parameter vector. For the problem at hand, we assume xmn,1 = 5, xmx,1 = 10, xmn,2 = − 2, xmx,2 = 0, xmn,3 = 0, and xmx,3 = 1. In Section 1.9, we will formally consider the construction of fitness functions, and in Section 1.10, we will