×

An ensemble approach with external archive for multi- and many-objective optimization with adaptive mating mechanism and two-level environmental selection. (English) Zbl 1484.90103

Summary: Based on mating and environmental selections employed, multi-objective evolutionary algorithms (MOEAs) are classified as Pareto-based, decomposition-based and indicator-based approaches that are associated with their own advantages and disadvantages. To benefit from the advantages of different MOEAs, we propose an ensemble framework (ENMOEA) in which mating and environmental selections of diverse MOEAs are combined. ENMOEA is a single-population competitive ensemble, where resource allocation to individual mating operators is done adaptively. In addition, ENMOEA employs a two-level environmental selection where constituent environmental selection operators are first applied to label solutions as “selected” and “non-selected”. Solutions “selected” by most operators are preferred for future evolution. An external archive is employed to facilitate effective usage of function evaluations and achieve a better comprise between convergence and diversity. To demonstrate generality of ENMOEA, we developed two variants: 1) specific case (\(\mathrm{ENMOEA_S}\) – combines different Pareto-based MOEAs) and 2) general case (\(\mathrm{ENMOEA_G}\) – combines Pareto-based, indicator-based and decomposition-based MOEAs). From simulation results on various test suites (DTLZ, WFG and 16 real-world problems), it is evident that ENMOEA is robust to the parameters of the constituent algorithms. In addition, it is evident that the effectiveness of ensemble improves with the diversity of the constituent algorithms.

MSC:

90C29 Multi-objective and goal programming
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming

Software:

MOEA/D; PlatEMO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Li, B.; Li, J.; Tang, K.e.; Yao, X., Many-objective evolutionary algorithms: a survey, ACM Comput. Surv. (CSUR), 48, 1, 1-35 (2015)
[2] Zhang, X.; Tian, Y.e.; Jin, Y., A knee point-driven evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 19, 6, 761-776 (2015)
[3] Palakonda, V.; Mallipeddi, R., Pareto dominance-based algorithms with ranking methods for many-objective optimization, IEEE Access, 5, 11043-11053 (2017)
[4] Li, M.; Yang, S.; Liu, X., Bi-goal evolution for many-objective optimization problems, Artif. Intell., 228, 45-65 (2015) · Zbl 1346.90741
[5] Yang, S.; Li, M.; Liu, X.; Zheng, J., A grid-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 17, 5, 721-736 (2013)
[6] 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)
[7] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 712-731 (2007)
[8] Elarbi, M.; Bechikh, S.; Gupta, A.; Said, L. B.; Ong, Y.-S., A new decomposition-based NSGA-II for many-objective optimization, IEEE Trans. Syst., Man, Cybernet.: Syst., 48, 1191-1210 (2017)
[9] Ma, X.; Yu, Y.; Li, X.; Qi, Y.; Zhu, Z., A survey of weight vector adjustment methods for decomposition based multi-objective evolutionary algorithms, IEEE Trans. Evol. Comput., 24, 4, 634-649 (2020)
[10] Pamulapati, T.; Mallipeddi, R.; Suganthan, P. N., ISDE+-an indicator for multi and many-objective optimization, IEEE Trans. Evol. Comput., 23, 346-352 (2019)
[11] Wang, R.; Purshouse, R. C.; Fleming, P. J., Preference-inspired co-evolutionary algorithms using weight vectors, Eur. J. Oper. Res., 243, 2, 423-441 (2015) · Zbl 1346.90755
[12] Li, M.; Yang, S.; Liu, X., Pareto or non-Pareto: Bi-criterion evolution in multiobjective optimization, IEEE Trans. Evol. Comput., 20, 5, 645-665 (2016)
[13] Laumanns, M.; Thiele, L.; Deb, K.; Zitzler, E., Combining convergence and diversity in evolutionary multiobjective optimization, Evol. Comput., 10, 3, 263-282 (2002)
[14] Wang, G.; Jiang, H., Fuzzy-dominance and its application in evolutionary many objective optimization, (Computational Intelligence and Security Workshops, 2007. CISW 2007. International Conference on (2007)), 195-198
[15] Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 1, 16-37 (2016)
[16] Falcón-Cardona, G.; Coello, C. A.C., Indicator-based multi-objective evolutionary algorithms: a comprehensive survey, ACM Comput. Surv. (CSUR), 53, 2, 1-35 (2020)
[17] Mallipeddi, R.; Suganthan, P. N., Ensemble of constraint handling techniques, IEEE Trans. Evol. Comput., 14, 4, 561-579 (2010)
[18] Wang, W.; Yang, S.; Lin, Q.; Zhang, Q.; Wong, K.-C.; Coello, C. A.C., An effective ensemble framework for multi-objective optimization, IEEE Trans. Evol. Comput. (2018)
[19] Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes, IEEE Trans. Evol. Comput., 16, 3, 442-446 (2012)
[20] Soria-Alcaraz, J. A.; Ochoa, G.; Sotelo-Figeroa, M. A.; Burke, E. K., A methodology for determining an effective subset of heuristics in selection hyper-heuristics, Eur. J. Oper. Res., 260, 3, 972-983 (2017) · Zbl 1403.90658
[21] Zhou, Y.; Wang, J.; Chen, J.; Gao, S.; Teng, L., Ensemble of many-objective evolutionary algorithms for many-objective problems, Soft. Comput., 21, 2407-2419 (2017)
[22] Praditwong, K.; Yao, X., A new multi-objective evolutionary optimisation algorithm: the two-archive algorithm, (International Conference on Computational Intelligence and Security (2006)), 286-291
[23] Wang, H.; Jiao, L.; Yao, X., Two_Arch2: an improved two-archive algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 19, 524-541 (2014)
[24] Ding, R.; Dong, H.; He, J.; Li, T., A novel two-archive strategy for evolutionary many-objective optimization algorithm based on reference points, Appl. Soft Comput., 78, 447-464 (2019)
[25] Cai, X.; Li, Y.; Fan, Z.; Zhang, Q., An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization, IEEE Trans. Evol. Comput., 19, 508-523 (2014)
[26] Wolpert, D. H.; Macready, W. G., No free lunch theorems for optimization, (IEEE Transactions on Evolutionary Computation (1997)), 67-82
[27] Li, K.; Fialho, A.; Kwong, S.; Zhang, Q., Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 18, 1, 114-130 (2014)
[28] Lin, Q.; Liu, Z.; Yan, Q.; Du, Z.; Coello, C. A.C.; Liang, Z.; Wang, W.; Chen, J., Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm, Inf. Sci., 339, 332-352 (2016)
[29] Qi, Y.; Hou, Z.; Yin, M.; Sun, H.; Huang, J., An immune multi-objective optimization algorithm with differential evolution inspired recombination, Appl. Soft Comput., 29, 395-410 (2015)
[30] Shim, V. A.; Tan, K. C.; Tang, H., Adaptive memetic computing for evolutionary multiobjective optimization, IEEE Trans. Cybern., 45, 4, 610-621 (2015)
[31] Lin, Q.; Chen, J.; Zhan, Z.-H.; Chen, W.-N.; Coello, C. A.C.; Yin, Y., A hybrid evolutionary immune algorithm for multiobjective optimization problems, IEEE Trans. Evol. Comput., 20, 711-729 (2015)
[32] Zhu, Q.; Lin, Q.; Du, Z.; Liang, Z.; Wang, W.; Zhu, Z.; Chen, J.; Huang, P.; Ming, Z., A novel adaptive hybrid crossover operator for multiobjective evolutionary algorithm, Inf. Sci., 345, 177-198 (2016)
[33] Gonçalves, R. A.; Almeida, C. P.; Pavelski, L. M.; Venske, S. M.; Kuk, J. N.; Pozo, A. T., Adaptive operator selection in NSGA-III, (2016 5th Brazilian Conference on Intelligent Systems (BRACIS) (2016)), 181-186
[34] Kuk, J.; Goncalves, R.; Almeida, C.; Venske, S.; Pozo, A., A new adaptive operator selection for NSGA-III applied to CEC 2018 many-objective benchmark, (2018 7th Brazilian Conference on Intelligent Systems (BRACIS) (2018)), 7-12
[35] Al Moubayed, N.; Petrovski, A.; McCall, J., D2MOPSO: MOPSO based on decomposition and dominance with archiving using crowding distance in objective and solution spaces, Evol. Comput., 22, 1, 47-77 (2014)
[36] Ke, L.; Zhang, Q.; Battiti, R., Hybridization of decomposition and local search for multiobjective optimization, IEEE Trans. Cybern., 44, 1808-1820 (2014)
[37] Li, K.; Deb, K.; Zhang, Q.; Kwong, S., An evolutionary many-objective optimization algorithm based on dominance and decomposition, IEEE Trans. Evol. Comput., 19, 5, 694-716 (2015)
[38] Cai, L.; Qu, S.; Cheng, G., Two-archive method for aggregation-based many-objective optimization, Inf. Sci., 422, 305-317 (2018)
[39] Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 5, 477-506 (2006)
[40] Tanabe, R.; Ishibuchi, H., An easy-to-use real-world multi-objective optimization problem suite, Appl. Soft Comput., 89, Article 106078 pp. (2020)
[41] Deb, K.; Agrawal, R. B., Simulated binary crossover for continuous search space, Complex Syst., 9, 115-148 (1995) · Zbl 0843.68023
[42] Deb, K.; Goyal, M., A combined genetic adaptive search (GeneAS) for engineering design, Comput. Sci. Inf., 26, 30-45 (1996)
[43] While, L.; Hingston, P.; Barone, L.; Huband, S., A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Comput., 10, 1, 29-38 (2006)
[44] D.A. Van Veldhuizen, G.B. Lamont, Multiobjective evolutionary algorithm research: A history and analysis, Citeseer (1998).
[45] Wang, Y.-N.; Wu, L.-H.; Yuan, X.-F., Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure, Soft. Comput., 14, 3, 193-209 (2010)
[46] Tian, Y.; Cheng, R.; Zhang, X.; Jin, Y., PlatEMO: a MATLAB platform for evolutionary multi-objective optimization [Educational Forum], IEEE Comput. Intell. Mag., 12, 4, 73-87 (2017)
[47] Li, B.; Tang, K.; Li, J.; Yao, X., Stochastic ranking algorithm for many-objective optimization based on multiple indicators, IEEE Trans. Evol. Comput., 20, 6, 924-938 (2016)
[48] Li, M.; Yang, S.; Liu, X., Shift-based density estimation for Pareto-based algorithms in many-objective optimization, IEEE Trans. Evol. Comput., 18, 3, 348-365 (2014)
[49] Xiang, Y.; Zhou, Y.; Li, M.; Chen, Z., A vector angle-based evolutionary algorithm for unconstrained many-objective optimization, IEEE Trans. Evol. Comput., 21, 1, 131-152 (2017)
[50] Gee, S. B.; Tan, K. C.; Shim, V. A.; Pal, N. R., Online diversity assessment in evolutionary multiobjective optimization: a geometrical perspective, IEEE Trans. Evol. Comput., 19, 4, 542-559 (2015)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.