工程科学与技术   2019, Vol. 51 Issue (1): 205-212
基于共享学习策略的微分进化算法
段美军1, 杨红雨1,2, 刘洪2, 陈俊逸1, 刘宇2     
1. 四川大学 视觉合成图形图像技术国防重点学科实验室,四川 成都 610065;
2. 四川大学 计算机学院,四川 成都 610065
基金项目: 国家重大科学仪器设备开发专项资助(2013YQ49087905);国家自然科学基金委员会与中国民用航空局联合资助项目(U1833115)
摘要: 针对传统微分进化算法易发生早熟收敛问题,提出基于共享学习策略的微分进化算法(SLDE),引入共享个体和共享学习因子。共享个体覆盖整个种群,较优个体可引导算法朝希望方向进化,较差个体则能维持种群的多样性,向共享个体学习可避免丢失个体信息,实现整个种群间的信息交换,有助于算法跳出局部最优解,提高算法的局部开采和全局勘探能力。同时,算法充分利用个体的进化信息,根据个体适应值到最优适应值的距离自适应地调整共享学习因子,以弥补随机个体对进化带来的随机性和盲目性,增强算法的搜索能力。采用22个不同特性的Benchmark测试函数对算法进行性能测试,与7种改进DE算法进行性能对比,实验结果表明,SLDE具有较强的跳出局部最优解能力,能显著减少进化代数,大幅地提高算法的收敛精度、收敛速度和稳定性,SLDE的全局优化性能整体上远优于其他改进DE算法。
关键词: 微分进化    共享学习    共享个体    共享学习因子    自适应    
Differential Evolution Algorithm Based on Sharing Learning
DUAN Meijun1, YANG Hongyu1,2, LIU Hong2, CHEN Junyi1, LIU Yu2     
1. National Key Lab. of Fundamental Sci. on Synthetic Vision, Sichuan Univ., Chengdu 610065, China;
2. College of Computer Sci., Sichuan Univ., Chengdu 610065, China
Abstract: In order to alleviate premature convergence in traditional differential evolution algorithms, a differential evolution algorithm based on sharing learning strategy (SLDE) was proposed and the concepts of sharing-individual (SI) and sharing learning factor were introduced in SLDE. The sharing-individual covers the whole population, while the superior individuals guide the promising searching direction, the inferior individuals maintain the population diversity in the evolution process. By learning from the sharing-individual, information exchange was achieved among the whole population to avoid missing information of individuals, which helps the algorithm jump over the trap of local optimal solution and improve the local and global exploration capability. Meanwhile, the evolutionary information of individuals was made full of use in SLDE, and the sharing learning factor was self-adaptively adjusted according to the distance of fitness value of individual and the optimal fitness value, in order to alleviate the randomness and blindness from the random individuals and enhance the searching ability. A total of 22 Benchmark test functions with different properties were used for performance test comparison with seven state-of-the-art DE variants. The experimental results showed that SLDE has strong ability to escape from local optima, significantly reduce the evolutionary generations and greatly improve the convergence precision, convergence speed and stability. The overall global optimization performance of SLDE is much better than other improved DE algorithms.
Key words: differential evolution    sharing learning    sharing-individual    sharing learning factor    self-adaptiveness    

微分进化算法(differential evolution, DE)是由Storn和Price针对实参优化问题提出的一种基于群体的随机优化方法[1]。DE算法原理简单,可调参数少,收敛速度快,鲁棒性好。目前,DE广泛用于神经网络参数训练、模式识别、机器人路径规划等科研和工程领域[27]

传统的DE算法与其他进化算法一样容易陷入局部最优,存在早熟收敛问题。因此,许多学者分别针对控制参数和变异模式提出了一系列改进的DE算法。

1)着重于控制参数自适应的算法:Liu等[8]利用模糊逻辑控制调节缩放因子(F)和交叉概率(CR),但是如何确定模糊隶属函数比较困难;Brest等[9]基于DE/rand/1提出一种自适应DE算法,在进化过程中按指定的阈值动态地调整FCR,但其阈值固定,缺乏进化过程的指导;Noman等[10]根据父代种群的平均适应值和子代个体的适应值动态调整F和CR;Tanabe等[11]提出一种基于历史优秀参数而实现控制参数自适应的技术。

2)侧重改进变异模式的算法:Zhang等[12]通过改进DE/current-to-best/1模式,提出DE/current-to-pbest/1变异模式,分别按正态分布和柯西分布随机生成FCR,且采用保持优秀参数的机制,有较优的优化性能;Qin[13]、Wang[14]、Mallipeddi[15]、Wu[16]等基于一些变异模式的优势,通过组合多种变异策略改善算法的寻优能力。但是,这些算法计算量较大,复杂度高。Gong等[17]引入一种基于个体适应值等级修复交叉概率的策略;刘昊等[18]基于择优学习的思想进行变异,算法的复杂度较小;Wang等[19]基于DE/rand/1提出一种改进的自适应算法(IMMSADE),控制参数是否调整由固定的阈值决定。

针对传统微分进化算法易发生早熟收敛问题,为进一步提高算法的寻优性能,作者提出了一种基于共享学习策略的微分进化算法(differential evolution based on sharing learning, SLDE)。选取22个不同特性的Benchmark测试函数对算法进行性能测试,与7种改进DE算法进行性能对比,实验结果表明,SLDE算法能显著减少进化代数,有效地打破局部优化积累,大幅提高收敛精度和稳定性。

1 微分进化算法

DE基于群体进化,标准DE算法包括变异、交叉以及选择操作,对于 $D$ 维优化问题:

$\left\{ \begin{aligned} & \min \;f({x_1},{x_2}, \cdots ,{x_D}) \\ &{\rm s.t.} \;{L_j} \le {x_j} \le {U_j},\; j = 1,2, \cdots ,D \end{aligned} \right.$ (1)

式中, ${L_j}$ ${U_j}$ 分别为第 $j$ 维变量的下边界和上边界。

与其他进化算法变异算子采用定义的概率分布函数不同,DE算法从当前种群中选取个体进行差分运算,并乘以缩放因子实现个体变异。常用的5类典型的变异策略如下:

1)DE/best/1

${{V}\!_i}\!^{t + 1} = {X}_{\rm{b}}^t + F({X}_{r1}^t - {X}_{r2}^t)$ (2)

2)DE/best/2

${{V}_i}\!^{t + 1} = {X}_{\rm{b}}^t + F({X}_{r1}^t - {X}_{r2}^t){\kern 1pt} + F({X}_{r3}^t - {X}_{r4}^t)$ (3)

3)DE/rand/1

${{V}_i}\!^{t + 1} = {X}_{r1}^t + F({X}_{r2}^t - {X}_{r3}^t)$ (4)

4)DE/rand/2

${{V}_i}\!^{t + 1} = {X}_{r1}^t + F({X}_{r2}^t - {X}_{r3}^t) + F({X}_{r4}^t - {X}_{r5}^t)$ (5)

5)DE/current-to-best/1

${{V}_i}\!^{t + 1} = {{X}_i}\!^t + F({X}_{\rm b}^t - {{X}_i}^t) + F({X}_{r1}^t - {X}_{r2}^t)$ (6)

式中: $i = \{ 1,2, \cdots ,{N_p}\} $ ${N_p}$ 为种群大小; $t = \{ 1,2, \cdots ,T\} $ 为进化代数; ${X}_{\rm b}^t$ 为当代种群中最优个体; ${{X}_i}\!\!^t$ 为对应的父代个体; ${X}_{r1}^t $ $ {X}_{r5}^t$ 为不同于 ${{X}_i}^t$ 的随机选择个体,且 ${r_1} \ne {r_2} \ne {r_3} \ne {r_4} \ne {r_5}$ $F \in [0,2]$ 为缩放因子。

通过对变异向量进行交叉操作生成实验向量 ${{U}}_{{i}}^{{{t + 1}}} = [U_{{{i}},1}^{t + 1},U_{{{i}},2}^{t + 1}, \cdots ,U_{{{i}},D}^{t + 1}]$ ,可增加种群的多样性以扩大搜索区域。常用的二项式交叉操作为:

$U_{i,j}^{t + 1} = \left\{ \begin{aligned} & V_{i,j}^{t + 1}\;,\;{\rm{rand}}(0,1) \le CR\;\;{\rm{or}}\;\;j = {j_{\rm {rand}}}; \\ & X_{i,j}^t\;,\;{\rm others} \end{aligned} \right.$ (7)

式中:交叉概率 $CR \in [0,1]$ ;若 $CR$ 较大,则会加快算法的收敛;若 $CR$ 较小,则算法的鲁棒性会更好; ${j_{{\rm{rand}}}}$ $[1,D]$ 之间的随机整数。

DE算法采用贪婪策略进行选择操作,根据目标向量 ${{X}_i}\!^t$ 和实验向量 ${{U}_i}\!^{t + 1}$ 的函数值选择最优个体,如式(8)所示:

${{X}_i}\!^{t + 1} = \left\{ \begin{aligned} & {{X}_i}\!^{t + 1}\;,f({{X}_i}\!^{t + 1}) < f({{X}_i}\!^t); \\ & {{X}_i}\!^t,{\rm{others}} \end{aligned} \right.$ (8)
2 SLDE算法 2.1 共享学习变异策略

典型变异策略中,DE/best/1和DE/best/2利用最优个体的信息而具有较强的局部开发能力,收敛速度较快,易早熟收敛;策略DE/rand/1和DE/rand/2仅基于随机个体的信息进行变异,具有较强的全局搜索能力,但缺乏最优个体信息的指导,收敛速度较慢;DE/current-to-best/1基于父代个体和最优个体进行变异,寻优精度较高,易陷入局部最优。为此,作者提出共享学习变异策略以提高算法的全局搜索和局部开发能力。

共享学习变异策略引入共享个体,通过最优个体与共享个体的差分学习各个个体之间的信息,并通过个体的适应值与最优适应值的距离自适应地调整共享学习因子。

${{V}_i}\!^{t + 1} = F({X}_{r1}^t - {X}_{r2}^t) + {\omega _i}\!^t \cdot ({{X}_{\rm b}}\!^t - {{\overline{{X}}^t}})$ (9)

式中, ${X}_{r1}^t$ ${X}_{r2}^t$ 为当代种群中不同于父代个体的随机个体, $ {{\overline{{X}}^t}}$ 为共享个体, ${\omega _i}\!^t$ 为共享学习因子。 $ {{\overline{{X}}^t}}$ ${\omega _i}\!^t$ 定义如下:

${{\overline{{X}}^t}} = \frac{1}{{{N_p}}}\left(\sum\limits_{i = 1}^{{N_p}} {{{X}_i}\!^t} \right)$ (10)
${\omega _i}\!^t = (f_{\max }^t - f({{X}_i}\!^t))/(f_{\max }^t - f_{\min }^t)$ (11)

式(11)中, $f_{\max }^t$ 为种群最优适应值, $f({{X}_i}^t)$ 为父代个体 ${{X}_i}\!^t$ 的适应值, $f_{\min }^t$ 为种群最差适应值。

作者提出的共享学习变异策略具有以下特性:

1)共享个体涵盖所有个体的信息,较优个体可引导算法朝希望方向进化,较差个体则能维持种群的多样性。通过向共享个体学习可实现整个种群之间信息交换,避免丢失个体信息,提高算法的全局搜索与局部开发能力。

2)根据个体的适应值自适应地调整共享学习因子,共享学习因子控制最优个体和共享个体的差分对个体变异的作用,弥补了随机个体本身的随机性对进化带来的随机性和盲目性,加快算法的收敛速度。

2.2 SLDE算法

SLDE算法的主要步骤如下:

Step1:初始化种群,设置算法的初始参数:种群大小 ${N_p}$ 、进化代数 $t$ 、问题维数D、最大进化代数T、算法收敛精度 $\varepsilon $ 、缩放因子F及交叉概率 $CR$

Step2:分别按式(10)、(11)更新共享个体及共享学习因子。

Step3:满足结束条件,终止算法并输出结果。

Step4:按式(9)的变异策略进行变异。

Step5:按式(7)、(8)进行交叉和选择操作。

Step6:令 $t = t + 1$ ,转到Step2继续执行。

3 算法性能分析 3.1 Benchmark测试函数

为测试算法的性能,选取22个不同特性的Benchmark测试函数进行性能测试,如表1所示。

表1 Benchmark测试函数 Tab. 1 Benchmark test functions

3.2 与改进的DE比较

将SLDE算法与aDE[10]、SHADE[11]、SaDE[13]、CoDE[14]、EPSDE[15]、Rcr-JADE[17]和PLDE[18]算法进行比较。参数设置:f12收敛精度为1E−3,f20f21收敛精度为1E−1,其余函数的收敛精度为1E−8,种群大小为100,独立实验次数为30,30维问题和100维问题的最大迭代次数分别为1 500和3 000。SLDE算法中 $F = 0.2$ $CR = 0.8$ ,其他算法控制参数的具体设置请参见相应的参考文献。

对算法的性能测试包括两个方面:

1)算法的收敛精度,如表23所示。

表2 SLDE与改进算法的优化结果(D=30) Tab. 2 Optimization results of SLDE and improved algorithms with 30 dimensions

表3 SLDE与改进算法的优化结果(D=100) Tab. 3 Optimization results of SLDE and improved algorithms with 100 dimensions

表23可得:1)对于单峰函数f1f4f6f8f10,SLDE均能寻优到全局最优解;在f5f9上,SLDE优势明显。2)对于阶跃函数f11和噪声函数f12,SLDE不劣于其他算法。3)对于多峰函数f13f18f22,SLDE能寻优到全局最优解;在f19上,SLDE优于EPSDE,且不劣于其他算法;在f20上,SLDE劣于其他算法。在f21上,D=30时,SLDE劣于其他算法;D=100时,SLDE为最优。4)相同的种群规模下,随着函数问题维数和最大迭代次数的增加,SLDE算法仍维持高的收敛精度,而其他算法的收敛精度则明显下降。

同时,为进一步评估算法整体寻优性能,本文对算法的优化结果进行非参数检验。表4为Wilcoxon检验结果(显著水平分别为0.05和0.10)。表5为Friedman和Kruskal_Wallis检验结果。

表4 Wilcoxon检验结果 Tab. 4 Results of Wilcoxon test

表5 Friedman和Kruskal_Wallis检验结果 Tab. 5 Results of Friedman test and Kruskal_Wallis test

表4中,R+为SLDE优于对比算法检验秩的和,R为对比算法优于SLDE检验秩的和,R+越大,SLDE算法更优。由表4可知,无论是高维还是低维问题,Wilcoxon检验所求得的R+均大于对比算法,SLDE整体上均显著优于其他改进算法。

表5可知,SLDE由Friedman和Kruskal_Wallis检验所得的平均秩均为最小,表明SLDE整体寻优性能最好,其次是Rcr-JADE(D=30)和SHADE(D=100)。

综合上述实验结果可以发现:SLDE以最优个体为基,由共享个体引导个体朝希望方向进化的策略是有效的,能较好地平衡算法的局部搜索和全局开发能力,从而提高算法的寻优精度。

2)算法的收敛速度和稳定性,如表67所示。

表6 平均迭代次数和实验成功率(D=30) Tab. 6 Mean iterations and success rate with 30 dimensions

表7 平均迭代次数和实验成功率(D=100) Tab. 7 Mean iterations and success rate with 100 dimensions

表67中,MEGN为达到指定收敛精度的平均进化代数,SR为实验成功率。分析表67中算法的收敛速度和稳定性可知,无论是低维问题还是高维问题,除f12f19f21外,SLDE均以最少的迭代次数达到指定精度且实验成功率均为100,稳定性最好,收敛速度最快。

图1给出部分函数的进化曲线。

图1 平均最优解的进化曲线(D=30) Fig. 1 Evolution curves of the mean best solution with 30 dimensions

观察图1中两类典型的进化曲线可知:如图1(a)(b)(e)所示,SLDE能寻优到全局最优值,其他比较算法未陷入“进化停滞”,但其平均最优解的精度远差于SLDE;SLDE能在较少的进化代数内寻优到全局最优解,而SHADE[11]、SaDE[13]、CoDE[14] 、EPSDE[15]、Rcr-JADE[17]和PLDE[18]则在不同的进化代数陷入“进化停滞”,如图1(c)(d)(f)所示。SLDE在进化中无明显的“进化停滞”,证明算法通过共享个体学习个体间的信息可帮助算法跳出局部最优解,提高算法的全局搜索能力。

4 结 论

针对传统微分进化算法早熟收敛导致收敛精度低问题,作者提出基于共享学习变异策略的微分进化算法(SLDE)。算法引入共享个体,通过最优个体与共享个体的差分实现整个种群之间的信息共享,提高了算法的搜索能力;根据个体的适应值自适应地调整共享学习因子,充分利用个体的进化信息,改善了种群进化的趋利性。实验结果表明:无论是单峰问题还是多峰问题,SLDE在收敛精度和收敛速度方面均优于其他改进的DE算法,具备更好的实时性和稳定性。

提出的SLDE算法采用固定的控制参数,未对控制参数策略进行研究,未来研究工作将关注控制参数的自适应调整策略,进一步提高算法的优化性能,以解决实际应用中更为复杂的优化问题。

参考文献
[1]
Storn R,Price K.Differential evolution:A simple and efficient adaptive scheme for global optimization over continuous spaces[R].Berkeley:University of California,Berkeley,1995.
[2]
Arce F, Zamorab E, Sossaa H, et al. Differential evolution training algorithm for dendrite morphological neural networks[J]. Applied Soft Computing, 2018, 68: 303-313. DOI:10.1016/j.asoc.2018.03.033
[3]
Ghosh A, Datta A, Ghosh S. Self-adaptive differential evolution for feature selection in hyperspectral image data[J]. Applied Soft Computing, 2013, 13(4): 1969-1977. DOI:10.1016/j.asoc.2012.11.042
[4]
Kok K Y, Rajendran P. Differential-evolution control parameter optimization for unmanned aerial vehicle path planning[J]. PLOS ONE, 2016, 11(3): e0150558. DOI:10.1371/journal.pone.0150558
[5]
Wang Haiyan, Zhang Yanwei, Zhao Jingling, et al. Batch optimized scheduling of intermingling flow-shop based on hybrid differential evolution algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(7): 1613-1625.
[6]
Marčič T, Štumberger B, Štumberger G. Differential-evolution-based parameter identification of a line-start IPM synchronous motor[J]. IEEE Transactions on Industrial Electronics, 2014, 61(11): 5921-5929. DOI:10.1109/TIE.2014.2308160
[7]
Kadhar K M A, Baskar S, Amali S M J. Diversity controlled self-adaptive differential evolution based design of non-fragile multivariable PI controller[J]. Engineering Applications of Artificial Intelligence, 2015, 46(PA): 209-222. DOI:10.1016/j.engappai.2015.09.015
[8]
Liu J, Lampinen J. A fuzzy adaptive differential evolution algorithm[J]. Soft Computing, 2005, 9(6): 448-462. DOI:10.1007/s00500-004-0363-x
[9]
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. DOI:10.1109/TEVC.2006.872133
[10]
Noman N,Bollegala D,Iba H.An adaptive differential evolution algorithm[C]//Proceedings of the 2011 IEEE Congress on Evolutionary Computation.New Orleans:IEEE,2011:2229–2236.
[11]
Tanabe R,Fukunaga A.Success-history based parameter adaptation for differential evolution[C]//Proceedings of the 2013 IEEE Congress on Evolutionary Computation.Cancun:IEEE,2013,71–78.
[12]
Zhang Jingqiao, Sanderson A C. JADE:Adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958. DOI:10.1109/TEVC.2009.2014613
[13]
Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaption for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417. DOI:10.1109/TEVC.2008.927706
[14]
Wang Yong, Cai Zixing, Zhang Qingfu. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 55-66. DOI:10.1109/TEVC.2010.2087271
[15]
Mallipeddi R, Suganthan P N, Pan Q K, et al. Differential evolution algorithm with ensemble of parameters and mutation strategies[J]. Applied Soft Computing, 2011, 11(2): 1679-1696. DOI:10.1016/j.asoc.2010.04.024
[16]
Wu Guohua, Shen Xin, Li Haifeng, et al. Ensemble of differential evolution variants[J]. Information Sciences, 2018, 423: 172-186. DOI:10.1016/j.ins.2017.09.053
[17]
Gong Wenyin, Cai Zhihua, Wang Yang. Repairing the crossover rate in adaptive differential evolution[J]. Applied Soft Computing, 2014, 15: 149-168. DOI:10.1016/j.asoc.2013.11.005
[18]
Liu Hao, Ding Jinliang, Yang Cui’e, et al. Perferred-learning-based differential evolution algorithm[J]. Journal of Shanghai Jiaotong University, 2017, 51(6): 704-708. [刘昊, 丁进良, 杨翠娥, 等. 基于择优学习策略的差分进化算法[J]. 上海交通大学学报, 2017, 51(6): 704-708. DOI:10.16183/j.cnki.jsjtu.2017.06.010]
[19]
Wang Shihao, Li Yuzhen, Yang Hongyu. Self-adaptive differential evolution algorithm with improved mutation mode[J]. Applied Intelligence, 2017, 47(3): 644-658. DOI:10.1007/s10489-017-0914-3