---
res:
bibo_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 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Jakob
foaf_name: Bossek, Jakob
foaf_surname: Bossek
foaf_workInfoHomepage: http://www.librecat.org/personId=102979
orcid: 0000-0002-4121-4668
- foaf_Person:
foaf_givenName: Dirk
foaf_name: Sudholt, Dirk
foaf_surname: Sudholt
bibo_doi: 10.1145/3583131.3590383
dct_date: 2023^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/9798400701191
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_subject:
- quality diversity
- runtime analysis
dct_title: Runtime Analysis of Quality Diversity Algorithms@
...