Covariance matrix adaptation for the rapid illumination of behavior space

Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, Amy K. Hoover

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We focus on the challenge of finding a diverse collection of quality solutions on complex continuous domains. While quality diversity (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.

    Original languageEnglish (US)
    Title of host publicationGECCO 2020 - Proceedings of the 2020 Genetic and Evolutionary Computation Conference
    PublisherAssociation for Computing Machinery
    Pages94-102
    Number of pages9
    ISBN (Electronic)9781450371285
    DOIs
    StatePublished - Jun 25 2020
    Event2020 Genetic and Evolutionary Computation Conference, GECCO 2020 - Cancun, Mexico
    Duration: Jul 8 2020Jul 12 2020

    Publication series

    NameGECCO 2020 - Proceedings of the 2020 Genetic and Evolutionary Computation Conference

    Conference

    Conference2020 Genetic and Evolutionary Computation Conference, GECCO 2020
    CountryMexico
    CityCancun
    Period7/8/207/12/20

    Keywords

    • Evolutionary algorithms
    • Hearthstone
    • Illumination algorithms
    • MAP-Elites
    • Optimization
    • Quality diversity

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Theoretical Computer Science

    Fingerprint Dive into the research topics of 'Covariance matrix adaptation for the rapid illumination of behavior space'. Together they form a unique fingerprint.

    Cite this