Covariance Matrix Adaptation MAP-Annealing
Single-objective optimization algorithms search for the single
highest-quality solution with respect to an objective. In contrast, 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. We propose a new quality diversity algorithm, Covariance
Matrix Adaptation MAP-Annealing (CMA-MAE), which bridges the gap between
single-objective optimization and QD optimization. We prove that CMA-MAE
smoothly blends between the Covariance Matrix Adaptation Evolution Strategy
(CMA-ES) single-objective optimizer and CMA-ME by gradually annealing a
discount function with a scalar learning rate. We show that CMA-MAE has better
performance than the current state-of-the-art QD algorithms on several
benchmark domains and that its performance is empirically invariant to the
archive resolution and robust to the discount function learning rate.