On the quality of discrete representations in multiple objective programming

Stacey L. Faulkenberg1, Margaret M. Wiecek1
1Department of Mathematical Sciences, Clemson University, Clemson, USA

Tóm tắt

Within the past ten years, emphasis has been placed on generating discrete representations of the nondominated set which are truly representative of the nondominated set as a whole. This paper reviews measures for assessing the quality of discrete representations as well as exact solution methods that attempt to produce representations satisfying certain quality criteria. The measures are classified according to the aspect of the representation which they assess: cardinality, coverage, or spacing. The proposed solution methods are categorized according to whether a measure is integrated into the procedure a priori (before generation of solution points), a posteriori (after the generation of solution points), or not at all. The paper concludes with a comparative discussion of these three approaches and directions for future research.

Từ khóa


Tài liệu tham khảo

Armann R (1989) Solving multiobjective programming problems by discrete representation. Optimization 20:483–492 Benson HP, Sayin S (1997) Towards finding global representations of the efficient set in multiple objective optimization. Nav Res Logist 44:47–67 Berezkin VE, Kamenev GK, Lotov AV (2006) Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier. Comput Math Math Phys 46(11):1918–1931 Buchanan J, Gardiner L (2003) A comparison of two reference point methods in multiple objective mathematical programming. Eur J Oper Res 149:17–34 Churkina SY (2002) Search for efficient solutions of multi-criterion problems by target-level method. Comput Math Model 13(2):208–213 Collette Y, Siarry P (2005) Three new metrics to measure the convergence of metaheuristics towards the Pareto frontier and the aesthetic of a set of solution in biobjective optimization. Comput Oper Res 32:773–792 Czyżak P, Jaszkiewicz A (1998) Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. J Multi-Criteria Decis Anal 7:34–47 Das I, Dennis JE (1998) Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim 8(3):631–657 Deb K, Agrawal S, Pratap A, Meyarivan T (2002) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: PPSN VI: proceedings of the 6th international conference on parallel problems solving from nature. Springer, Berlin, pp 849–858 Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197 Ehrgott M, Wiecek MM (2005) Multiobjective programming. In: Multiple criteria decision analysis: state of the art surveys. Springer, Berlin, pp 667–722 Eichfelder G (2009a) An adaptive scalarization method in multiobjective optimization. SIAM J Optim 19(4):1694–1718 Eichfelder G (2009b) A constraint method in nonlinear multi-objective optimization. In: Multiobjective programming and goal programming: theoretical results and practical applications. Springer, Berlin, pp 3–12 Farhang-Mehr A, Azarm S (2003) An information-theoretic entropy metric for assessing multi-objective optimization solution set quality. J Mech Des 125:655–663 Fliege J (2004) Gap-free computation of Pareto-points by quadratic scalarization. Math Methods Oper Res 59:69–89 Fu Y, Diwekar UM (2004) An efficient sampling approach to multiobjective optimization. Ann Oper Res 132:109–134 Guddat J, Vasquez FG, Tammer K, Wendler K (1985) Multiobjective and stochastic optimization based on parametric optimization. Akademie Verlag, Berlin Hamacher HW, Pedersen CR, Ruzika S (2007) Finding representative systems for discrete bicriterion optimization problems. Oper Res Lett 35:336–344 Helbig S (1994) On a constructive approximation of the efficient outcomes in bicriterion vector optimization. J Global Optim 5:35–48 Karasakal E, Köksalan M (2009) Generating a representative subset of the efficient frontier in multiple criteria decision making. Oper Res 57(1):187–199 Kim IY, de Weck OL (2006) Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation. Struct Multidiscipl Optim 31:105–116 Kouvelis P, Sayin S (2006) Algorithm robust for the bicriteria discrete optimization problem. Ann Oper Res 147:71–85 Leung Y-W, Wang Y (2003) U-measure: A quality measure for multiobjective programming. IEEE Trans Syst Man Cybern, Part A, Syst Humans 33(3):337–343 Lotov AV, Bushenkov VA, Kamenev GK (2004) Interactive decision maps: approximation and visualization of Pareto frontier. Kluwer Academic, Norwell Masin M, Bukchin Y (2008) Diversity maximization approach for multiobjective optimization. Oper Res 56(2):411–424 Mattson CA, Mullur AA, Messac A (2004) Smart Pareto filter: Obtaining a minimal representation of multiobjective design space. Eng Optim 36(6):721–740 Meng H-Y, Zhang X-H, Liu S-Y (2005) New quality measures for multiobjective programming. Lect Notes Comput Sci 3611:1044–1048 Messac A, Ismail-Yahaya A, Mattson CA (2003) The normalized normal constraint method for generating the Pareto frontier. Struct Multidiscipl Optim 25:86–98 Messac A, Mattson CA (2002) Generating well-distributed sets of Pareto points for engineering design using physical programming. Optim Eng 3:431–450 Messac A, Mattson CA (2004) Normal constraint method with guarantee of even representation of complete Pareto frontier. AIAA J 42(10):2101–2111 Morse JN (1980) Reducing the size of the nondominated set: pruning by clustering. Comput Oper Res 7:55–66 Pascoletti A, Serafini P (1984) Scalarizing vector optimization problems. J Optim Theory Appl 42(4):499–524 Ruzika S (2007) On multiple objective combinatorial optimization. PhD thesis, University of Kaiserslautern Ruzika S, Wiecek MM (2005) Approximation methods in multiobjective programming. J Optim Theory Appl 126(3):473–501 Sayin S (2000) Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming. Math Program 87:543–560 Sayin S (2003) A procedure to find discrete representations of the efficient set with specified coverage errors. Oper Res 51(3):427–436 Sayin S, Kouvelis P (2005) The multiobjective discrete optimization problem: A weighted min-max two-stage optimization approach and a bicriteria algorithm. Manag Sci 51(10):1572–1581 Schott JR (1995) Fault tolerant design using single and multicriteria genetic algorithm optimization. Master’s thesis, Massachusetts Institute of Technology Shao L, Ehrgott M (2007) Finding representative nondominated points in multiobjective linear programming. In Proceedings of the 2007 IEEE symposium on computational intelligence in multicriteria decision making (MCDM 2007), pp 245–252 Steuer RE, Choo EU (1983) An interactive weighted Tchebycheff procedure for multiple objective programming. Math Program 26(3):326–344 Steuer RE, Harris FW (1980) Intra-set point generation and filtering in decision and criterion space. Comput Oper Res 7:41–53 Sylva J, Crema A (2007) A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs. Eur J Oper Res 180:1011–1027 Van Veldhuizen DA (1999) Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. PhD thesis, Air Force Institute of Technology Wu J, Azarm S (2001) Metrics for quality assessment of a multiobjective design optimization solution set. Trans ASME 123:18–25 Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of Technology Zitzler E, Knowles J, Thiele L (2008) Quality assessment of Pareto set approximations. In: Multiobjective optimization: interactive and evolutionary approaches. Springer, Berlin, pp 373–404 Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Parallel problem solving from nature—PPSN V. Springer, Berlin, pp 292–301