基于最小距离和聚合策略的分解多目标进化算法

doi:10.11772/j.issn.1001-9081.2020060891

计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 22-28.DOI: 10.11772/j.issn.1001-9081.2020060891

所属专题：第八届中国数据挖掘会议(CCDM 2020)

• 第八届中国数据挖掘会议(CCDM 2020) • 上一篇下一篇

基于最小距离和聚合策略的分解多目标进化算法

李二超, 李康伟

兰州理工大学电气工程与信息工程学院, 兰州 730050

收稿日期:2020-05-30 修回日期:2020-07-28 发布日期:2020-08-11 出版日期:2021-01-10
通讯作者: 李二超
作者简介:李二超(1980-),男,河北保定人,教授,博士,主要研究方向:人工智能、多目标优化、机器人控制;李康伟(1994-),男,甘肃天水人,硕士研究生,主要研究方向:多目标优化。
基金资助:
国家自然科学基金资助项目（61763026）。

Decomposition based many-objective evolutionary algorithm based on minimum distance and aggregation strategy

LI Erchao, LI Kangwei

College of Electrical Engineering and Information Engineering, Lanzhou University of Technology, Lanzhou Gansu 730050, China

Received:2020-05-30 Revised:2020-07-28 Online:2020-08-11 Published:2021-01-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61763026).

摘要/Abstract

摘要： 针对基于帕累托（Pareto）支配的多目标进化算法在解决高维问题时选择压力降低，以及基于分解的多目标进化算法在提高收敛性和分布性的同时降低了种群多样性的问题，提出了一种基于最小距离和聚合策略的分解多目标进化算法。首先，使用基于角度分解的技术将目标空间分解为指定个数的子空间来提高种群的多样性；然后，在生成新解的过程中加入基于聚合的交叉邻域方法，使生成的新解更接近于父代解；最后，分两阶段在每个子空间内基于最小距离和聚合策略来选择解以提高收敛性和分布性。为了验证所提算法的可行性，采用标准测试函数ZDT和DTLZ进行仿真实验，结果表明所提算法的总体性能均优于经典的基于分解的多目标进化算法（MOEA/D）、MOEA/D-DE、NSGA-Ⅲ和GrEA。可见，所提算法在提高多样性的同时可以有效平衡收敛性和多样性。

关键词: 进化优化算法, 多目标优化问题, 收敛性, 多样性, 分布性, 分解

Abstract: Concerning the issue that the selection pressure of Pareto control based many-objective evolutionary algorithm is reduced when solving the problem of high-dimension and the diversity of the population is reduced of many-objective evolutionary algorithm based on decomposition when improving convergence and distribution, a decomposition based many-objective evolutionary algorithm based on minimum distance and aggregation strategy was proposed. Firstly, the angle decomposition based technique was used to decompose the target space into a specified number of subspaces in order to improve the diversity of population. Then, the method of cross neighborhood based on aggregation was added in the process of generating new solution, making the generated new solution closer to the parent solution. Finally, the convergence and distribution were improved by selecting solutions in each subspace based on minimum distance and aggregation strategy in two stages. In order to verify the feasibility of the algorithm, benchmark functions ZDT and DTLZ were used to conduct simulation experiments. The results show that the performance of the proposed algorithm is superior to those of the classical MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition), MOEA/D-DE (MOEA/D based on Differential Evolution), NSGA-Ⅲ (Nondominated Sorting Genetic Algorithms Ⅲ) and GrEA (Grid-based Evolutionary Algorithm). It can be seen that the proposed algorithm can effectively balance convergence and diversity while improving diversity.

Key words: evolutionary optimization algorithm, Many-objective Optimization Problem (MOP), convergence, diversity, distribution, decomposition

中图分类号:

TP181

李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.

LI Erchao, LI Kangwei. Decomposition based many-objective evolutionary algorithm based on minimum distance and aggregation strategy[J]. Journal of Computer Applications, 2021, 41(1): 22-28.

参考文献

[1] COLLETTE Y, SIARRY P. Multiobjective Optimization:Principles and Case Studies[M]. Berlin:Springer, 2004:273-316.
[2] SRINIVAS N, DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation,1994,2(3):221-248.
[3] SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of the 1st International Conference on Genetic Algorithms. Mahwah, NJ:Lawrence Erlbaum Associates,Inc.,1985:93-100.
[4] HORN J,NAFPLIOTIS N,GOLDBERG D E. A niched Pareto genetic algorithm for multiobjective optimization[C]//Proceedings of the 1st IEEE Conference on Evolutionary Computation/1994 IEEE World Congress on Computational Intelligence. Piscataway:IEEE,1994:82-87.
[5] ZITZLER E,THIELE L. Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[6] ZITZLER E,LAUMANNS M,THIELE L. SPEA2:improving the strength Pareto evolutionary algorithm[C]//Proceedings of EUROGEN 2011-Evolutionary and Deterministic Methods for Design,Optimization and Control with Applications to Industrial and Societal Problems. Athens:[s. n.],2001:95-100.
[7] DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[8] CAI X,SUN H,FAN Z. A diversity indicator based on reference vectors for many-objective optimization[J]. Information Sciences, 2018,430/431:467-486.
[9] 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.
[10] 袁源. 基于分解的多目标进化算法及其应用[D]. 北京:清华大学,2015:30-61. (YUAN Y. Decomposition-based multiobjective evolutionary algorithms and their applications[D]. Beijing:Tsinghua University,2015:30-61.)
[11] 巩敦卫, 刘益萍, 孙晓燕, 等. 基于目标分解的高维多目标并行进化优化方法[J]. 自动化学报,2015,41(8):1438-1451. (GONG D W,LIU Y P,SUN X Y,et al. Parallel many-objective evolutionary optimization using objectives decomposition[J]. Acta Automatica Sinica,2015,41(8):1438-1451.)
[12] BI X,WANG C. An improved NSGA-Ⅲ algorithm based on elimination operator for many-objective optimization[J]. Memetic Computing,2017,9(4):361-383.
[13] BANDYOPADHYAY S,MUKHERJEE A. An algorithm for manyobjective optimization with reduced objective computations:a study in differential evolution[J]. IEEE Transactions on Evolutionary Computation,2015,19(3):400-413.
[14] ZHANG X,TIAN Y,JIN Y. A knee point-driven evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation,2015,19(6):761-776.
[15] ASAFUDDOULA M,RAY T,SARKER R A. A decompositionbased evolutionary algorithm for many objective optimization[J]. IEEE Transactions on Evolutionary Computation,2015,19(3):445-460.
[16] LI Z, LIN K, NOUIOUA M, et al. DCDG-EA:dynamic convergence-diversity guided evolutionary algorithm for manyobjective optimization[J]. Expert Systems with Applications, 2019,118:35-51.
[17] ZHANG Q, LI H. MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[18] HE Z, YEN G G. Many-objective evolutionary algorithm:objective space reduction and diversity improvement[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(1):145-160.
[19] LIU H,GU F,ZHANG Q. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation,2014,18(3):450-455.
[20] LI H, ZHANG Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2):284-302.
[21] LI K,DEB K,ZHANG Q,et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.
[22] CAI X,MEI Z,FAN Z. A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors[J]. IEEE Transactions on Cybernetics,2018,48(8):2335-2348.
[23] TRIVEDI A,SRINIVASAN D,SANYAL K,et al. A survey of multiobjective evolutionary algorithms based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2017,21(3):440-462.
[24] 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.
[25] ZHOU A, QU B, LI H, et al. Multiobjective evolutionary algorithms:a survey of the state of the art[J]. Swarm and Evolutionary Computation,2011,1(1):32-49.
[26] GIAGKIOZIS I, FLEMING P J. Methods for multi-objective optimization:an analysis[J]. Information Sciences,2015,293:338-350.
[27] DAS I, DENNIS J E. Normal-boundary intersection:a new method for generating the Pareto surface in nonlinear multi-criteria optimization problems[J]. SIAM Journal on Optimization,1998,8(3):631-657.
[28] ZITZLER E,DEB K,THIELE L. Comparison of multiobjective evolutionary algorithms:empirical results[J]. Evolutionary Computation,2000,8(2):173-195.
[29] DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multi-objective optimization[M]//ABRAHAM A, JAIN L, GOLDBERG R. Evolutionary Multiobjective Optimization:Theoretical Advances and Applications. London:Springer,2005:105-145.
[30] 郑金华, 邹娟. 多目标进化优化[M]. 北京:科学出版社, 2017:203-208. (ZHENG J H, ZOU J. Multi-objective evolutionary optimization[M]. Beijing:Science Press,2017:203-208.)
[31] YANG S, LI M, LIU X, et al. A grid-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation,2013,17(5):721-736
[32] BOSMAN P A N,THIERENS D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation,2003,7(2):174-188.
[33] LI M, ZHENG J. Spread assessment for evolutionary multiobjective optimization[C]//Proceedings of the 2009 International Conference on Evolutionary Multi-Criterion Optimization,LNCS 5467. Berlin:Springer,2009:216-230.
[34] WANG Z K,ZHANG Q F,LI H,et al. On the use of two reference points in decomposition based multiobjective evolutionary algorithms[J]. Swarm and Evolutionary Computation,2017,34:89-102.

基于最小距离和聚合策略的分解多目标进化算法

Decomposition based many-objective evolutionary algorithm based on minimum distance and aggregation strategy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[2]	任烈弘, 黄铝文, 田旭, 段飞. 基于DFT的频率敏感双分支Transformer多变量长时间序列预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2739-2746.
[3]	李源, 林秋兰, 陈安之, 杨国利, 宋威, 王国仁. 基于树分解的时序最短路径计数查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2446-2454.
[4]	王东炜, 刘柏辰, 韩志, 王艳美, 唐延东. 基于低秩分解和向量量化的深度网络压缩方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 1987-1994.
[5]	张俊娜, 王欣新, 李天泽, 赵晓焱, 袁培燕. 基于动态服务缓存辅助的任务卸载方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1493-1500.
[6]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[7]	任帅, 纪元法, 孙希延, 韦照川, 林子安. 基于改进灰狼优化与支持向量回归的滑坡位移预测[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 972-982.
[8]	张卓, 陈花竹. 基于一致性和多样性的多尺度自表示学习的深度子空间聚类[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 353-359.
[9]	黄亚伟, 钱雪忠, 宋威. 基于双档案种群大小自适应方法的改进差分进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3844-3853.
[10]	曾渝, 张洋, 曾尚, 付茂栗, 何启学, 曾林隆. 基于多尺度门控膨胀卷积网络的时间序列预测算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3427-3434.
[11]	刘文博, 于连飞, 谢冬梅, 蔡闯, 曲志坚, 任崇广. 基于多尺度特征融合的时间序列长期预测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3435-3441.
[12]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[13]	徐则林, 杨敏, 陈勐. 融合空间和文本信息的兴趣点类别表征模型[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2456-2461.
[14]	周寅莹, 周允升, 余敦辉, 孙军. 基于消极相似性的自适应社会化推荐[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2439-2447.
[15]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.