一种基于新型邻域更新策略的MOEA/D算法

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

计算机科学 ›› 2019, Vol. 46 ›› Issue (5): 191-197.doi: 10.11896/j.issn.1002-137X.2019.05.029

一种基于新型邻域更新策略的MOEA/D算法

耿焕同, 韩伟民, 周山胜, 丁洋洋

(南京信息工程大学计算机与软件学院南京210044)

收稿日期:2018-04-04 修回日期:2018-07-27 发布日期:2019-05-15
作者简介:耿焕同(1973－),男,教授,博士生导师,CCF高级会员,主要研究方向为气象数据挖掘、计算智能、多目标优化,E-mail:htgent@nuist.edu.cn(通信作者);韩伟民(1992－),男,硕士生,主要研究方向为多目标优化;周山胜(1992－),男,硕士生,主要研究方向为多目标优化;丁洋洋(1992－),男,硕士生,主要研究方向为高维多目标优化。
基金资助:
国家重点研发计划(2017YFC1502104),江苏省自然科学基金(BK20151458),江苏省“青蓝工程”(2016)资助。

MOEA/D Algorithm Based on New Neighborhood Updating Strategy

GENG Huan-tong, HAN Wei-min, ZHOU Shan-sheng, DING Yang-yang

(College of Computer & Software,Nanjing University of Information Science&Technology,Nanjing 210044,China)

Received:2018-04-04 Revised:2018-07-27 Published:2019-05-15

摘要/Abstract

摘要： 针对MOEA/D算法求解复杂优化问题时,邻域更新策略的无限制替换易造成种群多样性缺失的问题,提出了一种基于新型邻域更新策略的MOEA/D算法(MOEA/D-ENU)。该算法在进化过程中对解的信息进行充分挖掘,按照邻域更新能力对产生的新解进行分类,并针对不同类型的新解,自适应地采取不同的邻域更新策略,在保证种群收敛速度的同时,又兼顾了种群的多样性。实验中,选取ZDT,UF,CF等9个函数作为标准测试集,将改进后的算法MOEA/D-ENU与其他5种算法进行对比实验,并以IGD和HV为评估指标。实验结果表明新算法具有更好的收敛性和分布性。

关键词: 分类, 基于分解的多目标进化算法, 邻域更新策略, 挖掘解

Abstract: To solve the problem of the lack of population diversity caused by the unrestricted replacement of neighbourhood updating strategy when the MOEA/D algorithm solves the complex optimization problem,a new MOEA/D algorithm based on new Neighbourhood Updating Strategy (MOEA/D-ENU) was proposed.In the process of evolution,the algorithm fully excavates the information of the solution,classifies the new solution generated according to the capacity of neighbourhood updating,and adopts different neighbourhood updating strategies adaptively to different types of new solutions to ensure the population convergence rate.At the same time,it takes into account the diversity of the population.The proposed algorithm was compared with five other algorithms on 9 benchmarks including ZDT,UF and CF.The values of IGD and HV show that MOEA/D-ENU has certain advantages than other algorithms in terms of convergence and distribution.

Key words: Classification, Excavating solution, Multiobjective evolutionary algorithm based on decomposition, Neighbourhood updating strategy

中图分类号:

TP183

耿焕同, 韩伟民, 周山胜, 丁洋洋. 一种基于新型邻域更新策略的MOEA/D算法[J]. 计算机科学, 2019, 46(5): 191-197. https://doi.org/10.11896/j.issn.1002-137X.2019.05.029

GENG Huan-tong, HAN Wei-min, ZHOU Shan-sheng, DING Yang-yang. MOEA/D Algorithm Based on New Neighborhood Updating Strategy[J]. Computer Science, 2019, 46(5): 191-197. https://doi.org/10.11896/j.issn.1002-137X.2019.05.029

参考文献

[1]SBALZARINI I F,MÜLLER S,KOUMOUTSAKOS P.Mul-tiobjective optimization using evolutionary algorithms[C]∥Summer Program.CiteSeer,2001:63-74.
[2]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.
[3]ZITZLER E,LAUMANNS M,THIELE L.SPEA2:Improving the Strength Pareto Evolutionary Algorithm[J].IEEEEvolutionary Computation,2002,10(3):263-282.
[4]JIANG S,ZHANG J,ONG Y S,et al.A Simple and Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm[J].IEEE Transactions on Cybernetics,2015,45(10):2202-2213.
[5]BEUME N,NAUJOKS B,EMMERICH M.SMS-EMOA:Multiobjective selection based on dominated hypervolume[J].European Journal of Operational Research,2007,181(3):1653-1669.
[6]LI Y L,ZHOU Y R,ZHAN Z H,et al.A primary theoretical study on decomposition-based multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation,2016,20(4):563-576.
[7]WANG R,ZHANG Q,ZHANG T.Decomposition-based algorithms using pareto adaptive scalarizingmethods[J].IEEE Transactions on Evolutionary Computation,2016,20(6):821-837.
[8]ZHANG Q,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[9]LI H,ZHANG Q.Multiobjective optimization problems withcomplicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[10]HOU W,DONG H B,YIN G S.Enhanced Multi-objective Evolutionary Algorithm Based on Decomposition[J].ComputerScience,2014,41(2):114-118.(in Chinese)侯薇,董红斌,印桂生.一种改进的基于分解的多目标进化算法[J].计算机科学,2014,41(2):114-118.
[11]MA Q.Multi-objective Evolutionary Algorithm Based WeightVectorsGeneration Method of MOEA/D[J].Computer Science,2016,43(s2):117-122.(in Chinese)马庆.基于多目标进化算法的MOEA/D权重向量产生方法[J].计算机科学,2016,43(S2):117-122.
[12]WANG Z,ZHANG Q,GONG M,et al.A replacement strategy for balancing convergence and diversity in MOEA/D[C]∥Evolutionary Computation.IEEE,2014:2012-2139.
[13]WANG Z,ZHANG Q,ZHOU A,et al.Adaptive ReplacementStrategies for MOEA/D[J].IEEE Transactions on Cybernetics,2017,46(2):474-486.
[14]ZHANG Q,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.IEEE,2009:203-208.
[15]ZITZLER E,DEB K,THIELE L.Comparison of Multiobjective Evolutionary Algorithms:Empirical Results[J].Evolutionary Computation,2000,8(2):173.
[16]HUBAND S,HINGSTON P,BARONE L,et al.A review ofmultiobjective test problems and a scalable test problem toolkit[J].IEEE Transactions on Evolutionary Computation,2006,10(5):477-506.
[17]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.
[18]LI K,DEB K,ZHANG Q,et al.Combining Dominance and Decomposition in Evolutionary Many-Objective Optimization[J].International Journal of Behavioral Development,2006,30(3):1.
[19]CHENG R,JIN Y,OLHOFER M,et al.A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.
[20]CHENG R,JIN Y,NARUKAWA K,et al.A MultiobjectiveEvolutionary Algorithm Using Gaussian Process-Based Inverse Modeling[J].IEEE Transactions on Evolutionary Computation,2015,19(6):838-856.

相关文章 15

[1]	陈志强, 韩萌, 李慕航, 武红鑫, 张喜龙. 数据流概念漂移处理方法研究综述 Survey of Concept Drift Handling Methods in Data Streams 计算机科学, 2022, 49(9): 14-32. https://doi.org/10.11896/jsjkx.210700112
[2]	周旭, 钱胜胜, 李章明, 方全, 徐常胜. 基于对偶变分多模态注意力网络的不完备社会事件分类方法 Dual Variational Multi-modal Attention Network for Incomplete Social Event Classification 计算机科学, 2022, 49(9): 132-138. https://doi.org/10.11896/jsjkx.220600022
[3]	郝志荣, 陈龙, 黄嘉成. 面向文本分类的类别区分式通用对抗攻击方法 Class Discriminative Universal Adversarial Attack for Text Classification 计算机科学, 2022, 49(8): 323-329. https://doi.org/10.11896/jsjkx.220200077
[4]	武红鑫, 韩萌, 陈志强, 张喜龙, 李慕航. 监督和半监督学习下的多标签分类综述 Survey of Multi-label Classification Based on Supervised and Semi-supervised Learning 计算机科学, 2022, 49(8): 12-25. https://doi.org/10.11896/jsjkx.210700111
[5]	檀莹莹, 王俊丽, 张超波. 基于图卷积神经网络的文本分类方法研究综述 Review of Text Classification Methods Based on Graph Convolutional Network 计算机科学, 2022, 49(8): 205-216. https://doi.org/10.11896/jsjkx.210800064
[6]	闫佳丹, 贾彩燕. 基于双图神经网络信息融合的文本分类方法 Text Classification Method Based on Information Fusion of Dual-graph Neural Network 计算机科学, 2022, 49(8): 230-236. https://doi.org/10.11896/jsjkx.210600042
[7]	高振卓, 王志海, 刘海洋. 嵌入典型时间序列特征的随机Shapelet森林算法 Random Shapelet Forest Algorithm Embedded with Canonical Time Series Features 计算机科学, 2022, 49(7): 40-49. https://doi.org/10.11896/jsjkx.210700226
[8]	杨炳新, 郭艳蓉, 郝世杰, 洪日昌. 基于数据增广和模型集成策略的图神经网络在抑郁症识别上的应用 Application of Graph Neural Network Based on Data Augmentation and Model Ensemble in Depression Recognition 计算机科学, 2022, 49(7): 57-63. https://doi.org/10.11896/jsjkx.210800070
[9]	张洪博, 董力嘉, 潘玉彪, 萧宗志, 张惠臻, 杜吉祥. 视频理解中的动作质量评估方法综述 Survey on Action Quality Assessment Methods in Video Understanding 计算机科学, 2022, 49(7): 79-88. https://doi.org/10.11896/jsjkx.210600028
[10]	杜丽君, 唐玺璐, 周娇, 陈玉兰, 程建. 基于注意力机制和多任务学习的阿尔茨海默症分类 Alzheimer's Disease Classification Method Based on Attention Mechanism and Multi-task Learning 计算机科学, 2022, 49(6A): 60-65. https://doi.org/10.11896/jsjkx.201200072
[11]	李小伟, 舒辉, 光焱, 翟懿, 杨资集. 自然语言处理在简历分析中的应用研究综述 Survey of the Application of Natural Language Processing for Resume Analysis 计算机科学, 2022, 49(6A): 66-73. https://doi.org/10.11896/jsjkx.210600134
[12]	邓凯, 杨频, 李益洲, 杨星, 曾凡瑞, 张振毓. 一种可快速迁移的领域知识图谱构建方法 Fast and Transmissible Domain Knowledge Graph Construction Method 计算机科学, 2022, 49(6A): 100-108. https://doi.org/10.11896/jsjkx.210900018
[13]	黄少滨, 孙雪薇, 李熔盛. 基于跨句上下文信息的神经网络关系分类方法 Relation Classification Method Based on Cross-sentence Contextual Information for Neural Network 计算机科学, 2022, 49(6A): 119-124. https://doi.org/10.11896/jsjkx.210600150
[14]	林夕, 陈孜卓, 王中卿. 基于不平衡数据与集成学习的属性级情感分类 Aspect-level Sentiment Classification Based on Imbalanced Data and Ensemble Learning 计算机科学, 2022, 49(6A): 144-149. https://doi.org/10.11896/jsjkx.210500205
[15]	康雁, 吴志伟, 寇勇奇, 张兰, 谢思宇, 李浩. 融合Bert和图卷积的深度集成学习软件需求分类 Deep Integrated Learning Software Requirement Classification Fusing Bert and Graph Convolution 计算机科学, 2022, 49(6A): 150-158. https://doi.org/10.11896/jsjkx.210500065

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于新型邻域更新策略的MOEA/D算法

MOEA/D Algorithm Based on New Neighborhood Updating Strategy

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0