Multi-Emitter MAP-Elites: Improving quality, diversity and convergence
speed with heterogeneous sets of emitters
speed with heterogeneous sets of emitters
File(s)
Accepted version
Author(s)
Cully, Antoine
Type
Conference Paper
Abstract
Quality-Diversity (QD) optimisation is a new family of learning algorithms
that aims at generating collections of diverse and high-performing solutions.
Among those algorithms, MAP-Elites is a simple yet powerful approach that has
shown promising results in numerous applications. In this paper, we introduce a
novel algorithm named Multi-Emitter MAP-Elites (ME-MAP-Elites) that improves
the quality, diversity and convergence speed of MAP-Elites. It is based on the
recently introduced concept of emitters, which are used to drive the
algorithm's exploration according to predefined heuristics. ME-MAP-Elites
leverages the diversity of a heterogeneous set of emitters, in which each
emitter type is designed to improve differently the optimisation process.
Moreover, a bandit algorithm is used to dynamically find the best emitter set
depending on the current situation. We evaluate the performance of
ME-MAP-Elites on six tasks, ranging from standard optimisation problems (in 100
dimensions) to complex locomotion tasks in robotics. Our comparisons against
MAP-Elites and existing approaches using emitters show that ME-MAP-Elites is
faster at providing collections of solutions that are significantly more
diverse and higher performing. Moreover, in the rare cases where no fruitful
synergy can be found between the different emitters, ME-MAP-Elites is
equivalent to the best of the compared algorithms.
that aims at generating collections of diverse and high-performing solutions.
Among those algorithms, MAP-Elites is a simple yet powerful approach that has
shown promising results in numerous applications. In this paper, we introduce a
novel algorithm named Multi-Emitter MAP-Elites (ME-MAP-Elites) that improves
the quality, diversity and convergence speed of MAP-Elites. It is based on the
recently introduced concept of emitters, which are used to drive the
algorithm's exploration according to predefined heuristics. ME-MAP-Elites
leverages the diversity of a heterogeneous set of emitters, in which each
emitter type is designed to improve differently the optimisation process.
Moreover, a bandit algorithm is used to dynamically find the best emitter set
depending on the current situation. We evaluate the performance of
ME-MAP-Elites on six tasks, ranging from standard optimisation problems (in 100
dimensions) to complex locomotion tasks in robotics. Our comparisons against
MAP-Elites and existing approaches using emitters show that ME-MAP-Elites is
faster at providing collections of solutions that are significantly more
diverse and higher performing. Moreover, in the rare cases where no fruitful
synergy can be found between the different emitters, ME-MAP-Elites is
equivalent to the best of the compared algorithms.
Date Issued
2021-06-26
Date Acceptance
2021-04-25
Citation
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp.84-92
ISBN
9781450383509
Publisher
ACM
Start Page
84
End Page
92
Journal / Book Title
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference
Copyright Statement
© 2021 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, (26 Jun 2021) https://dl.acm.org/doi/10.1145/3449639.3459326
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Identifier
http://arxiv.org/abs/2007.05352v1
Grant Number
EP/V006673/1
Source
Genetic and Evolutionary Computation Conference (GECCO)
Subjects
cs.NE
cs.NE
Publication Status
Published
Start Date
2021-07-10
Finish Date
2021-07-14
Coverage Spatial
Lille, France
Date Publish Online
2021-06-26