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

doi:10.11772/j.issn.1001-9081.2018010260

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (8): 2157-2163.DOI: 10.11772/j.issn.1001-9081.2018010260

Previous Articles Next Articles

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.

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

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

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

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

Abstract

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

摘要： 针对多目标差分进化算法在求解问题时收敛速度慢和均匀性欠佳的问题，提出了一种改进的排序变异多目标差分进化算法（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在收敛性和均匀性指标上明显优于对比算法。

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

CLC Number:

TP18

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 12

Recommended Articles

Metrics

[1]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[2]	LI Erchao, YANG Rongrong. Multi-objective estimation of distribution algorithm with adaptive opposition-based learning [J]. Journal of Computer Applications, 2021, 41(1): 15-21.
[3]	ZHANG Xin, ZOU Dexuan, SHEN Xin. Hybrid two-norm particle swarm optimization algorithm with crossover term [J]. Journal of Computer Applications, 2018, 38(8): 2148-2156.
[4]	YUAN Yichuan, YANG Zhou, LUO Tingxing, QIN Jin. Multi-population-based competitive differential evolution algorithm for dynamic optimization problem [J]. Journal of Computer Applications, 2018, 38(5): 1254-1260.
[5]	LI Zhen, ZHENG Xiangwei, ZHANG Hui. Virtual network embedding algorithm based on multi-objective particle swarm optimization [J]. Journal of Computer Applications, 2017, 37(3): 755-759.
[6]	GENG Huantong, LI Huijian, ZHAO Yaguang, CHEN Zhengpeng. Improved NSGA-Ⅱ algorithm based on adaptive hybrid non-dominated individual sorting strategy [J]. Journal of Computer Applications, 2016, 36(5): 1319-1324.
[7]	LI Kangshun, ZUO Lei, LI Wei. Novel differential evolution algorithm based on simplex-orthogonal experimental design [J]. Journal of Computer Applications, 2016, 36(1): 143-149.
[8]	PENG Hu HUANG Wei DENG Chang-shou. Multi-objective particle swarm optimization algorithm of multi-swarm co-evolution [J]. Journal of Computer Applications, 2012, 32(02): 456-460.
[9]	Shou-heng TUO Wen-yong WANG. Self-adaptive differential evolution algorithm based on orthogonal and niche elite for high-dimensional multi-modal optimization [J]. Journal of Computer Applications, 2011, 31(04): 1094-1098.
[10]	. Attribute reduction of rough sets based on differential evolutionary algorithm [J]. Journal of Computer Applications, 2010, 30(9): 2329-2331.
[11]	. Dynamic differential evolution algorithm with random mutation [J]. Journal of Computer Applications, 2009, 29(10): 2719-2722.
[12]	Mi-qing LI Jin-hua ZHENG Biao LUO Jun WU Shi-hua WEN. Multi-objective evolutionary algorithm based on neighborhood [J]. Journal of Computer Applications, 2008, 28(6): 1570-1574.