Genealogical Distance as a Diversity Estimate in Evolutionary Algorithms

Thomas Gabor, Lenz Belzner

Abstract

The evolutionary edit distance between two individuals in a population, i.e., the amount of applications of any genetic operator it would take the evolutionary process to generate one individual starting from the other, seems like a promising estimate for the diversity between said individuals. We introduce genealogical diversity, i.e., estimating two individuals' degree of relatedness by analyzing large, unused parts of their genome, as a computationally efficient method to approximate that measure for diversity.

Introduction

Maintaining population diversity is a critical challenge in Evolutionary Algorithms (EAs). Without it, populations often suffer from "premature convergence," where individuals cluster around a local optimum and lose the genetic variety needed to explore the wider fitness landscape. While diversity-aware selection can mitigate this, most existing distance metrics are domain-specific—requiring custom engineering for every new problem (e.g., Euclidean distance for paths vs. structural edit distance for code). This paper proposes Genealogical Distance, a domain-independent approach that leverages ancestry to estimate diversity with minimal computational overhead.

Methodology: The "Trash Gene" Approach

The authors propose shifting the focus from what an individual is (phenotype/genotype similarity) to where they came from (ancestry). They identify three levels of measurement:

  1. Evolutionary Edit Distance: The theoretical ideal representing the minimum number of genetic operations (mutations/recombinations) to transform one individual into another.
  2. Genealogical Tree Distance: Tracking the full lineage of a run to find the Latest Common Ancestor (LCA). While accurate, this becomes computationally expensive as populations grow and evolve.
  3. Trash Genes: Inspired by biological "junk DNA," the authors append a non-functional bit vector (e.g., 32 bits) to each genome. These bits have no effect on fitness but track ancestry through inheritance. When the functional genome mutates, a random bit in the trash vector flips; during crossover, children inherit trash bits via uniform crossover. The diversity estimate is then calculated as the Hamming distance between these vectors.

This method provides a high-fidelity proxy for ancestry. Crossover events naturally result in a ~50% shift in trash bits, while mutations cause smaller, single-bit changes, accurately reflecting the magnitude of jumps in the search space.

Experimental Evaluation

The approach was evaluated using a Robot Routing Task designed to trigger premature convergence. In this 2D environment, a robot must navigate around a large U-shaped obstacle to reach a goal. A standard genetic algorithm typically gets trapped on the "wrong" side of the obstacle because moving around it requires a temporary decrease in fitness.

The Robot Routing Task: A 2D environment featuring a U-shaped obstacle (gray) between the starting position (red) and the goal (green).

Results and Discussion

The experimental results demonstrate that genealogical distance effectively guides the population out of local optima. As shown in the performance plots, the baseline GA (black line) quickly plateaus, failing to navigate the obstacle. In contrast, the diversity-enabled versions—including the computationally efficient "Trash Bit" method (red line)—successfully reach higher fitness levels.

Performance comparison: Top fitness averaged over 10 runs for the baseline GA (black) versus diversity-aware methods including the trash-bit approach (red).

Key findings include:

  • Parity with Complex Metrics: The Trash Bit approach performed as well as domain-specific metrics and expensive tree-traversal methods.
  • Efficiency: While tree traversal scales with the number of nodes, comparing trash bits is a constant-time operation ($O(\tau)$) relative to the fixed length of the bit vector.
  • Robustness: A relatively small vector (32 bits) proved sufficient to maintain stable diversity estimates throughout the evolutionary process.

Conclusion and Future Work

Genealogical distance via trash genes offers a parameter-free, domain-independent solution for maintaining EA diversity. Future research may explore self-adaptive weighting for the diversity hyperparameter ($\lambda$) and the application of genealogical distance to parent selection to prevent inbreeding, mimicking biological systems more closely.

Summary updated

Abstract

The evolutionary edit distance between two individuals in a population, i.e., the amount of applications of any genetic operator it would take the evolutionary process to generate one individual starting from the other, seems like a promising estimate for the diversity between said individuals. We introduce genealogical diversity, i.e., estimating two individuals' degree of relatedness by analyzing large, unused parts of their genome, as a computationally efficient method to approximate that measure for diversity.
BibTeX
@inproceedings{gabor2017genealogical,
  author = {Thomas Gabor and Lenz Belzner},
  title = {{Genealogical Distance as a Diversity Estimate in Evolutionary Algorithms}},
  booktitle = {GECCO (Companion)},
  year = {2017},
  url = {https://openreview.net/forum?id=Bf6FsGjsE0},
}
Figure