GA Through Example

Thus far, much of this discussion has been conceptual. Let's now walk through an iteration of the algorithm to see how it actually works. In this example, we're trying to find a pair of parameters that maximize Equation 6.1.

(6.1)  

This equation is shown graphically in Figure 6.9 (3-dimensional plot) and Figure 6.10 (contour plot).

Figure 6.9: Graphical plot of Equation 6.1.

Figure 6.10: Contour plot of Equation 6.1 showing z-dimension via shading.

Our chromosome for this example is built from two genes, or two parameters, x and y. The first step is to create a pool of chromosomes from which we'll apply the genetic algorithm to find a solution. Figure 6.11 shows our initial population as selected randomly .

Figure 6.11: Initial population (t ).

Now that our initial population is available, we begin the evaluation process. To evaluate the chromosomes in our population, we determine their individual fitness. The fitness in this case is simply Equation 6.1. The larger the value resulting from the equation, the higher is the fitness of the chromosome. Figure 6.12 shows the fitness values of the evaluated chromosomes.

Figure 6.12: Fitness of initial population.

From Figure 6.12, we can see that chromosome C ₁ is very small, and therefore it is very unlikely to be selected. We select two pairs of parents for recombination. Each parent will contribute via crossover to children in the next generation. Based upon fitness, we select C ₃ and C ₂ as the first set of parents and C ₃ and C as the second set of parents. Since only two genes exist within the chromosome, we swap at the gene level resulting in each chromosome swapping its x and y elements. Figure 6.13 shows the new population (with the gene sources shown in parenthesis) as well as the new evaluated fitness of each new chromosome.

Figure 6.13: Next generation with fitness evaluated (population at t ₁ ).

Let's now observe the fitness values shown in Figure 6.12 compared to the fitness values in the new population of Figure 6.13. It's clear that the fitness values have increased (the largest fitness in t was 0.44 while the largest in t ₁ is 0.8). This means that the best solution within the population is better than the prior best solution from the old population. The average fitness in the first population was 0.231 while the average fitness in the new population is 0.39. This flow shows an obvious improvement in the population and the key elements of the genetic algorithm.

The mutation operator was not used in this example. For this type of problem, mutation could be implemented as slight random changes to the gene values (such as adding or subtracting a small value such as 0.1).

Note  

From this example, it should be clear that the crossover operator will not evolve into a perfect solution. The crossover operator uses the existing genetic material within the population to search the solution space. Only a limited number of combinations are possible, therefore, mutation would be necessary to introduce new material into the population to extend the search space.