On the quality of discrete representations in multiple objective programming
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