计算机科学

计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 222-228.doi: 10.11896/jsjkx.181001852

• 人工智能 • 上一篇    下一篇

基于败者组与混合编码策略的NSGA-II改进算法

刘鑫平, 顾春华, 罗飞, 丁炜超   

  1. (华东理工大学信息科学与工程学院 上海200237)
  • 收稿日期:2018-10-07 修回日期:2019-03-07 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 顾春华(1970-),男,博士,教授,主要研究方向为云计算、物联网,E-mail:lxp_ecust@163.com。
  • 作者简介:刘鑫平(1993-),男,硕士生,主要研究方向为多目标优化、云计算;罗飞(1978-),男,博士,副教授,主要研究方向为云计算、分布式计算;丁炜超(1989-),男,博士生,主要研究方向为云计算、数据中心资源管理与优化、大数据应用。
  • 基金资助:
    本文受国家自然科学基金项目(61472139)资助。

Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy

LIU Xin-ping, GU Chun-hua, LUO Fei, DING Wei-chao   

  1. (School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)
  • Received:2018-10-07 Revised:2019-03-07 Online:2019-10-15 Published:2019-10-21

PDF (PC)

790

摘要： 在精英选择中NSGA-II的拥挤系数算子对局部拥挤区域的分布性优化效果不佳,并且会使某些更接近Pareto最优解集的个体被淘汰。针对拥挤系数算子存在优秀个体不被保留的缺陷,提出了一种基于败者组与混合编码策略的改进算法(LGHC-NSGA-II)。参照棋类比赛中的双败淘汰制,构建了败者组外部归档集,在迭代结束后将归档集与末代父代种群合并,并采用循环拥挤系数排序策略优化分布性。同时,针对传统编码方式在全局或局部空间上搜索能力较差的缺陷,提出了一种混合编码策略,有效地提高了算法的收敛性。基于ZDT系列问题上的测试结果表明,改进算法与8种多目标进化算法相比,在算法的收敛性、分布性与鲁棒性上均具有较高的优越性。

关键词: NSGA-II, 败者组, 多目标进化算法, 混合编码, 循环拥挤系数排序

Abstract: The congestion coefficient operator of NSGA-II in elite selection can not optimize the distribution of local congestion area effectively,and some individuals closer to Pareto optimal solution set will be eliminated.An improved algorithm based on loser group and hybrid encoding strategy (LGHC-NSGA-II) was proposed to overcome the shortcomingthat excellent individuals are not retained in the congestion coefficient operator.Referring to the double-losing elimination system in chess games,an external archive set of loser group is constructed.After the iteration,the archive set is merged with the last generation parent population,and the distribution coefficient is optimized by cyclic congestion coefficient ranking strategy.At the same time,a hybrid coding strategy was proposed to overcome the shortcomings of traditional coding methods in global or local space,which effectively improves the convergence of the algorithm.The test results on ZDT series problems show that the improved algorithm is superior to eight multi-objective evolutionary algorithms in convergence,distribution and robustness.

Key words: Cyclic congestion coefficient ranking, Hybrid coding, Loser group, Multi-objective evolutionary algorithm, NSGA-II

中图分类号: 

  • TP301
[1]ZITZLER E,THIELE L.Multi-objective evolutionary algo-rithms:A comparative case study and the strength pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[2]CORNE D W,KNOWLES J D,OATES M J.The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization[C]//International Conference on Parallel Problem Solving From Nature.Springer-Verlag,2000:839-884.
[3]SRINIVAS N,DEB K.Multi-objective optimization using non-dominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.
[4]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.
[5]DEB K,AGRAWAL S,PRATAP A,et al.A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization:NSGA-II//International Conference on Parallel Problem Solving from Nature.Springer,2002.
[6]ZHANG Q,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[7]COELLO C A C.Evolutionary multi-objective optimization:a historical view of the field.IEEE Computational Intelligence Magazine,2006,1(1):28-36.
[8]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 Transactions on Evolutionary Computation,2014,18(4):577-601.
[9]LI M,ZHENG J,WU J.Improving NSGA-II Algorithm Based on Minimum Spanning Tree[C]//Asia-Pacific Conference on Simulated Evolution and Learning.Springer Berlin Heidelberg,2008:170-179.
[10]LUO C Y,CHEN M Y,ZHANG C Y.Improved NSGA-Ⅱ algorithm with circular crowded sorting[J].Control and Decision,2010,25(2):227-231.(in Chinese)
罗辞勇,陈民铀,张聪誉.采用循环拥挤排序策略的改进NSGA-Ⅱ算法[J].控制与决策,2010,25(2):227-231.
[11]SATO Y,SATO M,MIYAKAWA M.Distributed NSGA-II with migration using compensation on many-core processors for improving performance and accuracy[C]//the Genetic and Evolutionary Computation Conference Companion.2017:161-162.
[12]KUMAR M,GURIA C.The elitist non-dominated sorting ge-netic algorithm with inheritance(i-NSGA-II)and its jumping gene adaptations for multi-objective optimization[J].Information Sciences,2017,s382-383:15-37.
[13]XIE C W,LI K,LIAO G Y.Improved NSGA2 Algorithm with Differential Evolution Local Search[J].Computer Science,2013,40(10):235-238.(in Chinese)
谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA2算法[J].计算机科学,2013,40(10):235-238.
[14]SCHOTT J R.Fault Tolerant Design Using Single and Multicr-iteria Genetic Algorithm Optimization[J].Cellular Immunology,1995,37(1):1-13.
[15]VACHHANI V L,DABHI V K,PRAJAPATI H B.Improving NSGA-II for solving multi objective function optimization problems[C]//International Conference on Computer Communication and Informatics.IEEE,2016:1-6.
[16]LAI W X,DENG Z M.Improved NSGA2 Algorithm Based on Dominant Strength[J].Computer Science,2018,45(6):187-192.(in Chinese)
赖文星,邓忠民.基于支配强度的NSGA2改进算法[J].计算机科学,2018,45(6):187-192.
[17]ZITZLER E,DEB K,THIELE L.Comparison of Multiobjective Evolutionary Algorithms:Empirical Results[J].Evolutionary Computation,2000,8(2):173-195.
[18]HOLLAND J H.Adaptation in natural and artificial systems [J].Ann Arbor,1992,6(2):126-137.
[19]GRAY F.Pulse code communication[P].U.s.patent2,1953.
[20]ZITZLER E,THIELE L.Multiobjective evolutionary algo-rithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[21]ZHOU H,MENG L M,WANG L P,et al.Multi-objective Evolutionary Algorithm Based on Decomposition Using Dynamic Neighbor[J].Mini-micro Systems,2017,38(9):2039-2044.(in Chinese)
周欢,孟利民,王丽萍,等.动态邻域的分解多目标进化算法[J].小型微型计算机系统,2017,38(9):2039-2044.
[22]NEBRO A J,DURILLO J J,GARCIA-NIETO J,et al.SMPSO:A new PSO-based metaheuristic for multi-objective optimization[C]//Computational Intelligence in Miulticriteria Decision-ma-king,IEEE,2009:66-73.
[23]HU W,YEN G G,ZHANG X.Multiobjective Particle Swarm Optimization Based on Pareto Entropy[J].Journal of Software,2014,25(5):1025-1050.(in Chinese)
胡旺,YEN G G,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014(5):1025-1050.
[24]LIN Q,CHEN J,ZHAN Z H,et al.A Hybrid Evolutionary Immune Algorithm for Multiobjective Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2016,20(5):711-729.
[25]MA Y F,LI A R,YU H M,et al.Dynamic Crowding Distance-based Hybrid Immune Algorithm for Multi-objective Optimization Problem[J].Computer Science,2018,45(6):63-68.(in Chinese)
马元锋,李昂儒,余慧敏,等.基于动态拥挤距离的混合多目标免疫优化算法[J].计算机科学,2018,45(6):63-68.
[26]VAN D A,GARY V,LAMONT B.Multiobjective Evolutionary Algorithm Research:A History and Analysis[J].Evolutionary Computation,1998,8(2):125-147.
[27]VAN VELDHUIZEN D A,LAMONT G B.Evolutionary computation and convergence to a pareto front[C]//Koza J R.Late Breaking Papers at the Genetic Programming 1998 Conference.Stanford University,California,1998:221-228.
[1] 董明刚, 弓佳明, 敬超.
基于谱聚类的多目标进化社区发现算法研究
Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering
计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[2] 耿焕同, 韩伟民, 周山胜, 丁洋洋.
一种基于新型邻域更新策略的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
[3] 赖文星, 邓忠民.
基于支配强度的NSGA2改进算法
Improved NSGA2 Algorithm Based on Dominant Strength
计算机科学, 2018, 45(6): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2018.06.033
[4] 刘嘉怡,燕雪峰.
一种基于动态图编码的软件水印方案
Software Watermarking Scheme Based on Dynamic Graph Coding
计算机科学, 2017, 44(9): 131-135. https://doi.org/10.11896/j.issn.1002-137X.2017.09.026
[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] 贺 群，程 格，安军辉，戴光明，彭 雷.
基于Pareto的多目标克隆进化算法
Pareto-based Multi-object Clonal Evolutionary Algorithm
计算机科学, 2012, 39(Z6): 489-492.
[8] 谢承旺,丁立新.
多目标进化算法中多样性策略的研究
Diversity Strategies on Multiobjective Evolutionary Algorithms
计算机科学, 2010, 37(2): 175-179.
[9] 赵凤强,徐毅,李广强.
基于岛屿群体模型的多目标演化算法研究
Research on Multi-objective Evolutionary Algorithm Based on Island Model
计算机科学, 2010, 37(12): 190-192.
[10] 谢承旺,丁立新.
多目标进化算法中选择策略的研究
Study on Selection Strategies of Multiobjective Evolutionary Algorithms
计算机科学, 2009, 36(9): 167-172.
[11] 郑向伟 刘弘.
多目标进化算法研究进展

计算机科学, 2007, 34(7): 187-192.
[12] 余胜生 张剑 周敬利.
基于H．264标准的混合编码算法分析

计算机科学, 2005, 32(5): 109-111.
[13] 吴作顺 王石.
一个SPEA改进算法及其收敛性分析

计算机科学, 2005, 32(4): 74-76.
[14] 刘海林 刘永清.
基于多目标进化算法的目标规划研究

计算机科学, 2002, 29(9): 42-43.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发