# Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 26 references that are in the map.
- First posted on arXiv 14 Jul 2023.

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

- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network](https://mlsanity.com/paper/2007.05674/) (2020)
- [Policy Manifold Search: Exploring the Manifold Hypothesis for Diversity-based Neuroevolution](https://mlsanity.com/paper/2104.13424/) (2021)
- [From exploration to control: learning object manipulation skills through novelty search and local adaptation](https://mlsanity.com/paper/1901.00811/) (2019)
- [Interactive Constrained MAP-Elites: Analysis and Evaluation of the Expressiveness of the Feature Dimensions](https://mlsanity.com/paper/2003.03377/) (2020)
- [Evolutionary Diversity Optimization Using Multi-Objective Indicators](https://mlsanity.com/paper/1811.06804/) (2018)
- [Analysis of Evolutionary Diversity Optimisation for Permutation Problems](https://mlsanity.com/paper/2102.11469/) (2021)
- [Discrepancy-based Evolutionary Diversity Optimization](https://mlsanity.com/paper/1802.05448/) (2018)
- [Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem](https://mlsanity.com/paper/2010.10913/) (2020)
- [Feature-Based Diversity Optimization for Problem Instance Classification](https://mlsanity.com/paper/1510.08568/) (2015)
- [Prototype Discovery using Quality-Diversity](https://mlsanity.com/paper/1807.09488/) (2018)
- [Evolving Diverse Sets of Tours for the Travelling Salesperson Problem](https://mlsanity.com/paper/2004.09188/) (2020)
- [Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem](https://mlsanity.com/paper/2104.13538/) (2021)
- [Coevolutionary Pareto Diversity Optimization](https://mlsanity.com/paper/2204.05457/) (2022)
- [Computing Diverse Sets of High Quality TSP Tours by EAX-Based Evolutionary Diversity Optimisation](https://mlsanity.com/paper/2108.05005/) (2021)
- [Analysis of Quality Diversity Algorithms for the Knapsack Problem](https://mlsanity.com/paper/2207.14037/) (2022)
- [Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms](https://mlsanity.com/paper/2104.13133/) (2021)

## Built on by (most cited first, 2 of 2)

- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)

## Abstract (arXiv)

The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time O(n2), when the problem size n is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.