QD algorithms seek to find a diverse set of solutions, where the best candidates within distinct subspaces of the solution space are gradually discovered.
Motivation
MAP-Elites can been seen as part of the recent trend (…ok, maybe not that recent) in evolution algorithm community to favor exploration, i.e. focus on generating novel individuals even if they may not have the highest fitness. Lehman, J., & Stanley, K. O. (2008) famously demonstrated that in certain tasks with deceptive/delayed/sparse reward (maze navigation in this case), optimizing for novelty alone while neglecting performance can actually be a valid approach! It was also argued in Lehman, J., & Stanley, K. O. (2011) and Salimans, T., et al. (2017) that the density of high-performing solutions is often high enough and the reward structure deceptive to merit exploration over exploitation. The importance of exploration justifies the emergence a family of evolution algorithms called Quality-Diversity(QD) algorithms, which search for a set of high-performing and distinct solutions rather than just one best solution. MAP-Elites belongs to this family, and aside from MAP-Elites which explores the search space indirectly, another major sub-family of QD algorithm is represented by Novelty Search with Local Competition(NSLC), which actively optimizes for novelty along with fitness using multi-objective optimizer algorithms such as NSGA-II. - blog