Evaluating the Quality of Approximations to the Non-Dominated Set

For a copy of this paper, either

• view a full text copy of this paper

or contact
• vvv@imm.dtu.dk

The growing interest in hard multiple objective combinatorial and non- linear problems resulted in a significant number of heuristic methods aiming at generating sets of feasible solutions as approximations to the set of non-domina ted solutions. The issue of evaluating these approximations is addressed. Such e valuations are useful when performing experimental comparisons of different mult iple objective heuristic algorithms, when defining stopping rules of multiple ob jective heuristic algorithms, and when adjusting parameters of heuristic algorit hms to a given problem. A family of outperformance relations that can be used to compare approximations under very weak assumptions about a decision-maker’s pre ferences is introduced. These outperformance relations define incomplete orders in the set of all approximations. It is shown that in order to compare approxima tions, which are incomparable according to the outperformance relations, much st ronger assumptions about the decision-maker's preferences are necessary. A gener al framework that can be used to compare and evaluate approximations under the p resence of various types of additional information is proposed. Some particular comparison and evaluation methods based on this framework are suggested. The pro posed framework is also used to characterize some previously proposed evaluation methods.

Technical report 07/98