A decomposition based multiobjective evolutionary algorithm with self-adaptive mating restriction strategy

Xin Li1, Hu Zhang2, Shenmin Song1
1Center for Control Theory and Guidance Technology, Harbin Institute of Technology, Harbin, China
2Beijing Electro-Mechanical Engineering Institute, Beijing, China

Tóm tắt

MOEA/D decomposes the multiobjective optimization problem into a number of subproblems. However, one subproblem’s requirement for exploitation and exploration varies with the evolutionary process. Furthermore, different subproblems’ requirements for exploitation and exploration are also different as the subproblems have been solved in distinct degree. This paper proposes a decomposition based multiobjective evolutionary algorithm with self-adaptive mating restriction strategy (MOEA/D-MRS). Considering the distinct solved degree of the subproblems, each subproblem has a separate mating restriction probability to control the contributions of exploitation and exploration. Besides, the mating restriction probability is updated by the survival length at each generation to adapt to the changing requirements. The experimental results validate that MOEA/D-MRS performs well on two test suites.

Tài liệu tham khảo

Bader J, Zitzler E (2011) Hype: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19:45–76 Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181:1653–1669 Cai X, Li Y, Fan Z, Zhang Q (2014) An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization. IEEE Trans Evol Comput 19:508–523 Cai X, Yang Z, Fan Z, Zhang Q (2017) Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization. IEEE Trans Cybern 47:2824–2837 Chiang TC, Lai YP (2011) MOEA/D-AMS: Improving MOEA/D by an adaptive mating selection mechanism. In: Evolutionary computation. IEEE, New Orleans, pp 1473–1480 Dai C, Wang Y (2015) A new decomposition based evolutionary algorithm with uniform designs for many-objective optimization. Appl Soft Comput 30:238–248 Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New York Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197 Gong M, Wang Z, Zhu Z, Jiao L (2017) A similarity-based multiobjective evolutionary algorithm for deployment optimization of near space communication system. IEEE Trans Evol Comput 21:878–897 Gu F, Cheung YM (2018) Self-organizing map-based weight design for decomposition-based many-objective evolutionary algorithm. IEEE Trans Evol Comput 22:211–225 Huband S, Barone L, While L, Hingston P (2005) A scalable multi-objective test problem toolkit. Lect Notes Comput Sci 3410:280–295 Ishibuchi H, Yu S, Masuda H, Nojima Y (2017) Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Trans Evol Comput 21:169–190 Jiang S, Yang S (2016) An improved multiobjective optimization evolutionary algorithm based on decomposition for complex Pareto fronts. IEEE Trans Cybern 46:421–437 Jiang S, Yang S, Wang Y, Liu X (2018) Scalarizing functions in decomposition-based multiobjective evolutionary algorithms. IEEE Trans Evol Comput 22:296–313 Ke L, Zhang Q, Battiti R (2013) MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and ant colony. IEEE Trans Cybern 43:1845–1859 Ke L, Zhang Q, Battiti R (2014) Hybridization of decomposition and local search for multiobjective optimization. IEEE Trans Cybern 44:1808–1820 Li H, Zhang Q (2009) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 13:284–302 Li H, Zhang Q, Chen Q, Zhang L, Jiao YC (2016) Multiobjective differential evolution algorithm based on decomposition for a type of multiobjective bilevel programming problems. Knowl-Based Syst 107:271–288 Li H, Zhang Q, Deng J (2016) Biased multiobjective optimization and decomposition algorithm. IEEE Trans Cybern 47:52–66 Li K, Fialho A, Kwong S, Zhang Q (2014) Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 18:114–130 Li K, Kwong S, Zhang Q, Deb K (2015) Interrelationship-based selection for decomposition multiobjective optimization. IEEE Trans Cybern 45:2076–2088 Li K, Zhang Q, Kwong S, Li M, Wang R (2014) Stable matching-based selection in evolutionary multiobjective optimization. IEEE Trans Evol Comput 18:909–923 Li X, Zhang H, Song S (2018) A self-adaptive mating restriction strategy based on survival length for evolutionary multiobjective optimization. Swarm Evol Comput. https://doi.org/10.1016/j.swevo.2018.02.009 Li Y, Zhou A, Zhang G (2014) An MOEA/D with multiple differential evolution mutation operators. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2014), Beijing, China, 2014c. IEEE, pp 397–404 Lin Q et al (2017) A diversity-enhanced resource allocation strategy for decomposition-based multiobjective evolutionary algorithm. IEEE Trans Cybern 48:2388–2401 Lin Q et al (2016) Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm. Inf Sci 339:332–352 Lin Q, Tang C, Du Z, Li J, Chen J, Ming Z (2017) A novel adaptive control strategy for decomposition-based multiobjective algorithm. Comput Oper Res 78:94–107 Lin S, Lin F, Chen H, Zeng W (2016) A MOEA/D-based multi-objective optimization algorithm for remote medical. Neurocomputing 220:5–16 Liu HL, Chen L, Zhang Q, Deb K (2018) Adaptively allocating search effort in challenging many-objective optimization problems. IEEE Trans Evol Comput 22:433–448 Ma X et al (2014) MOEA/D with opposition-based learning for multiobjective optimization problem. Neurocomputing 146:48–64 Ma X, Liu F, Qi Y, Li L, Jiao L, Liu M, Wu J (2014) MOEA/D with Baldwinian learning inspired by the regularity property of continuous multiobjective problem. Neurocomputing 145:336–352 Ma X, Zhang Q, Tian G, Yang J, Zhu Z (2018) On Tchebycheff decomposition approaches for multiobjective evolutionary optimization. IEEE Trans Evol Comput 22:226–244 Mashwani WK, Salhi A (2014) Multiobjective memetic algorithm based on decomposition. Appl Soft Comput 21:221–243 Ming M, Wang R, Zha Y, Zhang T (2017) Pareto adaptive penalty-based boundary intersection method for multi-objective optimization. Inf Sci 414:158–174 Qi Y, Bao L, Ma X, Miao Q, Li X (2016) Self-adaptive multi-objective evolutionary algorithm based on decomposition for large-scale problems: a case study on reservoir flood control operation. Inf Sci 367–368:529–549 Qi Y, Hou Z, Li H, Huang J, Li X (2015) A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Comput Oper Res 62:61–77 Qi Y, Ma X, Liu F, Jiao L, Sun J, Wu J (2014) MOEA/D with adaptive weight adjustment. Evol Comput 22:231–264 Sato H (2014) Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization. In: Genetic and evolutionery computation conference (GECCO 2014), Vancouver, BC, Canada ACM, pp 645–652 Tan YY, Jiao YC, Li H, Wang XK (2013) MOEA/D+ uniform design: a new version of MOEA/D for optimization problems with many objectives. Comput Oper Res 40:1648–1660 Trivedi A, Srinivasan D, Pal K, Saha C, Reindl T (2017) Enhanced multiobjective evolutionary algorithm based on decomposition for solving the unit commitment problem. IEEE Trans Ind Inf 11:1346–1357 Trivedi A, Srinivasan D, Sanyal K, Ghosh A (2017) A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Trans Evol Comput 21:440–462 Venske SM, Gonçalves RA, Benelli EM, Delgado MR (2016) ADEMO/D: an adaptive differential evolution for protein structure prediction problem. Expert Syst Appl 56:209–226 Wang L, Zhang Q, Zhou A, Gong M, Jiao L (2016) Constrained subproblems in a decomposition-based multiobjective evolutionary algorithm. IEEE Trans Evol Comput 20:475–480 Wang R, Zhou Z, Ishibuchi H, Liao T, Zhang T (2018) Localized weighted sum method for many-objective optimization. IEEE Trans Evol Comput 22:3–18 Wang Z, Zhang Q, Li H, Ishibuchi H, Jiao L (2017) On the use of two reference points in decomposition based multiobjective evolutionary algorithms. Swarm Evol Comput 34:89–102 Wang Z, Zhang Q, Zhou A, Gong M, Jiao L (2017) Adaptive replacement strategies for MOEA/D. IEEE Trans Cybern 46:474–486 Wu M, Li K, Kwong S, Zhang Q, Zhang J (2018) Learning to decompose: a paradigm for decomposition-based multiobjective optimization. IEEE Trans Evol Comput. https://doi.org/10.1109/TEVC.2018.2865931 Wu M, Li K, Kwong S, Zhou Y, Zhang Q (2017) Matching-based selection with incomplete lists for decomposition multiobjective optimization. IEEE Trans Evol Comput 21:554–568 Xing H, Wang Z, Li T, Li H, Qu R (2017) An improved MOEA/D algorithm for multi-objective multicast routing with network coding. Appl Soft Comput 59:88–103 Yang S, Jiang S, Jiang Y (2016) Improving the multiobjective evolutionary algorithm based on decomposition with new penalty schemes. Soft Comput 21:1–15 Yuan Y, Xu H, Wang B, Zhang B, Yao X (2016) Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans Evol Comput 20:180–198 Zhang H, Zhang X, Gao XZ, Song S (2016) Self-organizing multiobjective optimization based on decomposition with neighborhood ensemble. Neurocomputing 173:1868–1884 Zhang J, Tang Q, Li P, Deng D, Chen Y (2016) A modified MOEA/D approach to the solution of multi-objective optimal power flow problem. Appl Soft Comput 47:494–514 Zhang Q (2015) Multiobjective evolutionary algorithm based on decomposition for 3-objective optimization problems with objectives in different scales. Soft Comput 19:157–166 Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731 Zhang Q, Liu W, Li H (2009) The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: Proceedings of the IEEE congress on evolutionary computation (CEC 09), Trondheim, Norway IEEE, pp 203–208 Zhang Q, Zhou A, Jin Y (2008) RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans Evol Comput 12:41–63 Zhang Q, Zhou A, Zhao S, Suganthan PN, Liu W, Tiwari S (2008) Multiobjective optimization test instances for the CEC 2009 special session and competition. Special session on performance assessment of multi-objective optimization algorithms, technique report. University of Essex, Colchester Technological University, Singapore Zhang YH, Gong YJ, Gu TL, Yuan HQ, Wei Z, Kwong S, Zhang J (2017) DECAL: decomposition-based coevolutionary algorithm for many-objective optimization. IEEE Trans Cybern. https://doi.org/10.1109/TCYB.2017.2762701 Zhao SZ, Suganthan PN, Zhang Q (2012) Decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes. IEEE Trans Evol Comput 16:442–446 Zheng J, Yu G, Zhu Q, Li X, Zou J (2016) On decomposition methods in interactive user-preference based optimization. Appl Soft Comput 52:952–973 Zhou A, Qu BY, Li H, Zhao SZ, Suganthan PN, Zhang Q (2011) Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol Comput 1:32–49 Zhou A, Zhang Q (2016) Are all the subproblems equally important? Resource allocation in decomposition-based multiobjective evolutionary algorithms. IEEE Trans Evol Comput 20:52–64 Zitzler E, Künzli S (2004) Indicator-based selection in multiobjective search. Lect Notes Comput Sci 3242:832–842 Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the Strength Pareto evolutionary algorithm. Swiss Federal Institute of Technology (ETH) Zurich, Zurich Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271