# Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential

arXiv: https://arxiv.org/abs/2407.08963 · HTML: https://mlsanity.com/paper/2407.08963/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 12 Jul 2024.

## Builds on (most cited first, 17 of 17)

- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Quality-Diversity Optimization: a novel branch of stochastic optimization](https://mlsanity.com/paper/2012.04322/) (2020)
- [Procedural Content Generation through Quality Diversity](https://mlsanity.com/paper/1907.04053/) (2019)
- [Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory](https://mlsanity.com/paper/1903.07410/) (2019)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [Analysis of Evolutionary Diversity Optimisation for Permutation Problems](https://mlsanity.com/paper/2102.11469/) (2021)
- [Seeking Quality Diversity in Evolutionary Co-design of Morphology and Control of Soft Tensegrity Modular Robots](https://mlsanity.com/paper/2104.12175/) (2021)
- [Evolutionary Diversity Optimisation for The Traveling Thief Problem](https://mlsanity.com/paper/2204.02709/) (2022)
- [Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem](https://mlsanity.com/paper/2010.10913/) (2020)
- [Evolving Flying Machines in Minecraft Using Quality Diversity](https://mlsanity.com/paper/2302.00782/) (2023)
- [Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem](https://mlsanity.com/paper/2104.13538/) (2021)
- [On the Use of Quality Diversity Algorithms for The Traveling Thief Problem](https://mlsanity.com/paper/2112.08627/) (2021)
- [Evolutionary Diversity Optimisation in Constructing Satisfying Assignments](https://mlsanity.com/paper/2305.11457/) (2023)
- [Diverse, Top-k, and Top-Quality Planning Over Simulators](https://mlsanity.com/paper/2308.13147/) (2023)
- [Parameterized Algorithms for Diverse Multistage Problems](https://mlsanity.com/paper/2105.04856/) (2021)
- [Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax](https://mlsanity.com/paper/2307.07248/) (2023)
- [Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint](https://mlsanity.com/paper/2307.07567/) (2023)

## Abstract (arXiv)

The main goal of diversity optimization is to find a diverse set of solutions which satisfy some lower bound on their fitness. Evolutionary algorithms (EAs) are often used for such tasks, since they are naturally designed to optimize populations of solutions. This approach to diversity optimization, called EDO, has been previously studied from theoretical perspective, but most studies considered only EAs with a trivial offspring population such as the (μ + 1) EA. In this paper we give an example instance of a k-vertex cover problem, which highlights a critical difference of the diversity optimization from the regular single-objective optimization, namely that there might be a locally optimal population from which we can escape only by replacing at least two individuals at once, which the (μ + 1) algorithms cannot do. We also show that the (μ + λ) EA with λ ≥ μ can effectively find a diverse population on k-vertex cover, if using a mutation operator inspired by Branson and Sutton (TCS 2023). To avoid the problem of subset selection which arises in the (μ + λ) EA when it optimizes diversity, we also propose the (1μ + 1μ) EAD, which is an analogue of the (1 + 1) EA for populations, and which is also efficient at optimizing diversity on the k-vertex cover problem.