Discovering the Elite Hypervolume by Leveraging Interspecies Correlation

Abstract

Evolution has produced an astonishing diversity of species, each filling a different niche. Algorithms like MAP-Elites mimic this divergent evolutionary process to find a set of behaviorally diverse but high-performing solutions, called the elites. Our key insight is that species in nature often share a surprisingly large part of their genome, in spite of occupying very different niches; similarly, the elites are likely to be concentrated in a specific "elite hypervolume" whose shape is defined by their common features. In this paper, we first introduce the elite hypervolume concept and propose two metrics to characterize it: the genotypic spread and the genotypic similarity. We then introduce a new variation operator, called "directional variation", that exploits interspecies (or inter-elites) correlations to accelerate the MAP-Elites algorithm. We demonstrate the effectiveness of this operator in three problems (a toy function, a redundant robotic arm, and a hexapod robot).

arXiv commentIn GECCO 2018

References in corpus (6)

• Robots that can adapt like animals
• Illuminating search spaces by mapping elites
• Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents
• Reset-free Trial-and-Error Learning for Robot Damage Recovery
• Data-Efficient Exploration, Optimization, and Modeling of Diverse Designs through Surrogate-Assisted Illumination
• Map-based Multi-Policy Reinforcement Learning: Enhancing Adaptability of Robots by Deep Reinforcement Learning

Cited by in corpus (24)

• Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
• Quality Diversity for Multi-task Optimization
• Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimization
• Discovering Representations for Black-box Optimization
• Multi-Objective Quality Diversity Optimization
• Differentiable Quality Diversity
• Policy Manifold Search: Exploring the Manifold Hypothesis for Diversity-based Neuroevolution
• 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
• Designing Air Flow with Surrogate-assisted Phenotypic Niching
• Dynamics-Aware Quality-Diversity for Efficient Learning of Skill Repertoires
• Evolving the Behavior of Machines: From Micro to Macroevolution
• Modeling User Selection in Quality Diversity
• Learning to Walk Autonomously via Reset-Free Quality-Diversity
• Overcoming Deceptiveness in Fitness Optimization with Unsupervised Quality-Diversity
• On the Importance of Environments in Human-Robot Coordination
• 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
• Quality-Diversity Optimisation on a Physical Robot Through Dynamics-Aware and Reset-Free Learning
• On Evolvability and Behavior Landscapes in Neuroevolutionary Divergent Search
• Self-Referential Quality Diversity Through Differential Map-Elites
• QED: using Quality-Environment-Diversity to evolve resilient robot swarms
• Policy Manifold Search for Improving Diversity-based Neuroevolution