MAP Elites - chunhualiao/public-docs GitHub Wiki

AlphaEvolve>

MAP-Elites (short for Multi-dimensional Archive of Phenotypic Elites) is a powerful evolutionary algorithm designed to explore and illuminate high-performing solutions across a diverse space of possibilities—not just find a single best solution.

It was introduced in 2015 by Mouret and Clune.

---

🎯 Core Idea of MAP-Elites

Instead of searching for the one best solution, MAP-Elites seeks to map out a diverse set of high-performing solutions across multiple dimensions of variation.

It builds a grid (archive) of "niches", where each cell represents a unique behavioral descriptor or feature combination, and stores the best solution found in each cell.

---

🧠 Key Concepts

Concept	Description
Feature dimensions	Continuous or discrete axes describing key properties of solutions (e.g. simplicity, size, symmetry)
Elite	The highest-performing solution (based on fitness) in a given feature cell
Archive	A map/grid from feature space to elite solutions
Illumination	The goal is not just to optimize, but to illuminate the space of how good solutions can be across variations

---

🔍 Example: MAP-Elites in Practice

Task: Discover good walking gaits for a robot

• Feature dimensions:

  • Speed (how fast the robot moves)
  • Stability (how much it wobbles)

• MAP-Elites maintains a grid:

  • X-axis: Speed (slow → fast)
  • Y-axis: Stability (wobbly → smooth)

• For each cell (e.g., "fast and stable"), MAP-Elites keeps the best solution found.

This gives a map of gaits:

• Some are fast but unstable
• Some are slow but highly stable
• Some are both fast and stable (rare but valuable)

You now have diverse solutions you can choose from depending on the situation.

---

🧬 MAP-Elites in AlphaEvolve

AlphaEvolve uses a MAP-Elites-inspired archive to store programs with associated evaluation metrics and behavioral characteristics.

Example: Tensor decomposition problem

• Feature dimensions (niches):

  • Discretization loss (how close are coefficients to half-integers)
  • Reconstruction loss
  • Numerical stability
  • Number of optimization steps required

• Each niche stores the best program that achieves a given combination of those descriptors.

This enables AlphaEvolve to explore multiple tradeoff regions rather than just hill-climbing toward a single best score.

---

🧠 Why MAP-Elites Matters

Benefit	Explanation
Maintains diversity	Prevents premature convergence by promoting exploration of the feature space
Encourages innovation	Finds creative outlier solutions that might be overlooked by standard optimization
Supports human insight	Scientists can explore the archive and ask: “How do different strategies perform under different constraints?”
Improves LLM prompting	AlphaEvolve uses diverse elites to construct rich prompts for LLMs, improving solution variety and quality

---

📊 Visual Example

Imagine this 2D grid of feature descriptors:

             ┌─────────┬─────────┬─────────┐
             │  Fast   │ Faster  │ Fastest │
             ├─────────┼─────────┼─────────┤
             │ Stable  │  ✨BEST  │ Unstable│
             ├─────────┼─────────┼─────────┤
             │ Wobbly  │ Moderate│ Smooth  │
             └─────────┴─────────┴─────────┘

Each cell contains the best solution seen for that behavior combo. MAP-Elites builds this map over time.

---

📚 Summary

Term	Meaning
MAP-Elites	A population-based search method that maps elites across multiple feature dimensions
Niche	A cell in feature space (e.g., "low loss and high stability")
Illumination	The goal is not just optimization, but understanding the landscape of high-quality solutions
Used in AlphaEvolve	To maintain diverse programs, guide LLM prompt generation, and encourage exploration of the solution space

---

Would you like a diagram showing how AlphaEvolve uses MAP-Elites with LLMs and the program database?