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