Evaluation of Non-Dominated Solution Sets for Multiple Objective Optimization Problems


Abstract

One potential approach to solving multiple criteria optimization problems is to use an "a posteriori" method that approximates the efficient frontier. A common difficulty in this type of approach, however, is evaluating the quality of approximate solutions, since sets of multiple solutions are generated by "a posteriori" methods. This necessitates a robust measure to evaluate sets of non-dominated solutions. Furthermore, a robust measure could play an important role in metaheuristic optimization (i.e., evolutionary algorithms, simulated annealing, etc.) for "tuning" various parameters. This measure could also be used as a "stopping criteria" of such heuristics. Integrated Preference Functional (IPF) is presented for these purposes. 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. IPF is compared to that of other measures appearing in the literature through numerical experiments---specifically, we use two "a posteriori" solution techniques based on genetic algorithms for a bi-criteria parallel machine scheduling problem and evaluate their performance (in terms of solution quality) using different measures. Experimental results show that the IPF measure evaluates the solution quality of approximations robustly (i.e., similar to visual comparison results) while other alternative measures can misjudge the solution quality. The computational effort to obtain IPF is negligible for bi-criteria cases. For three or more (k) objective cases, however, the exact calculation of IPF is computationally demanding since this requires high (k) dimensional integration. We suggest a theoretical framework to obtain IPF for k (>= 3) objectives and build a durable exact method to obtain IPF mainly using the methods of convex-hull, extreme points enumeration, and triangulation of convex polytope in computational geometry. We also resort to a sampling method since the exact method is computationally expensive. A Monte Carlo approximation method of IPF is experimented and its performance is compared to the exact value of IPF. We find that the number of weight vectors in R^k needed to estimate IPF within a specific level of error ratio is independent to the number of objectives or number of non-dominated points in a set. The required number of weight vectors increases exponentially as the error ratio we would require decreases. Finally, we recommend a desirable number of weight vectors required to estimate IPF within 5% and 1% error ratio with 5% significance level.