text: The optimization of functions to find the best solution according to one or several objectives has a central role in many engineering and research fields. Recently, a new family of optimization algorithms, named Quality-Diversity optimization, has been introduced, and contrasts with classic algorithms. Instead of searching for a single solution, Quality-Diversity algorithms are searching for a large collection of both diverse and high-performing solutions. The role of this collection is to cover the range of possible solution types as much as possible, and to contain the best solution for each type. The contribution of this paper is threefold. Firstly, we present a unifying framework of Quality-Diversity optimization algorithms that covers the two main algorithms of this family (Multi-dimensional Archive of Phenotypic Elites and the Novelty Search with Local Competition), and that highlights the large variety of variants that can be investigated within this family. Secondly, we propose algorithms with a new selection mechanism for Quality-Diversity algorithms that outperforms all the algorithms tested in this paper. Lastly, we present a new collection management that overcomes the erosion issues observed when using unstructured collections. These three contributions are supported by extensive experimental comparisons of Quality-Diversity algorithms on three different experimental scenarios.
  @cite_19: In contrast to the conventional role of evolution in evolutionary computation (EC) as an optimization algorithm, a new class of evolutionary algorithms has emerged in recent years that instead aim to accumulate as diverse a collection of discoveries as possible, yet where each variant in the collection is as fit as it can be. Often applied in both neuroevolution and morphological evolution, these new quality diversity (QD) algorithms are particularly well-suited to evolution's inherent strengths, thereby offering a promising niche for EC within the broader field of machine learning. However, because QD algorithms are so new, until now no comprehensive study has yet attempted to systematically elucidate their relative strengths and weaknesses under different conditions. Taking a first step in this direction, this paper introduces a new benchmark domain designed specifically to compare and contrast QD algorithms. It then shows how the degree of alignment between the measure of quality and the behavior characterization (which is an essential component of all QD algorithms to date) impacts the ultimate performance of different such algorithms. The hope is that this initial study will help to stimulate interest in QD and begin to unify the disparate ideas in the area.
  @cite_27: The recently introduced Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) is an evolutionary algorithm capable of producing a large archive of diverse, high-performing solutions in a single run. It works by discretizing a continuous feature space into unique regions according to the desired discretization per dimension. While simple, this algorithm has a main drawback: it cannot scale to high-dimensional feature spaces since the number of regions increase exponentially with the number of dimensions. In this paper, we address this limitation by introducing a simple extension of MAP-Elites that has a constant, pre-defined number of regions irrespective of the dimensionality of the feature space. Our main insight is that methods from computational geometry could partition a high-dimensional space into well-spread geometric regions. In particular, our algorithm uses a centroidal Voronoi tessellation (CVT) to divide the feature space into a desired number of regions; it then places every generated individual in its closest region, replacing a less fit one if the region is already occupied. We demonstrate the effectiveness of the new "CVT-MAP-Elites" algorithm in high-dimensional feature spaces through comparisons against MAP-Elites in a hexapod locomotion task.
  @cite_59: Exploration of the search space through the optimisation of phenotypic diversity is of increasing interest within the field of evolutionary robotics. Novelty search and the more recent MAP-Elites are two state of the art evolutionary algorithms which diversify low dimensional phenotypic traits for divergent exploration. In this paper we introduce a novel alternative for rapid divergent search of the feature space. Unlike previous phenotypic search procedures, our proposed Spatial, Hierarchical, Illuminated Neuro-Evolution (SHINE) algorithm utilises a tree structure for the maintenance and selection of potential candidates. SHINE penalises previous solutions in more crowded areas of the landscape. Our experimental results show that SHINE significantly outperforms novelty search and MAP-Elites in both performance and exploration. We conclude that the SHINE algorithm is a viable method for rapid divergent search of low dimensional, phenotypic landscapes.
  @cite_50: 
summary: However, the obligation to discretize the descriptor space may be limiting for some applications, and the uniform random selection may not be suitable for particularly large collections, as it dilutes the selection pressure. Indeed, the uniform random selection of individuals among the collection makes the selection pressure inversely proportional to the number of solutions actually contained in the collection. A simple way to mitigate this limitation is to use a biased selection according to the solution performance or according to its novelty score (like introduced by @cite_19 @cite_50 ). Another direction consists in having a number of cells irrespective of the dimensionality descriptor space, for example by using computational geometry to uniformly partition the high-dimensional descriptor space into a pre-defined number of regions @cite_27 , or by using Hierarchical Spatial Partitioning @cite_59 .