×

zbMATH — the first resource for mathematics

Domination measure: a new metric for solving multiobjective optimization. (English) Zbl 07290863
Summary: For general multiobjective optimization problems, the usual goal is finding the set of solutions not dominated by any other solutions, that is, a set of solutions as good as any other solution in all objectives and strictly better in at least one objective. In this paper, we propose a novel performance metric called the domination measure to measure the quality of a solution, which can be intuitively interpreted as the probability that an arbitrary solution in the solution space dominates that solution with respect to a predefined probability measure. We then reformulate the original problem as a stochastic and single-objective optimization problem. We further propose a model-based approach to solve it, which leads to an ideal version algorithm and an implementable version algorithm. We show that the ideal version algorithm converges to a set representation of the global optima of the reformulated problem; we demonstrate the numerical performance of the implementable version algorithm by comparing it with numerous existing multiobjective optimization methods on popular benchmark test functions. The numerical results show that the proposed approach is effective in generating a finite and uniformly spread approximation of the Pareto optimal set of the original multiobjective problem and is competitive with the tested existing methods. The concept of domination measure opens the door for potentially many new algorithms, and our proposed algorithm is an instance that benefits from domination measure.
The online supplement is available at https://doi.org/10.1287/ijoc.2019.0920.
MSC:
90C Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Auger A, Bader J, Brockhoff D, Zitzler E (2012) Hypervolume-based multiobjective optimization: theoretical foundations and practical implications. Theoret. Comput. Sci. 425(March):75-103.Crossref, Google Scholar · Zbl 1242.90205
[2] Bader J, Zitzler E (2011) Hype: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1):45-76.Crossref, Google Scholar
[3] Bader J, Deb K, Zitzler E (2010) Faster hypervolume-based search using Monte Carlo sampling. Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems (Springer, New York), 313-326.Crossref, Google Scholar · Zbl 1184.90147
[4] Bekker J, Aldrich C (2011) The cross-entropy method in multi-objective optimisation: An assessment. Eur. J. Oper. Res. 211(1):112-121.Crossref, Google Scholar · Zbl 1218.90177
[5] Beume N, Naujoks B, Emmerich M (2007) Sms-emoa: Multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3):1653-1669.Crossref, Google Scholar · Zbl 1123.90064
[6] Bhatia SK (2004) Adaptive k-means clustering. Barr V, Markov Z, eds. Proc. 17th Internat. Florida Artificial Intelligence Res. Soc. Conf. (AAAI Press, Menlo Park, CA), 695-699.Google Scholar
[7] Coello CAC, Van Veldhuizen DA, Lamont GB (2002) Evolutionary Algorithms for Solving Multi-Objective Problems, vol. 242 (Springer, New York).Crossref, Google Scholar
[8] Corne DW, Jerram NR, Knowles JD, Oates MJ (2001) Pesa-ii: region-based selection in evolutionary multiobjective optimization. Aguirre H, ed. Proc. Genetic Evolutionary Comput. Conf. (GECCO’2001) (ACM, New York).Google Scholar
[9] Custódio AL, Madeira JA, Vaz AIF, Vicente LN (2011) Direct multisearch for multiobjective optimization. SIAM J. Optim. 21(3):1109-1140.Crossref, Google Scholar · Zbl 1230.90167
[10] Deb K (2001) Multi-Objective Optimization Using Evolutionary Algorithms, vol. 16 (John Wiley & Sons, Hoboken, NJ).Google Scholar
[11] Feldman G, Hunter SR, Pasupathy R (2015) Multi-objective simulation optimization on finite sets: optimal allocation via scalarization. 2015 Winter Simulation Conf. (WSC) (IEEE Press, Piscataway, NJ), 3610-3621.Google Scholar
[12] Fleischer M (2003) The measure of Pareto optima applications to multi-objective metaheuristics. Evolutionary Multi-Criterion Optimization (Springer, New York), 519-533.Crossref, Google Scholar · Zbl 1036.90530
[13] Hu J, Fu MC, Marcus SI (2007) A model reference adaptive search method for global optimization. Oper. Res. 55(3):549-568.Link, Google Scholar · Zbl 1167.90690
[14] Huband S, Hingston P, Barone L, While L (2006) A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evolutionary Comput. 10(5):477-506.Crossref, Google Scholar
[15] Kim M, Hiroyasu T, Miki M, Watanabe S (2004) SPEA2+: Improving the performance of the strength Pareto evolutionary algorithm 2. Parallel Problem Solving from Nature-PPSN VIII (Springer, New York), 742-751.Crossref, Google Scholar
[16] Köksalan M, Phelps S (2007) An evolutionary metaheuristic for approximating preference-nondominated solutions. INFORMS J. Comput. 19(2):291-301.Link, Google Scholar · Zbl 1241.90114
[17] Le Riche R, Saouab A, Bréard J (2003) Coupled compression rtm and composite layup optimization. Compos. Sci. Tech. 63(15):2277-2287.Crossref, Google Scholar
[18] Lee LH, Chew EP, Teng S, Chen Y (2008) Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem. Eur. J. Oper. Res. 189(2):476-491.Crossref, Google Scholar · Zbl 1149.90355
[19] Lee LH, Chew EP, Teng S, Goldsman D (2010) Finding the non-dominated pareto set for multi-objective simulation models. IIE Trans. 42(9):656-674.Crossref, Google Scholar
[20] Mete HO, Zabinsky ZB (2014) Multiobjective interacting particle algorithm for global optimization. INFORMS J. Comput. 26(3):500-513.Link, Google Scholar · Zbl 1304.90189
[21] Minella G, Ruiz R, Ciavotta M (2008) A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS J. Comput. 20(3):451-471.Link, Google Scholar · Zbl 1243.90069
[22] Molina J, Laguna M, Martí R, Caballero R (2007) Sspmo: A scatter tabu search procedure for non-linear multiobjective optimization. INFORMS J. Comput. 19(1):91-100.Link, Google Scholar · Zbl 1241.90137
[23] Nam D, Park CH (2000) Multiobjective simulated annealing: A comparative study to evolutionary algorithms. Internat. J. Fuzzy Systems 2(2):87-97.Google Scholar
[24] Pal M, Bandyopadhyay S (2016) Reliability of convergence metric and hypervolume indicator for many-objective optimization. 2016 2nd Internat. Conf. Control, Instrumentation, Energy & Comm. (CIEC) (IEEE, Piscataway, NJ), 511-515.Google Scholar
[25] Qasem SN, Shamsuddin SM (2011) Radial basis function network based on time variant multi-objective particle swarm optimization for medical diseases diagnosis. Appl. Soft Comput. 11(1):1427-1438.Crossref, Google Scholar
[26] Rubinstein RY (2001) Combinatorial optimization, cross-entropy, ants and rare events. Uryasev S, Pardalos PM, eds. Stochastic Optimization: Algorithms and Applications (Springer, New York), 303-363.Google Scholar · Zbl 0984.90037
[27] Santiago A, Huacuja HJF, Dorronsoro B, Pecero JE, Santillan CG, Barbosa JJG, Monterrubio JCS (2014) A survey of decomposition methods for multi-objective optimization. Castillo O, Melin P, Pedrycz W, Kacprzyk J, eds. Recent Advances on Hybrid Approaches for Designing Intelligent Systems (Springer, New York), 453-465.Google Scholar
[28] Toffolo A, Lazzaretto A (2002) Evolutionary algorithms for multi-objective energetic and economic optimization in thermal system design. Energy 27(6):549-567.Crossref, Google Scholar
[29] Unveren A, Acan A (2007) Multi-objective optimization with cross entropy method: stochastic learning with clustered pareto fronts. 2007 IEEE Congress on Evolutionary Comput. (IEEE Press, Piscataway, NJ), 3065-3071.Google Scholar
[30] Zabinsky ZB (2013) Stochastic Adaptive Search for Global Optimization, vol. 72. (Springer, New York).Google Scholar
[31] Zhou E, Hu J (2014) Gradient-based adaptive stochastic search for non-differentiable optimization. IEEE Trans. Automat. Control. 59(7):1818-1832.Crossref, Google Scholar · Zbl 1360.90295
[32] Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. Eiben AE, Bäck T, Schoenauer M, Schwefel H-P, eds. Internat. Conf. Parallel Problem Solving Nature (Springer, New York), 292-301.Crossref, Google Scholar
[33] Zitzler E, Brockhoff D, Thiele L (2007) The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. Trautmann H, Rudolph G, Klamroth K, Schütze O, Wiecek M, Jin Y, Grimme C, eds. Evolutionary Multi-Criterion Optimization (Springer, New York), 862-876.Google Scholar
[34] Zitzler E,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.