Consider an optimization problem with k >= 2 objective functions: a
multiobjective problem. Assume that each objective function maps a
solution vector to an ordinal number (say to be minimized w.l.o.g) but
that each objective function is otherwise unknown and is not restricted
to being linear, continuous, etc. In general, the ranges of the
functions will also be different.
Given such a problem, it is often desirable to find the set of all
optimal "trade-off solutions" to the problem, the so-called Pareto
optimal (PO) set. Unfortunately, generating this set is often
intractable, so that we must satisfy ourselves with finding an
approximation to it. In this case, how should we measure how good our
approximation set is, given that it is a set of k-dimensional vectors?
More specifically, how can we compare the quality of two such
In this talk I will consider these questions. I will analyse several
different metrics proposed in the literature for evaluating and
comparing approximation sets. For this analysis I make use of some
outperformance relations that can be used to show that some metrics that
have been proposed are not reliably correct. In the end I will make some
recommendations about which metrics seem most useful in practice.
Multi-objective, Multi-criteria, Optimization, Performance Assessment,
J.D. Knowles. (2002)
Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization. Ph.D. Thesis. Department of Computer Science, University of Reading, Reading, UK.
J.D. Knowles and D.W. Corne. (2002)
On Metrics for Comparing Non-Dominated Sets.
Proceedings of the 2002 Congress on Evolutionary Computation Conference (CEC02). IEEE Press. To appear.
M.P. Hansen and A. Jaszkiewicz. (1998)
Evaluating the quality of approximations to the non-dominated set. Technical Report IMM-REP-1998-7.