《计算机应用研究》|Application Research of Computers

利用帕累托非支配关系实现高效三目标差分进化的方法

Using Pareto dominance relationship to realize efficient tripe-objective differential evolution algorithm

免费全文下载 (已被下载 次)  
获取PDF全文
作者 许玉龙,潘旭,王忠义,盛梦园,王林景
机构 1.河南中医药大学 信息技术学院,郑州 450046;2.郑州大学 信息工程学院,郑州 450052;3.香港科技大学 计算机科学与工程系,香港
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)03-035-0817-07
DOI 10.19734/j.issn.1001-3695.2017.09.0909
摘要 在多目标进化算法中,时间复杂度过高是普遍的问题,特别是三个目标函数以上时,解的等级分配占用了过多的运算时间。针对三目标问题,利用帕累托支配关系,对解的等级分配进行研究,发现经典的等级排序及分配方法存在一定的冗余操作,需对全部的解先排序后,才能再分配等级并选择下一代,造成部分不必要的运算。为减少该冗余,利用帕累托非支配关系结合差分进化,实现高效三目标进化算法。算法每次迭代对种群中最高等级的个体进行计算,在分配等级同时进行选择后代个体操作,当后代种群生成时便跳出计算,从而减少个体的计算数量,降低运算量;同时给出该方法的相关理论分析和证明过程。针对一系列三目标优化问题,将提出方法与著名排序方法NSGAⅡ及近年来优秀的ENS方法进行对比实验。仿真实验结果表明,提出方法在时间复杂度和收敛速度上优于经典方法,稍差于ENS方法。在标准测试函数DTLZ1-DTLZ6的性能上,提出方法近似于ENS方法,优于NSGAⅡ算法,从而验证了提出方法的有效性和正确性。
关键词 三目标进化;帕累托;非支配解排序;收敛速度
基金项目 国家自然科学基金资助项目(81703946,61772475)
河南省科技攻关研究项目(172102210361,172102310536)
河南省高校重点科研项目(15A520083,16A520060,17B520017)
河南中医药大学博士基金资助项目(BSJJ2015-19)
本文URL http://www.arocmag.com/article/01-2019-03-035.html
英文标题 Using Pareto dominance relationship to realize efficient tripe-objective differential evolution algorithm
作者英文名 Xu Yulong, Pan Xu, Wang Zhongyi, Sheng Mengyuan, Wang Linjing
机构英文名 1.InstituteofInformation&Technology,HenanUniversityofChineseMedicine,Zhengzhou450046,China;2.InstituteofInformationEngineering,ZhengzhouUniversity,Zhengzhou450052,China;3.Dept.ofComputerScience&Engineering,HongKongUniversityofScience&Technology,HongKong,China
英文摘要 In the Multi-objective evolutionary algorithm, the solution of the rank distribution takes up most of the computation time.According to the Pareto dominance relationship, this paper researched the solution of the rank and distribution, and found that there are some redundancy operation of rank and allocation in the classic methods.The classic algorithms need to rank all solutions, and select the next generation after sort, so it caused some unnecessary sort operations.To reduce the redundancy, this paper introduced a fast method of non-dominated sorting.The proposed algorithm only dealed the individual which belong the highest level in current population, and meanwhile it could choose individual into the next generation during the process of distribution level.When the next generation individuals were selected enough, the program was ended.This method reduced the number of the sorting of individuals, and also reduced the time complexity greatly.Then, it used three objectives optimization problem as an example, combined the fast non-dominated sorting method with the differential evolution algorithm, and proposed a fast three objective differential evolution algorithm based on non-dominated sorting.Finally, it compared this method with the famous ranking method and ENS/BNS method.The simulation results show that the proposed algorithm in time complexity and convergence speed is better than the classical method, and is not worse than the ENS/BNS algorithm.On the performance of the standard test function DTLZ1-DTLZ6, the proposed method is similar to or better than the comparison algorithms.The experiment verifies the correctness and effectiveness of the proposed method.
英文关键词 tripe-objective; Pareto; non-dominated solution sorted; convergence speed
参考文献 查看稿件参考文献
  [1] Coello C A, Lamont G B, Van Veldhuizen D A. Evolutionary algorithms for solving multi-objective problems[M] . Berlin:Springer, 2007:101-140.
[2] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm NSGA-Ⅱ[J] . IEEE Trans on Evolutionary Computation, 2002, 6(2):182-197.
[3] Zitzler E, Laumanns M, Thiele L. SPEA2:improving the strength Pareto evolutionary algorithm[C] //Proc of Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problem. 2002:95-100.
[4] Gong Maoguo, Wang Shanfeng, Liu Wenfeng, et al. Evolutionary computation in China:a literature survey[J] . CAAI Trans on Intelligence Technology, 2016, 1(4):334-354.
[5] 谢涛, 陈火旺, 康立山. 多目标优化的演化算法[J] . 计算机学报, 2003, 26(8):997-1003. (Xie Tao, Chen Huowang, Kang Lishan. Evolutionary algorithms of multi-objective optimization problems[J] . Chinese Journal of Computers, 2003, 26(8):997-1003. )
[6] Cui Xunxue, Li Qin, Tao Qing. Genetic algorithm for Pareto optimum-based route selection[J] . Journal of Systems Engineering and Electronics, 2007, 18(2):360-368.
[7] 王勇, 蔡自兴, 周育人, 等. 约束进化算法[J] . 软件学报, 2009, 20(1):11-29. (Wang Yong, Cai Zhixing, Zhou Yuren, et al. Constrained optimization evolutionary algorithms[J] . Journal of Software, 2009, 20(1):11-29. )
[8] 郑建国, 王翔, 刘荣辉. 求解约束优化问题的ε-DE算法[J] . 软件学报, 2012, 23(9):2374-2387. (Zheng Jianguo, Wang Xiang, Liu Ronghui. ε-differential evolution algorithm for constrained optimization problems[J] . Journal of Software, 2012, 23(9):2374-2387. )
[9] Tang Suqin, Cai Zixing, Zheng Jinhua. A fast method of constructing the non-dominated set:arena’s principle[C] //Proc of the 4th International Conference on Natural Computation. Piscataway, NJ:IEEE Press, 2008:391-395.
[10] McClymont K, Keedwell E. Deductive sort and climbing sort:new methods for non-dominated sorting[J] . Evolutionary Computation, 2012, 20(1):1-26.
[11] Zhang Xingyi, Tian Ye, Cheng Ran, et al. An efficient approach to non-dominated sorting for evolutionary multi-objective optimization[J] . IEEE Trans on Evolutionary Computation, 2015, 19(2):201-213.
[12] Xu Yulong, Fang Jian’an, Zhu Wu, et al. Differential evolution using a superior-inferior crossover scheme[J] . Computational Optimization and Applications, 2015, 61(1):243-274.
[13] Das S, Mullick S S, Suganthan P N. Recent advances in differential evolution:an updated survey[J] . Swarm and Evolutionary Computation, 2016, 27(4):1-30.
[14] Abbass H, Sarker R. The Pareto differential evolution algorithm[J] . International Journal on Artificial Intelligence Tools, 2002, 11(4):531-552.
[15] Robic T, Filipic B. DEMO:differential evolution for multi-objective optimization[C] //Proc of the 3rd International Conference on Evolutionary Multi-criterion Optimization. Berlin:Springer-Verlag, 2005:520-533.
[16] 杨平, 郑金华, 李密青, 等. 一种快速构造多目标Pareto非支配集的方法:选举法则[J] . 计算机应用研究, 2009, 26(2):488-491. (Yang Ping, Zheng Jinhua, Li Miqing, et al. Fast method of constructing multi-objective Pareto non-dominated set:election principle[J] . Application Research of Computers, 2009, 26(2):488-491. )
[17] 任长安, 李智勇, 陈友文. 一种改进的基于目标空间分割的多目标进化算法[J] . 计算机应用研究, 2010, 27(4):1311-1314, 1318. (Ren Chang’an, Li Zhiyong, Chen Youwen. Improved multi-objective evolutionary algorithm based on objective-space-divided[J] . Application Research of Computers, 2010, 27(4):1311-1314, 1318. )[18] 吴佳英, 李平, 郑金华. 一种基于多亲遗传机制的多目标优化算法[J] . 计算机应用与软件, 2008, 25(2):52-53, 79. (Wu Jiaying, Li Ping, Zheng Jinhua. A multi-objective genetic algorithm based on multi-parent crossover[J] . Computer Applications and Software, 2008, 25(2):52-53, 79. )
[19] 谭阳, 谭岳武, 唐钊轶. 基于海明差异评价的多目标进化算法[J] . 计算机工程, 2014, 40(2):212-218. (Tan Yang, Tan Yuewu, Tang Zhaoyi. Multi-objective evolutionary algorithm based on hamming differences evaluation[J] . Computer Engineering, 2014, 40(2):212-218. )
[20] 鲍培明, 朱庆保. 用于多目标进化的归一化排序非支配集构造方法[J] . 电子学报, 2009, 37(9):2010-2015. (Bao Peiming, Zhu Qingbao. A technique of building non-dominated set based on normalized sort in evolutionary multi-objective optimization[J] . Acta Electronica Sinica, 2009, 37(9):2010-2015. )
[21] 黄映, 李扬, 高赐威. 基于非支配排序差分进化算法的多目标电网规划[J] . 电网技术, 2011, 35(3):85-89. (Huang Ying, Li Yang, Gao Ciwei. Multi-objective transmission network planning based on non-dominated sorting differential evolution[J] . Power System Technology, 2011, 35(3):85-89. )
[22] 李斌, 钟润添, 肖金超, 等. 一种基于边缘分布估计的多目标优化算法[J] . 电子与信息学报, 2007, 29(11):2683-2687. (Li Bin, Zhong Runtian, Xiao Jinchao, et al. A multi-objective optimization algorithm based on marginal distribution estimation[J] . Journal of Electronics & Information Technology, 2007, 29(11):2683-2687. )
[23] Wang Xianping, Tang Lixin. An adaptive multi-population differential evolution algorithm for continuous multi-objective optimization[J] . Information sciences, 2016, 348(6):124-141.
[24] Cheng Jixiang, Yen G G, Zhang Gexiang. A grid-based adaptive multi-objective differential evolution algorithm[J] . Information Sciences, 2016, 367(11):890-908
[25] 李雯, 李和成. 基于空间网格划分的多目标进化算法[J] . 计算机工程与应用, 2014, 50(8):53-56, 117. (Li Wen, Li Hecheng. Multi-objective evolutionary algorithm based on space-gridding scheme[J] . Computer Engineering and Applications, 2014, 50(8):53-56, 117. )
[26] 许玉龙, 方建安, 张晗, 等. 基于非支配解排序的快速多目标微分进化算法[J] . 计算机应用, 2014, 34(9):2547-2551. (Xu Yulong, Fang Jian’an, Zhang Han, et al. Fast multi-objective differential evolution algorithm based on non-dominated solution sorting[J] . Journal of Computer Applications, 2014, 34(9):2547-2551. )
收稿日期 2017/9/3
修回日期 2017/11/21
页码 817-823,828
中图分类号 TP311
文献标志码 A