Covariance Matrix Adaptation MAP-Annealing
This addresses a problem for the quality diversity optimization community by improving algorithm robustness and performance, though it appears incremental as it builds directly on CMA-ME.
The paper tackles limitations of the Covariance Matrix Adaptation MAP-Elites (CMA-ME) algorithm in quality diversity optimization, such as premature abandonment of objectives and poor performance in low-resolution archives, by proposing CMA-MAE, which achieves state-of-the-art performance and robustness.
Single-objective optimization algorithms search for the single highest-quality solution with respect to an objective. Quality diversity (QD) optimization algorithms, such as Covariance Matrix Adaptation MAP-Elites (CMA-ME), search for a collection of solutions that are both high-quality with respect to an objective and diverse with respect to specified measure functions. However, CMA-ME suffers from three major limitations highlighted by the QD community: prematurely abandoning the objective in favor of exploration, struggling to explore flat objectives, and having poor performance for low-resolution archives. We propose a new quality diversity algorithm, Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), that addresses all three limitations. We provide theoretical justifications for the new algorithm with respect to each limitation. Our theory informs our experiments, which support the theory and show that CMA-MAE achieves state-of-the-art performance and robustness.