ABSTRACT
Illumination algorithms are a new class of evolutionary algorithms capable of producing large archives of diverse and high-performing solutions. Examples of such algorithms include Novelty Search with Local Competition (NSLC), the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) and the newly introduced Centroidal Voronoi Tessellation (CVT) MAP-Elites. While NSLC can be used in unbounded behavioral spaces, MAP-Elites and CVT-MAP-Elites require the user to manually specify the bounds. In this study, we introduce variants of these algorithms that expand their bounds based on the discovered solutions. In addition, we introduce a novel algorithm called "Cluster-Elites" that can adapt its bounds to non-convex spaces. We compare all algorithms in a maze navigation problem and illustrate that Cluster-Elites and the expansive variants of MAP-Elites and CVT-MAP-Elites have comparable or better performance than NSLC, MAP-Elites and CVT-MAP-Elites.
- A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret. 2015. Robots that can adapt like animals. Nature 521, 7553 (2015), 503--507.Google Scholar
- Herbert Edelsbrunner, David Kirkpatrick, and Raimund Seidel. 1983. On the shape of a set of points in the plane. IEEE Transactions on Information Theory 29, 4 (1983), 551--559. Google ScholarDigital Library
- Leonard Kauffman and Peter J. Rousseeuw. 1987. Clustering by means of Medoids. In Statistical Data Analysis Based on the L1 -Norm and Related Methods, Y. Dodge (Ed.). North-Holland, 405--416.Google Scholar
- J. Lehman and K. O. Stanley. 2008. Exploiting Open-Endedness to Solve Problems Through the Search for Novelty. In ALIFE. 329--336.Google Scholar
- J. Lehman and K. O Stanley. 2011. Abandoning objectives: Evolution through the search for novelty alone. Evol. Comp. 19 (2011), 189--223. Google ScholarDigital Library
- J. Lehman and K. O. Stanley. 2011. Evolving a Diversity of Virtual Creatures Through Novelty Search and Local Competition. In GECCO '11. ACM, 211--218. Google ScholarDigital Library
- E. Lewitus and H. Morlon. 2016. Natural constraints to species diversification. PLoS Biol 14, 8 (2016), e1002532.Google ScholarCross Ref
- J.-B. Mouret. 2011. Novelty-based multiobjectivization. In New Horizons in Evolutionary Robotics. Springer, 139--154.Google Scholar
- J.-B. Mouret and J. Clune. 2015. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015).Google Scholar
- J. K. Pugh, L. B. Soros, and K. O. Stanley. 2016. Quality Diversity: A New Frontier for Evolutionary Computation. Frontiers in Robotics and AI 3 (2016), 40.Google ScholarCross Ref
- L. Trujillo, G. Olague, E. Lutton, and F. F. De Vega. 2008. Discovering several robot behaviors through speciation. In Workshops on Applications of Evolutionary Computation. Springer, 164--174. Google ScholarDigital Library
- V. Vassiliades, K. Chatzilygeroudis, and J.-B. Mouret. 2016. Scaling Up MAP-Elites Using Centroidal Voronoi Tessellations. arXiv preprint arXiv:1610.05729 (2016).Google Scholar
Index Terms
- A comparison of illumination algorithms in unbounded spaces
Recommendations
Discovering the elite hypervolume by leveraging interspecies correlation
GECCO '18: Proceedings of the Genetic and Evolutionary Computation ConferenceEvolution has produced an astonishing diversity of species, each filling a different niche. Algorithms like MAP-Elites mimic this divergent evolutionary process to find a set of behaviorally diverse but high-performing solutions, called the elites. Our ...
Comparing multimodal optimization and illumination
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference CompanionIllumination algorithms are a recent addition to the evolutionary computation toolbox that allows the generation of many diverse and high-performing solutions in a single run. Nevertheless, traditional multimodal optimization algorithms also search for ...
An Extended Study of Quality Diversity Algorithms
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference CompanionIn a departure from conventional optimization where the goal is to find the best possible solution, a new class of evolutionary algorithms instead search for quality diversity (QD) -- a maximally diverse collection of individuals in which each member is ...
Comments