1 Genetic Lineages

In a system based on Darwinian evolution, where inheritance provides the motivation for transformation operators, a simple form of diversity measurement is the genetic lineage. McPhee and Hopper (1999) observed that the dominant operator, subtree crossover, preserves most of the root parent's genetic material (also noted by Poli and Langdon (1998a)), and thus they defined genetic lineages between the root parent to its offspring. The authors tracked lineages when they counted the appearance of the Eve individual, the latest common ancestor of the population. The Eve individual can then be traced back to a single individual in the initial population from which the entire final population descended. That is, when a latest-common-ancestor exists, one can trace the root-parents of all individuals in the final population back to this individual. By definition then, this Eve individual is the root-descendant of exactly one individual from the initial population. Remember that the lineage definition only considers the root-parent and offspring relationship.

Figure 5.1: An example of three individuals undergoing recombination, where after the second application of crossover all three are descendants from the same individual and represent the same genetic lineage.

McPhee and Hopper (1999) showed how entire populations quickly lose many genetic lineages and soon descend from only one individual. As genetic lineages tend to share common root shapes and contents, this loss of lineages in the population signifies the convergence toward a common tree shape and contents [Rosca and Ballard, 1999,Langdon and Poli, 2002,Poli and Langdon, 1998a].

Tracking the progression of genetic lineages through the evolutionary process provides a sense of the loss of genetic diversity in the population at little computational cost. Figure 5.1 is an example of the genetic lineages. Three individuals ($I_1,I_2,I_3$) produce offspring ( $I_1',I_2',I_3'$) via crossover. The root parent is denoted with a solid arrow. After another generation, the three new individuals all belong to the same genetic lineage, $I_3$. In this chapter, as in McPhee and Hopper (1999), a genetic lineage is defined as the path from the root parent to its child during two parent recombination.