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.
The HV indicator has good theoretical properties @cite_21 and can give a comprehensive evaluation of a solution set in terms of both convergence and diversity. While the computational complexity of calculating HV increases exponentially with the number of objectives, the Monte Carlo sampling method can provide a good balance between accuracy and running time @cite_44 @cite_13 . However, the HV indicator is sensitive to the choice of the reference point. How to choose a proper reference point is not trivial and different reference points can lead to inconsistent evaluation results @cite_38 . Take two solution sets ( @math and @math ) in Figure as an example. When the reference point is set to @math ( Figure (a) ), @math . When the reference point is @math ( Figure (b) ), @math .
@cite_44 @cite_38 @cite_21 @cite_13
2108968575 1521316934 2098907614 2009691097
In the field of evolutionary multi-criterion optimization, the hypervolume indicator is the only single set quality measure that is known to be strictly monotonic with regard to Pareto dominance: whenever a Pareto set approximation entirely dominates another one, then the indicator value of the dominant set will also be better. This property is of high interest and relevance for problems involving a large number of objective functions. However, the high computational effort required for hypervolume calculation has so far prevented the full exploitation of this indicator's potential; current hypervolume-based search algorithms are limited to problems with only a few objectives. This paper addresses this issue and proposes a fast search algorithm that uses Monte Carlo simulation to approximate the exact hypervolume values. The main idea is not that the actual indicator values are important, but rather that the rankings of solutions induced by the hypervolume indicator. In detail, we present HypE, a hypervolume estimation algorithm for multi-objective optimization, by which the accuracy of the estimates and the available computing resources can be traded off; thereby, not only do many-objective problems become feasible with hypervolume-based search, but also the runtime can be flexibly adapted. Moreover, we show how the same principle can be used to statistically compare the outcomes of different multi-objective optimizers with respect to the hypervolume----so far, statistical testing has been restricted to scenarios with few objectives. The experimental results indicate that HypE is highly effective for many-objective problems in comparison to existing multi-objective evolutionary algorithms. HypE is available for download at http: www.tik.ee.ethz.ch sop download supplementary hype . Evolutionary multiobjective optimization (EMO) boasts a proliferation of algorithms and benchmark problems. We need principled ways to compare the performance of different EMO algorithms, but this is complicated by the fact that the result of an EMO run is not a single scalar value, but a collection of vectors forming a nondominated set. Various metrics for nondominated sets have been suggested. We compare several, using the framework of 'outperformance relations' (Hansen and Jaszkiewicz, 1998). This enables us to criticize and contrast a variety of published metrics, leading to some recommendations on which seem most useful in practice. An important issue in multiobjective optimization is the quantitative comparison of the performance of different algorithms. In the case of multiobjective evolutionary algorithms, the outcome is usually an approximation of the Pareto-optimal set, which is denoted as an approximation set, and therefore the question arises of how to evaluate the quality of approximation sets. Most popular are methods that assign each approximation set a vector of real numbers that reflect different aspects of the quality. Sometimes, pairs of approximation sets are also considered. In this study, we provide a rigorous analysis of the limitations underlying this type of quality assessment. To this end, a mathematical framework is developed which allows one to classify and discuss existing techniques. Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.