IEEE Computational Intelligence Magazine - August 2019 - 63

followed by a description of the proposed test suite and the performance
verification. Finally, conclusions are
drawn in Section V.
II. Proposed Metric for Diversity
Assessment
A. Existing Metrics for Diversity
Assessment

In general, the performance metrics in
multi-objective optimization can be
divided into those assessing only convergence (e.g., GD [16] and CM [17]),
those assessing only diversity (e.g., Spacing [13] and PD [11]), and those assessing both convergence and diversity (e.g.,
IGD [15] and HV [18]). A detailed list of
most existing performance metrics can
be found in [19]. In the following, we
review the metrics assessing only diversity, which can be further grouped into
three categories.
The first category of metrics assesses
the diversity by calculating the minimum Euclidean distance of each solution to the others in the solution set,
such as Spacing [13] and T [20]. For
example, the Spacing value of a solution
set P can be calculated by
Spacing ^P h =

P

1 / ^dr - d h2 ,
i
P - 1 i =1
(1)

where d i denotes the minimum distance
of the i-th solution to the others in P,
and dr denotes the mean of all d i . In
short, Spacing measures the standard
deviation of the minimum distances of
each solution to the others. Hence, this
metric assesses the evenness of a solution
set without considering its spread.
The second category assesses the
diversity by dividing the objective space
into grids and counting the grids having
at least one solution, such as CL n [14],
DM [17], and DCI [19]. For example,
CL n divides the solutions in P into a
number of hypercubes and assesses the
diversity of P by
CL n (P ) =

P
,
NDC n (P )

(2)

where NDC n (P ) is the number of
hypercubes having at least one solution,

and n is a parameter denoting the number of divisions on each objective. Obviously, CL n mainly assesses the spread of a
solution set, since it does not consider the
evenness of solutions within the same
hypercube. Besides, according to (2), a
solution set containing fewer solutions
may have better (i.e., smaller) CL n value.
The third category adopts the measures in other fields, such as experimental design [21], spatial informatics [22],
and biology [23]. Taking the PD [11]
used for measuring the biodiversity as an
example, it calculates the diversity of a
solution set P by
PD ^P h = max
^PD (P \{p})
!
p

P

+ min

q ! P \{p}

f ( p) - f (q) p j, (3)

where f (p) - f (q) p denotes the L p norm based distance between solutions p
and q in objective space. It should be
noted that PD is designed for assessing
the diversity of points filling a hypercube,
whereas the Pareto optimal solutions
for an MOP usually lie on an (M - 1)dimensional manifold in an M-dimensional objective space [24], so that the solutions
far away from the Pareto front usually
contribute more to the PD value. As a
consequence, PD mainly considers the
spread since the solutions with worse convergence usually have larger spread.
It is worth noting that the metrics
assessing both convergence and diversity
can also be used to distinguish between
the diversity of two solution sets if they
have similar convergence, such as IGD
[15], Tp [25], and HV [18]. A set of reference points uniformly sampled on the
Pareto front is required for the calculation of IGD and Tp , where IGD calculates the averaged minimum distance
between each reference point and the
solution set and Tp calculates the averaged Hausdorff distance between the
reference point set and the solution set.
Besides, a reference point is required for
the HV metric to calculate the hypervolume of the area covered by a solution
set with respect to it. It is worth noting
that the reference point for the HV calculation is an anti-optimal point, which
is different from the reference points
used for the calculation of IGD or Tp .

B. Limitations of Existing Metrics
in Diversity Assessment

To illustrate the limitations of existing
metrics in diversity assessment, we consider four solution sets shown in Fig. 2 with
different distributions, where each set
consists of 105 non-dominated solutions.
The Pareto front is assumed to be a unit
sphere in the first octant. It is clear that P1
has good evenness and spread, whereas P2
merely concentrates on two curves of the
Pareto front, and most solutions in P3 do
not converge to the Pareto front. P4 is
obtained by projecting the solutions sampled by Das and Dennis's method [26] to
the unit sphere. Note that the spread of
P4 is similar to P1, but the evenness of P4
is worse than P1 since the solutions on
the border of P4 are obviously more
crowded than those in the middle.
In this example, Spacing, CL n, PD,
IGD, T p, and HV are employed to assess
the diversity of the four solution sets. As
suggested in the literature [7], [27], the
reference points for calculating IGD and
T p are 9870 points obtained by the same
method as P4. Besides, the parameter n
in CL n is set to 10, the parameter p in
PD is set to 0.1, the parameter p in T p is
set to 2, and the reference point for calculating HV is set to (1.1, 1.1, 1.1).
Note that smaller values of Spacing,
CL n, IGD, and T p and larger values of
PD and HV indicate better diversity.
As shown in Table I, none of the metrics identifies P1 as the one with the best
diversity, despite that P1 has the best diversity among the four solution sets. To be
specific, Spacing merely calculates the standard deviation of the minimum distances
between each solution and the others.
Since the solutions in P2 have smaller distances to each other than those in the
other solution sets, P2 has the best Spacing
value. CL n and PD consider spread much
more important than evenness, so P3
obtains the best CL n and PD values. Since
the reference points for the IGD calculation and the solutions in P4 have the same
distribution, P4 has a better IGD value
than the other solution sets. In fact, P1 and
P4 have similar spread, but according to
the Spacing values of P1 and P4, i.e., the
standard deviations of the minimum distances between solutions, the evenness of

AUGUST 2019 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

63
IEEE Computational Intelligence Magazine - August 2019

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2019
