Multi-Objective Performance Metrics: Appendix H

Appendix H
Multi-Objective Performance Metrics
In multi-objective optimization processes (MOPs), there are two distinct and orthogonal
goals [11] as follows: (1) discover solutions as close to the Pareto-optimal solutions as
possible, and (2) find solutions as diverse as possible in the obtained non-dominated front.
Therefore, in order to compare two or more MOEAs, at least two performance metrics (one
evaluating the progress towards the desired Pareto-optimal front i.e. P* and the other
evaluating the spread of Pareto-front obtained i.e. Q) need to be used and exact definitions of
these performance metrics are important.
For this purpose, various performance metrics are reported for MOEAs in the
reference [11]. In this work, four different measures such as generational distance (GD),
spacing (S), spread (∆) and hypervolume (HV) are used for numerical comparison of the
non-dominated fronts produced by various MOEAs.
The metric GD is used to evaluate the progress towards the Pareto-optimal front and
the metrics S and ∆ are used to evaluate the spread of the obtained non-dominated solutions.
The metric HV provides the combined qualitative information about closeness and diversity
in obtained Pareto-fronts.
G.1. Generational distance (GD)
Instead of finding whether a solution of Q belongs to the set of P* or not, the generational
distance metric (GD) recommended by Veldhuizen [170] evaluates an average distance of
the solutions of Q from P*, as follows:
1p
 Q p
 ∑ di 
GD =  
i =1
(H.1)
Q
For p = 2 , the parameter di is the Euclidean distance (in the objective space) between the
solution i ∈ Q and the nearest member of P*:

Appendix H: Multi-Objective Performance Metrics 2013
∑( f − f m*(i ) )
M 2
di = min* (i )
m (H.2)
k∈ P m =1
where f m*( i ) is the mth objective function of the kth member of P*. Intuitively, an algorithm having
a small value of GD is better.
G.2. Spacing (S)
The spacing metric (S) suggested by Schott [169] is calculated with a relative distance
measure between consecutive solutions in the obtained non-dominated set, as follows:
∑(d −d )
1 2
S= i (H.3)
Q i =1
M 
where d i = min ∑ f mi − f mk  and d is the mean value of the above distance measure
k∈Q ∧ k ≠ i
 m =1 
Q
d = ∑ d i Q . The distance measure is the minimum value of the sum of the absolute
i =1
difference in objective function values between the ith solution and any other solution in the
obtained non-dominated set. Notice that this distance measure is different from the minimum
Euclidean distance between two solutions.
The above metric measures the standard deviations of different di values. When the
solutions are nearly spaced, the corresponding distance measure will be small. Thus, an
algorithm finding a set of non-dominated solutions having smaller spacing (S) is better.
G.3. Spread (∆)
In MOPs, the main interest is to achieve a set of solutions that spans the entire Pareto-
optimal region. The spread metric (∆) suggested by Deb [165] measures the extent of spread
achieved among the obtained solutions. Then, the following metric is to calculate the non-
uniformity in the distribution:
M Q
∑ dme + ∑ di − d
∆= m =1
M
i =1
(H.4)
∑d
m =1
e
m +Qd
Dept. Of Electrical Engg., Faculty of Engineering, Dayalbagh Educational Institute, Agra-282110 326
Appendix H: Multi-Objective Performance Metrics 2013
where di are Euclidean distances between neighbouring solutions having the mean value d .
The parameter dme is the distance between the extreme solutions of P* and Q corresponding to
mth objective function. An algorithm finding a smaller value of ∆ is able to find a better
diverse set of non-dominated solutions.
G.4. Hypervolume (HV)
This metric provides a qualitative measure of convergence as well as diversity in a combined

sense. Nevertheless, it can be used along with one of the above two metrics to get a better
overall picture of algorithm performance.
It calculates the volume (in the objective space) covered by members of Q for
problems where all objectives are to be minimized [170]-[171]. Mathematically, for each
solution i ∈ Q , a hypercube vi is constructed with reference point W and the solution i as the
diagonal corners of the hypercube. The reference point can simply be the found by
constructing a vector of worst objective function values. Thereafter, a union of all
hypervolume (HV) is calculated as follows:
Q 
HV = volume  U vi  (H.5)
 i =1 
 
Obviously, an algorithm with large value of HV metric is desirable. This metric is

free from arbitrary scaling of objectives. For example, if the first objective function takes
values an order of magnitude more than of the second objective, a unit improvement in f1
would reduce HV much more than that a unit improvement in f2. Thus, this metric will
favour a set Q which has better converged solution set for the least-scaled objective function.
To eliminate this difficulty, the above metric can be evaluated by using normalized objective
function values.
Dept. Of Electrical Engg., Faculty of Engineering, Dayalbagh Educational Institute, Agra-282110 327

Multi-Objective Performance Metrics: Appendix H

Uploaded by

Copyright:

Available Formats

Multi-Objective Performance Metrics: Appendix H

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Multi-Objective Performance Metrics: Appendix H

Uploaded by

Copyright:

Available Formats

Appendix H

Multi-Objective Performance Metrics

G.1. Generational distance (GD)

solution i ∈ Q and the nearest member of P*:

G.2. Spacing (S)

G.3. Spread (∆)

G.4. Hypervolume (HV)

This metric provides a qualitative measure of convergence as well as diversity in a combined

Obviously, an algorithm with large value of HV metric is desirable. This metric is

You might also like