Skip to content

Review: Illuminating Search Spaces by Mapping Elites

Citation

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

Abstract

Most search algorithms return the single highest-performing solution in a space. This paper describes a different kind of algorithm, one that returns the highest-performing solution at each point of a low-dimensional feature space chosen by the user, so that the output is a map of how performance varies across the space rather than one point. The authors call this class of algorithm an illumination algorithm and give a simple, general instance of it, the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites). Across neural networks and simulated and real soft robots, MAP-Elites returns a diverse set of high-performing solutions, illuminates the relationship between the chosen features and performance, and often finds a better single solution than optimization algorithms, because searching for good solutions everywhere in the feature space explores more of the search space.

Most search returns one winner and discards the rest of the space it passed through. Mouret and Clune draw the distinction between an optimization algorithm, which returns the single highest-performing solution, and an illumination algorithm, which returns the highest-performing solution in each region of a user-chosen, low-dimensional feature space. An illumination algorithm therefore reports how performance varies across the feature space, which they call a phenotype-fitness map. It is a superset of optimization: the best cell of the map is also a global optimum.

The algorithm

MAP-Elites keeps a map from each cell of the feature space to the best solution found there, the cell's elite. Three user-supplied functions define a problem: a performance \( f(x) \) to be maximized, a feature descriptor \( b(x) \) that places a solution in the feature space, and a variation operator that makes a new candidate from an existing one. The feature space is low-dimensional by design and is discretized into cells at a granularity set by the available computation.

After seeding the map with a few random solutions, the loop repeats: draw a random occupied cell, vary its elite to make a candidate \( x' \), compute the candidate's descriptor \( b(x') \) and performance \( f(x') \), and store \( x' \) in cell \( b(x') \) when that cell is empty or when \( x' \) beats its current occupant. Placement is a plain keep-if-better rule; there is no temperature and no acceptance ratio. Because the descriptor is many-to-one, many distinct solutions can map to the same cell, and only the best is kept.

Two properties explain why the map fills with high performers. First, most elites are produced by varying an elite that already sits near them in the feature space, so local variation is enough to extend a filled region. Second, the whole archive of high performers acts as a reservoir of stepping stones: tracing the ancestry of a final elite shows lineages that traverse large parts of the feature space, so a good solution in one region seeds the discovery of good solutions in regions a search confined to one region would not reach. Keeping only an archive, with no separate population, also avoids the cycling that afflicts novelty-based methods, since the archive never forgets where it has already been.

Measuring an illumination run

The paper defines four quality measures. Global performance is the best solution found anywhere, divided by the best possible. Global reliability and precision (opt-in reliability) average, over all fillable cells or over the cells a run filled, the performance relative to the best possible in each cell. Coverage is the fraction of fillable cells the run filled. Across all three test domains MAP-Elites scores higher on reliability, precision, and coverage than a traditional evolutionary algorithm, novelty search with local competition, and random sampling, and it is competitive on global performance.

Place in the quality-diversity literature

MAP-Elites is one of the founding algorithms of quality-diversity (QD) search, the study of methods that return a collection of solutions that are at once high-performing and diverse rather than a single optimum. Its immediate ancestors are novelty search and its local-competition variant (Lehman and Stanley 2011), in which a solution competes on performance only against others that are near it in feature space. That idea of local competition is what separates QD from a traditional evolutionary algorithm, and in MAP-Elites it becomes competition within a cell. Since 2015 the field has grown a large family of variants: CVT- MAP-Elites for higher-dimensional feature spaces, CMA-ME and CMA-MAE that drive the search with covariance-matrix adaptation (Fontaine and Nikolaidis), gradient-informed and differentiable QD, Bayesian QD for expensive objectives, multi-objective MAP-Elites, and deep or unsupervised variants that learn the feature space rather than fixing it by hand. The quality-diversity community maintains a categorized bibliography of this literature at quality-diversity.github.io/papers.

Relevance to Hifuku

Hifuku is an illumination algorithm applied to phylogenetics. The feature space is the two-dimensional chart of tree space; the feature descriptor is a tree's barycentric coordinate on that chart; the performance is the alignment log-likelihood, computed exactly by the Felsenstein recursion; and the variation operators are the tree moves (NNI, SPR, branch slide, branch scale). The elite archive keeps the highest-likelihood tree per niche, so the output is a map of the likelihood landscape rather than a single maximum-likelihood tree. The tree is both the genome and the phenotype, a direct encoding with no decoding step. Hifuku turns the paper's coverage and precision measures into its halt condition: the survey stops on discovery saturation, when the rate of new niches and the rate of elite improvement both fall below threshold (see the theory overview, Section 2).