求解动态优化问题的多种群竞争差分进化算法

doi:10.11772/j.issn.1001-9081.2017102552

计算机应用 ›› 2018, Vol. 38 ›› Issue (5): 1254-1260.DOI: 10.11772/j.issn.1001-9081.2017102552

求解动态优化问题的多种群竞争差分进化算法

袁亦川¹, 杨洲¹, 罗廷兴², 秦进¹

1. 贵州大学计算机科学与技术学院, 贵阳 550000;
2. 贵阳市信息产业发展中心, 贵阳 550000

收稿日期:2017-10-27 修回日期:2017-12-26 出版日期:2018-05-10 发布日期:2018-05-24
通讯作者: 罗廷兴
作者简介:袁亦川(1991-),男,江西九江人,硕士研究生,CCF会员,主要研究方向:计算智能、机器学习;杨洲(1993-),女,贵州安顺人,硕士研究生,主要研究方向:计算智能、机器学习;罗廷兴(1977-),贵州贵定人,工程师,主要研究方向:云计算;秦进(1978-),贵州黔西人,副教授,博士,主要研究方向:计算智能、机器学习。
基金资助:
国家自然科学基金资助项目（61562009）；贵州大学引进人才科研项目（2012028）。

Multi-population-based competitive differential evolution algorithm for dynamic optimization problem

YUAN Yichuan¹, YANG Zhou¹, LUO Tingxing², QIN Jin¹

1. College of Computer Science and Technology, Guizhou University, Guiyang Guizhou 550000, China;
2. Guiyang Information Industry Development Center, Guiyang Guizhou 550000, China

Received:2017-10-27 Revised:2017-12-26 Online:2018-05-10 Published:2018-05-24
Contact: 罗廷兴
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61562009), the Introduced Talents for Research Project of Guizhou University (2012028).

摘要/Abstract

摘要： 针对动态优化问题（DOP）的求解，提出结合多种群方法和竞争策略的差分进化算法（DECS）。首先，将一个种群作为侦测种群，通过监测种群中所有个体的评价值和种群维度来判断环境是否发生变化。其次，将余下多个种群作为搜索种群，独立搜索环境中的最优值。在搜索过程中，引入排除规则，避免多个搜索种群聚集在同一个局部最优的邻域。在迭代若干代后对各搜索种群执行竞争操作，保留评估值最优个体所在的种群并对该种群的下一代个体生成采用量子个体生成机制，而对其他搜索种群重新初始化。最后，利用7个测试函数的49个动态变化问题对DECS进行验证，并将实验结果与人工免疫算法（Dopt-aiNet）、复位粒子群优化（rPSO）算法、改进差分进化（MDE）算法进行比较。实验结果表明，在49个问题上，DECS有34个问题的平均离线误差期望小于Dopt-aiNet算法，所有问题的平均离线误差期望都小于rPSO算法和MDE算法，因此DECS对DOP求解动态优化问题是可行的。

关键词: 差分进化算法, 动态优化, 多种群, 竞争策略, 排除规则

Abstract: To solve Dynamic Optimization Problems (DOP), a Differential Evolution algorithm with Competitive Strategy based on multi-population (DECS) was proposed. Firstly, one of the populations was chosen as a detection population. Whether the environment had changed was determined by monitoring the fitness values of all individuals in the population and dimension of the population. Secondly, the remaining populations were used as the search populations to search the optimal value independently. During the search, a exclusion rule was introduced to avoid the aggregation of multiple search populations in the same local optimal neighborhood. After the iteration of several generations, competitive operation was performed on all search populations. The population to which the optimal individual belong was retained and the next generation's individuals of the population were generated by using the quantum individual generation mechanism. Then other search populations were reinitialized. Finally, 49 dynamic change problems about 7 test functions were used to verify DECS, and the experimental results were compared with Artificial Immune Network for Dynamic optimization (Dopt-aiNet) algorithm, restart Particle Swarm Optimization (rPSO) algorithm, and Modified Differential Evolution (MDE) algorithm. The experimental results show that the average error mean of 34 problems for DECS is less than Dopt-aiNet and the average error mean of all problems for DECS was less than that for rPSO and MDE. Therefore, DECS is feasible to solve DOP.

Key words: Differential Evolution (DE) algorithm, dynamic optimization, multi-population, competitive strategy, exclusion rule

中图分类号:

TP301.6

袁亦川, 杨洲, 罗廷兴, 秦进. 求解动态优化问题的多种群竞争差分进化算法[J]. 计算机应用, 2018, 38(5): 1254-1260.

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.

参考文献

[1] DAS S, MANDAL A, MUKHERJEE R. An adaptive differential evolution algorithm for global optimization in dynamic environments[J]. IEEE Transactions on Cybernetics, 2014, 44(6):966-978.
[2] BREST J, ZAMUDA A, BOSKOVIC B, et al. Dynamic optimization using self-adaptive differential evolution[C]//Proceedings of the 11th Conference on Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2009:415-422.
[3] JIN Y, BRANKE J. Evolutionary optimization in uncertain environments:a survey[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(3):303-317.
[4] TROJANOWSKI K, MICHALEWICZ Z. Evolutionary optimization in non-stationary environments[J]. Journal of Computer Science & Technology, 2000(3):1-32.
[5] 陈莉, 丁立新. 动态优化算法综述[J]. 武汉大学学报(理学版), 2011, 57(3):255-264.(CHEN L,DING L X. A survey of dynamic optimization algorithms[J]. Journal of Wuhan University:Science Edition, 2011, 57(3):255-264.
[6] YANG S, LI C. A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(6):959-974.
[7] 姜立强, 强洪夫, 刘光斌. 求解动态优化问题的改进差分进化算法[J]. 小型微型计算机系统, 2013, 34(12):2837-2840.(JIANG L Q, QIANG H F, LIU G B. Modified differential evolution for dynamic optimization problems[J]. Journal of Chinese Computer Systems, 2013, 34(12):2837-2840.
[8] 陈健, 申元霞, 纪滨. 求解动态优化问题的多种群骨干粒子群算法[J]. 计算机工程与应用, 2017,53(19):45-50.(CHEN J,SHEN Y X,JI B. Multi-swarms bare bones particle swarms optimization of solving dynamic optimization problems[J]. Computer Engineering and Applications, 2017, 53(19):45-50.)
[9] ALI M Z, AWAD N H, SUGANTHAN P N, et al. An adaptive multipopulation differential evolution with dynamic population reduction[J]. IEEE Transactions on Cybernetics, 2016, 47(9):2768-2779.
[10] WEICKER K. An analysis of dynamic severity and population size[C]//Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. London:Springer-Verlag, 2000:159-168.
[11] ARAGON V S, ESQUIVEL S C. An evolutionary algorithm to track changes of optimum value locations in dynamic environments[J]. Journal of Computer Science & Technology, 2004, 4(3):127-133.
[12] ROHLFSHAGEN P, YAO X. Dynamic combinatorial optimisation problems:an analysis of the subset sum problem[J]. Soft Computing, 2011, 15(9):1723-1734.
[13] STORN R, PRICE K. Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4):341-359.
[14] DAS S, SUGANTHAN P N. Differential evolution:a survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1):4-31.
[15] TASGETIREN M F, SUGANTHAN P N. A multi-populated differential evolution algorithm for solving constrained optimization problem[C]//Proceedings of the 2006 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2006:33-40.
[16] BLACKWELL T, BRANKE J. Multi-swarm optimization in dynamic environments[C]//Proceedings of the 2004 European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin:Springer, 2004:489-500.
[17] MENDES R, MOHAIS A S. DynDE:a differential evolution for dynamic optimization problems[C]//Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2005:2808-2815.
[18] LI C, YANG S, NGUYEN T T, et al. Benchmark generator for CEC 2009 competition on dynamic optimization[J]. Sensor Letters, 2008, 11(5):900-909.
[19] DE F F O, VON Z F J. A dynamic artificial immune algorithm applied to challenging benchmarking problems[C]//Proceedings of the 11th Conference on Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2009:423-430.

求解动态优化问题的多种群竞争差分进化算法

Multi-population-based competitive differential evolution algorithm for dynamic optimization problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.
[2]	张鑫, 邹德旋, 沈鑫. 含交叉项的混合二范数粒子群优化算法[J]. 计算机应用, 2018, 38(8): 2148-2156.
[3]	刘宝, 董明刚, 敬超. 改进的排序变异多目标差分进化算法[J]. 计算机应用, 2018, 38(8): 2157-2163.
[4]	谢红侠, 马晓伟, 陈晓晓, 邢强. 基于多种群的改进粒子群算法多模态优化[J]. 计算机应用, 2016, 36(9): 2516-2520.
[5]	刘曦, 张潇璐, 张学杰. 异构云系统中基于智能优化算法的多维资源公平分配[J]. 计算机应用, 2016, 36(8): 2128-2133.
[6]	杨靖, 张宏军, 赵水宁, 占栋辉. 基于粒子群优化算法的虚拟机部署策略[J]. 计算机应用, 2016, 36(1): 117-121.
[7]	王铭波, 符强, 童楠, 刘政, 赵一鸣. 基于模拟退火机制的多种群萤火虫算法[J]. 计算机应用, 2015, 35(3): 691-695.
[8]	王晓娟刘三阳田文凯. 带高效变异尺度系数和贪婪交叉策略的回溯搜索优化算法[J]. 计算机应用, 2014, 34(9): 2543-2546.
[9]	熊杰邹长春. 基于差分进化的感应测井反演算法[J]. 计算机应用, 2014, 34(3): 911-914.
[10]	徐奕昕白焰赵天阳王仁书. 泊松分布下无线传感器网络多目标覆盖控制[J]. 计算机应用, 2013, 33(07): 1820-1824.
[11]	张敬敏李霞. 求解作业车间调度问题的差分和声搜索算法[J]. 计算机应用, 2013, 33(02): 329-356.
[12]	王永皎. 改进自适应差分进化算法求解大规模整数任务分配[J]. 计算机应用, 2012, 32(08): 2165-2167.
[13]	陈欢周永权赵光伟. 基于混沌序列的多种群入侵杂草算法[J]. 计算机应用, 2012, 32(07): 1958-1961.
[14]	余涛吴卫东. 基于多核处理器的L7-Filter规则匹配改进算法[J]. 计算机应用, 2012, 32(03): 609-613.
[15]	彭复明. 多种群协同进化数值优化算法[J]. 计算机应用, 2011, 31(03): 660-665.