artificial life

Chapter 5: Genetic Algorithms

5.4 Regeneration

The next step of a Genetic Algorithm is to create a new generation from the fittest individuals of the previous population. The simplest technique is cloning, where an individual is simply copied to the next generation. Usually only the most fit genotypes are copied to the next generation, this is known as elitism.

The population shown in Figure 5.1 is relatively small, so only one individual should be cloned, so that the following generation isn’t too similar to the current generation. Solution (f) is the most fit individual, and is the single individual cloned to the next generation.

The remaining members of the population are generated from crossover and mutation of the most fit individuals of the current population. To choose which individuals are to be mated and mutated a roulette style selection is held. The likelihood of a genotype being chosen for reproduction is proportional to its fitness relative to the rest of the population.

In this step it becomes apparent why the unfit candidates in the population are given negative fitness values. It would be simple to assign a fitness value of 0 to unfit individuals in order to eliminate them from contention for reproduction. However, giving failed individuals an equal fitness value ensures that all are equally unlikely to reproduce. At first glance this doesn’t seem like a problem, since the goal of the algorithm is not to produce flawed solutions. However, these failed solutions may have partial solutions that can be used to make more successful solutions. By giving the unfit solutions a negative fitness it is possible to have a continuum of fitness values. A genotype that resolves to a weight that is only one unit above the capacity is certainly more fit that a genotype that has a weight 100 units above the maximum capacity. Allowing negative fitness values captures this quality.

Due to the presence of negative fitness values some manipulation is necessary to determine the proportional probability of reproduction for each genotype. The absolute value of the lowest fitness is added to each fitness in order to shift the continuum of values and have them start at zero. The new values are then summed up to be used as the denominator in finding the probability of reproduction. For the population in Figure 5.1 this value would be 844. The probability of each individual is the adjusted fitness divided by the sum value. In the case of Solution (a) in Figure 5.1 the likelihood is 156/844. Solution (b) has a fitness of -98, it is the worst individual in the population, so the likelihood of its reproduction is 0/844. In this way the most unsatisfactory solution is immediately prevented from reproducing.

Figure 5.2 illustrates how Crossover and Mutation operations are used with the selected individuals to create new genotypes. In both examples in Figure 5.2 the fitness of the individuals increased after crossover and mutation. It is just as likely that crossover/mutation produces a genotype that has a lower fitness, or a genotype with an unacceptable solution.

Crossover and mutation are performed on the current generation until the descendant generation has been filled. The descendant generation is then evaluated using the fitness function and the same procedure is used to create yet another generation of possible solutions.