where α is an algorithm constant often taken to be 0.5. Observe that in this algorithm the average gene value for the children is the same as for the parents. Canonical GAs also have this property.
Another commonly used crossover algorithm is simulated binary crossover. This algorithm is designed to yield results that would be similar to those obtained by crossover within a gene using the canonical GA. These properties include the fact that the sum of the gene values is the same for the children as the parents and that the children tend to be similar to the parents (which is also the case in simple‐blend crossover). In this algorithm, first a random number in [0,1) is computed as in (1.6-5) from which a factor β is computed as
Figure 1.10 Single‐point crossover.
In (1.6-8), ηc is an algorithm parameter. Once β is found, the genes of the children are computed as
(1.6-9)
(1.6-10)
In both simple blend and simulated binary crossover, it is possible to generate gene values outside of [0,1]. For example, suppose the parent gene values are 0.5 and 1, and we use simple‐blend crossover with α = 0.8. Further, suppose υ = 0.9. The resulting gene values for the children would be 0.39 and 1.11, the latter of which is outside the allowed set of values. In this case, gene repair becomes necessary. There are several approaches to this. Hard limiting the gene values is one approach. For example, a gene value calculated as 1.2 is simply represented as 1.0. Similarly, a gene value of −2.1 would be set to 0. Alternately, gene values can be ring mapped, which is to say corrected using a modulus 1 operator. In this case, 1.2 would be repaired to 0.2 and −2.1 would be repaired to 0.9. For integer‐coded genes, additional repair is necessary in order to make sure that the gene values take on allowed values.
Our discussion of simple blend and simulated binary crossover has focused at the gene level, and so it is now appropriate to consider the application of these processes at the chromosome level. There are several approaches that could be taken. In scalar crossover, each gene in a chromosome that is being operated upon undergoes a crossover operation independently. Each gene in a chromosome uses a different υ. In vector crossover, υ is the same for all genes in a crossover. This leads to scalar simple‐blend crossover, vector simple‐blend crossover, scalar simulated binary crossover, and vector simulated binary crossover.
As can be seen, it is perhaps too easy to create new genetic operators. However, before leaving the topic, one final combination will be considered, namely, single‐point simple‐blend crossover. In this algorithm, a single gene of the chromosome is selected as a crossover point. Unlike single‐point crossover, however, the crossover point is a gene, not a position between genes. That gene is operated upon with the simple blend operator. The remaining genes are interchanged as in single‐point crossover. The process is illustrated in Figure 1.11. Therein, the third gene is randomly selected as the crossover point, α is taken as 0.5, and υ was 0.81 (determined at random). Single‐point simple‐blend crossover is somewhat similar to the inheritance of quantitative traits wherein multiple genes are involved in determining the extent of an attribute. One could also devise single‐point simulated binary crossover or multipoint simple‐blend crossovers in a straightforward fashion.
Figure 1.11 Single‐point simple‐blend crossover.
Mutation
In the process of the duplication of chromosomes to form gametes, occasionally errors in DNA duplication occur, which are referred to as mutations. Normally, particularly in mature species, these mutations have either little effect or a harmful effect. However, occasionally mutations yield beneficial traits. This is particularly true in the early evolution of a species. Mutation in GAs helps to explore the parameter space; in doing so, many mutations are harmful, but occasionally mutations occur which are very beneficial.
Referring to the pseudo‐code in Table 1.2, genes are selected at random for mutation. Many chromosomes will have no mutations, and others may have several. There are several approaches that can be applied to mutate a gene. One approach, referred to as total mutation, is to simply reinitialize the mutated gene at random in the interval [0,1]. Figure 1.12 illustrates the total mutation operator applied to the third gene of a chromosome (which could be either a1 or a2 with respect to Table 1.2).
A second method is partial absolute mutation. In this method, if the jth gene is selected for mutation, the mutated value is given by
(1.6-11)
where N(·) denotes a zero‐mean, unity variance Gaussian random number generator and σ is a desired standard deviation. A related method is partial relative mutation wherein the modified gene value may be expressed as
(1.6-12)
In partial absolute mutation, the size of the mutation is independent of the value of the gene; in relative mutation, the size of the perturbation tends to increase with the magnitude of the coded gene value. In both of these methods, gene repair is necessary because either method could result in a gene value outside of [0,1].
There are also vector‐based mutation operators. In absolute vector mutation, we have
(1.6-13)
where V(·) denotes a unit vector with the same dimensionality as the chromosome in a random direction. For relative vector mutation, we have
(1.6-14)
where Ng is the number of genes in the chromosome in question. Both of these operators require gene repair.
Figure 1.12 Total mutation.
A
