基于多目标进化算法混合框架的MOEA/D算法

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

摘要/Abstract

摘要： 针对混合多目标进化算法中如何设计全局搜索算法和局部搜索策略结合机制的难点问题以及提高多目标进化算法的求解性能,基于反馈控制思想,提出了一种系统化、模块化的全局优化与局部搜索相结合的混合MOEA/D算法,算法中设计了一种基于拥挤熵的种群多样性度量方法;提出了基于简化二次逼近的局部搜索策略,以及针对MOEA/D的种群多样性增强策略。数值实验表明所提算法具有良好性能,可以兼顾算法求解的多样性和收敛性,所提混合框架可有效提升现有多目标进化算法的求解性能。

关键词: 多目标优化, 进化算法, 混合框架, MOEA/D, 反馈控制

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

中图分类号:

TP18

田红军, 汪镭, 吴启迪. 基于多目标进化算法混合框架的MOEA/D算法[J]. 系统仿真学报, 2020, 32(2): 201-216.

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.

参考文献

[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.