×

zbMATH — the first resource for mathematics

A reference point-based evolutionary algorithm for approximating regions of interest in multiobjective problems. (English) Zbl 1446.90141
Summary: Most evolutionary multiobjective optimization algorithms are designed to approximate the entire Pareto front. During the last decade, a series of preference-based evolutionary algorithms have been developed, where a part of the Pareto front is approximated by incorporating the preferences of a Decision Maker. However, only a few such algorithms are able to obtain well-distributed solutions covering the complete “region of interest” that is determined by a reference point. In this paper, a preference-based evolutionary algorithm for approximating the region of interest is proposed. It is based on the state-of-the-art genetic algorithm NSGA-II and the CHIM approach introduced in the NBI method which is used to obtain uniformly distributed solutions in the region of interest. The efficiency of the proposed algorithm has been experimentally evaluated and compared to other state-of-the-art multiobjective preference-based evolutionary algorithms by solving a set of multiobjective optimization benchmark problems. It has been shown that the incorporation of the Decision Maker’s preferences and the CHIM approach into the NSGA-II algorithm allows approximating the whole region of interest accurately while maintaining a good distribution of the obtained solutions.
MSC:
90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
68W25 Approximation algorithms
90C59 Approximation methods and heuristics in mathematical programming
Software:
E-NAUTILUS; MOEA/D; NBI
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrawal, RB; Deb, K.; Agrawal, R., Simulated binary crossover for continuous search space, Complex Syst, 9, 2, 115-148 (1995) · Zbl 0843.68023
[2] Bechikh, S.; Kessentini, M.; Said, LB; Ghédira, K., Chapter Four—Preference incorporation in evolutionary multiobjective optimization: a survey of the state-of-the-art, Adv Comput, 98, 141-207 (2015)
[3] Benson, HP; Sayin, S., Towards finding global representations of the efficient set in multiple objective mathematical programming, Nav Res Logist, 44, 1, 47-67 (1997) · Zbl 0882.90116
[4] Branke, J., MCDA and multiobjective evolutionary algorithms. Multiple criteria decision analysis, 977-1008 (2016), New York: Springer, New York
[5] Cabello, J.; Luque, M.; Miguel, F.; Ruiz, A.; Ruiz, F., A multiobjective interactive approach to determine the optimal electricity mix in Andalucía (Spain), Top, 22, 1, 109-127 (2014) · Zbl 1298.90045
[6] Coello, CAC; Van Veldhuizen, DA; Lamont, GB, Evolutionary algorithms for solving multi-objective problems (2002), New York: Springer, New York
[7] Das, I.; Dennis, JE, Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J Optim, 8, 3, 631-657 (1998) · Zbl 0911.90287
[8] Deb, K., Multi-objective genetic algorithms: problem difficulties and construction of test problems, Evol Comput, 7, 205-230 (1999)
[9] Deb, K., Multi-objective optimization using evolutionary algorithms (2001), New York: Wiley, New York · Zbl 0970.90091
[10] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints, IEEE Trans Evol Comput, 18, 4, 577-601 (2014)
[11] Deb K, Kumar A (2007) Interactive evolutionary multi-objective optimization and decision-making using reference direction method. In: Proceedings of the 9th annual conference on genetic and evolutionary computation, ACM, pp 781-788
[12] Deb K, Pratap A, Agarwal S, Meyarivan T (2002a) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182-197
[13] Deb K, Thiele L, Laumanns M, Zitzler E (2002b) Scalable multi-objective optimization test problems. In: Proceedings of the 2002 congress on evolutionary computation, CEC’02, pp 825-830, IEEE
[14] Deb, K.; Sundar, J.; Udaya Bhaskara Rao, N.; Chaudhuri, S., Reference point based multi-objective optimization using evolutionary algorithms, Int J Comput Intell Res, 2, 3, 273-286 (2006)
[15] Deb K, Siegmund F, Ng AH (2014) R-HV: a metric for computing hyper-volume for reference point based EMOs. In: International conference on swarm, evolutionary, and memetic computing, Springer, pp 98-110
[16] Figueira, JR; Liefooghe, A.; Talbi, EG; Wierzbicki, AP, A parallel multiple reference point approach for multi-objective optimization, Eur J Oper Res, 205, 2, 390-400 (2010) · Zbl 1188.90237
[17] Filatovas, E.; Kurasova, O.; Sindhya, K., Synchronous R-NSGA-II: an extended preference-based evolutionary algorithm for multi-objective optimization, Informatica, 26, 1, 33-50 (2015)
[18] Filatovas E, Kurasova O, Redondo JL, Fernández J (2016) A preference-based multi-objective evolutionary algorithm for approximating a region of interest. In: XIII Globall optimizatin workshop, GOW’16, pp 21-24
[19] Filatovas, E.; Lančinskas, A.; Kurasova, O.; Žilinskas, J., A preference-based multi-objective evolutionary algorithm R-NSGA-II with stochastic local search, Cent Eur J Oper Res, 25, 4, 859-878 (2017) · Zbl 1390.90582
[20] Fonseca CM, Fleming PJ et al (1993) Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: ICGA, vol 93, Morgan Kaufmann Publishers Inc., pp 416-423
[21] Hong, W.; Tang, K., Convex hull-based multi-objective evolutionary computation for maximizing receiver operating characteristics performance, Memet Comput, 8, 1, 35-44 (2016)
[22] Hong W, Lu G, Yang P, Wang Y, Tang K (2015) A new evolutionary multi-objective algorithm for convex hull maximization. In: IEEE Congress on evolutionary computation, CEC’15, pp 931-938, IEEE
[23] Karasakal, E.; Silav, A., A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage, Top, 24, 1, 206-232 (2016) · Zbl 1338.90373
[24] Korhonen, PJ; Laakso, J., A visual interactive method for solving the multiple criteria problem, Eur J Oper Res, 24, 2, 277-287 (1986) · Zbl 0581.90088
[25] Kurasova, O.; Petkus, T.; Filatovas, E., Visualization of Pareto front points when solving multi-objective optimization problems, Inf Technol Control, 42, 4, 353-361 (2013)
[26] Lam, JSL, An integrated approach for port selection, ship scheduling and financial analysis, Netnomics Econ Res Electron Netw, 11, 1, 33-46 (2010)
[27] Li, K.; Deb, K., Performance assessment for preference-based evolutionary multi-objective optimization using reference points, COIN Rep, 1, 1, 1-23 (2016)
[28] Li L, Yevseyeva I, Basto-Fernandes V, Trautmann H, Jing N, Emmerich M (2017) Building and using an ontology of preference-based multiobjective evolutionary algorithms. In: International conference on evolutionary multi-criterion optimization, pp 406-421
[29] Messac, A.; Mattson, CA, Normal constraint method with guarantee of even representation of complete Pareto frontier, AIAA J, 42, 10, 2101-2111 (2004)
[30] Messac, A.; Ismail-Yahaya, A.; Mattson, CA, The normalized normal constraint method for generating the Pareto frontier, Struct Multidiscip Optim, 25, 2, 86-98 (2003) · Zbl 1243.90200
[31] Miettinen, K., Nonlinear multiobjective optimization (1999), New York: Springer, New York · Zbl 0949.90082
[32] Mohammadi A, Omidvar MN, Li X (2013) A new performance metric for user-preference based multi-objective evolutionary algorithms. In: 2013 IEEE Congress on evolutionary computation (CEC), pp 2825-2832
[33] Molina, J.; Santana, LV; Hernández-Díaz, AG; Coello Coello, CA; Caballero, R., g-dominance: Reference point based dominance for multiobjective metaheuristics, Eur J Oper Res, 197, 2, 685-692 (2009) · Zbl 1159.90424
[34] Moreno, J.; Ortega, G.; Filatovas, E.; Martínez, JA; Garzón, EM, Improving the performance and energy of non-dominated sorting for evolutionary multiobjective optimization on GPU/CPU platforms, J Glob Optim, 71, 3, 631-649 (2018) · Zbl 1402.90172
[35] Motta, RS; Afonso, SM; Lyra, PR, A modified NBI and NC method for the solution of N-multiobjective optimization problems, Struct Multidiscip Optim, 46, 2, 239-259 (2012) · Zbl 1274.90370
[36] Ortega, G.; Filatovas, E.; Garzón, E.; Casado, LG, Non-dominated sorting procedure for Pareto dominance ranking on multicore CPU and/or GPU, J Glob Optim, 69, 3, 607-627 (2017) · Zbl 1382.90099
[37] Petkus, T.; Filatovas, E.; Kurasova, O., Investigation of human factors while solving multiple criteria optimization problems in computer network, Technol Econ Dev Econ, 15, 3, 464-479 (2009)
[38] Purshouse RC, Deb K, Mansor MM, Mostaghim S, Wang R (2014) A review of hybrid evolutionary multiple criteria decision making methods. In: 2014 IEEE Congress on evolutionary computation, CEC’14), pp 1147-1154, IEEE
[39] Redondo, J.; Fernández, J.; Álvarez, J.; Arrondo, A.; Ortigosa, P., Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem, Comput Oper Res, 62, 1, 337-349 (2015) · Zbl 1348.90413
[40] Roy PC, Islam MM, Deb K (2016) Best order sort: a new algorithm to non-dominated sorting for evolutionary multi-objective optimization. In: Proceedings of the 2016 on genetic and evolutionary computation conference companion, pp 1113-1120, ACM
[41] Ruiz AB, Saborido R, Luque M (2015a) A preference-based evolutionary algorithm for multiobjective optimization: the weighting achievement scalarizing function genetic algorithm. J Glob Optim 62(1):101-129 · Zbl 1329.90132
[42] Ruiz AB, Sindhya K, Miettinen K, Ruiz F, Luque M (2015b) E-NAUTILUS: a decision support system for complex multiobjective optimization problems based on the NAUTILUS method. Eur J Oper Res 246(1):218-231 · Zbl 1346.90751
[43] Said, LB; Bechikh, S.; Ghédira, K., The r-dominance: a new dominance relation for interactive evolutionary multicriteria decision making, IEEE Trans Evol Comput, 14, 5, 801-818 (2010)
[44] Santos, J.; Ferreira, A.; Flintsch, G., A multi-objective optimization-based pavement management decision-support system for enhancing pavement sustainability, J Clean Prod, 164, 1380-1393 (2017)
[45] Shao, L.; Ehrgott, M., Discrete representation of non-dominated sets in multi-objective linear programming, Eur J Oper Res, 255, 3, 687-698 (2016) · Zbl 1394.90519
[46] Siddiqui, S.; Azarm, S.; Gabriel, SA, On improving normal boundary intersection method for generation of Pareto frontier, Struct Multidiscip Optim, 46, 6, 839-852 (2012) · Zbl 1274.90363
[47] Siegmund F, Ng AH, Deb K (2012) Finding a preferred diverse set of Pareto-optimal solutions for a limited number of function calls. In: 2012 IEEE Congress on evolutionary computation, CEC’12, pp 1-8
[48] Talbi, EG, Metaheuristics: from design to implementation (2009), New York: Wiley, New York
[49] Tang S, Cai Z, Zheng J (2008) A fast method of constructing the non-dominated set: Arena’s principle. In: Fourth international conference on natural computation, ICNC’08, vol 1, pp 391-395, IEEE
[50] Thiele, L.; Miettinen, K.; Korhonen, PJ; Molina, J., A preference-based evolutionary algorithm for multi-objective optimization, Evol Comput, 17, 3, 411-436 (2009)
[51] Wickramasinghe UK, Carrese R, Li X (2010) Designing airfoils using a reference point based evolutionary many-objective particle swarm optimization algorithm. In: 2010 IEEE Congress on evolutionary computation, CEC’10, pp 1-8
[52] Yuan, X.; Tian, H.; Yuan, Y.; Huang, Y.; Ikram, RM, An extended NSGA-III for solution multi-objective hydro-thermal-wind scheduling considering wind power cost, Energy Convers Manag, 96, 568-578 (2015)
[53] Zapotecas Martínez S, Coello Coello CA (2010) a novel diversification strategy for multi-objective evolutionary algorithms. In: Proceedings of the 12th annual conference companion on genetic and evolutionary computation, GECCO’10, pp 2031-2034. ACM, New York, NY, USA
[54] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans Evol Comput, 11, 6, 712-731 (2007)
[55] Zhang, X.; Ye, T.; Cheng, R.; Jin, Y., An efficient approach to non-dominated sorting for evolutionary multi-objective optimization, IEEE Trans Evol Comput, 19, 2, 201-213 (2012)
[56] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, CM; Da Fonseca, VG, Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans Evol Comput, 7, 2, 117-132 (2003)
[57] Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Parallel problem solving from nature—PPSN V, Springer, pp 292-301
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.