Back to the program.
On Metrics for Comparing Non-Dominated Sets
Joshua D. Knowles
Université Libre de Bruxelles
Brussels, Belgium


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.


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


  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.
  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.
  3. M.P. Hansen and A. Jaszkiewicz. (1998) Evaluating the quality of approximations to the non-dominated set. Technical Report IMM-REP-1998-7.