基于支配强度的NSGA2改进算法

doi:10.11896/j.issn.1002-137X.2018.06.033

摘要/Abstract

摘要： NSGA2是一种简单、高效且被广泛使用的多目标进化算法(Multi-objective Evolutionary Algorithm,MoEA),但在求解实际工程领域中的高维、复杂非线性多目标优化问题(Multi-objective Optimization Problems,MOP)时,存在无法有效识别伪非支配解、计算效率低、解集收敛性和分布性较差等设计缺陷。对此,文中提出一种基于支配强度的NSGA2改进算法(INSGA2-DS)。新算法采用快速支配强度排序法构造非支配集,引入了考虑方差的拥挤距离公式,并通过自适应精英保留策略动态调整精英保留规模。基于标准测试函数的仿真实验表明,INSGA2-DS算法较好地改善了NSGA2算法的收敛性和分布性。

关键词: NSGA2, 多目标进化算法, 多目标优化问题, 支配强度

Abstract: NSGA2 algorithm is a simple,efficient and widely used multi-objective evolutionary algorithm.However,when solving high-dimensional and complex nonlinear multi-objective optimization problems in practical engineering field,NSGA2 has some obvious design defects,such as ineffective identification of pseudo non-dominated solutions,low computational efficiency,poor convergence and distribution.In order to remedy the above drawbacks,this paper proposed an improved NSGA2 algorithm based on dominant strength (INSGA2-DS).INSGA2-DS uses the fast dominant strength sorting method to construct non-dominated set,introduces a new crowding distance with considering variance to improve the distribution of solution sets,and adopts the adaptive elitist retention strategy to adjust elitist retention scale in evolutionary process automatically.The experimental results of INSGA2-DS and NSGA2 with standard test functions show that INSGA2-DS algorithm can improve the convergence and distribution of NSGA2 algorithm effectively.

Key words: Dominant strength, Multi-objective evolutionary algorithm, Multi-objective optimization problems, NSGA2

中图分类号:

TP301

赖文星, 邓忠民. 基于支配强度的NSGA2改进算法[J]. 计算机科学, 2018, 45(6): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2018.06.033

LAI Wen-xing, DENG Zhong-min. Improved NSGA2 Algorithm Based on Dominant Strength[J]. Computer Science, 2018, 45(6): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2018.06.033

参考文献

[1]ZITZLER E,DEB K,THIELE L.Comparison of multiobjective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.
[2]SRINIVAS N,DEB K.Muiltiobjective optimization using non-dominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.
[3]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[4]KOLLAT J B,REED P M.The value of online adaptive search:a performance comparison of NSGAII,ε-NSGAII and εMOEA[C]//International Conference on Evolutionary Multi-Criterion Optimization.Springer Berlin Heidelberg,2005:386-398.
[5]ZHANG Q,LI H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712.
[6]LI H,ZHANG Q.Multiobjective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[7]TAN K C,CHIAM S C,MAMUN A A,et al.Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization[J].European Journal of OperationalResearch,2009,197(2):701-713.
[8]ELHOSSINI A,AREIBI S,DONY R.Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization[J].Evolutionary Computation,2010,18(1):127-156.
[9]XIE C W,LI K,LIAO G Y.Improved NSGA2 Algorithm with Differential Evolutionary Local Search[J].Computer Science,2013,40(10):235-238,273.
谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA2算法[J].计算机科学,2013,40(10):235-238,273.
[10]DEB K,JAIN H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach,part I:Solving problems with box constraints[J].IEEE Trans.Evolutionary Computation,2014,18(4):577-601.
[11]SHIM V A,TAN K C,TANG H.Adaptive memetic computing for evolutionary multiobjectiveoptimization[J].IEEE Transactions on Cybernetics,2015,45(4):610-621.
[12]QIU X,XU J X,TAN K C,et al.Adaptive Cross-Generation Differential Evolution Operators for MultiobjectiveOptimization[J].IEEE Transactions on Evolutionary Computation,2016,20(2):232-244.
[13]COELLO C A C,VAN VELDHUIZEN D A,Lamont G B.Evolutionary algorithms for solving multi-objective problems[M].New York:Kluwer Academic,2002.
[14]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007:109-112.
[15]DEB K.Multi-objective optimization using evolutionary algorithms[M].New York:John Wiley & Sons,2001.
[16]DEB K.Multi-objective genetic algorithms:Problem difficulties and construction of test problems[J].Evolutionary computation,1999,7(3):205-230.
[17]DEB K,THIELE L,LAUMANNS M,et al.Scalable test problems for evolutionary multi objectiveo ptimization[M].London:Springer,2005.
[18]COELLO C A C,PULIDO G T,LECHUGA M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

相关文章 15

[1]	董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究 Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering 计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[2]	董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034
[3]	耿焕同, 韩伟民, 周山胜, 丁洋洋. 一种基于新型邻域更新策略的MOEA/D算法 MOEA/D Algorithm Based on New Neighborhood Updating Strategy 计算机科学, 2019, 46(5): 191-197. https://doi.org/10.11896/j.issn.1002-137X.2019.05.029
[4]	刘鑫平, 顾春华, 罗飞, 丁炜超. 基于败者组与混合编码策略的NSGA-II改进算法 Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy 计算机科学, 2019, 46(10): 222-228. https://doi.org/10.11896/jsjkx.181001852
[5]	刁兴春,刘艺,曹建军,尚玉玲. 多目标蚁群优化研究综述 Reviews of Multiobjective Ant Colony Optimization 计算机科学, 2017, 44(10): 7-13. https://doi.org/10.11896/j.issn.1002-137X.2017.10.002
[6]	马庆. 基于多目标进化算法的MOEA/D权重向量产生方法 Multi-objective Evolutionary Algorithm Based Weight Vectors Generation Method of MOEA/D 计算机科学, 2016, 43(Z11): 117-122. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.025
[7]	苏丁为,周创明,王毅. 基于直觉模糊熵的粒子群多目标优化 Particle Swarm Algorithm for Multi-objective Optimization Based on Intuitionistic Fuzzy Entropy 计算机科学, 2016, 43(8): 262-266. https://doi.org/10.11896/j.issn.1002-137X.2016.08.053
[8]	谢承旺,李凯,廖国勇. 一种带差分局部搜索的改进型NSGA2算法 Improved NSGA2Algorithm with Differential Evolution Local Search 计算机科学, 2013, 40(10): 235-238.
[9]	贺群，程格，安军辉，戴光明，彭雷. 基于Pareto的多目标克隆进化算法 Pareto-based Multi-object Clonal Evolutionary Algorithm 计算机科学, 2012, 39(Z6): 489-492.
[10]	李东,潘志松. 一种适用于大规模变量的并行遗传算法研究 Research on Parallel Genetic Algorithms Based on MapReduce 计算机科学, 2012, 39(7): 182-184.
[11]	郭思涵，龚小胜. 正交设计的E占优策略求解高维多目标优化问题研究 Research of Orthogonal E-dominant(OE) Strategy to Solve Large-dimensional Objective Optimization Problems 计算机科学, 2012, 39(2): 276-279.
[12]	谢承旺,丁立新. 多目标进化算法中多样性策略的研究 Diversity Strategies on Multiobjective Evolutionary Algorithms 计算机科学, 2010, 37(2): 175-179.
[13]	谢承旺,丁立新. 多目标进化算法中选择策略的研究 Study on Selection Strategies of Multiobjective Evolutionary Algorithms 计算机科学, 2009, 36(9): 167-172.
[14]	郑向伟刘弘. 多目标进化算法研究进展计算机科学, 2007, 34(7): 187-192.
[15]	吴作顺王石. 一个SPEA改进算法及其收敛性分析计算机科学, 2005, 32(4): 74-76.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed