The Structure of Evolutionary Exploration: On Crossover, Buildings Blocks, and Estimation-Of-Distribution Algorithms

Marc Toussaint

TL;DR

This paper re-examines the concept of "building blocks" in evolutionary computation, arguing that crossover actually destroys correlations and reduces complexity, contrary to common intuition. It proposes that Estimation-of-Distribution Algorithms (EDAs) are better suited for "correlated exploration," a concept crucial for efficient search and adaptation.

What Problem Does This Paper Address?

The concept of "building blocks" is central to understanding how genetic algorithms (GAs) work. Traditionally, crossover is thought to combine these building blocks to create better solutions. However, this paper questions this view, particularly in light of natural evolution's "building blocks" (like functional modules controlled by single genes) which exhibit high correlation. The authors aim to clarify what "building blocks" truly mean in the context of GAs, especially when comparing standard crossover operators with more modern approaches like Estimation-of-Distribution Algorithms (EDAs). They want to understand how different operators affect the correlational structure of the search distribution, which is key to how effectively an algorithm explores the search space.

Methods

The paper uses an information-theoretic approach, focusing on entropy and mutual information, to analyze the search distribution generated by different evolutionary operators.

  • Mutation: Analyzed as a simple operator that increases entropy and decreases mutual information between genes, making it marginally explorative but not correlated.
  • Crossover: Formally defined and analyzed using a "mask distribution." The core finding is that crossover, regardless of the mask, preserves marginal distributions but destroys mutual information between genes, transforming it into entropy. This means it breaks down existing correlations rather than building them.
  • Estimation-of-Distribution Algorithms (EDAs): Presented as algorithms that do aim to capture and utilize correlations in the search distribution, leading to "correlated exploration."

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of operators rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Crossover is Anti-Correlational: The most striking insight is that crossover, far from building complex correlations (building blocks), actively destroys them. It transforms mutual information into entropy, making the resulting population less complex in terms of gene interdependencies.
  • "Building Blocks" Re-evaluated: The paper suggests that the traditional view of building blocks in GAs might be misleading. Instead of creating them, crossover breaks down existing, naturally occurring correlations (like those in individuals themselves).
  • EDAs for Correlated Exploration: EDAs are highlighted as the algorithms that truly achieve "correlated exploration" by explicitly modeling the search distribution and its dependencies, which is crucial for efficient adaptation.
  • Information-Theoretic Framework: Using entropy and mutual information provides a rigorous way to quantify the impact of operators on the search distribution's structure.

Key Results

  • Mutation: Increases entropy and decreases mutual information. It is marginally explorative but not correlated.
  • Crossover: Preserves marginal distributions and their entropies but decreases mutual information. This leads to a less correlated search distribution. The degree of correlation destruction depends on the crossover mask.
  • Correlated Exploration: Defined as an operator that increases entropy while also increasing mutual information (or at least not decreasing it significantly relative to entropy increase). EDAs are shown to be capable of this, while GAs with crossover are not.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical. While it lays a strong foundation, empirical validation of these concepts across various problems and EDA variants would be valuable.
  • Genotype vs. Phenotype: The paper touches upon the distinction between genotype and phenotype mapping. It suggests that "phenotypic correlated exploration" might be achievable with crossover and mutation under non-trivial genotype-phenotype mappings, which is an area for further exploration.
  • EDA Objective: The paper critiques some algorithms that claim to be EDAs but only model marginals, arguing that true EDAs should capture correlations. This distinction is important for algorithm design and understanding.

Summary updated

Abstract

The notion of building blocks can be related to the structure of the offspring probability distribution: loci of which variability is strongly correlated constitute a building block. We call this correlated exploration. With this background we analyze the structure of the offspring probability distribution, or exploration distribution, for a GA with mutation only, a crossover GA, and an Estimation-Of-Distribution Algorithm (EDA). The results allow a precise characterization of the structure of the crossover exploration distribution. Essentially, the crossover operator destroys mutual information between loci by transforming it into entropy; it does the inverse of correlated exploration. In contrast, the objective of EDAs is to model the mutual information between loci in the fitness distribution and thereby they induce correlated exploration.
BibTeX
@inproceedings{toussaint2003structure,
  author = {Marc Toussaint},
  title = {{The Structure of Evolutionary Exploration: On Crossover, Buildings Blocks, and Estimation-Of-Distribution Algorithms}},
  booktitle = {GECCO},
  year = {2003},
  doi = {10.1007/3-540-45110-2\_17},
}
Figure