MAP-Elites

Most optimization algorithms have one job: find the best answer. Feed them a fitness function and they race toward a single peak, discarding every solution that isn't quite good enough along the way.

MAP-Elites — short for Multi-dimensional Archive of Phenotypic Elites, introduced by Jean-Baptiste Mouret and Jeff Clune in 2015 — does something fundamentally different. Instead of converging on one solution, it asks: what is the best solution for each distinct type of behavior?

Picture a two-dimensional grid where each cell represents a different behavioral niche — say, robots that are fast-and-tall versus slow-and-short, or game-playing strategies that are aggressive-and-creative versus passive-and-predictable. MAP-Elites runs an evolutionary loop and, each time it finds a solution, places it in the grid cell that matches its behavior. If a better solution later arrives for the same cell, it replaces the old one. Over time the entire map fills up: every niche has its own champion.

The result is not one answer but a behavioral atlas — a rich landscape that reveals the best the algorithm can achieve across every corner of the space. That atlas has turned out to be extraordinarily useful in robotics, game design, materials discovery, and beyond.

Each cell in the grid below represents a unique behavioral niche defined by two features: speed (columns) and robustness (rows). A cell's color shows the fitness of the best solution found so far for that niche — darker means higher fitness. Empty cells are niches that haven't been filled yet.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="iter-label">{{label_iter}} <span id="iter-count">0</span></span>
</div>
<div id="map-grid" class="map-grid" aria-label="{{grid_aria}}"></div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.iter-label { font-size: .85rem; color: #555; margin-left: .2rem; }
.map-grid { display: grid; gap: 3px; margin-bottom: .5rem; }
.cell { width: 100%; aspect-ratio: 1; border-radius: 5px; border: 1px solid #c8d3dc;
        display: flex; align-items: center; justify-content: center;
        font: 600 10px ui-monospace, monospace; color: #fff; transition: background .25s; }
.cell.empty { background: #e8eef3; border-color: #c8d3dc; }
.cell.filled { border-color: transparent; }
.cell.new { outline: 2px solid #f4a261; outline-offset: 1px; }
.row-label, .col-label { font-size: .7rem; color: #666; text-align: center; }
.axis-row { display: flex; align-items: center; gap: 3px; }
.axis-label-y { font-size: .7rem; color: #555; writing-mode: vertical-rl;
                transform: rotate(180deg); text-align: center; margin-right: 2px; }
.axis-label-x { font-size: .7rem; color: #555; text-align: center; margin-top: 2px; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }

// Code not found

Click Step to run one iteration: MAP-Elites mutates a random existing elite (or generates one from scratch) and places it in the matching niche if it beats the current occupant. Click Run to animate the process and watch the map fill. Notice how the algorithm builds a diverse archive rather than piling up near a single peak — it is simultaneously discovering and optimizing across the whole space.

MAP-Elites belongs to the family of quality-diversity (QD) algorithms — methods that explicitly reward both how good a solution is and how different it is from everything else found so far.

The core loop is deceptively simple:

1. Initialize — generate a random population and place each individual in the map cell that matches its behavioral descriptor (a vector of measurable features).
2. Select — pick a random elite from the archive.
3. Vary — apply mutation or crossover to produce an offspring.
4. Evaluate — measure the offspring's fitness and compute its behavioral descriptor.
5. Update — if the offspring's cell is empty, or if it beats the current occupant, place it there. Otherwise discard it.
6. Repeat — go to step 2.

The map has $G = g_1 \times g_2 \times \cdots \times g_k$ cells for $k$ behavioral dimensions each discretized into $g_i$ bins. Filling the map requires at least $G$ evaluations, but in practice many more: each cell's niche may be hard to stumble into by mutation alone, and the algorithm has no explicit plan for which niches to target next.

No convergence guarantee. Unlike gradient descent, MAP-Elites makes no promise about finding the global optimum in any cell. Its strength is breadth: by the time it terminates it has found something for every reachable niche, even if each individual solution is only locally good.

The illumination metric — coverage (fraction of cells filled) and QD-score (sum of fitnesses across all filled cells) — measures progress, but optimizing these metrics is itself an open research problem. Recent variants like CVT-MAP-Elites, CMA-ME, and DQD (differentiable quality diversity) push the frontier by using smarter variation operators and gradient information.

The key insight of MAP-Elites — keep the best of every type, not just the best overall — turns out to apply almost everywhere:

• Legged robotics: the original 2015 paper used MAP-Elites to pre-compute a behavioral repertoire of walking gaits for a six-legged robot. When a leg broke at runtime, the robot queried the archive for the best gait given its current capability — recovering in seconds instead of minutes of re-optimization.
• Video-game content generation: MAP-Elites can fill a grid of level archetypes (easy-and-long vs. hard-and-short, etc.) giving designers a browsable palette rather than a single "best" level.
• Materials and drug discovery: descriptor dimensions might encode physical properties (conductivity, solubility), and every filled cell is a candidate material or molecule that is locally optimal for that profile.
• Neural architecture search: behavioral dimensions describe inference-speed vs. accuracy trade-offs; the map gives engineers a Pareto-like frontier automatically.
• Illuminating evolutionary algorithms: MAP-Elites is often used as a diagnostic tool — what solutions are possible across the space, and where does evolution struggle to reach?

Wherever you need not just one answer but a catalogue of diverse, high-quality alternatives, MAP-Elites is the algorithm to reach for.

Most optimization tells you what the best answer is. MAP-Elites tells you what the best answer is for every kind of situation — and that distinction matters enormously when the real world doesn't hand you a fixed context.

By maintaining an archive of elites across behavioral dimensions, the algorithm trades the narrow guarantee of convergence for something richer: a behavioral atlas that simultaneously optimizes and explores. The map it produces isn't just a bag of solutions — it is a structured window into what is possible, and where the limits lie.

The next time you see a system that needs not one strategy but a whole repertoire — a robot that adapts when a limb fails, a game that generates varied levels, a lab that screens molecules across many property profiles — you are looking at a problem that MAP-Elites was born to solve.