TL;DR
This paper investigates the impact of "spurious dependencies" – learned relationships in a problem that don't actually exist – on the performance and scalability of Estimation of Distribution Algorithms (EDAs). The authors propose a theoretical model for these spurious dependencies on the Onemax problem and demonstrate that they significantly increase the required population size for EDAs, while having a less pronounced effect on convergence time, especially when using certain replacement strategies.
What Problem Does This Paper Address?
Estimation of Distribution Algorithms (EDAs) are a class of evolutionary algorithms that learn a probabilistic model from promising solutions to generate new candidates. A known issue is that EDAs can sometimes learn "spurious dependencies," meaning they infer relationships between variables that aren't actually present in the underlying problem. While previous work has touched on model accuracy in EDAs, there's been a lack of theoretical analysis on how these spurious dependencies specifically affect EDA performance and, crucially, their scalability. This paper aims to fill that gap by theoretically analyzing and empirically verifying the impact of spurious dependencies on population sizing and convergence time.
Methods
The authors focus on EDAs that use marginal product models (MPMs), specifically the extended compact genetic algorithm (ECGA), and the Onemax problem as a testbed. Onemax is chosen because it's a simple problem where no dependencies are theoretically needed for optimal performance.
- Theoretical Model: They propose a model for spurious dependencies by artificially creating linkage groups of a certain size ($k_{spurious}$) in the MPM. This simulates the effect of an EDA learning these non-existent relationships.
- Population Sizing Analysis: They extend existing theoretical models for population sizing (initial supply and gambler's ruin models) to account for these artificial spurious dependencies. This allows them to predict how population size requirements change with the degree of spuriousness.
- Empirical Evaluation: They conduct experiments using ECGA and a fixed-model EDA with varying degrees of spurious linkage. They measure population size, number of generations to convergence, and other performance metrics.
Datasets
Not discussed in the paper. The experiments use the Onemax problem, which is a synthetic benchmark problem, not a dataset in the traditional sense.
Key Insights and Ideas
- Spurious dependencies inflate population size: The most significant finding is that spurious dependencies, even on a simple problem like Onemax, substantially increase the population size required for an EDA to converge. This effect is more pronounced than the impact on convergence time.
- Gambler's ruin model is a good predictor: The gambler's ruin model, a theoretical framework for population sizing, proves to be a more accurate predictor of population size requirements under spurious dependencies than the initial supply model.
- Convergence time is less affected (usually): For most standard replacement strategies (full and elitist replacement), the number of generations to convergence is only slightly affected, and can even decrease, with spurious dependencies. This is because the populations might lose diversity faster.
- Niching exacerbates the problem: When niching (a technique to preserve diversity and find multiple solutions) is introduced, the negative effects of spurious dependencies on convergence time become dramatically worse, growing exponentially with the degree of spuriousness. This highlights the interaction between model inaccuracies and search strategies.
- Model building is still dominant: Despite the impact of spurious dependencies, the paper reiterates that for typical EDAs, the population sizing requirements for model building itself (learning the correct dependencies) are still the dominant factor, often leading to exponential growth in population size.
Key Results
- The theoretical models predict that population size grows approximately exponentially with the size of spurious linkage groups.
- Experimental results confirm this prediction, showing a clear increase in population size as spurious linkage group size increases, with the gambler's ruin model providing a good fit.
- For full and elitist replacement, the number of generations to convergence either slightly decreases or remains relatively stable with increasing spuriousness.
- With restricted tournament replacement (RTR), which incorporates niching, the number of generations to convergence grows dramatically (faster than exponentially) with spurious linkage group size.
- The paper provides theoretical ratios ($Y_{is}$ and $Y_{dm}$) quantifying how much population sizing requirements increase due to spurious dependencies compared to a perfect model.
Limitations and Future Work
- Convergence Time Model: The paper hypothesizes about the effects of spurious dependencies on convergence time but does not provide a rigorous theoretical model for it, especially in the presence of niching. Developing such a model is a key future direction.
- Overlapping Subproblems: The current model assumes disjoint linkage groups. Future work could examine spurious dependencies in models where subproblems overlap, potentially using Bayesian networks.
- Interaction with Model Building: The paper focuses on fixed spurious models. Understanding the interplay between the discovery of spurious dependencies during model building and their subsequent effects is an important area.
- Niching Interaction: The significant impact of spurious dependencies in the presence of niching suggests that further research into the interaction between model inaccuracies and niching strategies is crucial, especially for complex problems.
Summary updated