Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization

Area of Science:

• Optimization
• Computational Intelligence
• Search Algorithms

Background:

• Real-world applications often require a diverse set of solutions rather than a single optimal one.
• Decision-makers need multiple options for comparison and exploration based on various criteria.
• Existing methods like evolutionary diversity optimization, quality diversity, and multimodal optimization address solution diversity.

Purpose of the Study:

• To investigate the trade-off between solution diversity and average quality.
• To evaluate the capability of existing search heuristics in identifying a fixed number of solutions with a minimum pairwise distance and maximized average quality.
• To understand how this trade-off is influenced by the characteristics of the optimization problem.

Main Methods:

• Performing subset selection on search trajectories of established search heuristics.
• Analyzing the performance of these heuristics against a baseline of uniform random sampling.
• Empirically studying the relationship between minimum pairwise distance and average quality.

Main Results:

• Naive uniform random sampling provides a surprisingly strong baseline for achieving diverse, high-quality solutions.
• Off-the-shelf heuristics often do not outperform random sampling in this specific task.
• The trade-off between diversity and quality is dependent on the properties of the optimization problem.

Conclusions:

• There is a need for algorithms specifically designed to generate diverse solutions with high average quality.
• Current search heuristics may not be optimally suited for problems requiring a guaranteed minimum pairwise distance among solutions.
• Random sampling serves as a critical benchmark for evaluating diversity-aware optimization strategies.