Genetic Reproduction

Reproduction is controlled by mutation and crossover operators. Crossover defines the procedure for generating a child from two parents. Before the actual crossover is performed, the parents need to be selected. Several selection schemes are possible:

1. The best individuals of every generation are selected.

2. An individual is selected based on its fitness relative to the other individuals. The better the fitness the more likely this individual gets chosen. The probability $p$ for an individual with fitness $S$ to get chosen among $N$ individuals is equal to $p=S/\sum_{i=1}^{N}{S_i}$. This is called the ROULETTE-WHEEL selection scheme.

3. Two individuals are selected using (2), the one with the better fitness is finally chosen.

4. Individuals are chosen randomly. Each individual has the same chance of being chosen independent of its fitness.

5. Individuals are chosen based on a two stage stochastic selection. In the first stage a temporary population is computed in which an individual from the base population may occur several times corresponding to the integer part of its expected fitness (i.e. the absolute fitness divided by the average fitness). The fraction of the expected fitness is used to give the individual another chance for being represented in the temporary population. This is best illustrated in an example. If the expected fitness is e.g. $2.4$, than this individual will be represented at least $2$ times in the temporary population. It gets a $40\%$ chance of being represented a third time. In the second stage one individual is chosen uniformly (4) from the temporary population.

Figure 5.13: Different crossover methods in genetic algorithms. Fig. (a) depicts the one-point crossover. A random point that splits the genome into two parts is chosen. The children are created by combining the two parts in the shown way. Fig. (b) shows the two-point crossover, where the genomes are split into three parts. The resulting parts are combined in an alternating manner to form the children. In case of the array uniform crossover (fig. (c)) for each gene of the newly generated child a coin is flipped to decide from which parent it will be taken over.

After individuals were chosen for mating, one of the crossovers as depicted in Fig. 5.13 takes place. Finally, mutation is performed on the newly introduced off-springs (right after the crossover). It introduces new genetic material into a population by replacing one parameter in a genome by a random value within the allowed range. The parameter ${P_{\!mut}}$ of the genetic algorithm thereby controls the mutation probability.

The parameters ${\ensuremath P_{\!cr\!oss}}$ and ${P_{\!mut}}$ have a big impact on the performance of the genetic algorithm. Although a direct relationship to a gradient based optimizer can not be drawn, the crossover operation results in a local exploration of the target function, since only a combination of other individuals is created. The parameter values are reused. The mutation operation on the other hand introduces (totally new) parameter values into the genome which have never been used before. Thereby, the algorithm effectively 'escapes' any local extrema. There is no general rule on how to set those parameters. In the example presented in Section 5.6 some combinations of those values have been tried.

2003-03-27