Observing the Population Dynamics in GE by means of the Intrinsic Dimension

Eric Medvet, Alberto Bartoli, Alessio Ansuini, Fabiano Tarlao

Abstract

Monitoring population dynamics is crucial for understanding the behavior of Evolutionary Algorithms (EAs) and preventing premature convergence. This study introduces Intrinsic Dimension (ID) as a novel metric to characterize the structural complexity of populations in Grammatical Evolution (GE). By applying the TWO-NN estimator to unique genotypes, we demonstrate that ID offers insights distinct from and complementary to traditional diversity measures. Our results show that while diversity often decreases as populations converge, ID typically increases, suggesting that selective pressure forces the population into more complex geometric structures within the search space. This metric reveals the structural limitations of random initialization and provides a more robust indicator of search space exploration.

Introduction

In Evolutionary Computation, maintaining population diversity is essential to avoid local optima. Standard metrics for diversity usually count the fraction of unique individuals. However, "uniqueness" does not capture the geometric distribution of the population. A population might consist of unique individuals that are nonetheless clustered along a simple, low-dimensional manifold, limiting the effective search area.

This paper investigates whether Intrinsic Dimension—the minimum number of variables needed to describe a dataset—can provide deeper insights into the structural dynamics of an evolving population. By measuring the dimensionality of the space occupied by genotypes, we can better understand how an algorithm explores the fitness landscape.

Methodology

The authors apply ID estimation to Grammatical Evolution (GE), specifically using the Weighted Hierarchical GE (WHGE) variant. To calculate the ID, they employ the TWO-NN estimator, which is computationally efficient as it only requires the distances between each individual and its two nearest neighbors.

Because GE genotypes are represented as bit strings, Hamming distance is used as the distance metric. To ensure the metric reflects the structural complexity of the search rather than just the presence of clones, the authors calculate the ID based only on the set of unique genotypes in each generation. The study evaluates this approach on two benchmark problems with tunable difficulty: the Parity Problem and the KLandscape synthetic benchmark, with parameters $b$ and $k$ adjusted to vary ruggedness.

Results and Discussion

Comparison of Best Fitness, Diversity, and Intrinsic Dimension (ID) across generations for varying problem difficulty ($k$). The top and bottom rows represent different benchmark configurations.

The experimental results, illustrated in the figure above, highlight a significant divergence between traditional diversity and ID.

The "Poor Quality" of Randomness

At initialization (generation 0), populations exhibit maximum diversity—nearly every individual is unique. However, the ID at this stage is consistently low, near 1. This suggests that random initialization creates a population that, despite being unique, occupies a very "thin" or simple structure in the search space. This structural simplicity may explain why initialization is often a bottleneck in GE performance.

Structural Evolution under Selection

As evolution progresses, selective pressure "stretches" the population. While diversity typically drops sharply and then plateaus, ID tends to start low and steadily increase, often reaching values between 2 and 2.5. This indicates that as the algorithm finds better solutions (seen in the "Best fitness" plots), the population is forced to organize into more complex, higher-dimensional structures to continue exploring the landscape.

Degeneracy and Stability

In later stages of evolution, diversity sometimes increases slightly due to representation degeneracy—where multiple genotypes map to the same successful phenotype. Traditional diversity metrics might interpret this as a renewed exploration. However, the ID remains steady during these phases, correctly identifying that the underlying geometric complexity of the search has not fundamentally changed. This makes ID a more reliable indicator of true structural exploration.

Conclusion

Intrinsic Dimension provides a unique perspective on the population dynamics of Grammatical Evolution. It reveals that the "shape" of a population evolves from a simple one-dimensional structure at initialization to a more complex manifold as the search matures. While this study was preliminary, the results suggest that ID could be used as a functional component in EAs—for instance, to guide selection mechanisms or to design initialization strategies that start with higher structural dimensionality. Future work will focus on scaling these experiments and refining ID estimators for discrete search spaces.

Summary updated

Abstract

We explore the use of Intrinsic Dimension (ID) for gaining insights in how populations evolve in Evolutionary Algorithms. ID measures the minimum number of dimensions needed to accurately describe a dataset and its estimators are being used more and more in Machine Learning to cope with large datasets. We postulate that ID can provide information about population which is complimentary w.r.t.\ what (a simple measure of) diversity tells. We experimented with the application of ID to populations evolved with a recent variant of Grammatical Evolution. The preliminary results suggest that diversity and ID constitute two different points of view on the population dynamics.
BibTeX
@inproceedings{medvet2018observing,
  author = {Eric Medvet and Alberto Bartoli and Alessio Ansuini and Fabiano Tarlao},
  title = {{Observing the Population Dynamics in GE by means of the Intrinsic Dimension}},
  booktitle = {Parallel},
  year = {2018},
}
Figure