Multi-objective Analysis of MAP-Elites Performance
Eivind Samuelsen

Kyrre Glette

University of Oslo
Department of Informatics
Postboks 1080, Blindern
0316, Oslo, Norway
eivinsam@ifi.uio.no

University of Oslo
Department of Informatics
Postboks 1080, Blindern
0316, Oslo, Norway
kyrrehg@ifi.uio.no

arXiv:1803.05174v1 [] 14 Mar 2018

ABSTRACT
In certain complex optimization tasks, it becomes necessary to
use multiple measures to characterize the performance of different
algorithms. This paper presents a method that combines ordinal
effect sizes with Pareto dominance to analyze such cases. Since
the method is ordinal, it can also generalize across different optimization tasks even when the performance measurements are
differently scaled. Through a case study, we show that this method
can discover and quantify relations that would be difficult to deduce
using a conventional measure-by-measure analysis. This case study
applies the method to the evolution of robot controller repertoires
using the MAP-Elites algorithm. Here, we analyze the search performance across a large set of parametrizations; varying mutation
size and operator type, as well as map resolution, across four different robot morphologies. We show that the average magnitude
of mutations has a bigger effect on outcomes than their precise
distributions.

CCS CONCEPTS
•Computing methodologies → Search methodologies; Evolutionary robotics; •Mathematics of computing → Nonparametric statistics; •General and reference → Performance;

KEYWORDS
Quality Diversity, MAP-Elites, Multi-objective Analysis
ACM Reference format:
Eivind Samuelsen and Kyrre Glette. 2018. Multi-objective Analysis of
MAP-Elites Performance. In Proceedings of the Genetic and Evolutionary
Computation Conference 2018, Kyoto, Japan, July 15–19, 2018 (GECCO ’18),
8 pages.
DOI: 10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

Search algorithms can be applied to a multitude of tasks in engineering, science and other fields, from scheduling and optimization
tasks to design and creativity [8, 15]. While in some straightforward
cases it is sufficient for the search to end up with the single best
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or a
fee. Request permissions from permissions@acm.org.
GECCO ’18, Kyoto, Japan
© 2018 ACM. 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
DOI: 10.1145/nnnnnnn.nnnnnnn

solution, or a set of nondominated solutions in the case of a multiobjective optimization task, it would in some cases be an advantage
to be able to investigate a range of different and high-performing
solutions from the same search process.
In this context, algorithms like Novelty Search [9] and MAPElites [11] have been proposed, which explore and keep track of
solutions that are high-performing but different according to a
behavior criterion. These algorithms, named Quality Diversity
(QD) or Illumination algorithms, have been successfully applied
to e.g. avoiding deception and promoting diversity in hard search
domains [10], for the generation of a large set of qualitatively different artworks [13], or for exploring the design space of airfoils [7]. It
should be noted that the explorative nature of these algorithms can
have a dual purpose–either solely as a diversity-enhancing functionality, serving as stepping stones for the algorithm to overcome
deceptive search spaces [10]–or also for inspecting or exploiting
the generated repertoire of solutions [11].
These QD algorithms have been particularly successful in the
Evolutionary Robotics (ER) field [5], with applications such as soft
robot evolution [11], damage recovery [2], and locomotion repertoire generation [4, 6]. Recently, Pugh et al. [14] compared the
performances of a range of QD variants, and Cully and Demiris [3]
proposed a unifying framework for QD.
Among the QD algorithms, MAP-Elites [11] has the property
of concentrating the search in a space of user-defined features, or
behaviors, discretized into a grid. As the algorithm progresses, the
cells in this grid are progressively filled with solutions according
to their position in the behavior space, and solutions are replaced
with better fit ones within the same cell. This property stands out
as particularly attractive for some applications, since the result of
the search is a regular grid and one can easily locate a cell with a
desired behavior, e.g. for use in locomotion repertoire generation
tasks [6].
MAP-Elites gives room for multiple algorithm performance measures – one would like to know how much of the defined behavior
space is covered (i.e.,diversity), as well as how good these behaviors
are (i.e., quality). These aspects are covered in [11] by the coverage
and precision measures, respectively. However, for many applications, like e.g. repertoire generation for locomotion primitives, one
would be interested in not only many diverse solutions, but also
high-performing ones. One way to to capture this property would
be by summing the fitnesses of all solutions found, and the global
reliability measure from [11], as well as the QD-score measure [14]
are based on this.
These approaches are based on the combination of the diversity and quality measures into one measure, however, we propose

GECCO ’18, July 15–19, 2018, Kyoto, Japan
to consider the dual dimensionality explicitly through a paretobased analysis method. In multi-objective optimization, it is known
that any way of combining multiple objective functions into one
gives challenges related to scaling and potential loss of solutions,
compared to a pareto-based treatment [8]. The same concept also
applies when comparing algorithms on multiple performance measures, and so it is natural to attempt a Pareto-based analysis in this
case.
In order to use Pareto dominance, it is natural to consider ordinal
statistics: statistics that compare ordering instead of the values
directly [1]. From another perspective, Neumann et al. [12] also
suggested that Pareto dominance could be promising to incorporate
into the Vargha-Delaney effect size. Using ordinal statistics also
enables us to generalize across groups that naturally have different
scaling or distributions of the performance measures. In our case,
this approach allows us to generalize the effect of mutation sizes
across different robot morphologies.
We have earlier co-evolved robot morphologies and controllers,
and produced real-world instances of these [16, 17]. To fully make
use of a new morphology, it would be relevant to learn a repertoire
of walking behaviors, such as being able to move forwards and
backwards and turn with different speeds, much in the same vein
as [4] and [6]. Therefore, as a case study for our proposed method
we employ MAP-Elites to generate controller repertoires for a set
of selected robot morphologies. In this setting, it is relevant to find
good parameter performance across different morphologies, and
we thus include four morphologies in the study.
While this study considers simulation-only experiments, we
envisage a future scenario where the robots apply this repertoire
generation as a real-world learning phase, to properly account for
the real-world dynamics. As such, it would be relevant to keep the
repertoire map small, to be able to build the map with a relatively
low number of evaluations, and we include the map size as another
parameter in the study.
Another aspect that could have a significant impact on the performance of the evolutionary search, is the choice of variation
operators. We observe that for the mutation operator, several studies in ER consider a certain probability for each variable of the
solution to be subject to a Gaussian perturbation, while other studies apply a perturbation to all variables. While both approaches
seem intuitive at a first glance, the distributions of magnitudes of
these schemes differ, and we seek to understand how this affects
the performance of our search. We also introduce two variants the
above-mentioned schemes, which result in a smoother distribution,
and include all four variants in our study.
Further, the mutation size, i.e. the sigma value of the Gaussian
distribution, is a parameter typically subject to tuning, but which
in the case of MAP-Elites is more time-consuming as the algorithm
requires a larger number of evaluations than a typical evolutionary
algorithm to finish. Still, we choose to add a range of sigma values
to our case study to shed light on possible performance trade-offs.
The results from our experimental runs are reported in effect size
tables, allowing for statistical comparisons, as well as visualizing
them in bag plots, giving a good overview of the multi-objective
performance aspects. We also visualize an excerpt of the results in
a measure-by-measure fashion, to illustrate the difference between
the approaches.

Eivind Samuelsen and Kyrre Glette
Table 1: Experiment setup
PhysX version
Ground-robot friction
Timestep
Control system period
Pre-evaluation periods
Evaluation periods
Samples per period
Behavior features
Performance measure

Initial population
Initial mutation
Initial σ
Total evaluations per run
Map resolutions
σ values
Mutation types
Robots

robot2
robot3
robot4
robot5

Total combinations
Runs per combination

3.4
0.3 / 0.3
128−1 s
1s
1
4
4
- Turn rate
- Adjusted forward speed
Weighed penalties for
- Large body pitch
- Low body height
- Sideways movement
100
all-hard
0.5
20000
5 × 5, 7 × 7, 9 × 9
0.01, 0.1, 0.2, 0.4, 0.8
all-hard, some-hard,
all-soft, some-soft
4 legs, 6 joints
4 legs, 9 joints
4 legs, 10 joints
6 legs, 14 joints
240
12

To summarize, this paper makes two major contributions: First,
we demonstrate how we can apply a Pareto dominance based
Cliff’s delta calculation for comparing performances of MAP-Elites
searches, and how to visualize the differences in performance with
bag plots. Secondly, we demonstrate the usefulness of these methods with a case study in evolutionary robotics, with a particular
focus on different mutation schemes and how these affect performance.

2

METHODS

We have implemented the MAP-Elites algorithm as described in [11]
to find repertoires of robot gaits that effect useful behaviors. We
then analyze the effect of different map resolutions, mutation operators and mutation sizes on the quality of the repertoires for four
different robots. The robots and the simulator are described in
subsection 2.1. The gait behavior and performance measures are
defined in subsection 2.3. The mutation operators are described in
subsection 2.4. The measures used to judge repertoire quality is
defined in subsection 2.5. Finally, the methods used to analyze the
results are presented in subsections 2.6 and 2.7. A summary of key
details is shown in Table 1. The experiment data and R source code
for the analysis is available online.1

1 (link

made available after review)

Multi-objective Analysis of MAP-Elites Performance

GECCO ’18, July 15–19, 2018, Kyoto, Japan

D

v1

SP

ϕ
0

v0
-0.5

robot2

0.0

0.5

1.0

1.5

(a) Joint set point (S P ) as a function of t

robot3
D

1

0
0

1

2

3

(b) Wrapping d onto [0, 1]

robot4

robot5

Figure 2: Control system parametrization

Figure 1: The four robot morphologies

na

2.1

Simulated Robots

The algorithm was run on four of the five robot morphologies
from [16], illustrated in Figure 1. The morphologies has retained
their original numbering. The fifth morphology, robot 1, provoked
simulator instabilities that we were currently unable to rectify, and
was not included in these experiments.
The robots were simulated using the PhysX simulator. The
subject robot is placed on a infinite flat plane. When given a new gait
to evaluate by MAP-Elites, it first runs the gait for one period before
starting to sample position and orientation. Sampling continues
until a given number of periods have elapsed. Based on the samples,
behavior and performance (subsection 2.3) are given to MAP-Elites.
This repeats without restarting the simulator, until the run ends
when a certain number of evaluations has been reached or the
simulator detects that the robot has been in a tilted or flipped state
for 20 consecutive evaluations. After each evaluation the current
coverage and precision (subsection 2.5) is logged for analysis.

2.2

Control System

Each joint is controlled by an open-loop controller with four parameters: phase offset ϕ, duty cycle D, and two extreme values
v 0 and v 1 , as shown in Figure 2a. The duty cycle is encoded as a
continuous parameter d such that
(
d − bdc bdc is even
D=
dde − d otherwise
as illustrated in Figure 2b. This lets d be mutated freely as a continuous variable while mapping it to the correct range without
discontinuities and without getting stuck at the extreme values.
The parameters are encoded symmetrically, so that each joint on
the left side of the body share duty cycle and amplitude parameters
with the corresponding joint on the right side. The phase offset is
coded differentially, i.e. it is ϕ on the left side and ϕ + ∆ϕ on the
right.

2.3

Behavior and Fitness

The behavior descriptor is composed of two features that are designed to work well as control parameters for a higher-level control

nb
Figure 3: Forward movement estimation. The length of
the circular segment is RΘ, which gives an estimate of the
amount of forward movement. SE R approximately corresponds to the shaded area, and measures the amount of sideways motion.
system: average turn rate and adjusted forward speed. Average
ÍN
turn speed is measured simply as bT = i=0
∆α i /∆t, where N
is the number of sample periods and ∆t is the time elapsed. To
calculate the adjusted forward speed, first the average position and
orientation of the robot during the first and last periods are estimated. Lines perpendicular to the orientations and intersecting the
positions are constructed, illustrated as na and nb in Figure 3. The
point where these two lines cross is used as a center of curvature,
C; using it we can estimate the turn radius and its standard error
ÍN
R = N1+1 i=0
|x i − C |
q Í
N (|x − C | − R)2
SE R = N1 i=0
i
and the change in orientation relative to C
ÍN
Θ = N1 i=1
∠x i Cx i−1
where then angle ∠x i Cx i−1 between x i C and Cx i−1 signed. The
adjusted forward speed is then defined as b F = RΘ/∆t.
As the fitness measure, we compute a weighted sum of several
penalty measures
P = 10SE R + |θ | + 10−h/0.05
where |θ | is the average absolute pitch of the body, and h is the
average height of the body reference point. This penalizes large
sideways motion, up/down tilt and having the body close to the
ground. The penalty score is then inverted into

f = max 0, −5 log10 P

GECCO ’18, July 15–19, 2018, Kyoto, Japan

Eivind Samuelsen and Kyrre Glette
all-hard

4

all-soft
some-hard

Density

3

some-soft
2

2.5

1

0
0

1

2

3

Magnitude

Figure 4: Simulated distribution density of the magnitude of
the four tested mutation operators with k = 20 parameters
and σ = 1.
In addition to producing a value increasing with solution quality, f
can be thought of as being measured in centimeter-height equivalents: it reduces to f ≈ 100h when the sideways and pitch penalties
are small , and f ≤ 100h in general.

2.4

running the experiments with five different values for σ . We also
attempt to control for effects caused by running with three different
map resolutions. The extents the map cells covers in behavior space
are kept constant. All combinations of mutation type, mutation
magnitude and map resolution is run multiple times on all robots,
as summarized in Table 1.

x∈M

where m (x) is the score in cell x of map m or zero if empty, M is the
set of all cells, and n (m) is the number of filled cells in m. Coverage
is defined as the fraction of cells filled:
n (m)
C (m) =
N (m)
where N (m) is the total number of cells in the map. Finally, global
reliability is defined as the average score across all cells, which can
be expressed as
G (m) =

Mutation Operators and Other Variables

We test four different mutation operators: two of them, referred
to here as all-hard and some-hard, consists of doing a Gaussian
mutation to all parameters and to each parameter with a probability
1/k respectively. The other two, referred to as all-soft and somesoft, are variants of the first two with modifications to smooth out
the magnitude distribution. The four distributions are shown in
Figure 4, and are defined by the change in parameters δ M as


√
δ all-hard ∼ N 0, σ Ik / k − 1


√
δ all-soft ∼ N 0, σ Ik / k − 1 U (0, 2)
(
Ni (0, σ ) probability 1/k
δ some-hardi ∼
0
otherwise
(
Ni (0, σ ) i = j or probability 1/(k − 1)
δ some-softi ∼
0
otherwise
The issue in the magnitude distribution of all-hard is that it
has very low density near zero, so that small mutations are very
unlikely; all-soft modifies all-hard by multiplying by a uniformly
distributed scalar between 0 and 2, which scatters the mutation
magnitude while leaving the expected magnitude the same. Also notice√that the standard deviation of the two ’all’ operators is divided
by k − 1, which keeps the mode of the magnitude distributions
equal to 1.
Some-hard, on the other hand, has a (1 − 1/k)k chance of not
mutating at all, which results in reevaluation of the same individual.
Some-soft prevents this by first picking one random parameter j
for mutation, and then mutating each other parameter with a probability 1/(k − 1). This removes the probability of a zero magnitude,
and gives a minimal change to the rest of the distribution.
In addition to testing different mutation distributions, we also
test what effect the mutation magnitudes has on the algorithm by

Performance Measures

Performance measures similar to those in [11] and [14] are used;
presicion is defined as the average score of filled cells:
QD-score (m)
1 Õ
m (x)
P (m) =
=
n (m)
n (m)

QD-score (m)
= P (m) C (m)
N (m)

meaning that reliability can be seen as either the QD-score normalized for map resolution, or the product of precision and coverage.
These definitions differs from those in [11] in that they do not scale
the cell scores against the best observed score for each cell.

2.6

Cliff’s Delta

Cliff’s delta, or the d statistic [1], is an ordinal estimate of how
separated two distributions are, and can be expressed as
dab = p (a > b) − p (a < b)

(1)

It can either be calculated exactly by comparing all possible pairs
of observations from the samples, approximated by comparing a
large number of random pairs, or through its relation
2U
−1
mn
to the Wilcoxon-Mann-Whitney (WMW) U statistic. Because of this
linear relation, testing whether d is likely to be zero corresponds to
doing a WMW U test. The d statistic is also related to Vargha and
Delaney’s effect size Â [18] by
dab =

dab = 2Âab − 1
Since it is ordinal, we can use it to measure differences across incomparable groups, for example compare the performance of two
algorithms across different benchmarks, or in this case, different
parametrizations of an algorithm across different robot morphologies. Assuming equal weight to the different groups, this can be
done by ensuring that comparisons are always done between observations in the same group, and weighting the groups equally.
This can be calculated as
1 Õ
dab =
d (a | д, b | д)
|G |
д ∈G

Multi-objective Analysis of MAP-Elites Performance

2.7

Pareto Domination

Considering the performance measures defined in Subsection 2.5
from the perspective of multi-objective optimization, we can see
that we have three objectives we want to optimize, and so, rather
than analyzing which algorithms perform well with regards to
the objectives individually, we should be interested in to what degree the different algorithms produce superior results across all
objectives. Pareto domination provides a way to test this: an objective vector x is said to dominate another vector y if all individual
objectives are at least as good, and at least one objective is better:
x p y ≡ ∀i x i D yi ∧ ∃i x i B yi
As suggested in [12], we can replace the comparison operators in
(1) with Pareto domination, resulting in a measure of what degree
one sample dominates the other:


dab = p a p b − p a ≺p b
Like the scalar d statistic, this can be used to compare distributions
to decide which is better. Note, however, that the WMW U statistic
and test cannot be generalized in the same manner, so it cannot
be used to calculate the Pareto d statistic. This is because Pareto
dominance is not able to produce a simple ranking of a sample.
Note that given the way precision, coverage and reliability is
defined here, reliability is redundant when considering Pareto domination: consider if, for some maps m and n, G (m) < G (n), thus
implying m p n. Expanding this as products of P and C we get
P (m) C (m) < P (n) C (n)
However, since both P and C are always non-negative, this would
imply P (m) < P (n) ∨ C (m) < C (n), and then we would already
have m p n based on precision and coverage alone.

3

RESULTS

Figure 5 shows the conventional box plots for coverage, reliability
and precision after the last evaluation for each robot. Each box
represents all the runs where one parameter is set to a certain value.
For each parameter, the data has been adjusted to remove variation
caused by the the other two parameters, in order not to exaggerate
the variance of the different values.
The plots indicate that mutation magnitude has the largest effect
on all three measures. Coverage and reliability increases with
mutation magnitude, while high mutation magnitudes seem to
have a negative effect on precision. There also seems to be a small
negative effect on all three measures from increasing map resolution.
There is little or no difference between the mutation types on any
of the measures. Only robot2 deviates notably from the patterns,
and those differences are mainly visible in a change of scales.
Figure 6 shows coverage-precision bag plots of the results by
robot and variable. Each plot contains one trace and one bag for
each parameter value. The traces are of the means of the results
after every 50th evaluation starting with the end of initialization.
The marks on the traces are placed so that the number of evaluations
are approximately tripled between each mark. The bags show the
extents of the central halves of the results after the last evaluation,
and are roughly analogous to the boxes in a box plot.
In the plots, mutation magnitude has the most visible effect. The
traces spread out from a common origin into different niches in

GECCO ’18, July 15–19, 2018, Kyoto, Japan
order from least magnitude, least coverage, to largest magnitude,
most coverage. Magnitudes 0.2, 0.4 and 0.8 forms a clear Pareto
front, while 0.1 and 0.05 are behind 0.2 on average on most robots.
There is considerable overlap in the central-half bags, but a clear
distinction between the bags of the extreme parameter values for
all robots but robot2. In the plots for the other two parameters
there are not any such clear patterns. The bags for mutation type
almost completely overlap, with what is perhaps a slight advantage
to some-soft on average. Of the three map resolutions, 5 × 5 is
considerably better on average, but also has much larger variation
than the other two.
Of the four morphologies, robot2 stands out by having much
higher precision and lower coverage than the others, along with
correspondingly higher precision variance and lower coverage variance. The others generally have about the same shape and average
development; however, robot3 appears to achieve better coverage
with higher mutation sizes, while robot4 has bigger variation in
precision.
Table 2 shows the Cliff’s deltas for all pairs of values of all
parameters. The tables are arranged so that the row names group a
and the column names group b in dab . The effect sizes are presented
as 99% confidence intervals using the following notation:
 0.123 0.123
0.123 (45) = −0.045
, +0.045 = [0.078, 0.168]
The confidence intervals are computed by bootstrapping the statistic. The number before the parentheses is the center of the confidence interval, and the number within is the nonzero digits of
half the interval size up until the last written digit of the center
value. This makes it easy to see how big the effect is estimated to
be, compared to the uncertainty of the estimate.
Using the confidence interval we can easily check whether it is
likely that some value is the true effect size. With Cliff’s delta, if
the confidence interval does not overlap with zero, it is unlikely
that the true effect size is equal to zero or of opposite sign.2 In the
tables, effect sizes with intervals overlapping zero are grayed out.
In Table 2 we also display the orderings of the parametrizations
in the cases where this is possible to deduce. It was possible to find
a complete ordering for map resolutions, while for the mutation
magnitudes only a partial ordering was possible. Finally, for the
mutation types there is no consistent ordering, but some-soft is
better than all-hard and some-hard, and all-soft is better than somehard. However, the effect sizes are very small compared to the
mutation magnitude effects.

4

DISCUSSION

Figure 5 and Figure 6 both attempt to visualize the same information, but from different perspectives. Because of the large number
of different parameter values in the experiment, the box plots in
Figure 5 require the same amount of space as Figure 6 does, but to
us it is clear that Figure 6 gives a significantly clearer view of the
performance trade-offs of a set of parametrizations this large.
In addition, plotting along the coverage-precision dimensions
allows us to trace the search progress with systematic marks. As
an obervation from this, there is a tendency for the exponentially
2 In

fact, this is equivalent to a hypothesis test.

GECCO ’18, July 15–19, 2018, Kyoto, Japan

0.2

1.5
robot2

robot2

0.3

Eivind Samuelsen and Kyrre Glette

1.2
0.9

0.1
0.8

10

0.6
robot2

0.6

5
2
robot3

0.4

robot3

0.2
1

0

10
0.0
robot3

8
0
6

0.6

4
0.4

2.0
robot4

0.2

12
1.5

0.0

0.5

9
robot4

robot4

1.0

6

0.0

0.6

3
0.4

1.5
1.0
0.5

0.0

8
robot5

robot5

robot5

0.2

10

6
4

0.0

(a) Coverage

(b) Reliability

0.05
0.1
0.2
0.4
0.8
5
7
9
all-hard
all-soft
some-hard
some-soft

0.05
0.1
0.2
0.4
0.8
5
7
9
all-hard
all-soft
some-hard
some-soft

0.05
0.1
0.2
0.4
0.8
5
7
9
all-hard
all-soft
some-hard
some-soft

2

(c) Precision

Figure 5: Box plots of the three objectives, across robots and parameters. For each of the parameters the data has been adjusted
to remove variation from the other two parameters, which is why some of the box whiskers extend below zero.

Multi-objective Analysis of MAP-Elites Performance

GECCO ’18, July 15–19, 2018, Kyoto, Japan

10.0

10.0

7.5

7.5

7.5

5.0

5.0

5.0

2.5

2.5

2.5

6

6

6

5

5

5

4

4

4

3

3

3

2

2

2

8

8

8

6

6

6

4

4

4

2

2

2

7

7

7

6

6

6

5

5

5

4

4

4

3

3

3

Precision

10.0

robot4

12.5

robot3

12.5

robot2

12.5

0.0

0.2

0.4

0.6

0.0

0.2

0.4

0.6

Coverage
5

7

9

(a) Map resolution

robot5

2

2

2

0.05

0.1

0.2

0.4

(b) Mutation magnitude

0.8

0.0

0.2

0.4

all-hard

all-soft

some-hard

some-soft

0.6

(c) Mutation type

Figure 6: Precision and coverage grouped by the different variables. The light gray curves are isocurves for reliability.

GECCO ’18, July 15–19, 2018, Kyoto, Japan

Eivind Samuelsen and Kyrre Glette

Table 2: Effect sizes between parameter values

7
9

Compared to
5
7
-0.164(42)
-0.266(47) -0.140(48)
579

REFERENCES

(a) Map sizes when grouped by mutation magnitude.

0.1
0.2
0.4
0.8

Compared to
0.05
0.1
0.2
0.4
0.223(62)
0.380(56) 0.216(61)
0.342(53) 0.252(56) 0.111(60)
0.155(50) 0.090(48) -0.025(57) -0.138(61)
0.4  {0.8, 0.2}  0.1  0.05

(b) Mutation magnitudes when grouped by map resolution.

all-soft
some-hard
some-soft

all-hard
0.042(63)
-0.044(60)
0.074(55)

Compared to
all-soft
some-hard
-0.105(61)
0.013(64)

0.118(62)

(c) Mutation types when grouped by mutation magnitude and map
resolution.

placed marks to be evenly spaced in the plot, indicating a trend of
exponential convergence.
From the mutation magnitude plot for robot3 in Figure 6, we can
see that 0.4 and 0.8 are one the same isocurve, which would have
resulted in similar reliability values. Still, the bag plot highlights the
difference in these parametrizations, and makes it easier to select
based on the application. To achieve the same insights with the box
plots, one would need to cross-reference at least two of them.
Regarding the variation on mutation operation and magnitude,
it is perhaps surprising to see that the exact method of mutation appears to be of little consequence relative to the mutation magnitude.
Still, from Table 2c, we can pinpoint that there are certain differences, and that our proposed soft versions have a small positive
effect compared to the standard schemes.

5

the method could find application beyond MAP-Elites , in particular it should be applicable to other algorithms within the Quality
Diversity domain.

CONCLUSION

We have presented a method for multi-objective performance analysis of the MAP-Elites algorithm, based on ordinal effect sizes and
pareto dominance. Since the method uses ordinal effect size, it allows us to draw general conclusions on the performance of various
parameter values across groups of different scaling, such as varying
robot morphologies.
Through a thorough case study we demonstrated that this approach allowed us to better identify trade-offs in precision and
coverage introduced by various algorithmic parameter changes.
We also observed that the magnitude of mutations had a bigger
effect on outcomes than the details of the mutation operators.
We expect the method to be useful for other MAP-Elites practitioners, both for analyzing new algorithmic features as well as for
tuning performance to specific applications. We also expect that

[1] Norman Cliff. 1993. Dominance statistics: Ordinal analyses to answer ordinal
questions. Psychological Bulletin 114, 3 (1993), 494. https://doi.org/10.1037/
0033-2909.114.3.494
[2] Antoine Cully, Jeff Clune, Danesh Tarapore, and J.-B. Mouret. 2015. Robots that
can adapt like animals. Nature (2015), 1–26.
[3] Antoine Cully and Yiannis Demiris. 2017. Quality and Diversity Optimization: A
Unifying Modular Framework. IEEE Transactions on Evolutionary Computation
May (2017).
[4] Antoine Cully and Jean-Baptiste Mouret. 2016. Evolving a Behavioral Repertoire
for a Walking Robot. Evolutionary computation 24, 1 (2016), 59–88.
[5] Stephane Doncieux, Nicolas Bredeche, Jean-Baptiste Mouret, and Agoston
E. (Gusz) Eiben. 2015. Evolutionary robotics: what, why, and where to. Frontiers
in Robotics and AI 2 (2015), 4.
[6] Miguel Duarte, Jorge Gomes, Sancho Moura Oliveira, and Anders Lyhne Christensen. 2017. Evolution of Repertoire-based Control for Robots with Complex
Locomotor Systems. IEEE Transactions on Evolutionary Computation X (2017),
1–14.
[7] Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. 2017. Data-efficient
exploration, optimization, and modeling of diverse designs through surrogateassisted illumination. In GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference. 99–106.
[8] Abdullah Konak, David W. Coit, and Alice E. Smith. 2006. Multi-objective
optimization using genetic algorithms: A tutorial. Reliability Engineering &
System Safety 91, 9 (2006), 992 – 1007. https://doi.org/10.1016/j.ress.2005.11.018
[9] Joel Lehman and Kenneth O Stanley. 2011. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th
annual conference on Genetic and evolutionary computation. ACM, 211–218.
[10] Joel Lehman, Kenneth O Stanley, and Risto Miikkulainen. 2013. Effective Diversity Maintenance in Deceptive Domains. In GECCO 2013: Proceedings of the 2013
Genetic and Evolutionary Computation Conference. 215–222.
[11] Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping
elites. 521, 7553 (2015), 9993. arXiv:1504.04909
[12] Geoffrey Neumann, Mark Harman, and Simon Poulding. 2015. Transformed
Vargha-Delaney Effect Size. In Search-Based Software Engineering, Márcio Barros
and Yvan Labiche (Eds.). Springer International Publishing, 318–324. https:
//doi.org/10.1007/978-3-319-22183-0_29
[13] Anh Nguyen, Jason Yosinski, and Jeff Clune. 2015. Innovation Engines: Automated Creativity and Improved Stochastic Optimization via Deep Learning. In
GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation
Conference. 959–966.
[14] Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. 2016. Quality Diversity: A
New Frontier for Evolutionary Computation. Frontiers in Robotics and AI 3, July
(2016), 1–17.
[15] Gábor Renner and Anikó Ekárt. 2003. Genetic algorithms in computer aided
design. Computer-Aided Design 35, 8 (2003), 709 – 726. https://doi.org/10.1016/
S0010-4485(03)00003-4 Genetic Algorithms.
[16] Eivind Samuelsen and Kyrre Glette. 2015. Real-world reproduction of evolved
robot morphologies: Automated categorization and evaluation. In Lecture Notes
in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Vol. 9028. 771–782.
[17] Eivind Samuelsen, Kyrre Glette, and Jim Torresen. 2013. A hox gene inspired
generative approach to evolving robot morphology. In GECCO 2013 - Proceedings
of the 2013 Genetic and Evolutionary Computation Conference. 751–758.
[18] András Vargha and Harold D Delaney. 2000. A critique and improvement of
the CL common language effect size statistics of McGraw and Wong. Journal of
Educational and Behavioral Statistics 25, 2 (2000), 101–132. https://doi.org/10.
3102/10769986025002101

