Coevolutionary Pareto diversity optimization

Aneta Neumann, Denis Antipov, Frank Neumann

Abstract

Traditional optimization often focuses on finding a single global optimum, yet real-world decision-making frequently requires a diverse set of high-quality alternatives. This paper presents Coevolutionary Pareto Diversity Optimization (PDO), a novel framework that balances the pursuit of optimality with the maintenance of solution variety. By utilizing two coevolving populations—one dedicated to optimization and another to diversity—and facilitating genetic exchange between them, PDO achieves superior performance compared to existing state-of-the-art methods.

Introduction

In many practical scenarios, the "best" solution is not a fixed target. Factors such as implementation difficulty, robustness, or changing constraints may make a slightly sub-optimal but diverse solution more desirable. The challenge lies in efficiently computing a set of solutions that are both high-performing and significantly different from one another. While Pareto optimization handles trade-offs and Evolutionary Diversity Optimization (EDO) promotes variety, combining these effectively has remained difficult. Existing methods often struggle to maintain a balance, either becoming too "greedy" for quality or losing focus on performance in favor of entropy.

Methodology: A Coevolutionary Approach

The PDO framework addresses this by employing two distinct populations that interact throughout the evolutionary process:

  1. Optimization Population ($P_O$): This population employs standard Pareto optimization techniques. It treats problem constraints as a secondary objective, allowing the algorithm to navigate the search space more effectively and converge toward the global optimum.
  2. Diversity Population ($P_D$): This population maintains solutions that meet a predefined minimum quality threshold ($f_{min}$). Its objective is to maximize entropy, ensuring that the set of solutions represents a wide variety of configurations.

Inter-population Crossover (PDO-C)

A key innovation is the introduction of inter-population crossover. By allowing individuals from $P_O$ (high quality) to breed with individuals from $P_D$ (high diversity), the algorithm injects high-performing genetic material into the diverse population. This helps $P_D$ explore high-quality regions of the search space that might otherwise be overlooked. Additionally, the PDO-CH variant incorporates "heavy-tail" mutations to facilitate larger jumps across the search landscape.

Experimental Evaluation

The researchers evaluated PDO on the Maximum Coverage Problem, an NP-hard combinatorial problem. The goal is to select a subset of nodes in a graph to cover the maximum number of other nodes under a budget constraint. Benchmarks included standard graphs from the vertex cover test suite: frb30-15, frb35-17, and frb40-19.

Key Results and Discussion

The experimental results demonstrate the clear superiority of the coevolutionary approach.

Comparison of PDO against GDGS and DIVEA across various benchmark graphs. PDO consistently achieves higher optimization values and diversity scores.

As shown in the results table above, PDO significantly outperforms DIVEA, the previous state-of-the-art, in both solution quality and diversity across all tested instances ($p < 0.001$). The split-population strategy prevents the algorithm from stagnating, as $P_O$ acts as a scout for the global peak while $P_D$ populates the surrounding high-quality plateau.

Furthermore, the impact of inter-population crossover is evident when comparing the PDO variants.

Performance comparison of PDO variants (PDO, PDO-C, PDO-CH). The inclusion of crossover (PDO-C) significantly enhances diversity without compromising solution quality.

The data indicates that PDO-C consistently achieves higher entropy levels than the baseline PDO. This confirms that recombining known high-quality solutions is an effective strategy for discovering diverse alternatives that maintain high performance.

Conclusion and Future Work

Coevolutionary Pareto Diversity Optimization represents a significant step forward in finding diverse, high-quality solutions for complex combinatorial problems. By decoupling the goals of optimization and diversity into separate but interacting populations, the framework avoids common trade-off pitfalls.

Future research will explore the application of PDO to non-binary encodings, such as continuous domains or tree structures. Additionally, testing the framework on real-world machine learning tasks like feature selection and ensemble pruning could provide valuable insights into its utility for improving model generalization.

Summary updated

BibTeX
@inproceedings{neumann2022coevolutionary,
  author = {Aneta Neumann and Denis Antipov and Frank Neumann},
  title = {{Coevolutionary Pareto diversity optimization}},
  booktitle = {GECCO},
  year = {2022},
  doi = {10.1145/3512290.3528755},
}
Figure