Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space

Abstract

We focus on the challenge of finding a diverse collection of quality solutions on complex continuous domains. While quality diver-sity (QD) algorithms like Novelty Search with Local Competition (NSLC) and MAP-Elites are designed to generate a diverse range of solutions, these algorithms require a large number of evaluations for exploration of continuous spaces. Meanwhile, variants of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are among the best-performing derivative-free optimizers in single-objective continuous domains. This paper proposes a new QD algorithm called Covariance Matrix Adaptation MAP-Elites (CMA-ME). Our new algorithm combines the self-adaptation techniques of CMA-ES with archiving and mapping techniques for maintaining diversity in QD. Results from experiments based on standard continuous optimization benchmarks show that CMA-ME finds better-quality solutions than MAP-Elites; similarly, results on the strategic game Hearthstone show that CMA-ME finds both a higher overall quality and broader diversity of strategies than both CMA-ES and MAP-Elites. Overall, CMA-ME more than doubles the performance of MAP-Elites using standard QD performance metrics. These results suggest that QD algorithms augmented by operators from state-of-the-art optimization algorithms can yield high-performing methods for simultaneously exploring and optimizing continuous search spaces, with significant applications to design, testing, and reinforcement learning among other domains.

arXiv commentAccepted to GECCO 2020

References in corpus (9)

• Robots that can adapt like animals
• Illuminating search spaces by mapping elites
• Go-Explore: a New Approach for Hard-Exploration Problems
• Procedural Content Generation through Quality Diversity
• Discovering the Elite Hypervolume by Leveraging Interspecies Correlation
• Autonomous skill discovery with Quality-Diversity and Unsupervised Descriptors
• Optimizing Hearthstone Agents using an Evolutionary Algorithm
• Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms
• Evaluating MAP-Elites on Constrained Optimization Problems

Cited by in corpus (34)

• Deep Learning for Procedural Content Generation
• Multi-Objective Quality Diversity Optimization
• Differentiable Quality Diversity
• Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters
• Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding
• Empirical analysis of PGA-MAP-Elites for Neuroevolution in Uncertain Domains
• Dynamics-Aware Quality-Diversity for Efficient Learning of Skill Repertoires
• Evolving the Behavior of Machines: From Micro to Macroevolution
• Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem
• Few-shot Quality-Diversity Optimization
• Ensemble Feature Extraction for Multi-Container Quality-Diversity Algorithms
• Preference-Learning Emitters for Mixed-Initiative Quality-Diversity Algorithms
• Sparse Reward Exploration via Novelty Search and Emitters
• Learning to Walk Autonomously via Reset-Free Quality-Diversity
• A Unified Substrate for Body-Brain Co-evolution
• Don't Bet on Luck Alone: Enhancing Behavioral Reproducibility of Quality-Diversity Solutions in Uncertain Domains
• Surrogate Infeasible Fitness Acquirement FI-2Pop for Procedural Content Generation
• Parametric-Task MAP-Elites
• Overcoming Deceptiveness in Fitness Optimization with Unsupervised Quality-Diversity
• Generating and Adapting to Diverse Ad-Hoc Cooperation Agents in Hanabi
• On the Importance of Environments in Human-Robot Coordination
• Relevance-guided Unsupervised Discovery of Abilities with Quality-Diversity Algorithms
• Gradient-Informed Quality Diversity for the Illumination of Discrete Spaces
• Enhancing MAP-Elites with Multiple Parallel Evolution Strategies
• Improving the Data Efficiency of Multi-Objective Quality-Diversity through Gradient Assistance and Crowding Exploration
• Curiosity creates Diversity in Policy Search
• Self-Referential Quality Diversity Through Differential Map-Elites
• Quality-diversity in dissimilarity spaces
• Understanding trade-offs in classifier bias with quality-diversity optimization: an application to talent management
• Self-building Neural Networks
• Generating Diverse Indoor Furniture Arrangements
• Learning in Sparse Rewards settings through Quality-Diversity algorithms
• Generating Diverse Challenging Terrains for Legged Robots Using Quality-Diversity Algorithm
• Compressing and Comparing the Generative Spaces of Procedural Content Generators