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

Vassilis Vassiliades 1 Konstantinos Chatzilygeroudis 1 Jean-Baptiste Mouret 1
1 LARSEN - Lifelong Autonomy and interaction skills for Robots in a Sensing ENvironment
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : 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.
Type de document :
Article dans une revue
IEEE Transactions on Evolutionary Computation, Institute of Electrical and Electronics Engineers, 2017, pp.9. 〈http://ieeexplore.ieee.org/abstract/document/8000667/〉. 〈10.1109/TEVC.2017.2735550〉
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01630627
Contributeur : Jean-Baptiste Mouret <>
Soumis le : mardi 7 novembre 2017 - 20:13:52
Dernière modification le : jeudi 11 janvier 2018 - 06:27:29

Fichier

ieee_tec_voronoi_map_elites.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vassilis Vassiliades, Konstantinos Chatzilygeroudis, Jean-Baptiste Mouret. Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm. IEEE Transactions on Evolutionary Computation, Institute of Electrical and Electronics Engineers, 2017, pp.9. 〈http://ieeexplore.ieee.org/abstract/document/8000667/〉. 〈10.1109/TEVC.2017.2735550〉. 〈hal-01630627〉

Partager

Métriques

Consultations de la notice

43

Téléchargements de fichiers

12