An improved NSGA-III algorithm based on elimination operator for many-objective optimization
Tóm tắt
Due to the low selection pressure of the Pareto-dominance relation and the ineffectivity of diversity maintenance schemes in the environmental selection, the classical Pareto-dominance based multi-objective evolutionary algorithms (MOEAs) fail to handle many-objective optimization problems. The recently presented non-dominated sorting genetic algorithm III (NSGA-III) employs the uniformly distributed reference points to significantly promote population diversity, but the convergence based on the Pareto-dominance relation could still be enhanced. For this purpose, an improved NSGA-III algorithm based on elimination operator (NSGA-III-EO) is proposed. In the proposed algorithm, the elimination operator first identifies the reference point with maximum niche count and then employs the penalty-based boundary intersection distance to rank the individuals associated with it. To this end, the selection scheme is used to remove the worse individuals rather than to select the superior individuals. The proposed NSGA-III-EO is tested on a number of well-known benchmark problems with up to fifteen objectives and shows the competitive performance compared with five state-of-the-art MOEAs. Additionally, it is also tested on constrained problems having a large number of objectives and shows good performance.
Tài liệu tham khảo
Adra SF, Fleming PJ (2011) Diversity management in evolutionary many-objective optimization. IEEE Trans Evol Comput 15:183–195. doi:10.1109/Tevc.2010.2058117
Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19:45–76. doi:10.1162/Evco_a_00009
Bi X, Wang C (2016) An improved NSGA-III algorithm based on objective space decomposition for many-objective optimization. Soft Comput. doi:10.1007/s00500-016-2192-0
Cai L, Qu S, Yuan Y, Yao X (2015) A clustering-ranking method for many-objective optimization. Appl Soft Comput 35:681–694. doi:10.1016/j.asoc.2015.06.020
Carreno Jara E (2014) Multi-objective optimization by using evolutionary algorithms: the p-optimality criteria evolutionary computation. IEEE Trans. 18:167–179. doi:10.1109/TEVC.2013.2243455
Chand S, Wagner M (2015) Evolutionary many-objective optimization: a quick-start guide. Surv Oper Res Manag Sci 20:35–42. doi:10.1016/j.sorms.2015.08.001
Cheng J, Yen GG, Zhang G (2015) A many-objective evolutionary algorithm with enhanced mating and environmental selections. IEEE Trans Evol Comput 19:592–605. doi:10.1109/TEVC.2015.2424921
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:631–657
Deb K, Jain H (2014) 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:577–601. doi:10.1109/Tevc.2013.2281535
Deb K, Thiele L, Laumanns M, Zitzler E (2005) Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, Jain L, Goldberg R (eds) Evolutionary multiobjective optimization. Advanced information and knowledge processing. Springer, London, pp 105–145. doi:10.1007/1-84628-137-7_6
Freire H, Oliveira PBD, Pires EJS, Bessa M (2015) Many-objective optimization with corner-based search. Memet Comput 7:105–118. doi:10.1007/s12293-015-0151-4
Fu G, Kapelan Z, Kasprzyk JR, Reed P (2013) Optimal design of water distribution systems using many-objective visual analytics. J Water Resour Plan Manag 139:624–633
Gomez RH, Coello CAC (2015) Improved metaheuristic based on the R2 indicator for many-objective optimization. Paper presented at the Gecco’15: proceedings of the 2015 genetic and evolutionary computation conference, Madrid, Spain
He Z, Yen GG, Zhang J (2014) Fuzzy-based Pareto optimality for many-objective evolutionary algorithms. IEEE Trans Evol Comput 18:269–285. doi:10.1109/TEVC.2013.2258025
Huband S, Hingston P, Barone L, While L (2006) A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans Evol Comput 10:477–506. doi:10.1109/TEVC.2005.861417
Jain H, Deb K (2014) An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach. Part II: handling constraints and extending to an adaptive approach. IEEE Trans Evol Comput 18:602–622. doi:10.1109/Tevc.2013.2281534
Joshi R, Deshpande B (2014) Empirical and analytical study of many-objective optimization problems: analysing distribution of nondominated solutions and population size for scalability of randomized heuristics. Memet Comput 6:133–145. doi:10.1007/s12293-014-0133-y
Li K, Deb K, Zhang Q, Kwong S (2015) An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans Evol Comput 19:694–716. doi:10.1109/TEVC.2014.2373386
Li M, Yang S, Liu X (2014) Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Trans Evol Comput 18:348–365. doi:10.1109/TEVC.2013.2262178
Lygoe R, Cary M, Fleming P (2013) A real-world application of a many-objective optimisation complexity reduction process. In: Purshouse R, Fleming P, Fonseca C, Greco S, Shaw J (eds) Evolutionary multi-criterion optimization, vol 7811. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, pp 641-655. doi:10.1007/978-3-642-37140-0_48
Sato H (2015) Analysis of inverted PBI and comparison with other scalarizing functions in decomposition based MOEAs. J Heuristics 21:819–849. doi:10.1007/s10732-015-9301-6
Starkey A, Hagras H, Shakya S, Owusu G, Mohamed A, Alghazzawi D (2016) A cloud computing based many objective type-2 fuzzy logic system for mobile field workforce area optimization. Memet Comput 8:269–286. doi:10.1007/s12293-016-0206-1
Trivedi A, Srinivasan D, Sanyal K, Ghosh A (2016) A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Trans Evol Comput. doi:10.1109/TEVC.2016.2608507
While L, Bradstreet L, Barone L (2012) A fast way of calculating exact hypervolumes. IEEE Trans Evol Comput 16:86–95. doi:10.1109/TEVC.2010.2077298
Xiang Y, Zhou Y, Li M, Chen Z (2017) A vector angle-based evolutionary algorithm for unconstrained many-objective optimization. IEEE Trans Evol Comput 21:131–152. doi:10.1109/TEVC.2016.2587808
Yang S, Li M, Liu X, Zheng J (2013) A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 17:721–736. doi:10.1109/TEVC.2012.2227145
Yuan Y, Xu H, Wang B, Yao X (2016) A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 20:16–37. doi:10.1109/TEVC.2015.2420112
Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731. doi:10.1109/TEVC.2007.892759
Zhang X, Tian Y, Jin Y (2016) Approximate non-dominated sorting for evolutionary many-objective optimization. Inf Sci 369:14–33. doi:10.1016/j.ins.2016.06.007
Zhang XY, Tian Y, Jin YC (2015) A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 19:761–776. doi:10.1109/Tevc.2014.2378512
Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271. doi:10.1109/4235.797969
Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7:117–132. doi:10.1109/TEVC.2003.810758