Back to the program.
On Metrics for Comparing Non-Dominated Sets
Joshua D. Knowles
IRIDIA;; Université Libre de Bruxelles;; Brussels, Belgium
On 2002-05-02 at 15:00:00 (Brussels Time)

Abstract

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 approximation sets? 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.

Keywords

Multi-objective, Multi-criteria, Optimization, Performance Assessment, Partially-Ordered Sets.

References

  1. 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.
    See http://iridia.ulb.ac.be/~jknowles/thesis.html
  2. J.D. Knowles and D.W. Corne. (2002) On Metrics for Comparing Non-Dominated Sets. In Proceedings of the 2002 Congress on Evolutionary Computation Conference (CEC02). IEEE Press. To appear.
    See http://iridia.ulb.ac.be/~jknowles/publications.html
  3. M.P. Hansen and A. Jaszkiewicz. (1998) Evaluating the quality of approximations to the non-dominated set. Technical Report IMM-REP-1998-7.
    See http://citeseer.nj.nec.com/hansen98evaluating.html