Quality Diversity: A New Frontier for Evolutionary Computation

By Justin K. Pugh, Lisa B. Soros, Kenneth O. Stanley. 2016

687 citations recorded by the source corpus.

While evolutionary computation and evolutionary robotics take inspiration from nature, they have long focused mainly on problems of performance optimization. Yet evolution in nature can be interpreted as more nuanced than a process of simple optimization. In particular, natural evolution is a divergent search that optimizes locally within each niche as it simultaneously diversifies. This tendency to discover both quality and diversity at the same time differs from many of the conventional algorithms of machine learning, and also thereby suggests a different foundation for inferring the approach of greatest potential for evolutionary algorithms. In fact, several recent evolutionary algorithms called quality diversity (QD) algorithms(e.g. novelty search with local competition and MAP-Elites) have drawn inspiration from this more nuanced view, aiming to fill a space of possibilities with the best possible example of each type of achievable behavior. The result is a new class of algorithms that return an archive of diverse, high-quality behaviors in a single run. The aim in this paper is to study the application of QD algorithms in challenging environments (in particular complex mazes) to establish their best practices for ambitious domains in the future. In addition to providing insight into cases when QD succeeds and fails, a new approach is investigated that hybridizes multiple views of behaviors (called behavior characterizations) in the same run, which succeeds in overcoming some of the challenges associated with searching for QD with respect to a behavior characterization that is not necessarily sufficient for generating both quality and diversity at the same time.

Subfields: Artificial Intelligence

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

Citations in the corpus

Diversity is All You Need: Learning Skills without a Reward Function (2018, background): “Prior work in neuroevolution and evolutionary algorithms has studied how complex behaviors can be learned by directly maximizing diversity (Lehman & Stanley, 2011a;b; Woolley & Stanley, 2011; Stanley & Miikkulainen, 2002; Such et al., 2017; Pugh et al., 2016; Mouret & Doncieux, 2009).”
Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions (2019, background): “Population-based algorithms going back to novelty search [48] that encourage behavioral (as opposed to genetic) diversity [42–46, 49 ] In the canonical example of novelty search (NS) [48], individuals are selected purely based on how different their behaviors are compared to an archive of…”
Effective Diversity in Population-Based Reinforcement Learning (2020, background): “One particularly exciting class of neuroevolution methods is Quality Diversity (QD, (Pugh et al., 2016)) where algorithms explicitly seek high performing, yet diverse behaviors (Cully et al.”
Quality and Diversity Optimization: A Unifying Modular Framework (2017, background): “However, very few works compare MAP-Elites and NSLC on the same applications (the few exceptions being [16], [17], [31], [36]), or investigate alternative approaches to produce collections of solutions.”
Minimal criterion coevolution: a new approach to open-ended search (2017, background): “In recent years these algorithms have increased in sophistication as researchers have learned to balance divergent pressure with a more objective tness-like counterpart to produce a process called quality diversity (QD) that yields both high quality and diversity simultaneously in one run [22].”
Intrinsically Motivated Goal Exploration Processes with Automatic Curriculum Learning (2017, methodology): “When goal sampling is made in this form of function space, IMGEPs correspond to quality-diversity algorithms (Pugh et al., 2016) such as MAP-Elite (Cully et al., 2015).”
Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents (2017, methodology): “That is the approach of novelty search (Lehman & Stanley, 2011a) and quality diversity algorithms (Cully et al., 2015; Mouret & Clune, 2015; Pugh et al., 2016), which are described in detail below.”
DREAM Architecture: a Developmental Approach to Open-Ended Learning in Robotics (2020, methodology): “ntroduces a further challenge in the form of the reality gap [76], where policies learnt in simulation must be transferred to the real robot. Our approach [73] uses a Quality-Diversity (QD) algorithm [77, 78] to build such a skill repertoire, and a generalization approach based on a local linear mod”
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.”
ARCH-Elites: quality-diversity for urban design (2021, background): “We report the maximum fitness in the run’s archive, coverage [4] and QD-score [5].”
Exploration in Deep Reinforcement Learning: A Survey (2022, background): “More detailed reviews of exploration in evolution strategies can be found in [78] and [79].”
Diverse Agents for Ad-Hoc Cooperation in Hanabi (2019, background): “Diversity of behavior can be pursued either as desirable target in its own right or as an intermediate step to high-quality solutions, as showcased by novelty search, which can outperform traditional optimization in deceptive environments even though it abandons the notion of an objective function [”
Mathematical discoveries from program search with large language models (2023, background): “This approach, which aims to preserve diversity 55,56 , is related to Lexicase 57 in that both approaches consider a set of test cases for scoring an individual, and it is related to fitness uniform optimization 58 , which also clusters individuals on the basis of their fitness value; however, we…”
Learning to Score Behaviors for Guided Policy Optimization (2019, methodology): “For BGES, these embeddings are those typically used in Quality Diversity algorithms (Pugh et al., 2016), while for BGPG we reinterpret the action distribution currently used in KL-based trust regions (Schulman et al., 2017; 2015).”
Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions (2020, background): “The balance between diversity and optimization figures prominently in the field 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.”
Automated Curriculum Learning by Rewarding Temporally Rare Events (2018, background): “events as well as the environment’s original objective, inspired by quality diversity methods [35] that use a combination of diversity and objective-based search [10, 30].”