Mouret, J. B., & Clune, J. (2015). Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909.

MAP-Elites (Multi-dimensional Archive of Phenotypic Elites) search

Some optimization problems involve search spaces that are non-differentiable or cannot be expressed mathematically. We may have some performance metric to identify high-performing solutions, but we do not have access to the underlying function that determines the performance. In such cases we would use a "black box" optimization algorithm such as evolutionary algorithms.

Note: in evolutionary algorithms, the feature space is sometimes called the "behavior space".

General idea of MAP-Elites: searching in a high (potentially infinite-dimensional) space, user specifies some lower-dimensional feature space; performance of solutions is measured in this lower-dimensional space.

"Illumination algorithm", contrasted with optimization algorithms (but can be used as optimization algorithms):

designed to return the highest-performing solution at each point in the feature space. They thus illuminate the fitness potential of a each region of the feature space.

Novelty search is an example of an illumination algorithm, as is MAP-Elites.

MAP-Elites algorithm: