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]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>i</mml:mi> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> . Here k is a granularity parameter $$1 \le k \le n+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . 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)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -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 an edge-weighted graph, we show that QD finds a minimum spanning forest in expected polynomial time. We further consider QD’s performance on classes of transformed functions in which the feature space is not well aligned with the problem. The asymptotic performance is unaffected by transformations on easy functions like OneMax . Applying a worst-case transformation to a deceptive problem increases the expected optimisation time from $$O(n^2 \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> to an exponential time. However, QD is still faster than a (1+1) EA by an exponential factor.