Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization
<|reference_start|>Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization: In real-world applications, users often favor structurally diverse design choices over one high-quality solution. It is hence important to consider more solutions that decision-makers can compare and further explore based on additional criteria. Alongside the existing approaches of evolutionary diversity optimization, quality diversity, and multimodal optimization, this paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold while maximizing their average quality.   We obtain first insight into these objectives by performing a subset selection on the search trajectories of different well-established search heuristics, whether specifically designed with diversity in mind or not. We emphasize that the main goal of our work is not to present a new algorithm but to look at the problem in a more fundamental and theoretically tractable way by asking the question: What trade-off exists between the minimum distance within batches of solutions and the average quality of their fitness? These insights also provide us with a way of making general claims concerning the properties of optimization problems that shall be useful in turn for benchmarking algorithms of the approaches enumerated above.   A possibly surprising outcome of our empirical study is the observation that naive uniform random sampling establishes a very strong baseline for our problem, hardly ever outperformed by the search trajectories of the considered heuristics. We interpret these results as a motivation to develop algorithms tailored to produce diverse solutions of high average quality.<|reference_end|>
@article{santoni2024illuminating,
    title={Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization},
    author={Maria Laura Santoni, Elena Raponi, Aneta Neumann, Frank Neumann, Mike
  Preuss, Carola Doerr},
    journal={arXiv preprint arXiv:2408.16393},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.16393},
    primaryClass={cs.LG}
}