Analysis of epistasis correlation on NK landscapes with nearest-neighbor interactions

Martin PelikanGECCO 2011 · DOI

TL;DR

This paper investigates the relationship between "epistasis correlation," a measure of variable interactions in optimization problems, and problem difficulty. By studying NK landscapes, the authors find that while epistasis correlation can indicate problem difficulty, it's not a perfect predictor, especially for algorithms that can handle epistasis.

What Problem Does This Paper Address?

Optimization problems often become harder for evolutionary algorithms when their variables interact strongly. This interaction is known as "epistasis." While measures like epistasis correlation exist to quantify these interactions, their direct link to problem difficulty has been debated. Specifically, a problem with high epistasis isn't always difficult, and vice-versa. This paper aims to empirically study this relationship on a well-defined class of problems (NK landscapes) and evaluate how different evolutionary algorithms, some designed to handle epistasis and others not, perform in relation to it.

Methods

The study compares two evolutionary algorithms:

  • Genetic Algorithm (GA) with uniform crossover: This is a standard GA where variables are treated independently, making it potentially vulnerable to epistasis.
  • Hierarchical Bayesian Optimization Algorithm (hBOA): This is an Estimation of Distribution Algorithm (EDA) that explicitly builds probabilistic models to capture variable dependencies (linkage), allowing it to handle epistasis more effectively.

Both algorithms incorporate a deterministic hill climber (DHC) for local search to improve solution quality. The problems used are nearest-neighbor NK landscapes, a class of problems where interactions are localized and can be tuned by parameters n (number of bits) and k (neighborhood size). Epistasis correlation is calculated using a population-based approximation.

Datasets

The paper uses nearest-neighbor NK landscapes as its benchmark. These are synthetic problems where parameters n (number of bits, ranging from 20 to 100) and k (neighborhood size, ranging from 2 to 6) can be systematically varied to control problem difficulty and the degree of epistasis. The authors generated a large number of these instances (up to 10,000 per n/k combination) and categorized them into "easy" and "difficult" based on the performance of the optimization algorithms.

Key Insights and Ideas

  • Epistasis correlation generally decreases as neighborhood size (k) increases: This aligns with the intuition that larger neighborhoods imply more interactions, thus stronger epistasis.
  • Epistasis correlation is largely independent of problem size (n): This suggests that the number of variables itself doesn't directly dictate the strength of interactions, but rather how those variables are connected.
  • hBOA is less sensitive to epistasis than GA: This is a crucial finding. While epistasis correlation can be a useful indicator, algorithms like hBOA that can learn and exploit variable dependencies are less hindered by high epistasis.
  • Epistasis correlation is not a perfect predictor of difficulty: The paper confirms previous observations that simple problems can have strong epistasis and hard problems can have weak epistasis. This highlights the complexity of problem difficulty beyond just variable interactions.

Key Results

  • For hBOA, as problem difficulty (measured by DHC steps) increases, epistasis correlation generally decreases, indicating stronger epistasis. This trend holds for most k values.
  • For GA with uniform crossover, the same trend is observed: increased difficulty correlates with decreased epistasis correlation.
  • The paper presents tables showing the average DHC steps and epistasis correlation for easy and hard instances across different n and k values for both hBOA and GA. For example, with n=100, k=2, hBOA shows a decrease in epistasis correlation from around 0.66 for easiest instances to 0.64 for hardest instances. GA shows a similar trend.
  • The number of evaluations and DHC flips generally increase polynomially with n and exponentially with k for both algorithms.

Limitations and Future Work

  • Epistasis correlation as a sole predictor: The authors acknowledge that epistasis correlation alone is insufficient for practitioners to assess problem difficulty. The relationship is complex, and other factors contribute to difficulty.
  • Future Work: The authors suggest combining different measures of problem difficulty to provide a more robust assessment. They also propose extending the analysis to other classes of problems, such as spin glass or graph problems, to generalize the findings.

Summary updated

BibTeX
@inproceedings{pelikan2011analysis,
  author = {Martin Pelikan},
  title = {{Analysis of epistasis correlation on NK landscapes with nearest-neighbor interactions}},
  booktitle = {GECCO},
  year = {2011},
  doi = {10.1145/2001576.2001714},
}
Figure