One of the most common approaches for multiobjective optimization is to generate a solution set that well approximates the whole Pareto-optimal frontier to facilitate the later decision-making process. However, how to evaluate and compare the quality of different solution sets remains challenging. Existing measures typically require additional problem knowledge and information, such as a reference point or a substituted set of the Pareto-optimal frontier. In this paper, we propose a quality measure, called dominance move (DoM), to compare solution sets generated by multiobjective optimizers. Given two solution sets, DoM measures the minimum sum of move distances for one set to weakly Pareto dominate the other set. DoM can be seen as a natural reflection of the difference between two solutions, capturing all aspects of solution sets' quality, being compliant with Pareto dominance, and does not need any additional problem knowledge and parameters. We present an exact method to calculate the DoM in the biobjective case. We show the necessary condition of constructing the optimal partition for a solution set's minimum move, and accordingly propose an efficient algorithm to recursively calculate the DoM. Finally, DoM is evaluated on several groups of artificial and real test cases as well as by a comparison with two well-established quality measures.
@cite_32 introduced a quality measure based on the integrated preference functional (IPF), without the requirement of the knowledge of the Pareto-optimal frontier. This measure used partial information on the decision maker's value function and was designed for biobjective optimization problems. Later, @cite_36 extended this IPF measure, enabling it feasible for general @math -objective optimization problems. However, since the the form of the decision maker's value function was represented as a convex combination of objectives, only supported points in a solution set contribute to the IPF result. To address this issue, @cite_54 considered the weighted Tchebycheff function as the value function in IPF, which makes the evaluation result include the information of unsupported points. This modification introduces an additional parameter, the ideal point (for the calculation of the Tchebycheff function), which may affect the evaluation result to some extent.
@cite_36 @cite_54 @cite_32
2103640719 2002895030
We consider the problem of evaluating the quality of solution sets generated by heuristics for multiple-objective combinatorial optimization problems. We extend previous research on the integrated preference functional (IPF), which assigns a scalar value to a given discrete set of nondominated points so that the weighted Tchebycheff function can be used as the underlying implicit value function. This extension is useful because modeling the decision maker's value function with the weighted Tchebycheff function reflects the impact of unsupported points when evaluating sets of nondominated points. We present an exact calculation method for the IPF measure in this case for an arbitrary number of criteria. We show that every nondominated point has its optimal weight interval for the weighted Tchebycheff function. Accordingly, all nondominated points, and not only the supported points in a set, contribute to the value of the IPF measure when using the weighted Tchebycheff function. Two-and three-criteria numerical examples illustrate the desirable properties of the weighted Tchebycheff function, providing a richer measure than the original IPF based on a convex combination of objectives. We present the Integrated Preference Functional (IPF) for comparing the quality of proposed sets of near-pareto-optimal solutions to bi-criteria optimization problems. Evaluating the quality of such solution sets is one of the key issues in developing and comparing heuristics for multiple objective combinatorial optimization problems. The IPF is a set functional that, given a weight density function provided by a decision maker and a discrete set of solutions for a particular problem, assigns a numerical value to that solution set. This value can be used to compare the quality of different sets of solutions, and therefore provides a robust, quantitative approach for comparing different heuristic, a posteriori solution procedures for difficult multiple objective optimization problems. We provide specific examples of decision maker preference functions and illustrate the calculation of the resulting IPF for specific solution sets and a simple family of combined objectives.