Information Technology Reference
In-Depth Information
PE N
∩
ones. The goal of multiple objective Pareto pro-
cedures is to find a good approximation of the set
of efficient solutions. It is unlikely that the whole
set of Efficient solutions (
E
) is fully known. While
the outcomes from compared algorithms are dif-
ferent, they can still be all equally Pareto efficient.
Usually, the three following conditions are
considered as desirable for a good multi-objective
algorithm:
Q PE
(
)
=
100
%
1
PE
Czyzak & Jaszkiewicz (1998) presents a quality
measure of the percentage of reference solutions
found by the algorithm:
PE R
∩
Q PE
(
)
=
100
%
2
R
•
The distance of the obtained set of
Potentially Efficient solutions (
PE
) to the
E
should be minimized.
Both of the above metrics are cardinal.
In the case of real-life MOCO problems, it may
be impossible to obtain, in a reasonable time, a
significant percentage of efficient solutions. In
this case, obtaining near-efficient solutions would
also be highly appreciated. Following Knowles
& Corne (2002), a more general and economic
criterion may be to concentrate on evaluating
the distance of solutions to the efficient frontier.
The
Dist
1
R
and
Dist
2
R
metrics by Czyzak &
Jaszkiewicz (1998), can serve this purpose. We
suggest using them because they are not difficult
to compute, and they seem to be complementary
to the
C
metric by Zitzler (1999), when compared
according to the properties analyzed by Knowles
& Corne (2002).
The
C
metric, also a cardinal measure, com-
pares two sets of
PE
,
A
and
B
. A reference set,
R
,
is not required and it is really easy to compute as:
•
The distribution of the solutions in
PE
should be uniform.
•
The larger the number of obtained solu-
tions,
i.e.
[
PE
], the better the algorithm.
The last two conditions present more weak-
nesses than strengths. If
E
does not present a
uniform distribution, or [
E
]=1, the algorithm that
obtains the proper
E
will not fulfil these condi-
tions. Furthermore, an algorithm that just reports
a huge number of solutions does not ensure their
quality (in terms of efficiency). To have an idea
of quality, a reference set of
E
(
R
, in the follow-
ing) should be considered. The ideal
R
is the set
E
. However, for MOCO problems it is unlikely
that the whole
E
is known (except for small size
instances, with non-practical application). A useful
practice is having a set
R
as close to
E
as possible,
then filtering the
PE
output with
R
, to obtain a
net set of non-dominated solutions
b B
∈
/
∃ ∈
a A a
:
b
C A B
( ,
)
=
B
(
)
}
N
={
X
is Pareto efficient in
PE R
∪
The following statements can aid the under-
standing of
C
(
A
,
B
):
N
will be at least as good as
R
. One can mea-
sure the quality of the output as the percentage of
solutions in
PE
that survive the filtering process
with
R
:
•
If
C
(
A
,
B
)=1, all solutions in
B
are weakly
dominated by
A
.
•
If
C
(
A
,
B
)=0, none of the solutions in
B
are
weakly dominated by
A
.
Search WWH ::
Custom Search