A novel methodology for diversity preservation in evolutionary algorithms

Giovanni Squillero, Alberto Paolo TondaGecco (companion) 2008 · DOI

TL;DR

This paper introduces a novel method to enhance diversity in evolutionary algorithms by analyzing the structure and order of genetic material within individuals, not just the presence of alleles. This improved approach significantly boosts the efficiency of evolutionary algorithms in solving complex problems, outperforming traditional methods and even previous entropy-based techniques.

What Problem Does This Paper Address?

Evolutionary algorithms (EAs) are powerful tools for optimization and problem-solving, but they face a critical challenge: maintaining diversity within the population. As EAs evolve, individuals can converge towards similar solutions, leading to premature convergence and potentially suboptimal outcomes. Traditional methods to combat this, like avoiding individuals with identical fitness, are often insufficient when diverse individuals can have similar performance. This paper tackles this issue by proposing a more sophisticated way to measure and preserve genetic diversity within the population.

Methods

The authors build upon an existing entropy-based diversity preservation method. In their previous work, they treated the population as a message and calculated its entropy based on the frequency of alleles (symbols) within individuals. This paper introduces a significant enhancement: instead of just looking at the presence of alleles, they now consider the order and position of these alleles within an individual's genetic structure.

Specifically, they propose two key modifications:

  1. N-uples of Nodes and Position: They treat n-uples of nodes (representing sequences of genetic information) and the position of an allele within a directed graph (representing an individual) as atomic elements. This means that the same allele appearing in different positions or as part of different sequences is now considered distinct.
  2. N-grams: They also incorporate the occurrence of n-grams (sequences of n consecutive node values) as symbols. This allows the algorithm to identify and preserve individuals with unusual patterns or structures, even if their individual allele frequencies are not particularly unique.

These new "symbols" are then used to compute a "delta-entropy," which measures how much an individual contributes to the overall population's diversity. Individuals with unique structures or patterns will have higher delta-entropy and are thus more likely to be selected for reproduction, promoting diversity.

Datasets

The paper does not use traditional datasets. Instead, it employs two custom-designed benchmarks to evaluate the effectiveness of their proposed method:

  1. Prime Numbers Function: Evolving assembly code to discern prime numbers between 1 and 20.
  2. Finding the Right Path: Evolving code for a simple program to navigate an arena, avoid obstacles, and reach a goal with the fewest instructions.

These benchmarks are designed to be challenging and require significant diversity to find optimal solutions.

Key Insights and Ideas

  • Structure Matters: The most significant insight is that the structure and order of genetic information are crucial for maintaining diversity, not just the presence of individual components.
  • Beyond Simple Frequencies: Traditional entropy measures based solely on allele frequencies are insufficient. Considering positional and sequential information provides a richer representation of an individual's uniqueness.
  • Preserving "Unique Structures": The new method effectively identifies and preserves individuals with "peculiar genotypes" or "unusual patterns," which are vital for exploring diverse regions of the solution space.
  • Improved Efficiency: By better preserving diversity, the evolutionary process becomes more efficient, leading to faster convergence to good solutions.

Key Results

The authors conducted preliminary experiments comparing their new entropy-based approach with:

  • A tournament selection based solely on fitness.
  • An older entropy-based method.
  • No explicit diversity preservation mechanism.

For the Prime Numbers Function benchmark: * The new entropy approach achieved the desired function in 600-700 generations. * The older entropy approach and fitness-only selection did not converge even after 2000 generations.

For the Finding the Right Path benchmark: * Preliminary experiments consistently showed an improvement in the fitness values of the best individual using the new entropy approach across various population sizes. * Table 1 shows that for a population size of 10, the fitness-based selection failed to find a solution, while the entropy-based selection found a best individual length of 22. Similar improvements were observed for larger population sizes.

Limitations and Future Work

Limitations: * The authors acknowledge that the preliminary experiments were limited in scope, using only two extreme cases of tournament selection (fitness-only vs. entropy-based). * They mention that the optimal parameters for the island model genetic algorithm (mentioned as a related approach) are problem-dependent. While not directly a limitation of their method, it highlights the complexity of diversity preservation.

Future Work: * The authors plan to conduct more tests with varying fitness landscapes and population sizes to gain a better understanding of the new entropy computation's performance under different conditions. * They are also running more tests with the older entropy computation to further evaluate the improvement of their new approach.

Summary updated

BibTeX
@inproceedings{squillero2008novel,
  author = {Giovanni Squillero and Alberto Paolo Tonda},
  title = {{A novel methodology for diversity preservation in evolutionary algorithms}},
  booktitle = {Gecco (companion)},
  year = {2008},
  doi = {10.1145/1388969.1389049},
}
Figure