Using Centroidal Voronoi Tessellations to Scale Up the Multidimensional Archive of Phenotypic Elites Algorithm
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
The recently introduced multidimensional 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, predefined 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836
Completely Derandomized Self-Adaptation in Evolution Strategies
Hansen, N., & Ostermeier, A. (2001) · Evolutionary Computation · doi:10.1162/106365601750190398 · Cited by 4,397
Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images
Nguyen, A., Yosinski, J., & Clune, J. (2014) · arXiv · doi:10.48550/arxiv.1412.1897 · Cited by 3,258
Deep neural networks are easily fooled: High confidence predictions for unrecognizable images
Nguyen, A., Yosinski, J., & Clune, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298640 · Cited by 3,258
Scaling laws predict global microbial diversity
Locey, K. J., & Lennon, J. T. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1521291113 · Cited by 1,184
Robots that can adapt like animals
Cully, A., Clune, J., Tarapore, D., & Mouret, J.-B. (2015) · Nature · doi:10.1038/nature14422 · Cited by 979 · cited 5×
“For instance, it has been used to produce: behavioral repertoires that enable robots to adapt to damage in a matter of minutes [25], [26], perform complex tasks [27], or even adapt to damage while completing their”
BackgroundMethodInfluentialSelf-citationQuality Diversity: A New Frontier for Evolutionary Computation
Pugh, J. K., Soros, L. B., & Stanley, K. O. (2016) · Frontiers in Robotics and AI · doi:10.3389/frobt.2016.00040 · Cited by 514 · cited 7×
“For this reason they are called illumination algorithms [6] or quality diversity (QD) algorithms [7], [8].”
BackgroundMethodInfluentialQuality and Diversity Optimization: A Unifying Modular Framework
Cully, A., & Demiris, Y. (2018) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2017.2704781 · Cited by 258
A formal test of the theory of universal common ancestry
Theobald, D. L. (2010) · Nature · doi:10.1038/nature09014 · Cited by 231 · cited 1×
“Evolution started from a common ancestor [1] and gave rise to the biodiversity we see today, which is estimated to amount to 1 trillion species [2].”
Background
Cited by
Quality and Diversity Optimization: A Unifying Modular Framework
Cully, A., & Demiris, Y. (2018) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2017.2704781 · Cited by 258
A Survey on Policy Search Algorithms for Learning Robot Controllers in a Handful of Trials
Chatzilygeroudis, K., Vassiliades, V., Stulp, F., Calinon, S., & Mouret, J.-B. (2020) · IEEE Transactions on Robotics · doi:10.1109/tro.2019.2958211 · Cited by 160
Self-citationLLMatic: Neural Architecture Search Via Large Language Models And Quality Diversity Optimization
Nasir, M. U., Earle, S., Togelius, J., James, S., & Cleghorn, C. (2024) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3638529.3654017 · Cited by 52
“Mutate the temperature for the next generation .”
BackgroundThe OpenELM Library: Leveraging Progress in Language Models for Novel Evolutionary Algorithms
Bradley, H., Fan, H., Galanos, T., Zhou, R., Scott, D., & Lehman, J. (2024) · Genetic and Evolutionary Computation · doi:10.1007/978-981-99-8413-8_10 · Cited by 19
Metadata
- Authors
- Vassiliades, V., Chatzilygeroudis, K., & Mouret, J.-B.
- Venue
- IEEE Transactions on Evolutionary Computation
- Published
- 2018-08
- Volume
- 22
- Issue
- 4
- Pages
- 623-630
- ISSN
- 1089-778X (ISSN-L)
- 1941-0026
- OpenAlex
- W2739858255
- Cited by
- 151
- References
- 9
- FWCI
- 6.89
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Using Centroidal Voronoi Tessellations to Scale Up the Multidimensional Archive of Phenotypic Elites Algorithm. https://app.cochat.ai/papers/10.1109/tevc.2017.2735550
- The paper
- Vassiliades, V., Chatzilygeroudis, K., & Mouret, J.-B. (2018). Using Centroidal Voronoi Tessellations to Scale Up the Multidimensional Archive of Phenotypic Elites Algorithm. IEEE Transactions on Evolutionary Computation. https://doi.org/10.1109/tevc.2017.2735550
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.