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

doi:10.11772/j.issn.1001-9081.2017102552

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (5): 1254-1260.DOI: 10.11772/j.issn.1001-9081.2017102552

Previous Articles Next Articles

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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP301.6

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

[1]	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.
[2]	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.
[3]	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.
[4]	CHEN Huan ZHOU Yong-quan ZHAO Guang-wei. Multi-population invasive weed optimization algorithm based on chaotic sequence [J]. Journal of Computer Applications, 2012, 32(07): 1958-1961.
[5]	YU Tao WU Wei-dong. Improved L7-Filter's pattern matching algorithm based on multi-core processors [J]. Journal of Computer Applications, 2012, 32(03): 609-613.
[6]	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.
[7]	PENG Fu-ming. Muti-population coevolutionary algorithm for numerical optimization [J]. Journal of Computer Applications, 2011, 31(03): 660-665.
[8]	. Attribute reduction of rough sets based on differential evolutionary algorithm [J]. Journal of Computer Applications, 2010, 30(9): 2329-2331.
[9]	. Dynamic differential evolution algorithm with random mutation [J]. Journal of Computer Applications, 2009, 29(10): 2719-2722.
[10]	. New evolutionary algorithm based on girdding for dynamic optimization problems [J]. Journal of Computer Applications, 2008, 28(2): 319-321.