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:

- create an empty
$N$ -dimensional map of elites (solutions$\mathcal X$ and their performances$\mathcal P$ ) - for
iterations (with iterator$I$ ), or until some termination criteria is satisfied$i$ - if
$i < G$ , generate random solution$x'$ - else randomly select an elite
from$x$ $\mathcal X$ - create randomly modified copy of
$x$ ,$x'$ (via mutation/crossover)

- create randomly modified copy of
- record
$x'$ 's feature descriptor$b'$ (mapping it to a cell in the feature space) - compute performance
$p'$ of$x'$ - if
is empty or worse than$\mathcal P(b')$ $p'$ - set
$\mathcal P(b') = p'$ - set
$\mathcal X(b') = x'$

- set

- if

Example:

- user chooses a performance measure (i.e. fitness function)
$f(x)$ that evaluates a solution$x$ - user chooses
dimensions of interest; these define the feature space$N$ - e.g. with a robot it could be its height, weight, and energy consumption

- the
$N$ dimensions are discretized at some granularity (either user-specifier or limited by computational resources). This discretization makes the feature space into a lattice (i.e. it's broken up into cells) - we have a feature function (aka "behavior function")
$b(x)$ that maps a solution$x$ to an$N$ -dimensional vector describing its features (i.e. mapping it to the feature space). some of these features may need to be measured through e.g. simulation, such as energy consumption. - search happens in the search space, where we search through genotypes/genomes
$x$ (rather than directly searching phenotypes)