Illuminating search spaces by mapping elites

By Jean-Baptiste Mouret, Jeff Clune. arXiv.org, 2015

952 citations recorded by the source corpus.

Many 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 highest-performing 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 high-performing 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 cost-to-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 MAP- Elites (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 finding a single, best solution, it will advance science and engineering.

Subfields: Artificial Intelligence, Sociology and Political Science

View Paper: https://www.semanticscholar.org/paper/45373921f06a6efebefa6189d2dd80362ab0836e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions (2020, background): “The balance between diversity and optimization ﬁgures prominently in the ﬁeld called quality diversity (QD) (Lehman & Stanley, 2011b; Mouret & Clune, 2015; Pugh et al., 2016), in which the aim is to collect a diversity of high-quality solutions.”
First return, then explore (2020, background): “This behaviour is reminiscent of the MAP-Elites algorithm 19 , and quality diversity algorithms more broadly 20,21 , although it is novel because it applies such ideas to reach new locations within a state space, instead of to discover new styles of behaviour as MAP-Elites typically does.”
Robots that can adapt like animals (2014, background): “3c, the undamaged robot takes 24 s [16 s; 41 s] in 3 [2; 5] physical trials and the repaired robot takes 29 s [16 s; 82 s] in 3.”
AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025, positive): “In AlphaEvolve , the evolutionary database implements an algorithm that is inspired by a combination of the MAP elites algorithm [74] and island-based population models [83, 97].”
Effective Diversity in Population-Based Reinforcement Learning (2020, methodology): “The MAPElites [37] algorithm is conceptually similar to ours, the authors seek to find quality solutions in differing dimensions.”
Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning (2017, background): “…Deb & Myburgh, 2016), indirect encoding (Stanley, 2007; Stanley et al., 2009; Clune et al., 2011), and encouraging diversity (Lehman & Stanley, 2011a; Mouret & Clune, 2015; Pugh et al., 2016) (a subject we do take an initial look at here with our nov-elty search experiments), just to name a few.”
Reset-free Trial-and-Error Learning for Robot Damage Recovery (2016, methodology): “ve, it can be straightforward to parallelize and can run on large clusters before deploying the robot. So far, it has been successfully used to generate: behaviors for legged robots [7], robotic arms [7, 44] and wheeled robots [48, 49, 46]; designs for airfoils [50], as well as for the morphologies ”
AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence (2019, methodology): “Research has shown that such goal switching signiﬁcantly improves the performance of QD algorithms [123, 116, 70].”
Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions (2019, background): “If the skills learned in the latter environment apply, it could revolutionize the behavior in the former, reflecting the fact that the most promising stepping stone to the best possible outcome may not be the current top performer in that environment [34, 36, 54].”
Fiber: A Platform for Efficient Development and Distributed Training for Reinforcement Learning and Population-Based Methods (2020, methodology): “…data, both in the conventional supervised context and in reinforcement learning (RL) (Espeholt et al. 2018; Mnih et al. 2016; Ecoffet et al. 2019; Nair et al. 2015; Horgan et al. 2018; Jader-berg et al. 2018; Sutton and Barto 2018) and population-based methods (Salimans et al. 2017; Jaderberg et…”
Walk These Ways: Tuning Robot Control for Generalization with Multiplicity of Behavior (2022, background): “Quality diversity (QD) methods [13, 14, 15] learn a library of diverse policies by enforcing a novelty objective defined among trajectories.”
Diverse Agents for Ad-Hoc Cooperation in Hanabi (2019, methodology): “MAP-Elites [9] is an example of QD algorithm that attempts to “illuminate” the behavior space by mapping each individual to behavioral “niche”, while maintaining an archive of the best individual (an elite) in each niche.”
The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities (2018, positive): “Toevolve a large diversity of gaits, the team used the MAP-Elites evolutionary algorithm [99], which simultaneously searches for the fittest organism over every combination of chosen dimensions of variation (i.e., ways that phenotypes can vary).”
Quality Diversity: A New Frontier for Evolutionary Computation (2016, background): “This section describes each of the various algorithms considered in this study, beginning with those featured by Pugh et al. (2015). Because the pursuit of quality diversity has only recently become a subject of persistent research interest, there are only two main QD algorithms currently represente”