The solution to this problem is straightforward. Using (1.5A-2), we obtain
At this point, we can now consider the primary aspects of a GA. These are illustrated in Figure 1.8. Therein, the first step is initialization that yields an initial population denoted P[1]. Next, the fitness of every member of the population is evaluated. Based on the fitness, a mating pool M[k] is determined by the selection process. The individuals in this population will mate and genetic operators such as crossover, segregation, and mutation will be used to produce children who will form the next generation P[k + 1]. A stopping criterion is then checked; this can be as simple as checking a generation number. Once the stopping criterion is met, the algorithm concludes by selection of the most fit individual of the final population to be the optimizer. This process is implemented by the argmax() operator, which returns the argument that maximizes its objective (which, in this case, is carried about by inspection of the finite population).
It is now appropriate to consider each of these operations in more detail, beginning with the initialization step. The genetic code of every member of the population is initialized at random. This yields an initial population of designs, denoted P[1]. The next step in the algorithm is to compute the fitness of every member of the population. This is accomplished by applying (1.5-3) and (1.5-5) to every member of the population. Example 1.5A illustrates this step for a single member of the population.
Figure 1.8 Canonical genetic algorithm.
The next step in the process is selection. In this step, members of the population P[k] are placed into the mating pool M[k]. Two algorithms to do this are roulette wheel selection and tournament selection. In both methods, the mating pool is initially empty and is filled one member at a time by repeatedly applying the selection mechanism. In roulette wheel selection, members of the population are drawn into the mating pool with a probability proportional to their fitness. In particular, the probability of individual i being drawn into the mating pool on a given draw is given by
(1.5-6)
When applying this particular algorithm, it is important that the fitness function be constructed so that fi ≥ 0. If this is not the case, it is possible to scale/adjust the fitness so that the condition is satisfied (for example, by adding a constant). Note that once a population member has been copied to the mating pool, it is not removed from the population. Thus, it can be copied to the mating pool multiple times.
In n‐way tournament selection, n members of the population are selected at random, and the member of this subset with the highest function is put into the mating pool. Here again, the member placed into the mating pool is not removed from the population. In tournament selection, there is no restriction on the range of the fitness function, which provides a slight simplification.
The next step in process is mating, which is comprised of chromosome crossover, segregation, and mutation. In this step, pairs of parents are used to create pairs of children. Pseudo‐code for this step appears in Table 1.2. Therein, underlined text denotes comments. Referring to the pseudo‐code, θp1 and θp2 denote the genetic code from parents taken from the mating pool. A crossover operator is applied to the codes to form intermediate genetic codes θa1 and θa2. Crossover occurs at random points within a given chromosome. If it occurs, then all elements of the portion of the chromosome strings of the two parents past the crossover point are interchanged. This is similar to biological crossover but not identical: In the case of biological crossover, this process occurs in the formation of the gametes. The net result is the same. Next, the chromosomes of θa1 and θa2 are randomly segregated to form the next stage of intermediate codes θb1 and θb2, much as the chromosome pairs of a cell are segregated in forming gametes. Genetic codes θb1 and θb2 are then mutated to form θc1 and θc2, which will be the children. The mutation operator consists of random interchanges of 0 and 1. The final step in the process is that the children θc1and θc2 are placed into the next generation P[k + 1]. It should be noted that in many GAs there is only a provision to have one chromosome, in which case the chromosome segregation process does not come into play and so genetic diversity is brought about solely by crossover and mutation.
Table 1.2 Pseudo‐Code for Mating, Crossover, Segregation, and Mutation
for i =1 to Np/2 compute element indices i1 = 2i − 1 i2 = 2i get genetic codes of parents θp1 = i1th individual in M[k] θp2 = i2th individual in M[k] apply genetic operators apply crossover to {θp1,θp2} yielding {θa1,θa2} segregate chromosomes of {θa1,θa2}yielding{θb1,θb2} apply mutation to {θb1,θb2} yielding {θc1,θc2} place children into next population θc1 becomes the i1th individual of P[k + 1] θc1 becomes the i2th individual of P[k + 1] end
|
Let us consider the crossover, segregation, and mutation processes on a numerical example. Figure 1.9 illustrates these operators. Therein g1 − g4 denote genes 1–genes 4 and c1 and c2 denote chromosomes 1 and 2, respectively. We start at the left of the diagram with the two parents θp1 and θp2. The first operator applied is crossover. Assuming the crossover point is between the first and second bits in the first chromosome, and that no crossover occurs in the second chromosome, we arrive at θa1 and θa2. The portions of the genetic code which have been acted on by the crossover operator are shown in bold. Next, chromosome segregation occurs. In this case, by a random choice the first child inherits the first chromosome from θa2 and the second chromosome from θa1.
