Source-linked AI summary
Illuminating search spaces by mapping elites
Jean-Baptiste Mouret, Jeff Clune
TL;DR
Existing search algorithms often target a single best solution and can become trapped by local optima. The paper introduces MAP-Elites, which maps the best solutions across user-defined feature dimensions; across reported domains, it illuminates feature-performance relationships, returns diverse solutions, and matches or outperforms control algorithms, with preliminary evidence cautioning against firm conclusions.
Problem
Traditional search algorithms focus on one or a few high-quality solutions, while deceptive black-box landscapes can contain local optima separated from better optima by low-performing valleys.
Method
MAP-Elites evaluates candidate solutions and retains the highest-performing one in each cell of a discretized, user-defined feature space.
Results
MAP-Elites significantly outperformed or matched control algorithms on finding the single highest-performing solution and, in one reported domain, scored higher on global performance, reliability, precision, and coverage.
Takeaways & Limitations
MAP-Elites provides a map of fitness potential and a diverse repertoire of high-performing solutions while also serving as a powerful optimization algorithm.
Takeaways & Limitations
The preliminary draft reports only preliminary experimental data, and MAP-Elites cannot add new cell types that were absent from the original feature space.
Abstract
from arXiv · showhide
Many fields use search algorithms, which automatically explore a search space to find high-performing solutions: chemists search through the space of molecules to discover new drugs; engineers search for stronger, cheaper, safer designs, scientists search for models that best explain data, etc. The goal of search algorithms has traditionally been to return the single highest-performing solution in a search space. Here we describe a new, fundamentally different type of algorithm that is more useful because it provides a holistic view of how high-performing solutions are distributed throughout a search space. It creates a map of high-performing solutions at each point in a space defined by dimensions of variation that a user gets to choose. This Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm illuminates search spaces, allowing researchers to understand how interesting attributes of solutions combine to affect performance, either positively or, equally of interest, negatively. For example, a drug company may wish to understand how performance changes as the size of molecules and their cost-to-produce vary. MAP-Elites produces a large diversity of high-performing, yet qualitatively different solutions, which can be more helpful than a single, high-performing solution. Interestingly, because MAP-Elites explores more of the search space, it also tends to find a better overall solution than state-of-the-art search algorithms. We demonstrate the benefits of this new algorithm in three different problem domains ranging from producing modular neural networks to designing simulated and real soft robots. Because MAP- Elites (1) illuminates the relationship between performance and dimensions of interest in solutions, (2) returns a set of high-performing, yet diverse solutions, and (3) improves finding a single, best solution, it will advance science and engineering.
1 Background and Motivation
Traditional search algorithms seek high-quality solutions, but often converge early or struggle with deceptive local optima. MAP-Elites instead explores user-selected feature dimensions to illuminate performance relationships while preserving diverse high-performing solutions.
- Search algorithms automatically seek high-quality solutions across large spaces, supporting applications throughout science and engineering.
- Highly deceptive black-box problems challenge search because reaching better optima may require crossing low-performing valleys.
- Many diversity-promoting methods still converge to one or a few good solutions and stop improving.
- MAP-Elites searches for the highest-performing solution at every point in a user-defined, discretized feature space.
- Its benefits include user-controlled diversity, illumination of feature-performance relationships, and often better optimization through broader exploration.
- MAP-Elites returns a mapped repertoire of diverse, high-performing individuals rather than only one best solution.
2 Optimization vs. Illumination Algorithms
Optimization algorithms typically seek the best solution, whereas illumination algorithms seek the best solution at each point in a user-defined feature space. MAP-Elites implements this illumination objective through a feature-performance map.
- Optimization algorithms generally target the highest-performing solution, while illumination algorithms target the highest-performing solution in each feature-space region.
- Illumination algorithms reveal the fitness potential of different feature-space areas and therefore include optimization algorithms as a broader class.
- MAP-Elites returns a feature-performance map containing the elite solution associated with each represented cell.
- MAP-Elites is presented alongside Novelty Search + Local Competition and MOLE as an illumination algorithm.
3 Details of the MAP-Elites algorithm
MAP-Elites evaluates candidate genomes by performance and user-selected features, retaining the best candidate in each discretized feature-space cell. It repeatedly samples archive members to generate and evaluate new candidates until termination.
- Users choose a fitness function and N dimensions of variation that define the feature space of interest.
- Feature dimensions are discretized according to user preference or computational resources, with granularity optionally increasing during search.
- For each feature-space cell, MAP-Elites retains the highest-performing candidate among genomes mapped to that cell.
- Each candidate genome is evaluated through a fitness function and a feature function that returns an N-dimensional feature vector.
- The algorithm initializes an archive with randomly generated genomes, then repeatedly selects archive cells to produce new candidates until a termination criterion is reached.
- The archive functions as the evolutionary population, with members differentiated by the chosen feature dimensions.
- Hierarchical MAP-Elites begins with coarse cells and subdivides them during search to support coarse-to-fine exploration.
4 Differences between MAP-Elites and previous, related algorithms
MAP-Elites differs from related illumination algorithms by using a simple archive-based selection scheme that maintains the best solution independently in each feature-space cell. The paper reports stronger empirical performance than the compared alternatives while noting differences in search dynamics and computational demands.
- NS+LC and MOLE share MAP-Elites’ goal of finding high-performing solutions across feature space but are more complicated and perform worse empirically in the reported comparisons.
- Novelty Search requires nearest-neighbor calculations each generation, while MAP-Elites only looks up a cell occupant, an O(1) operation.
- MAP-Elites uses one archive rather than separate population and archive structures, avoiding the cycling associated with diversity-driven population movement.
- MAP-Elites selects from an archive and changes only cell occupancy and cell performance, making its selection pressure easier to understand than the dynamic pressures of Novelty Search.
- Unlike Novelty Search, MAP-Elites compares organisms with the current occupant of their own cell rather than nearest neighbors.
- MAP-Elites preserves fitness improvements within any cell, whereas MOLE’s global performance competition can favor a few globally strong individuals.
5 Criteria for Measuring the Algorithms
The paper evaluates algorithms using measures of global performance, reliability, precision, and coverage. These criteria distinguish finding the best solution from reliably filling feature-space cells with high-performing solutions.
- Global performance: Global performance measures the highest-performing solution found relative to the best possible or best observed performance.It is the traditional, most common evaluation measure for optimization algorithms.
- Global reliability: Global reliability averages each cell’s best found solution relative to the best known performance for that cell, assigning zero to unfilled cells.Cells never filled by any algorithm are excluded to avoid division by zero and penalizing algorithms for potentially unfillable cells.
- Global reliability: Global reliability is the most important criterion for illumination algorithms because it measures how reliably they find high-performing solutions across the map.Pure optimization algorithms are not expected to perform well on this criterion, even when they are ideal optimization methods.
- Precision: Precision measures the average relative performance only across cells an algorithm fills, capturing whether its returned solutions are high-performing where it chooses to search.This opt-in reliability criterion is expected to favor optimization algorithms that explore fewer regions but perform well within them.
- Coverage: Coverage measures the fraction of fillable feature-space cells an algorithm fills, without considering the performance of solutions in those cells.Illumination algorithms are expected to perform well on coverage, whereas ideal optimization algorithms are not.
6 Experiments and Results
Across neural-network and soft-robot domains, MAP-Elites finds diverse high-performing solutions while illuminating how performance varies across feature spaces. Its advantages include stronger overall search, broader coverage, and visible fitness patterns, although precision and experimental completeness remain qualified in some settings.
- Neural-network domain: MAP-Elites scored significantly higher than three controls on global performance, global reliability, precision, and coverage (p < 1×10−7).The controls were a traditional evolutionary algorithm, novelty search with local competition, and random sampling.
- Neural-network domain: MAP-Elites’ high-performing elites usually arise from nearby parents, while their full lineages often traverse distant regions of feature space.This combination suggests that simultaneously maintaining elites across locations supplies stepping stones for discovering solutions in new regions.
- Simulated soft robots: MAP-Elites was significantly worse at precision than two controls (p < 0.01), because it distributed evaluations across many more cells instead of concentrating them on a few.The authors hypothesize that longer runs could allow MAP-Elites to catch up to or surpass the controls in precision.
- Simulated soft robots: MAP-Elites reveals fitness potential across feature-space regions, including broad performance trends and narrow high-performing islands that traditional optimization might require many runs to detect.In soft-robot maps, increasing bone generally reduced speed at fixed body size, while one-voxel-wide designs formed an anomalous high-performance region.
- Real soft robot arm: The real-arm experiment used three actuated joints, with each solution represented by three joint-angle values.The arm connected Dynamixel AX-18 servos with compliant tubes, and an external camera tracked the endpoint.
7 Discussion and Conclusion
The paper presents MAP-Elites as a promising illumination algorithm that maps high-performing solutions across user-defined feature spaces while also performing strongly as an optimizer. Its preliminary evidence spans three domains, and the authors emphasize both diverse solution repertoires and a limitation concerning predefined feature spaces.
- MAP-Elites finds the highest-performing solution at each point in a user-defined feature space, illuminating relationships between features and performance.
- Preliminary experiments suggest MAP-Elites outperforms previous illumination algorithms, although the authors caution that its empirical performance is not yet certain.
- Feature maps reveal tradeoffs and possibilities that optimization algorithms returning a single solution do not show, while providing diverse high-performing alternatives.
- MAP-Elites significantly outperformed or matched control algorithms on the narrow objective of finding the single highest-performing solution in each run.
- MAP-Elites captures some diversity-creating force associated with natural evolution but cannot add new cell types beyond the original feature space.
- The conclusion characterizes illumination algorithms as valuable tools for learning about complex search spaces and MAP-Elites as simple, intuitive, and promising.
8 Alternate variants of MAP-Elites
The paper discusses several MAP-Elites variants intended to increase diversity, guide exploration, or combine nearby solutions. It notes that future work must determine when these variants consistently improve on the simple default algorithm.
- Future research is needed to determine whether, and for which problems, alternate MAP-Elites variants consistently outperform the simple default version.
- Variants can store multiple genomes per feature cell to promote diversity.
- Cell-selection bias can prioritize empty neighboring cells or cells near low- or high-performing areas, but preliminary experiments found no improvement over default MAP-Elites.
- Crossover may be restricted to organisms nearby in feature space so that organisms with similar competing conventions are combined.
9 Methods
The methods define reliability and coverage measures for feature maps and describe hierarchical, parallel MAP-Elites experiments across neural-network and soft-robot domains. The experiments use user-defined features, performance measures, discretized cells, and multiple evaluation budgets.
- Hierarchical MAP-Elites begins with large cells and subdivides them over time while restricting competition to solutions with similar features.
- The parallelized implementation distributes batches of evaluations across networked computers and returns performance scores and behavioral descriptors.
- The experiments include 20 replicates for retina treatments and 10 replicates for soft physical-arm treatments, except for the deterministic grid search.
- MAP-Elites evaluates candidate genomes by performance and user-chosen feature dimensions, retaining the highest-performing genome in each feature-space cell.
- The soft-robot MAP-Elites feature dimensions include percentage of bones and percentage of voxels filled.
- Global reliability compares each filled cell's performance with the best performance found for that cell across all runs and treatments, averaging over nonempty cells.
- Opt-in reliability, or precision, averages normalized performance only over cells filled by the algorithm in a given run.
- Coverage counts nonempty cells in a run relative to the theoretically fillable cells, approximated using unique cells observed across treatments.