Hot off the Press: Quality-Diversity Algorithms Can Provably Be Helpful for Optimization

摘要

Quality-Diversity (QD) algorithms are a new type of Evolutionary Algorithms (EAs), aiming to find a set of high-performing, yet diverse solutions. They have many successful applications in reinforcement learning and robotics, helping improve the robustness in complex environments. Furthermore, they often empirically find a better overall solution than traditional search algorithms which explicitly search for a single highest-performing solution. However, their theoretical analysis is far behind. In this paper, we try to shed some light on the optimization ability of QD algorithms theoretically. By comparing the popular QD algorithm MAP-Elites with (μ + 1)-EA (a typical EA focusing on finding better objective values only), we prove that on two NP-hard problems, i.e., monotone approximately submodular maximization and set cover, MAP-Elites can achieve the (asymptotically) optimal polynomial-time approximation ratio, while (μ + 1)-EA requires exponential expected time on some instances. This provides theoretical justification for that QD algorithms can be helpful for optimization, and discloses that the simultaneous search for high-performing solutions with diverse behaviors can provide stepping stones to good overall solutions and help avoid local optima.