Runtime Analysis of Quality Diversity Algorithms
Bossek, Jakob
Sudholt, Dirk
quality diversity
runtime analysis
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 ith 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 {$\leq$} k {$\leq$} 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 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.
Association for Computing Machinery
2023
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://ris.uni-paderborn.de/record/48872
Bossek J, Sudholt D. Runtime Analysis of Quality Diversity Algorithms. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’23. Association for Computing Machinery; 2023:1546–1554. doi:<a href="https://doi.org/10.1145/3583131.3590383">10.1145/3583131.3590383</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/3583131.3590383
info:eu-repo/semantics/altIdentifier/isbn/9798400701191
info:eu-repo/semantics/closedAccess