Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem

Abstract

A core challenge of evolutionary search is the need to balance between exploration of the search space and exploitation of highly fit regions. Quality-diversity search has explicitly walked this tightrope between a population's diversity and its quality. This paper extends a popular quality-diversity search algorithm, MAP-Elites, by treating the selection of parents as a multi-armed bandit problem. Using variations of the upper-confidence bound to select parents from under-explored but potentially rewarding areas of the search space can accelerate the discovery of new regions as well as improve its archive's total quality. The paper tests an indirect measure of quality for parent selection: the survival rate of a parent's offspring. Results show that maintaining a balance between exploration and exploitation leads to the most diverse and high-quality set of solutions in three different testbeds.

arXiv commentProceedings of the Genetic and Evolutionary Computation Conference, 9 pages, 6 figures, 3 tables

References in corpus (7)

• Illuminating search spaces by mapping elites
• First return, then explore
• Procedural Content Generation through Quality Diversity
• Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
• Autonomous skill discovery with Quality-Diversity and Unsupervised Descriptors
• Data-Efficient Exploration, Optimization, and Modeling of Diverse Designs through Surrogate-Assisted Illumination
• Talakat: Bullet Hell Generation through Constrained Map-Elites

Cited by in corpus (2)

• Preference-Learning Emitters for Mixed-Initiative Quality-Diversity Algorithms
• MAP-Elites with Transverse Assessment for Multimodal Problems in Creative Domains