Differential Evolution Algorithm Guided by Elite Island Population

doi:10.3778/j.issn.1002-8331.2009-0214

Abstract

Abstract:

A differential evolution algorithm based on elitist island population（EIDE） is proposed to solve the problems of premature convergence and search stagnation. In order to enhance both global search and local search ability, the algorithm divides the population into several island populations, and dynamically classifies types of these island populations according to the fitness. For the elite islands, an adaptive method of control parameters is proposed. The adaptive parameters are determined by the fitness of the mutation individuals and the whole island, so mutation operators and crossovers operator will be adjusted adaptively. And a mutation strategy to enhance local search is combined to improve convergence speed and accuracy. For common islands, mutation and crossover operators suitable for global search are used to maintain population diversity. The algorithm proposes two strategies to control the flow of high-quality genes, one is called a direction-controlled migration strategy, and the other is individual transfer strategy, so that the algorithm can effectively avoid premature convergence and search stagnation. By testing on 9 typical test functions, the results show that the proposed algorithm has strong global optimization ability, stability, and has quicker convergence speed.

Key words: differential evolutionary algorithm, island model, subpopulation classification, parameter adaptation

摘要：

针对差分进化算法常见的早熟收敛、搜索停滞和求解精度低的问题，研究一种精英化岛屿种群的差分进化算法（EIDE）。为了实现全局搜索与局部搜索能力并重，EIDE划分多个岛屿种群，根据迭代时的适应度情况，动态地将岛屿种群分类为精英岛屿和普通岛屿；针对精英岛屿，提出一种控制参数自适应方法，依据岛屿适应度情况，自适应地调整变异概率与交叉概率，同时算法利用增强局部搜索的变异策略，提高收敛速度与精度；针对普通岛屿，使用适合全局搜索的变异与交叉概率及变异策略，维护种群多样性。EIDE提出了一种可控的“移民”与“个体迁移”策略，控制优质基因流动，有效避免早熟收敛与搜索停滞问题。在9个benchmark函数上的测试结果表明，新算法具有较强的全局寻优能力与稳定性，且收敛速度较快。

关键词: 差分进化算法, 岛屿模型, 子种群分类, 参数自适应

QIAN Zhengyuan, ZENG Guosun. Differential Evolution Algorithm Guided by Elite Island Population[J]. Computer Engineering and Applications, 2021, 57(20): 73-81.

钱峥远，曾国荪. 精英化岛屿种群引导的差分进化算法[J]. 计算机工程与应用, 2021, 57(20): 73-81.

References

[1] 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.
[2] ZHOU S C，XING L N，ZHENG X，et al.A self-adaptive differential evolution algorithm for scheduling a single batch-processing machine with arbitrary job sizes and release times[J].IEEE Transactions on Cybernetics，2019：1-13.
[3] TANG L，ZHAO Y，LIU J.An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production[J].IEEE Transactions on Evolutionary Computation，2014，18（2）：209-225.
[4] 张晓丽.基于改进差分进化算法的二维最大熵图像分割[J].自动化技术与应用，2016，35（6）：69-72.
ZHANG X L.2-D maximum entropy method in image segmentation based on dynamic differential evolution[J].Techniques of Automation and Applications，2016，35（6）：69-72.
[5] 杨媛媛，杨京燕，夏天，等.基于改进差分进化算法的风电并网系统多目标动态经济调度[J].电力系统保护与控制，2012，40（23）：24-29.
YANG Y Y，YANG J Y，XIA T，et al.Multi-objective dynamic economic dispatch in wind power integrated system based on an improved differential evolution algorithm[J].Power System Protection and Control，2012，40（23）：24-29.
[6] 段建东，杨杉.基于改进差分进化法的含双馈型风电场的配电网无功优化[J].电力自动化设备，2013，33（11）：123-127.
DUAN J D，YANG S.Reactive power optimization of distribution network with doubly-fed wind farm based on improved differential evolution method[J].Electric Power Automation Equipment，2013，33（11）：123-127.
[7] LIN X，LUO W J，XU P L.Differential evolution for multimodal optimization with species by nearest-better clustering[J].IEEE Transactions on Cybernetics，2019：1-14.
[8] 丁青锋，尹晓宇.差分进化算法综述[J].智能系统学报，2017，12（4）：431-442.
DING Q F，YIN X Y.Research survey of differential evolution algorithms[J].CAAI Transactions on Intelligent Systems，2017，12（4）：431-442.
[9] LAMPINEN J，ZELINKA I.On stagnation of the differential evolution algorithm[C]//Proceedings of the 6th International Mendel Conference on Soft Computing，2000：76-83.
[10] WANG Y，CAI Z X，ZHANG Q F.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：55-66.
[11] WANG Y，CAI Z，ZHANG Q.Enhancing the search ability of differential evolution through orthogonal crossover[J].Information Sciences，2012，185（1）：153-177.
[12] DAS S，KONAR A，CHAKRABORTY U K.Two improved differential evolution schemes for faster global search[C]//Genetic and Evolutionary Computation Conference，2005.
[13] BREST J，GREINER S，BOSKOVIC B，et al.Self-adapting control parameters in differential evolution：a comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation，2006，10（6）：646-657.
[14] WU L H，WANG Y N，ZHOU S W.Self-adapting control parameters modified differential evolution for trajectory planning of manipulators[J].Control Theory & Applications，2007，5（4）：365-373.
[15] NOMAN N，BOLLEGALA D，IBA H.An adaptive differential evolution algorithm[C]//IEEE Congress of Evolutionary Computation，2011：2229-2236.
[16] ZHANG J，MEMBER S.JADE：adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.
[17] QIN A K，SUGANTHAN P N.Self-adaptive differential evolution algorithm for numerical optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation，2005：2-4.
[18] DUBREUIL M，GAGNE C，PARIZEAU M.Analysis of a master-slave architecture for distributed evolutionary computations[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B（Cybernetics），2006，36（1）：229-235.
[19] KUSHIDA J I，HARA A，TAKAHAMA T.Island-based differential evolution with varying subpopulation size[C]//2013 IEEE 6th International Workshop on Computational Intelligence and Applications，2013：119-124.
[20] ALBA E，DORRONSORO B.The exploration/exploitation tradeoff in dynamic cellular genetic algorithms[J].IEEE Transactions on Evolutionary Computation，2005，9（2）：126-142.
[21] 沈鑫，邹德旋，张强.采用双变异策略的自适应差分进化算法及应用[J].计算机工程与应用，2020，56（4）：146-157.
SHEN X，ZOU D X，ZHANG Q.Adaptive differential evolution algorithm using double mutation strategies and its application[J].Computer Engineering and Applications，2020，56（4）：146-157.
[22] 陈颖，林盈，胡晓敏.多种群多策略的并行差分进化算法[J].计算机科学与探索，2014，8（12）：1502-1510.
CHEN Y，LIN Y，HU X M.Parallel differential evolution with multi-population and multi-strategy[J].Journal of Frontiers of Computer Science and Technology，2014，8（12）：1502-1510.
[23] 李学强，黄翰，郝志峰.基于邻域差分和协方差信息的单目标进化算法[J].软件学报，2018，29（9）：2606-2615.
LI X Q，WANG H，HAO Z F.Evolutionary algorithm for single-objective optimization based on neighborhood difference and covariance information[J].Journal of Software，2018，29（9）：2606-2615.
[24] LIANG J J，QU B Y，SUGANTHAN P N，et al.Problem definitions and evaluation criteria for the CEC 2015 competition on learning-based real-parameter single objective optimization[R].Singapore：Nanyang Technological University，2014.
[25] YAO X，LIU Y，LIN G.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation，1999，3（2）：82-102.