Population Diversity and Fitness Measures Based on Genomic DistancesReport
We define a class of genetic algorithms where, at each time step, two parents are selected to produce a child which then replaces one member of the population at the next time step. We consider the finite-population case. We define a general crossover and mutation operation, as well as a genomic distance between individuals. We require a specific property to hold for such operations and distance functions, and present examples of crossover operations, mutation operations, and distance functions which meet the requirements. We then define the sum over all pairwise population distances as a measure of the diversity of a population and consider the time evolution of the expected diversity of a population. We show that under uniform, independent selection of parents and the individual to be replaced the expected diversity is strictly decreasing. For this case we calculate an explicit formula for the diversity at each time step, based only on the initial population diversity. We then consider and discuss the case where independent, fitness-based selection is used and show that the expected diversity is strictly decreasing whenever the same probability function is used to select both the parents and the individual to be replaced. We qualitatively discuss conditions where expected diversity will increase rather than decrease with fitness-based selection. Finally, we discuss fitness measures based on a distance function.
All rights reserved (no additional license for public reuse)
Barker, AL, and WN Martin. "Population Diversity and Fitness Measures Based on Genomic Distances." University of Virginia Dept. of Computer Science Tech Report (1999).
University of Virginia, Department of Computer Science