1 A Caricature of Tournament Selection

To illustrate the loss of genetic lineages, a modified version of tournament selection is used. This version represents a caricature of standard tournament selection, placing emphasis on the selection of the fitter individuals. The individuals in a population $p$ of size $\mu$ are sorted into ascending fitness order, from worst to best. A tournament size $T$ defines the number of equal-sized partitions that divide the sorted population, where a partition contains $\frac{\mu}{T}$ individuals. Partitions $p^1,p^2, \ldots, p^T$ serve to separate the worst fit ($p^1 \ldots$) from the best fit individuals ($\ldots p^T$). This assumes a unique fitness value for each individual. In a generational algorithm, to produce a child in the next generation, a tournament is held to find the root parent. If the population size is $\mu$, then we hold $\mu$ tournaments to produce all the children. Typically, $2 \times \mu$ tournaments are held to select for both parents for crossover, but since only the root parent and child are used to define lineages, only the one tournament to select the root parent is considered. Every individual in $p$ has the expectation of being selected for a tournament $\frac{T}{\mu} \times \mu = T$ times.

To further simplify the model, tournament selection will pick one individual from each partition, where there are $T$ partitions. Thus, in every tournament held, the winner of that tournament will come from $p^T$. Every child in the next generation will be of a genetic lineage that came from $p^T$. In practice, individuals are randomly selected from the population to make a tournament. To simulate the random nature of tournament selection, it will be assumed that the number of offspring each individual in $p^T$ produces for the next generation will be equal.