Nearly all science and engineering fields use search algorithms, which automatically explore a search space to find high-performing solutions: chemists search through the space of molecules to discover new drugs; engineers search for stronger, cheaper, safer designs, scientists search for models that best explain data, etc. The goal of search algorithms has traditionally been to return the single highestperforming solution in a search space. Here we describe a new, fundamentally different type of algorithm that is more useful because it provides a holistic view of how highperforming solutions are distributed throughout a search space. It creates a map of high-performing solutions at each point in a space defined by dimensions of variation that a user gets to choose. This Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm illuminates search spaces, allowing researchers to understand how interesting attributes of solutions combine to affect performance, either positively or, equally of interest, negatively. For example, a drug company may wish to understand how performance changes as the size of molecules and their costto-produce vary. MAP-Elites produces a large diversity of high-performing, yet qualitatively different solutions, which can be more helpful than a single, high-performing solution. Interestingly, because MAP-Elites explores more of the search space, it also tends to find a better overall solution than state-of-the-art search algorithms. We demonstrate the benefits of this new algorithm in three different problem domains ranging from producing modular neural networks to designing simulated and real soft robots. Because MAPElites (1) illuminates the relationship between performance and dimensions of interest in solutions, (2) returns a set of high-performing, yet diverse solutions, and (3) improves the state-of-the-art for finding a single, best solution, it will catalyze advances throughout all science and engineering fields. Author's Note: This paper is a preliminary draft of a paper that introduces the MAP-Elites algorithm and explores its capabilities. Normally we would not post such an early draft with only preliminary experimental data, but many people in the community have heard of MAP-Elites, are using it in their own papers, and have asked us for a paper that describes it so that they can cite it, to help them implement MAP-Elites, and that describes the experiments we have already conducted with it. We thus want to share both the details of this algorithm and what we have learned about it from our preliminary experiments. All of the experiments in this paper will be redone before the final version of the paper is published, and the data are thus subject to change. Every field of science and engineering makes use of search algorithms, also known as optimization algorithms, which seek to automatically find a high-quality solution or set of high-quality solutions amongst a large space of possible solutions 1, 2 . Such algorithms often find solutions that outperform those designed Fig. 1 . The MAP-Elites algorithm searches in a high-dimensional space to find the highest-performing solution at each point in a low-dimensional feature space, where the user gets to choose dimensions of variation of interest that define the low dimensional space. We call this type of algorithm an "illumination algorithm", because it illuminates the fitness potential of each area of the feature space, including tradeoffs between performance and the features of interest. For example, MAP-Elites could search in the space of all possible robot designs (a very high dimensional space) to find the fastest robot (a performance criterion) for each combination of height and weight. by human engineers 3 : they have designed antennas that NASA flew to space 4 , found patentable electronic circuit designs 3 , automated scientific discovery 5 , and created artificial intelligence for robots [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] . Because of their widespread use, improving search algorithms provides substantial benefits for society. Most search algorithms focus on finding one or a small set of high-quality solutions in a search space. What constitutes highquality is determined by the user, who specifies one or a few objectives that the solution should score high on. For example, a user may want solutions that are high-performing and low-cost, where each of those desiderata is quantifiably measured either by an equation or simulator. Traditional search algorithms include hill climbing, simulated annealing, evolutionary algorithms, gradient ascent/descent, Bayesian optimization, and multi-objective optimization algorithms 1, 2 . The latter return a set of solutions that represent the best tradeoffs between objectives 16 . A subset of optimization problems are challenging because they require searching for optima in a function or system that is either non-differentiable or cannot be expressed mathematically, typically because a physical system or a complex simulation is required. Such problems require "black box" optimization algorithms, which search for high-performing solutions armed only with the ability to determine the performance of a solution, but without access to the evaluation function that determines that performance. On such problems, one cannot use optimization methods that require calculating the gradient of the function, such as gradient ascent/descent. A notorious challenge in black box optimization is the presence of local optima (also called local minima) 1, 2 . A problem with most search algorithms of this class is that they try to follow a path that will lead to the best global solution by relying on the heuristic that random changes to good solutions lead to better solutions. This approach does not work for highly deceptive problems, however, because in such problems one has to cross low-performing valleys to find the global optima, or even just to find better optima 2 . Because evolutionary algorithms are one of the most success-
The Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm of Mouret and Clune uses the feature-space to maintain diversity in a different manner: at each point in the feature space (which is discretised for this purpose), an archive is maintained of the best individual having the features, where best is measured in terms of objective fitness REF .
Illuminating search spaces by mapping elites
ArXiv
ArXiv
Computer Science Biology