改进的排序变异多目标差分进化算法

doi:10.11772/j.issn.1001-9081.2018010260

计算机应用 ›› 2018, Vol. 38 ›› Issue (8): 2157-2163.DOI: 10.11772/j.issn.1001-9081.2018010260

改进的排序变异多目标差分进化算法

刘宝^1,2, 董明刚^1,2, 敬超^1,2

1. 桂林理工大学信息科学与工程学院, 广西桂林 541004;
2. 广西嵌入式技术与智能系统重点实验室(桂林理工大学), 广西桂林 541004

收稿日期:2018-01-29 修回日期:2018-03-14 出版日期:2018-08-10 发布日期:2018-08-11
通讯作者: 董明刚
作者简介:刘宝(1986-),男,安徽六安人,硕士研究生,主要研究方向:智能计算;董明刚(1977-),男,湖北安陆人,教授,博士,CCF会员,主要研究方向:智能计算、机器学习;敬超(1983-),男,河南长葛人,讲师,博士,主要研究方向:云数据中心能耗管理。
基金资助:
国家自然科学基金资助项目（61563012，61203109）；广西自然科学基金资助项目（2014GXNSFAA118371，2015GXNSFBA139260）；广西嵌入式技术与智能系统重点实验室基金。

Multi-objective differential evolution algorithm with improved ranking-based mutation

LIU Bao^1,2, DONG Minggang^1,2, JING Chao^1,2

1. College of Information Science and Engineering, Guilin University of Technology, Guilin Guangxi 541004, China;
2. Guangxi Key Laboratory of Embedded Technology and Intelligent System(Guilin University of Technology), Guilin Guangxi 541004, China

Received:2018-01-29 Revised:2018-03-14 Online:2018-08-10 Published:2018-08-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61563012,61203109), Guangxi Natural Science Foundation (2014GXNSFAA118371, 2015GXNSFBA139260), Guangxi Key Laboratory of Embedded Technology and Intelligent System Foundation.

摘要/Abstract

摘要： 针对多目标差分进化算法在求解问题时收敛速度慢和均匀性欠佳的问题，提出了一种改进的排序变异多目标差分进化算法（MODE-IRM）。该算法将参与变异的三个父代个体中的最优个体作为基向量，提高了排序变异算子的求解速度；另外，算法采用反向参数控制方法在不同的优化阶段动态调整参数值，进一步提高了算法的收敛速度；最后，引入了改进的拥挤距离计算公式进行排序操作，提高了解的均匀性。采用标准多目标优化问题ZDTl~ZDT4，ZDT6和DTLZ6~DTLZ7进行仿真实验:MODE-IRM在总体性能上均优于MODE-RMO和PlatEMO平台上的MOEA/D-DE、RM-MEDA以及IM-MOEA；在世代距离（GD）、反向世代距离（IGD）和间隔指标（SP）性能度量指标方面，MODE-IRM在所有优化问题上的均值和方差均明显小于MODE-RMO。实验结果表明MODE-IRM在收敛性和均匀性指标上明显优于对比算法。

关键词: 多目标优化问题, 差分进化算法, 排序变异算子, 反向参数控制, 拥挤距离

Abstract: Focusing on the slow convergence and the poor uniformity of multi-objective differential evolution algorithms when solving multi-objective optimization problems, a Multi-Objective Differential Evolution algorithm with Improved Ranking-based Mutation (MODE-IRM) was proposed. The optimal individual involved in the mutation was used as the base vector, which accelerated the resolving speed of the ranking-based mutation operator. In addition, a strategy of opposition-based parameter was adopted to dynamically adjust the values of parameters in different optimization stages, so the convergence rate was further accelerated. Finally, an improved crowding distance calculation formula was introduced in the sort operation, which improved the uniformity of solutions. Simulation experiments were conducted on the standard multi-objective optimization problems including ZDTl-ZDT4, ZDT6 and DTLZ6-DTLZ7. MODE-IRM's overall performance was much better than MODE-RMO and other three algorithms of the PlatEMO including MOEA/D-DE (Multiobjective Evolutionary Algorithm based on Decomposition with Differential Evolution), RM-MEDA (Regularity Model-based Multi-objective Estimation of Distribution Algorithm) and IM-MOEA (Inverse Modeling Multi-objective Evolutionary Algorithm). Moreover, in terms of the performance metrics including GD (Generational Distance), IGD (Inverted Generational Distance) and SP (Spacing), the mean and variance of MODE-IRM on all problems were significantly less than those of MODE-RMO. The simulation results show that MODE-IRM has better performance in convergence and uniformity.

Key words: multi-objective optimization problem, Differential Evolution (DE) algorithm, ranking-based mutation operator, opposition-based parameter control, crowding distance

中图分类号:

TP18

刘宝, 董明刚, 敬超. 改进的排序变异多目标差分进化算法[J]. 计算机应用, 2018, 38(8): 2157-2163.

LIU Bao, DONG Minggang, JING Chao. Multi-objective differential evolution algorithm with improved ranking-based mutation[J]. Journal of Computer Applications, 2018, 38(8): 2157-2163.

参考文献

[1] 蔡延光,宋康,张敏捷,等.自适应多目标混合差分进化算法在联盟运输调度中的应用[J].计算机应用,2010,30(11):2887-2890. (CAI Y G, SONG K, ZHANG M J, et al. Adaptive multi-objective hybrid differential evolution algorithm in union transport scheduling[J]. Journal of Computer Applications, 2010, 30(11):2887-2890.)
[2] BALAJI S, DEVARAJ D, HOSIMINTHILAGAR S, et al. Improved multi objective differential evolution algorithm for congestion management in restructured power systems[C]//Proceedings of the 2016 IEEE Industrial Electronics and Applications Conference. Piscataway, NJ:IEEE, 2016:203-210.
[3] SIKDAR U K, EKBAL A, SAHA S. Differential evolution based multiobjective optimization for biomedical entity extraction[C]//ICACCI 2014:Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics. Piscataway, NJ:IEEE, 2014:1039-1044.
[4] 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.
[5] ZHANG Q F, LI H. MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.
[6] 许玉龙,方建安,张晗,等.基于非支配解排序的快速多目标微分进化算法[J].计算机应用,2014,34(9):2547-2551. (XU Y L, FANG J A, ZHANG H, et al. Fast multi-objective differential evolution algorithm based on non-dominated solution sorting[J]. Journal of Computer Applications, 2014,34(9):2547-2551.)
[7] 魏文红,王甲海,陶铭,等.基于泛化反向学习的多目标约束差分进化算法[J].计算机研究与发展,2016,53(6):1410-1421. (WEI W H, WANG J H, TAO M, et al. Multi-objective constrained differential evolution using generalized opposition-based learning[J]. Journal of Computer Research and Development, 2016, 53(6):1410-1421.)
[8] ALI M, SIARRY P, PANT M. An efficient differential evolution based algorithm for solving multi-objective optimization problems[J]. European Journal of Operational Research, 2011, 217(2):404-416.
[9] LEUNG S W, ZHANG X, YUE S Y. Multiobjective differential evolution algorithm with opposition-based parameter control[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2012:1-8.
[10] ZHAO L, LI D, HUANG X, et al. Modified non-dominated sorted differential evolution for multi-objective optimization[C]//CCC 2017:Proceedings of the 201736th Chinese Control Conference. Piscataway, NJ:IEEE, 2017:2830-2834.
[11] CHEN X, DU W, QIAN F. Multi-objective differential evolution with ranking-based mutation operator and its application in chemical process optimization[J]. Chemometrics & Intelligent Laboratory Systems, 2014, 136:85-96.
[12] GONG W, CAI Z. Differential evolution with ranking-based mutation operators[J]. IEEE Transactions on Cybernetics, 2013, 43(6):2066-2081.
[13] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289. (GONG M G, JIAO L C, YANG D D, et al. Research on evolutionary multi-objective optimization algorithm[J]. Journal of Software, 2009, 20(2):271-289.)
[14] 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.
[15] QIAN W, LI A. Adaptive differential evolution algorithm for multiobjective optimization problems[J]. Applied Mathematics & Computation, 2008, 201(1/2):431-440.
[16] WANG Y-N, WU L-H, YUAN X-F. Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure[J]. Soft Computing, 2010, 14:193-209.
[17] TIZHOOSH H R. Opposition-based learning:a new scheme for machine intelligence[C]//CIMCA '05:Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Washington, DC:IEEE Computer Society, 2005:695-701.
[18] DEB K, THIELE L, LAUMANNS M, et al. Scalable multi-objective optimization test problems[C]//CEC'02:Proceedings of the 2002 Congress on Evolutionary Computation. Washington, DC:IEEE Computer Society, 2002:825-830.
[19] TIAN Y, CHENG R, ZHANG X, et al. PlatEMO:a MATLAB platform for evolutionary multi-objective optimization[J]. IEEE Computational Intelligence Magazine, 2017, 12(4):73-87.
[20] TIAN Y, Zhang X, CHENG R, et al. A multi-objective evolutionary algorithm based on an enhanced inverted generational distance metric[C]//CEC'16:Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Washington, DC:IEEE Computer Society, 2016:5222-5229.
[21] COELLO COELLO 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.

改进的排序变异多目标差分进化算法

Multi-objective differential evolution algorithm with improved ranking-based mutation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[3]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[4]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[5]	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.
[6]	谭阳, 唐德权, 曹守富. 基于超球形模糊支配的高维多目标粒子群优化算法[J]. 计算机应用, 2019, 39(11): 3233-3241.
[7]	张鑫, 邹德旋, 沈鑫. 含交叉项的混合二范数粒子群优化算法[J]. 计算机应用, 2018, 38(8): 2148-2156.
[8]	袁亦川, 杨洲, 罗廷兴, 秦进. 求解动态优化问题的多种群竞争差分进化算法[J]. 计算机应用, 2018, 38(5): 1254-1260.
[9]	李贞, 郑向伟, 张辉. 基于多目标粒子群优化的虚拟网络映射算法[J]. 计算机应用, 2017, 37(3): 755-759.
[10]	刘曦, 张潇璐, 张学杰. 异构云系统中基于智能优化算法的多维资源公平分配[J]. 计算机应用, 2016, 36(8): 2128-2133.
[11]	耿焕同, 李辉健, 赵亚光, 陈正鹏. 基于自适应混合非支配个体排序策略的改进型NSGA-Ⅱ算法[J]. 计算机应用, 2016, 36(5): 1319-1324.
[12]	王晓娟刘三阳田文凯. 带高效变异尺度系数和贪婪交叉策略的回溯搜索优化算法[J]. 计算机应用, 2014, 34(9): 2543-2546.
[13]	熊杰邹长春. 基于差分进化的感应测井反演算法[J]. 计算机应用, 2014, 34(3): 911-914.
[14]	徐奕昕白焰赵天阳王仁书. 泊松分布下无线传感器网络多目标覆盖控制[J]. 计算机应用, 2013, 33(07): 1820-1824.
[15]	张敬敏李霞. 求解作业车间调度问题的差分和声搜索算法[J]. 计算机应用, 2013, 33(02): 329-356.