Enhancing MAP-Elites with Multiple Parallel Evolution Strategies

Abstract

With the development of fast and massively parallel evaluations in many domains, Quality-Diversity (QD) algorithms, that already proved promising in a large range of applications, have seen their potential multiplied. However, we have yet to understand how to best use a large number of evaluations as using them for random variations alone is not always effective. High-dimensional search spaces are a typical situation where random variations struggle to effectively search. Another situation is uncertain settings where solutions can appear better than they truly are and naively evaluating more solutions might mislead QD algorithms. In this work, we propose MAP-Elites-Multi-ES (MEMES), a novel QD algorithm based on Evolution Strategies (ES) designed to exploit fast parallel evaluations more effectively. MEMES maintains multiple (up to 100) simultaneous ES processes, each with its own independent objective and reset mechanism designed for QD optimisation, all on just a single GPU. We show that MEMES outperforms both gradient-based and mutation-based QD algorithms on black-box optimisation and QD-Reinforcement-Learning tasks, demonstrating its benefit across domains. Additionally, our approach outperforms sampling-based QD methods in uncertain domains when given the same evaluation budget. Overall, MEMES generates reproducible solutions that are high-performing and diverse through large-scale ES optimisation on easily accessible hardware.

References in corpus (14)

• A Brief Survey of Deep Reinforcement Learning
• Procedural Content Generation through Quality Diversity
• Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
• Reset-free Trial-and-Error Learning for Robot Damage Recovery
• Discovering the Elite Hypervolume by Leveraging Interspecies Correlation
• Scaling MAP-Elites to Deep Neuroevolution
• Hierarchical Behavioral Repertoires with Unsupervised Descriptors
• Discovering Representations for Black-box Optimization
• Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters
• Empirical analysis of PGA-MAP-Elites for Neuroevolution in Uncertain Domains
• Learning to Walk Autonomously via Reset-Free Quality-Diversity
• Benchmarking Quality-Diversity Algorithms on Neuroevolution for Reinforcement Learning
• Uncertain Quality-Diversity: Evaluation methodology and new methods for Quality-Diversity in Uncertain Domains
• Assessing Quality-Diversity Neuro-Evolution Algorithms Performance in Hard Exploration Problems