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 $I$ iterations (with iterator $i$), or until some termination criteria is satisfied
- if $i < G$, generate random solution $x'$
- else randomly select an elite $x$ from $\mathcal X$
- create randomly modified copy of $x$, $x'$ (via mutation/crossover)
- record $x'$'s feature descriptor $b'$ (mapping it to a cell in the feature space)
- compute performance $p'$ of $x'$
- if $\mathcal P(b')$ is empty or worse than $p'$
- set $\mathcal P(b') = p'$
- set $\mathcal X(b') = x'$
Example:
- user chooses a performance measure (i.e. fitness function) $f(x)$ that evaluates a solution $x$
- user chooses $N$ dimensions of interest; these define the feature space
- 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)