# Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm

arXiv: https://arxiv.org/abs/1610.05729 · HTML: https://mlsanity.com/paper/1610.05729/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2016.

## Built on by (most cited first, 30 of 66)

- [LLMatic: Neural Architecture Search via Large Language Models and Quality Diversity Optimization](https://mlsanity.com/paper/2306.01102/) (2023)
- [Differentiable Quality Diversity](https://mlsanity.com/paper/2106.03894/) (2021)
- [CodeEvolve: an open source evolutionary coding agent for algorithmic discovery and optimization](https://mlsanity.com/paper/2510.14150/) (2025)
- [Quality-Diversity through AI Feedback](https://mlsanity.com/paper/2310.13032/) (2023)
- [Discovering Many Diverse Solutions with Bayesian Optimization](https://mlsanity.com/paper/2210.10953/) (2022)
- [Unsupervised Behaviour Discovery with Quality-Diversity Optimisation](https://mlsanity.com/paper/2106.05648/) (2021)
- [pyribs: A Bare-Bones Python Library for Quality Diversity Optimization](https://mlsanity.com/paper/2303.00191/) (2023)
- [Evolutionary Reinforcement Learning: A Survey](https://mlsanity.com/paper/2303.04150/) (2023)
- [Covariance Matrix Adaptation MAP-Annealing](https://mlsanity.com/paper/2205.10752/) (2022)
- [Cousins Of The Vendi Score: A Family Of Similarity-Based Diversity Metrics For Science And Machine Learning](https://mlsanity.com/paper/2310.12952/) (2023)
- [GAVEL: Generating Games Via Evolution and Language Models](https://mlsanity.com/paper/2407.09388/) (2024)
- [Neuroevolution is a Competitive Alternative to Reinforcement Learning for Skill Discovery](https://mlsanity.com/paper/2210.03516/) (2022)
- [Dynamics-Aware Quality-Diversity for Efficient Learning of Skill Repertoires](https://mlsanity.com/paper/2109.08522/) (2021)
- [Proximal Policy Gradient Arborescence for Quality Diversity Reinforcement Learning](https://mlsanity.com/paper/2305.13795/) (2023)
- [Generating Behaviorally Diverse Policies with Latent Diffusion Models](https://mlsanity.com/paper/2305.18738/) (2023)
- [QDax: A Library for Quality-Diversity and Population-based Algorithms with Hardware Acceleration](https://mlsanity.com/paper/2308.03665/) (2023)
- [B2Opt: Learning to Optimize Black-box Optimization with Little Budget](https://mlsanity.com/paper/2304.11787/) (2023)
- [Diversifying AI: Towards Creative Chess with AlphaZero](https://mlsanity.com/paper/2308.09175/) (2023)
- [Accelerated Quality-Diversity through Massive Parallelism](https://mlsanity.com/paper/2202.01258/) (2022)
- [Training Diverse High-Dimensional Controllers by Scaling Covariance Matrix Adaptation MAP-Annealing](https://mlsanity.com/paper/2210.02622/) (2022)
- [Benchmarking Quality-Diversity Algorithms on Neuroevolution for Reinforcement Learning](https://mlsanity.com/paper/2211.02193/) (2022)
- [Quality Diversity through Human Feedback: Towards Open-Ended Diversity-Driven Optimization](https://mlsanity.com/paper/2310.12103/) (2023)
- [VIEW: Visual Imitation Learning with Waypoints](https://mlsanity.com/paper/2404.17906/) (2024)
- [Automatic Acquisition of a Repertoire of Diverse Grasping Trajectories through Behavior Shaping and Novelty Search](https://mlsanity.com/paper/2205.08189/) (2022)
- [Problem-solving benefits of down-sampled lexicase selection](https://mlsanity.com/paper/2106.06085/) (2021)
- [Surrogate Assisted Generation of Human-Robot Interaction Scenarios](https://mlsanity.com/paper/2304.13787/) (2023)
- [Dominated Novelty Search: Rethinking Local Competition in Quality-Diversity](https://mlsanity.com/paper/2502.00593/) (2025)
- [Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search](https://mlsanity.com/paper/2105.04247/) (2021)
- [Learning to Walk Autonomously via Reset-Free Quality-Diversity](https://mlsanity.com/paper/2204.03655/) (2022)
- [Quality Diversity Evolutionary Learning of Decision Trees](https://mlsanity.com/paper/2208.12758/) (2022)

## Abstract (arXiv)

The recently introduced Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) is an evolutionary algorithm capable of producing a large archive of diverse, high-performing solutions in a single run. It works by discretizing a continuous feature space into unique regions according to the desired discretization per dimension. While simple, this algorithm has a main drawback: it cannot scale to high-dimensional feature spaces since the number of regions increase exponentially with the number of dimensions. In this paper, we address this limitation by introducing a simple extension of MAP-Elites that has a constant, pre-defined number of regions irrespective of the dimensionality of the feature space. Our main insight is that methods from computational geometry could partition a high-dimensional space into well-spread geometric regions. In particular, our algorithm uses a centroidal Voronoi tessellation (CVT) to divide the feature space into a desired number of regions; it then places every generated individual in its closest region, replacing a less fit one if the region is already occupied. We demonstrate the effectiveness of the new "CVT-MAP-Elites" algorithm in high-dimensional feature spaces through comparisons against MAP-Elites in maze navigation and hexapod locomotion tasks.