Linkage neighbors, optimal mixing and forced improvements in genetic algorithms

Peter A. N. Bosman, Dirk ThierensGECCO 2012 · DOI

TL;DR

This paper introduces "Linkage Neighbors" (LN), a new way for genetic algorithms (GAs) to understand how different variables in a problem are related. By combining LN with "Forced Improvements" (FI), the authors achieve better performance on complex optimization problems, especially those with overlapping variable dependencies, outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Genetic algorithms (GAs) are powerful optimization tools, but their efficiency heavily depends on how well they can identify and exploit "linkage" – the relationships between different variables that influence the overall solution quality. Traditional GAs often struggle with problems where variables are interdependent in complex, overlapping ways. While methods like the Linkage Tree Genetic Algorithm (LTGA) have made progress, they have limitations in representing these overlapping dependencies. This paper aims to address this by proposing a more flexible linkage model and a technique to improve convergence.

Methods

The core of this paper lies in two main contributions:

  • Linkage Neighbors (LN) Model: Instead of a rigid hierarchical structure like the Linkage Tree (LT), the LN model focuses on identifying "neighbors" for each variable. This allows for a more flexible representation of overlapping building blocks. The paper explores different ways to learn these neighbors, primarily using mutual information (MI) between variables.
  • Forced Improvements (FI): This technique enhances the convergence of GAs. When standard "Optimal Mixing" (OM) – a method that iteratively improves a cloned solution by incorporating parts of other solutions – fails to yield an improvement, FI applies OM using the current best-known solution as a donor. This directs the search towards the optimum without requiring explicit diversity-reducing selection steps, which can prematurely halt exploration.

The authors also introduce Multiscale Linkage Neighbors (MLN), an extension of LN that models linkages at multiple levels of granularity, further improving performance on complex problems.

Datasets

The paper evaluates its proposed methods on a combination of standard benchmarks and a more challenging real-world problem:

  • Linkage Benchmark Problems:
    • Onemax: A simple problem where all variables contribute equally to the fitness.
  • Trap-5: A deceptive problem designed to test an EA's ability to handle linkage.
  • NK-S1: A class of problems (NK landscapes) known for their complex, potentially overlapping dependencies.
  • Weighted MAXCUT: A combinatorial optimization problem representing a real-world challenge. The authors generated their own instances for controlled scalability analysis.

Key Insights and Ideas

  • Overlapping dependencies are crucial: The paper strongly suggests that many real-world problems, particularly those beyond simple benchmarks, exhibit complex, overlapping variable dependencies that rigid hierarchical models like LT struggle to capture.
  • Linkage Neighbors offer flexibility: The LN model, by focusing on pairwise relationships and allowing for overlap, proves more adept at representing these complex dependencies.
  • Mutual Information is a powerful tool for linkage learning: The paper demonstrates that MI can effectively identify linkage relationships, even in the presence of noise from EA operators.
  • Forced Improvements accelerate convergence: FI is shown to be an effective way to drive convergence towards a single optimum without sacrificing too much diversity, outperforming traditional selection mechanisms in certain scenarios.
  • Multiscale modeling is beneficial: The MLN model, by considering linkages at different scales, further enhances performance, especially on problems where dependencies aren't neatly categorized into just "strong" or "weak."

Key Results

  • Benchmark Performance: The LNGA (Linkage Neighbors GA) with the simplest learning approach (MI-indep) outperformed LTGA on the common linkage benchmark problems, even outperforming LTGA.
  • Weighted MAXCUT Performance: While LNGA initially struggled on weighted MAXCUT, the MLNGA variants showed robust performance, with the bucket-exponential decomposition being the most efficient.
  • Scalability: The proposed methods, particularly MLNGA, demonstrated good scalability on weighted MAXCUT, though LTGA still showed superior performance as problem size increased for this specific problem.
  • Forced Improvements Impact: The FI technique was shown to establish efficient convergence without requiring additional population-wise selection or losing diversity too quickly.

Limitations and Future Work

  • LTGA's Advantage on MAXCUT: Despite the improvements of LN and MLN, the LT model still showed superior performance on weighted MAXCUT as problem size increased. The authors speculate this might be due to LT's inherent hierarchical structure and the inclusion of singletons in its FOS.
  • Future Work: The authors suggest exploring the use of concepts from LN and MLN to adjust the LT model. They also propose investigating the direct selection of subsets from the powerset of all variables to build a FOS, provided runtime complexity can be managed. Further research into the optimal configuration of thresholds for LN and MLN is also implied.

Summary updated

BibTeX
@inproceedings{bosman2012linkage,
  author = {Peter A. N. Bosman and Dirk Thierens},
  title = {{Linkage neighbors, optimal mixing and forced improvements in genetic algorithms}},
  booktitle = {GECCO},
  year = {2012},
  doi = {10.1145/2330163.2330247},
}
Figure