MOEA/D Algorithm Based on the Hybrid Framework for Multi-objective Evolutionary Algorithm

doi:10.16182/j.issn1004731x.joss.17-9183

Abstract

Abstract: Aimto the difficulties of designing the bonding mechanism of global optimization algorithm and local search strategy for hybrid multi-objective evolutionary algorithm, and of improving the performance of multi-objective evolutionary algorithms, based on the feedback control idea, a systematic and modular hybrid MOEA/D algorithm combining the global optimization and local search is proposed. In the algorithm, a diversity measure method based on crowded entropy is designed; a local search strategy based on simplified quadratic approximation and population diversity enhancement strategy for MOEA/D is proposed. The numerical experiments show that the proposed HMOEA/D can achieve a balance between diversity and convergence of algorithm. The proposed hybrid framework can effectively improve the performance of existing multi-objective evolutionary algorithms.

Key words: multi-objective optimization, evolutionary algorithm, hybrid framework, MOEA/D, feedback control

CLC Number:

TP18

Tian Hongjun, Wang Lei, Wu Qidi. MOEA/D Algorithm Based on the Hybrid Framework for Multi-objective Evolutionary Algorithm[J]. Journal of System Simulation, 2020, 32(2): 201-216.

References

[1] Coello C A, Lamont G B.Applications of Multi-Objective Evolutionary Algorithms[M]. Singapore: World Scientific, 2004: 3-11.
[2] Medaglia A L, Villegas J G, Rodriguez-Coca D M. Hybrid Bi-objective Evolutionary Algorithms for The Design of A Hospital Waste Management Network[J]. Heuristics (S1381-1231), 2009, 15(2): 153-176.
[3] Fei Z S, Li B, Yang S S, et al.A Survey of Multi-Objective Optimization in Wireless Sensor Networks: Metrics, Algorithms, and Open Problems[J]. IEEE Communications Surveys & Tutorials (S1553-877X), 2017, 19(1): 550-586.
[4] Qi Y T, Hou Z T, Li H H, et al.A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows[J]. Computers & Operations Research (S0305-0548), 2015, 62: 61-67.
[5] Lin Q Z, Zhu Q L, Huang P Z, et al.A Novel Hybrid Multi-objective Immune Algorithm with Adaptive Differential Evolution[J]. Computers & Operations Research (S0305-0548), 2015, 62: 95-111.
[6] Liu C A, Jia H M.Dynamic Multi-objective Evolutionary Algorithm with Two Stages Evolution Operation[J]. Intelligent Automation and Soft Computing (S1079-8587), 2015, 4(21): 575-588.
[7] Aimin Z, Jin Y C, Zhang Q F.A Population Prediction Strategy for Evolutionary Dynamic Multi-objective Optimization[J]. IEEE Transactions on Cybernetics (S1083-4419), 2014, 44(1): 40-53.
[8] Deb K, Lele S, Datta R.A hybrid Evolutionary Multi-objective and SQP Based Procedure for Constrained Optimization[C]. Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2007: 36-45.
[9] Rafiul H M, Nath B, Kirley M, et al.A hybrid of Multi-objective Evolutionary Algorithm and HMM-Fuzzy Model for Ttime Series Prediction[J]. Neuro Computing (S0925-2312), 2012, 81: 1-11.
[10] Wang H F, Fu Y P, Huang M, et al.A hybrid Evolutionary Algorithm with Adaptive Multi-population Strategy for Multi-objective Optimization Problems[J]. Soft Computing (S2588-2872), 2017, 21: 5975-5987.
[11] Liu R C, Li J X, F J, et al. A Co-evolutionary technique Based on Multi-swarm Particle Swarm Optimization for Dynamic Multi-objective Optimization[J]. European Journal of Operational Research (S0377-2217), 2017: 1028-1051.
[12] Wali K M, Abdellah S, Ozgur Y, et al.Hybrid Adaptive Evolutionary Algorithm Based on Decomposition[J]. Applied Soft Computing (S1568-4946), 2017, 57: 363-378.
[13] Yuan Y, Xu H, Wang B, et al.Balancing Convergence and Diversity in Decomposition-based Many-objective Optimizers[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2016, 20(2): 180-198.
[14] Wang R, Zhang Q, Zhang T.Decomposition-based Algorithms Using Pareto Adaptive Scalarizing Methods[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2016, 20(6): 821-837.
[15] Li K, Zhang Q F, Kwong S, et al.Stable Matching-based Selection in Evolutionary Multi-objective Optimization[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2014, 18(6): 909-923.
[16] Wang W L, Ying S L, Li L, et al.An improved Decomposition-based Multi-objective Evolutionary Algorithm with A Better Balance of Convergence and Diversity[J]. Applied Soft Computing (S1568-4946), 2017, 57: 627-641.
[17] Ishibuchi H, Murata T.A multi-objective Genetic Local Search Algorithm and Its Application to Flow Shop Scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 1998, 28(3): 392-403.
[18] Goel T, Deb K.Hybrid Methods for Multi-objective Evolutionary Algorithms[C]. Proceedings of the Fourth Asia-Pacific Conference on Simulated Evolution and Learning. Singapore:(SEAL 2002), 2002: 188-192.
[19] Sindhya K, Sinha A, Deb K, et al.Local Search Based Evolutionary Multi-objective Optimization Algorithm for Constrained and Unconstrained Problems[C]. Proceedings of Congress on Evolutionary Computation. Norway: IEEE, 2009: 2919-2926.
[20] Sindhya K, Deb K, Miettinen K.A Local Search Based Evolutionary Multi-objective Optimization Approach for Fast and Accurate Convergence[C]. Parallel Problem Solving from Nature (PPSN X). Berlin: Springer Berlin Heidelberg, 2008: 815-824.
[21] 贾树晋, 杜斌, 岳恒. 基于局部搜索与混合多样性策略的多目标粒子群算法[J]. 控制与决策, 2012, 27(6): 813-826.
Jia Shujin, Du Bin, Yue Heng.Local Search and Hybrid Diversity Strategy Based Multi-objective Particle Swarm Optimization Algorithm[J]. Control and Decision, 2012, 27(6): 813-826.
[22] Zhang Q F, Li H.MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2007, 11(6): 712-731.
[23] Li H, Zhang Q F.Multi-objective Optimization Problems with Complicated Pareto Sets MOEA/D and NSGA-II[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2009, 12(2): 284-302.
[24] Zhang Q F, Liu W, Li H.The Performance of A New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances[C]. IEEE Congress on Evolutionary Computation (CEC'09). Piscataway, 2009: 203-208.
[25] Ishibuchi H, Sakane Y, Tsukamoto N, et al.Adaptation of sScalarizing Functions in MOEA/D: An Adaptive Scalarizing Function Based Multi-objective Evolutionary Algorithm[C]. Proceedings of the 5th international conference devoted to evolutionary multi-criterion optimization (EMO'09). France: Nantes, 2009: 438-452.
[26] 吴亮红, 王耀南. 动态差分进化算法及其应用[M]. 北京: 科学出版社, 2014: 66-74.
Wu Lianghong, Wang Yaonan.Dynamic Differential Evolutionary Algorithm and Application[M]. Beijing: Science Press, 2014: 66-74.
[27] Sindhya K, Miettinen K, Deb K.An Improved Concurrent-hybrid Algorithm for Enhanced Diversity and Accuracy in Evolutionary Multi-objective Optimization in Evolutionary and Deterministic Methods for Design, Optimization and Control, Applications to Industrial and Societal Problems[M]. Burczynski T, Periaux J, eds. Barcelona, Spain: CIMNE, 2011: 182-187.
[28] 谭艳艳. 几种改进的分解类多目标进化算法及其应用[D]. 西安: 西安电子科技大学, 2013: 64-65.
Tan Yanyan.Several Modified Decomposition-Based Multi-objective Evolutionary Algorithms and Their Applications[D]. Xi'an: Xidian University, 2013: 64-65.
[29] Ali M M, Torn A, Vitanen S.A numerical Comparison of Some Modified Controlled Random Search Algorithms[J]. Journal of Global Optimization (S0925-5001), 1997, 11(4): 377-385.
[30] Fabre M G, Pulido G T, Coello C A C. Two Novel Approaches for Many-objective Optimization[C]. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010). Barcelona: Springer-Verlag, 2010: 1-8.
[31] Miettinen K.Nonlinear Multi-objective Optimization. Norwell[M]. MA: Kluwer, 1999: 171-179.
[32] Sindhya K, Deb K, Miettinen K.A local Search Based Evolutionary Multi-objective Optimization Approach for Fast and Accurate Convergence[C]. Parallel Problem Solving from Nature (PPSN X). Berlin: Springer Berlin Heidelberg, 2008: 815-824.
[33] Zhang Q F, Zhou A, Zhao S, et al.Multi-objective optimization test instances for the CEC 2009 special session and competition[R]. Technical Report CES-487, School of Computer Science and Electronic Engineering, University of Essex, UK, 2008.
[34] Zhang Q F, Li H.MOEA/D: A Multi-objective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2007, 11(6): 712-731.
[35] Kukkonen S, Lampinen J.Performance Assessment of Aeneralized Differential Evolution with A Given Set of Constrained Multi-objective Test Problems[C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 3593-3600.
[36] Tseng L Y, Chen C.Multiple Trajectory Search for Unconstrained/Constrained Multi-objective Optimization [C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 1951-1958.
[37] Liu M, Zou X, Chen Y, et al.Performance Assessment of DMOEA-DD with CEC 2009 MOEA Competition Test Instances[C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 2913-2918.
[38] Sindhya K, Sinha A, Deb K, et al.Local Search Based Evolutionary Multi-objective Optimization Algorithm for Constrained and Unconstrained Problems[C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 2919-2926.
[39] Wang Y, Dang C, Li H, et al.A Clustering Multi-objective Evolutionary Algorithm Based on Orthogonal and Uniform Design[C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 2927-2933.
[40] Qu B Y, Suganthan P N.Multi-objective Evolutionary Programming Without Non-domination Sorting Is Up to Twenty Times Faster[C]. IEEE Congress on Evolutionary Computation (CEC'09). NJ: IEEE Press, 2009: 2934-2939.
[41] Gong D, Liu Y, Sun X, et al.Parallel Many-objective Evolutionary Optimization Uusing Oobjectives Decomposition[J]. Automatica (S0005-1098), 2015, 41(8): 1438-1451.
[42] Zitzler E, Thiele L, Laumanns M, et al.Performance Assessment of Multi-objective Ooptimizers: An Analysis and Review[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 2003, 7(2): 117-132.
[43] Van Veldhuizen D A, Lamont G B. Multi-objective Evolutionary Algorithm Test Suites[C]. Proceedings of the 1999 ACM symposium on applied computing. New York: ACM Press, 1999: 351-357.
[44] Zitzler E, Thiele L.Multi-Objective Evolutionary Algorithms: A comparative Case Study and The Strength Pareto Approach[J]. IEEE Transaction on Evolutionary Computation (S1089-778X), 1999, 3(4): 257-271.