chromosomes. Next, let us assume that mutation acts to change the status of the first bit of gene 3 in θb2. This yields θc1 and θc2, where the affected bit is again indicated in boldface.
At this point, the main points of a canonical GA have been described. This canonical form is the type of algorithm first developed by Holland. The canonical GA can also be used to explain the effectiveness of GAs using schema theory. A schema is a pattern of bits; one reason GAs are so effective is that they can be shown to exhibit an implicit parallelism in which all schema that result in higher than average fitness tend to propagate. The interested reader is referred to textbooks on GAs such as those by Goldberg [4,5].
Figure 1.9 Chromosome crossover, segregation, and mutation in Example 1.5B.
At this point, an example would prove useful. Before embarking on such an example, however, it will prove useful to address one weakness of the GA. This weakness is the encoding algorithm. Although the representation of a member of the population as a string similar to that in DNA is intellectually appealing, it is also inconvenient. Further, a binary representation of real numbers suffers from finite resolution and the fact that sometimes large numbers of bits may need to change to accomplish a small change unless, for example, a Gray code scheme is used. As it turns out, it is possible to create a GA without encoding genes as strings and, instead, representing them with real numbers. Real‐coded GAs are simpler to write than their canonical counterparts and very effective. They will be our next topic.
1.6 Real‐Coded Genetic Algorithms
Real‐coded GAs are very similar to canonical GAs except that instead of each gene being represented as a binary string, each gene is represented by a real number. This proves convenient for coding purposes and makes representing each gene to the numerical precision of floating‐point numbers for a given machine (computer) straightforward. Beyond the change of the way in which a gene is represented, the algorithm presented in Figure 1.8 is still applicable, though we will need to modify the encoding, crossover, and mutation operators.
Encoding
Let us begin our development by considering the form of the genetic code for the ith individual. In the case of the canonical GA, this was given by (1.5-2), where each element of θi was represented by a string. In the real‐coded GA, (1.5-2) still applies. However, instead of each element of θi being represented by a string, in a real‐coded GA each element is represented by a real number. In fact, a real‐coded GA could be written such that θi = xi. However, it will be convenient to provide a mapping of xi to θi so that the gene values of θi fall into the domain [0,1].
The mapping between xi and θi is accomplished on a gene‐by‐gene basis. A simple choice is a linear map. Let x and θ denote a gene (element) of the xi and θi. For a linear mapping, we have
(1.6-1)
where j denotes the gene number and
where xmn,j and xmx,j denote the minimum and maximum values of the parameter.
Closely related to linear mapping is integer mapping, wherein x, xmn,j, and xmx,j are integers. In this case, (1.6-2) still applies, but we require
(1.6-3)
This mapping is useful in choosing, for example, between different types of steel in a design. If the third gene represented the type of steel used, and five types of steels were being considered, then xmn,3 = 1, xmx,3 = 5, and θ ∈ {0.00, 0.25, 0.50, 0.75, 1.00}.
In some cases, the domain of a parameter may span many decades in magnitude. If the domain of the parameter is always positive, then a logarithmic mapping is appropriate. In this case,
(1.6-4)
Crossover
In the case of the canonical GA, crossover is accomplished by breaking the subject chromosomes of the parents at the same point and interchanging them to form the corresponding chromosomes of the children. This interchange substantially alters the gene where the chromosome is interchanged, and it results in an interchange of genes falling after the interchange point.
There are several algorithms to achieve crossover in real‐coded GAs. One of them is single‐point crossover, which can be readily generalized to n‐point crossover. This method is straightforward and is readily illustrated by the example shown in Figure 1.10. Therein, the genetic code for two parents, θp1 and θp2, is shown. Observe that the elements of these vectors are real numbers in the domain [0,1]. In this algorithm, a crossover point is chosen at random and the genes after the crossover points are interchanged (these genes are in bold) to form two new genetic codes, θa1 and θa2, which will become children after the application of additional genetic operators such as mutation.
Single‐point crossover is very similar to biological crossover. However, note that gene values cannot become altered using this operator. This limits the amount of genetic diversity that can be brought about.
Simple‐blend crossover can be used to increase the genetic diversity. Let us consider the jth gene of parents θp1 and θp2. If the jth gene is being crossed over, the new gene values are determined by first computing a random number υ given by
where U(·) denotes a random number generator that generates a uniformly distributed random number in the range [0,1]. Next, the gene values of the children are set to
(1.6-6)
(1.6-7)
