Runtime Analysis of Quality Diversity Algorithms

Abstract

Quality diversity~(QD) is a branch of evolutionary computation that gained increasing interest in recent years. The Map-Elites QD approach defines a feature space, i.e., a partition of the search space, and stores the best solution for each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean optimisation on the ``number of ones'' feature space, where the $i$th cell stores the best solution amongst those with a number of ones in $[(i-1)k,ik-1]$. Here $k$ is a granularity parameter $1\le k\le n+1$. We give a tight bound on the expected time until all cells are covered for arbitrary fitness functions and for all $k$ and analyse the expected optimisation time of QD on \textsc{OneMax} and other problems whose structure aligns favourably with the feature space. On combinatorial problems we show that QD finds a $(1-1/e)$-approximation when maximising any monotone sub-modular function with a single uniform cardinality constraint efficiently. Defining the feature space as the number of connected components of a connected graph, we show that QD finds a minimum spanning tree in expected polynomial time.

This version fixes a bug in Theorem 6.1 of the paper published at GECCO 2023. It claims an upper bound of $O(nm\log n)$ for the expected time to locate the empty edge set, but the proof arguments were insufficient (thanks to Frank Neumann for spotting this). We now give a bound of $O(nm\log (n{w}_{\max }))$ for integer edge weights where $w_{\max }$ is the largest edge weight

References in corpus (3)

• Illuminating search spaces by mapping elites
• Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation
• Exponential Slowdown for Larger Populations: The $(\mu +1)$-EA on Monotone Functions