MAP-Elites

From WFM Labs


A MAP-Elites archive over two staffing behavior descriptors (part-time share and surge-reserve depth). Each cell keeps the highest-fitness elite plan for that niche, with colour showing fitness. A conventional optimizer returns only the single starred cell; the archive also retains robust, reserve-heavy plans (circled) that a single-objective search discards, and leaves infeasible niches empty.

MAP-Elites (Multi-dimensional Archive of Phenotypic Elites) is an optimization algorithm that returns not a single best solution but an archive of high-performing solutions spread across a user-defined space of solution types. It belongs to a family of methods called quality-diversity (QD), and its inventors describe it as an illumination algorithm: rather than converging on one winner, it "illuminates" the fitness potential of every region of a chosen feature space, revealing the best achievable solution of each kind together with the trade-off structure between performance and features of interest.[1] The algorithm was introduced by Jean-Baptiste Mouret and Jeff Clune in 2015 and became widely known through a companion application, published in Nature, in which a legged robot used a MAP-Elites-generated repertoire of behaviors to recover from damage.[2]

MAP-Elites is of interest to workforce management and contact center planning because it reframes the central staffing question. Conventional planning answers "how many people do we need?" with a single number optimized against a forecast; illumination instead produces a portfolio of qualitatively different high-performing plans across dimensions such as cost, service level, and resilience to demand shocks. This makes it a candidate tool for building a precomputed contingency repertoire — a shelf of good plans held ready for the days a forecast breaks — an application developed in detail by Ted Lango's WFM Labs research on staffing under volatility.[3]

Background: from optimization to illumination

Conventional optimization seeks a single point: the solution that maximizes an objective function, or in the multi-objective case the Pareto set of non-dominated trade-offs.[1] This is powerful when the goal is genuinely to find one best answer, but it is silent about the interior of the search space — any solution that is dominated on the chosen objectives is, by construction, discarded even if it is decisive under conditions the objectives do not capture.

Illumination algorithms take a different stance, with intellectual roots in novelty search, introduced by Joel Lehman and Kenneth Stanley, which showed that in deceptive problems abandoning the objective and rewarding behavioral novelty alone could outperform objective-driven search.[4] Quality-diversity methods combine that drive for diversity with a drive for quality: they aim to fill a space of possibilities with the best possible example of each type of achievable behavior.[5] MAP-Elites is the most widely used QD algorithm, alongside Novelty Search with Local Competition.[5]

Core mechanism

MAP-Elites operates on two functions defined over candidate solutions:

  • A fitness (or performance) function f(x), a single score used to rank solutions. Because "good" is often several competing things at once, fitness typically involves scalarization of multiple objectives.
  • A feature descriptor (also called a behavioral or phenotypic descriptor) b(x), which measures not how good a solution is but what kind of solution it is. In the robotics example, descriptors might be a robot's height and weight, or the fraction of time each leg spends on the ground.[1][2]

The descriptor space is discretized into a grid of cells (also called niches). Each cell retains only the single highest-fitness solution — the "elite" — whose descriptor falls within it; this map of elites gives the algorithm its name.[1] The basic loop is:

  1. Initialize by generating a batch of random solutions, evaluating each to obtain its fitness and descriptor, and placing it in the corresponding cell (keeping the higher-fitness solution when two land in the same cell).
  2. Iterate: select an occupied cell at random, produce a variant of its elite by random mutation (and optionally crossover), evaluate the variant, and place it in the cell named by its descriptor — but only if that cell is empty or the variant beats the incumbent elite.
  3. Repeat until an evaluation budget or coverage threshold is reached, then return the filled archive.[1]

Because a strong solution bred for one cell often seeds an even better solution in a neighboring cell, MAP-Elites shares information across niches in a way that independent per-cell optimization does not.[1][3] The result is an archive that simultaneously contains a diverse repertoire and, as its single highest-fitness occupant, the global optimum a conventional optimizer would have returned. Illumination is therefore in this sense a superset of optimization: the map is obtained "for free" relative to the single-best-plan objective.[1][3]

Empty cells are informative in their own right. A region that no solution can fill while satisfying the problem's constraints marks the boundary of what is feasible, rather than a failure of the search.[1][3]

Relationship to quality-diversity and novelty search

MAP-Elites is one instantiation of the broader quality-diversity paradigm, which Pugh, Soros and Stanley framed as a distinct goal for evolutionary computation: producing a large collection of solutions that are each high-performing and collectively diverse, rather than a single optimum.[5] The two canonical QD algorithms are MAP-Elites, which imposes diversity through a fixed grid of descriptor cells, and Novelty Search with Local Competition, which grows an unstructured archive by rewarding solutions that are both novel and locally superior.[5][4] The distinguishing modelling choice in MAP-Elites is the hand-selected descriptor space: the archive will faithfully diversify along whatever dimensions the designer names, which is both the method's leverage and its principal hazard (see Limitations).

Modern QD research has extended the basic algorithm substantially. CMA-ME (Covariance Matrix Adaptation MAP-Elites) replaces random mutation with the self-adaptation machinery of CMA-ES, substantially improving performance on continuous problems,[6] and is implemented in the open-source pyribs library, which provides a modular framework for MAP-Elites-style QD optimization.[7] Other variants include CVT-MAP-Elites, which uses a centroidal Voronoi tessellation to scale the archive to high-dimensional descriptor spaces, and methods that learn descriptors from data rather than fixing them by hand.[8]

Applications

Robotics and adaptive control

The best-known application is damage recovery in robotics. Cully and colleagues had a six-legged robot use MAP-Elites offline to discover a repertoire of thousands of distinct gaits — the highest-performing exemplar of each behavioral type — before any damage occurred. When a leg was subsequently disabled, the robot did not re-optimize from scratch; it searched the precomputed archive for gaits that did not rely on the failed component and recovered functional locomotion in about two minutes.[2] The lesson generalizes beyond robots: damage tolerance was obtained by having already explored the space of behaviors and retained the best of each kind, so that a violated assumption was met by selection from a trusted set rather than reconstruction under duress.[2][3]

Design, engineering and machine learning

Because illumination exposes the trade-off structure of a design space, MAP-Elites and its QD relatives have been applied to generative design and engineering (mapping high-performing designs across features such as size, weight, or aesthetic descriptors), to reinforcement learning (discovering diverse policies rather than a single one), to procedural content generation in games, and to hyperparameter optimization and automated machine learning. It has also been applied to scheduling problems: a MAP-Elites-based hyper-heuristic has been studied for the resource-constrained project scheduling problem,[9] and QD has been used in financial portfolio optimization, where an archive of near-optimal portfolios is argued to be more robust than a single estimate-sensitive mean–variance optimum.[10]

Workforce management and contact-center capacity planning

The application most relevant to this wiki is workforce capacity planning and scheduling. MAP-Elites was first applied to a real workforce problem by Urquhart and Hart, who used it to both optimize and illuminate a workforce scheduling-and-routing application, producing not one schedule but a repertoire of competitive schedules that maximized planner choice across behavioral dimensions.[11]

Ted Lango's WFM Labs research extends this idea specifically to inbound contact center staffing under volatility, and supplies the connective framing for why illumination matters to workforce management.[3] The central argument is that a staffing plan was never a headcount but a portfolio — the mix of full-time, part-time, seasonal, in-house, outsourced and on-call capacity — and that under demand volatility there is no single best portfolio but a landscape of them. Conventional planning sizes one plan against a forecast of the expected day; but a plan optimized for the mean is by construction a bet on the average, whose error concentrates precisely on the off-schedule surges — what aviation calls irregular operations (IROPS) and what telecom and insurance operators experience as outage- and catastrophe-driven spikes — that the mean does not represent.[3][12] This connects directly to the Flaw of Averages: optimizing for a single expected scenario systematically selects plans that fail when the realized scenario differs.

In Lango's formulation the two feature descriptors are structural levers a planner can actually set — the part-time share of the workforce (the elasticity lever) and the depth of a held surge reserve (contingent, on-call capacity). Each candidate plan is scored by an Erlang C queueing evaluator on both an ordinary day and a parametric IROPS surge day, subject to hard service level floors, and fitness is combined across the competing KPIs of calm-day service, surge-day service, and cost using Chebyshev (achievement) scalarization rather than a naive weighted sum, so that balanced plans in concave regions of the trade-off are not skipped over.[3] The resulting archive is offered as a precomputed contingency repertoire with three practical payoffs:[3]

  • Robust plans an optimizer discards. The archive surfaces heavily part-time, well-reserved operating models that look expensive on a calm day — and are therefore dominated in a forecast-driven Pareto search — yet are the ones still meeting service targets during a surge.
  • The boundary of the feasible. Cells that no plan can fill while clearing the storm-service floor draw an explicit map of what the operation can and cannot promise on its worst day; as leadership raises the minimum acceptable storm-day service, the feasible region visibly shrinks.
  • An ownable leadership choice. The map turns the committed-versus-contingent question into a visible decision. Committed flex (scheduled part-time) is paid for every day; contingent flex (an on-call reserve or overflow partner) costs a retainer to keep ready and the full rate only when called in. Which is cheaper depends on how often disruption strikes, and Lango reports a frequency crossover — a "rent versus buy" tipping point — between the two.[3]

Lango positions illumination as complementary to, not a replacement for, the linear programming-plus-simulation methods used in call center staffing:[3] the incumbent solver can serve as the in-cell optimizer that finds the best plan for each descriptor cell, while MAP-Elites maps the space of operating-model types. He frames it as a "Level 4" technique in a WFM maturity progression — mapping the whole space of staffing lines and showing which survive a shock — building on his earlier arguments for bringing operations research and stochastic/Monte-Carlo methods into workforce planning.[3] A stochastic demand model scored by conditional value-at-risk (CVaR) on the surge-day service tail is described in that work as future development beyond the initial deterministic design.[3]

A separate methodological proposal in the same work concerns the division of labor between large language models and deterministic computation: an LLM is well suited to the variation operator (cheaply proposing a large, varied supply of candidate plans) but not to producing the answer directly, while selection is reserved for an inspectable, reproducible simulation. This "generator proposes, deterministic engine decides" split is presented as Lango's own framing rather than an established result of the QD literature.[3]

Strengths

  • Diversity and choice. A single run yields many qualitatively different high-performing solutions, giving a decision-maker a repertoire rather than a dictated answer.[1][11]
  • Illumination of trade-off structure. The archive maps how performance varies across the chosen features, including the feasible/infeasible boundary, information a single optimum cannot convey.[1][3]
  • Robustness and adaptation. Holding a precomputed repertoire allows fast recovery when assumptions break, without re-optimizing from scratch.[2]
  • No cost to the best-plan objective. The global optimum remains recoverable as the highest-fitness cell, so mapping the space does not sacrifice single-solution quality.[1]

Limitations

  • Choice of descriptors. The archive only diversifies along the descriptors the designer names; poorly chosen, superficial descriptors illuminate cosmetic rather than meaningful variety. This hazard motivates research on learning descriptors from data instead of fixing them by hand.[8]
  • Curse of dimensionality. A finely gridded descriptor space grows exponentially in the number of feature dimensions, so basic MAP-Elites is typically limited to a small number of descriptors; scalable variants such as CVT-MAP-Elites and CMA-ME address this partially.[6][8]
  • Discretization choices. Grid resolution trades archive richness against the evaluation budget and the reliability of each cell's elite.
  • Computational cost. Filling an archive requires many more evaluations than finding a single optimum, which matters when each evaluation is an expensive simulation.[1]
  • Inherited model assumptions. In applied settings the archive is only as trustworthy as the simulator that scores it; illumination inherits every assumption of the underlying model.[3]

See also

References

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 Mouret, J.-B., Clune, J. (2015). "Illuminating search spaces by mapping elites". arXiv:1504.04909 [cs.AI].
  2. ↑ 2.0 2.1 2.2 2.3 2.4 Cully, A., Clune, J., Tarapore, D., Mouret, J.-B. (2015). "Robots that can adapt like animals". Nature 521 (7553), 503–507. doi:10.1038/nature14422.
  3. ↑ 3.00 3.01 3.02 3.03 3.04 3.05 3.06 3.07 3.08 3.09 3.10 3.11 3.12 3.13 3.14 3.15 Lango, T. (2026). "When the Plan Breaks: Illuminating Staffing with MAP-Elites". WFM Labs Applied Research. community.wfmlabs.org. Retrieved 2026-07-11.
  4. ↑ 4.0 4.1 Lehman, J., Stanley, K. O. (2011). "Abandoning Objectives: Evolution Through the Search for Novelty Alone". Evolutionary Computation 19 (2), 189–223. doi:10.1162/EVCO_a_00025.
  5. ↑ 5.0 5.1 5.2 5.3 Pugh, J. K., Soros, L. B., Stanley, K. O. (2016). "Quality Diversity: A New Frontier for Evolutionary Computation". Frontiers in Robotics and AI 3, 40. doi:10.3389/frobt.2016.00040.
  6. ↑ 6.0 6.1 Fontaine, M. C., Togelius, J., Nikolaidis, S., Hoover, A. K. (2020). "Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space". Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO), 94–102. doi:10.1145/3377930.3390232. arXiv:1912.02400.
  7. ↑ Tjanaka, B., Fontaine, M. C., Nikolaidis, S., et al. (2023). "pyribs: A Bare-Bones Python Library for Quality Diversity Optimization". Proceedings of the 2023 Genetic and Evolutionary Computation Conference (GECCO). doi:10.1145/3583131.3590374.
  8. ↑ 8.0 8.1 8.2 Grillotti, L., Cully, A. (2022). "Unsupervised Behaviour Discovery with Quality-Diversity Optimisation". IEEE Transactions on Evolutionary Computation 26 (6), 1539–1552. doi:10.1109/TEVC.2022.3159855.
  9. ↑ Chand, S., Rajesh, K., Chandra, R. (2022). "MAP-Elites based Hyper-Heuristic for the Resource Constrained Project Scheduling Problem". arXiv:2204.11162 [cs.NE].
  10. ↑ Gašperov, B., Đurasević, M., Jakobović, D. (2024). "Finding Near-Optimal Portfolios with Quality-Diversity". Applications of Evolutionary Computation – EvoApplications 2024. doi:10.1007/978-3-031-56852-7_1. arXiv:2402.16118.
  11. ↑ 11.0 11.1 Urquhart, N., Hart, E. (2018). "Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application (WSRP) via Map-Elites". Parallel Problem Solving from Nature – PPSN XV, 488–499. doi:10.1007/978-3-319-99253-2_39. arXiv:1805.11555.
  12. ↑ Savage, Sam L. (2009). The Flaw of Averages: Why We Underestimate Risk in the Face of Uncertainty. Hoboken, NJ: John Wiley & Sons. ISBN 978-0-471-38197-6.
Retrieved from "https://wiki.wfmlabs.org/w/index.php?title=MAP-Elites&oldid=3599"