Covariance matrix adaptation for the rapid illumination of behavior space

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