基于Lévy飞行的自适应差分进化算法

呼忠权 王洪斌

摘  要： 针对目前差分进化算法存在全局搜索与局部寻优的矛盾、搜索停滞、收敛速度慢的问题，提出一种改进算法：基于Lévy飞行的自适应差分进化算法。该算法鉴于Lévy飞行步长符合重尾分布的特点，在变异过程中结合差分进化算法的基本变异和Lévy飞行变异两种模式，并通过引入自适应缩放因子和交叉概率算子，改善种群在交叉与变异过程中的不足。通过理论分析与Benchmark函数的数值验证，并与其他6种算法进行比较。结果表明，所提新算法能够在全局搜索与局部寻优之间进行较好的平衡，而且收敛速度更快，种群多样性得到了很好的保存，一定程度上避免了搜索停滞的出现。

关键词： 自适应差分进化算法; Lévy飞行; 全局搜索; 局部寻优; 理论分析; 实验验证

中图分类号： TN967.34?34; TP18                 文献标识码： A                      文章编号： 1004?373X（2020）04?0167?06

Adaptive differential evolution algorithm based on Lévy flight

HU Zhongquan， WANG Hongbin

（Hebei Key Laboratory of Industrial Computer Control Engineering， Yanshan University， Qinhuangdao 066004， China）

Abstract： A new improved algorithm： adaptive differential evolution algorithm based on Lévy flight （ADELF） is proposed to improve contradictions between global search and local optimization， search stagnation and slow convergence in current differential evolution algorithm. The algorithm was consistent with the heavy tailed distribution of Lévy flight steps. In consideration of the fact that Lévy flight step size conforms to the characteristics of heavy?tailed distribution， this algorithm combines the basic variation of differential evolution algorithm and Lévy flight variation in the variation process. The adaptive scaling factor and crossover probability operator are introduced to improve the shortage of population in the process of cross and mutation. The experiment was performed the theoretical analysis and numerical verification of benchmark function， with which other 6 algorithms are compared. The results show that the new algorithm can make a better balance between the global search and the local optimization， has faster convergence speed， and the population diversity is well preserved， which avoids the appearance of the search stagnation to a certain extent.

Keywords： adaptive differential evolution algorithm; Lévy flight; global search; local optimization; theoretical analysis; experimental verification

0  引  言

目标优化问题已在人工智能、计算机科学、信息科学、自动化等众多领域得到极其广泛的应用。而全局优化算法成为目标优化问题的关键，优化算法普遍存在早熟收敛、全局搜索与局部寻优的矛盾等问题。因此，近年来，随机启发式搜索算法在全局优化问题上得到了较大关注，而差分进化算法在此类算法中表现的更为优秀，引起了学者的极大关注。

差分进化[1]（Differential Evolution，DE）算法具有可靠、准确、快速、鲁棒性强等优点，在众多领域中得到应用。但原始的DE算法存在着明显的不足：早熟收敛、搜索停滞、收敛速度与收敛精度的矛盾以及对控制参数的选择非常敏感。

在算法性能改善方面，国内外都进行了很多研究。文献[2]总结分析了近年来DE算法的研究进展，并推荐使用自适应种群大小的方式来求解高维实际问题;文献[3]引入外部存档和精英保留策略的方法对算法进行改进，改善了算法的性能;文献[4]对变异策略和参数都采用了自适应选择和调整，改善了已有算法的收敛速度和求解精度;文献[5]采用共轭增强的方法指引算法进行局部搜索，平衡了算法的全局搜索与局部寻优的能力;文献[6]利用Lévy飞行进行步长调整，在改进算法中结合已有的PGLFDE和FBDE算法来改进基本DE算法的性能;文献[7]利用云计算改进算法计算速度，并将差分算法与轮盘赌相结合用于改善全局寻优能力。

上述对算法的改进，都取得了一定的研究成果，但在如何平衡全局搜索与局部寻优、收敛速度以及保持种群多样性等方面还有待进一步研究。因此，本文在目前研究的基础上，提出基于Lévy飞行的自适应差分进化算法（Adaptive Differential Evolution Algorithm Based on Lévy Flight，ADELF）。

1  Lévy分布与Lévy飞行

Lévy分布[8?9]属于重尾分布，相比于高斯分布和柯西分布分布更為广泛。Lévy过程的框架最早是在20世纪30年代由法国数学家Paul Pierre Lévy提出。Lévy分布的概率密度函数为：

[Lα，γ（z）=1π0∞exp（-γqα）cos（qz）dq] （1）

式中，[α， γ]为两个特征参数。Lévy分布、高斯分布和柯西分布的概率分布对比如图1所示。

Lévy飞行是一种马尔可夫[10]随机过程，行走的步长满足一个重尾的Lévy分布。Lévy飞行具有更强的扰动能力，是一种比布朗随机运动更有效的搜索策略，通过大概率短距离和小概率长距离搜索，既可以扩大搜索范围，又能在特定区域增强局部搜索效果，提高算法的全局搜索和局部寻优能力。

Mantegna提出的生成Lévy随机步长[7]的公式为：

[s=xy1α] （2）

式中，x和y服从正态分布，[x?N（0，σ2x）]，[y?N（0，σ2y）]。

[σx（α）=Γ（1+α）?sin（πα2）Γ[（1+α）2]?α?2（α-1）21α] （3）

[σy=1] （4）

式中，[Γ（x）]表示伽马分布。

200次Lévy飞行的曲线见图2。行步长分布见图3。

2  ADELF算法结构

ADELF算法基本思想是将Lévy飞行和差分进化算法的基本进化模式二者结合，共同完成种群的进化。针对基本差分进化算法对参数选择比较敏感，引入自适应变异缩放因子（F）和自适应交叉概率（CR），用于改善算法性能。

2.1  变异模式

变异模式实现方法如下：

[Vi（g+1）=Xbest（g）+F?（Xr2（g）-Xr1（g）），                            rand（0，1）≤cL（g），                otherwise  ] （5）

式中：[c=gGm];[i≠r1≠r2]，[i=1，2，…，NP];[r1，r2]均为区间[1， NP]内的随机整数，NP表示种群大小;g表示进化代数;[Gm]表示最大迭代次数;[Xi（g）]表示第g代种群中第i个个体;F表示缩放因子;[Xbest（g）]表示当前种群中的最优个体;[L（g）]表示使用Lévy飞行产生的新个体;[Vi（g+1）]表示第g代种群中的临时新个体。

变异过程中，基本变异模式中待变异个体为当前种群中的最优个体，保存了寻优的方向，加速了算法的收敛速度;Lévy飞行产生的新变异个体保证了算法的全局寻优能力，减小了算法陷入局部最优解的可能性。

选择条件设置为rand（0，1）与[c]进行比较，而不是将rand（0，1）与c进行比较，从图4中可以看出，这种方法可以使基本变异模式被选中的概率增大，加快了算法的收敛速度。

2.2  自适应参数

自适应参数[11]（F和CR）能够较好地平衡全局搜索和局部寻优，能够一定程度上降低算法对参数的敏感性。为了保证收敛速度，避免早熟收敛的发生，采取自适应机制对缩放因子和交叉概率进行赋值，具体方法如下：

[F=Fmax-（Fmax-Fmin）·fi - fminfmax+fmin，   fi≥f-Fmax，      fi

[CR=CRmin+（CRmax-CRmin）·fi - fminfmax+fmin，   fi≥f-CRmin，     fi

式中：[Fmax]和[Fmin]分别为F的上、下限;[CRmax]和[CRmin]分别为CR的上、下限;[fi]是个体[Xi（g）]的适应度值;[fmax]和[fmin]分别是当前种群中最大和最小的适应度值;[f-]为当前种群适应度的平均值。

2.3  算法描述

ADELF算法主要流程描述如下：

输入：搜索空间、种群大小、目标函数、迭代次数、求解精度。

输出：最优解。

1） 参数初始化：种群大小、最大迭代次数、缩放因子、交叉概率、求解精度等。

2） 初始化种群，并评估每个个体。

3） 计算适应度值和目标函数值。

4） 变异模式的选择，并对个体进行变异操作。

5） 交叉操作。

6） 选择操作。

7） 结束条件：满足求解精度要求或者达到最大迭代次数;否则，转至步骤3）。

3  数值求解及分析

本文通过对10个Benchmark测试函数进行了数值求解，将ADELF算法与另外6种算法进行比较。另外6种算法的参数设置详见文献[11?12]。

表1中PSO?w，CLPSO，DMSDELS和ADDE的部分求解数据来自文献[11]。表2为10个Benchmark测试函数，维数（D）、自变量范围（S）、函数全局最小值和函数类型分别给出。数值求解结果详见表1。

对于单峰函数的求解，除了函数[f3（x）]，ADELF算法求解能力优于其他所有算法，求解的最优值更加接近理论最优解。由于DE2算法的收敛速度最快，对于单峰函数的求解有着明显的优势，因此，DE2算法在求解[f3（x）]的时候优于其他算法。

对于多峰函数的求解，ADELF和ADDE算法的表现更为优秀，求解能力更强。对于函数[f9（x）]的求解，ADDE算法优于ADELF，虽然ADELF也能求解到最优解，但是搜索精度和平均值上稍差于ADDE。从10组求解结果来看，ADELF还是优于ADDE的。

通过对函数求解的结果可以看出，改进算法结合了DE2的优点，发挥了Lévy飞行变异的全局搜索的特点。改进算法整体上优于列举的其他算法。

为了深入而准确地了解算法的收敛速度，分别对数值求解结果相近的函数[f5（x）]和[f6（x）]进行了最优解收敛曲线的绘制。为了尽可能消除随机性带来的偏差，分别对测试函数进行20次求解，并计算每代最优解的平均值。图5所示两幅图分别对应数函数[f5（x）]和[f6（x）]的最优解的平均值收敛曲线。

由图5可知，ADELF算法的收敛速度是最快的。从求解结果和收敛速度上来看ADELF和ADDE算法的表现非常相似。为了更深入地了解两种算法的求解能力，用这两种算法分别对2维和3维函数求解，分析函数[f5（x）]和[f8（x）]在降维求解后的种群分布。解的分布如图6、图7所示。

由表1可知，虽然ADELF和ADDE算法对于函数[f5（x）]和[f8（x）]的求解结果相同，但是从图6和图7中可知，ADELF比ADDE解的分布更加广，增加了种群的差异性，利于算法进行全局寻优和局部搜索，能够有效地避免算法的早熟收敛和算法停滞。

综上所述，ADELF算法仅在函数[f3（x）]和[f8（x）]的求解时，分别稍差于DE2和ADDE算法。但从10个基准测试函数的求解结果、收敛曲线和种群分布来综合分析，改进算法的全局寻优能力、收敛速度都得到了提高和改善。

4  结  语

将行走步长满足Lévy分布的Lévy飞行变异方式引入到差分进化算法中，提出基于Lévy飞行的自适应差分进化算法，并通过对10组标准测试函数进行求解计算对比，以及对降维函数求解后种群的分布分析。结果表明，所提算法能够一定程度上增强种群的差异性、避免早熟收敛，同时增强了原有算法的全局搜索和局部寻优能力，为算法的工程应用提供了一定的理论支撑。虽然算法在理论分析上尚显不足，但其优异的表现，相信随着研究的深入，差分进化算法定将取得更为广阔的应用。

参考文献

[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] PIOTROWSKI A P. Review of differential evolution population size [J]. Swarm & evolutionary computation， 2017（34）： 1?24.

[3] 陶勇，沈济南.基于自适应差分进化策略的多目标进化算法[J].控制工程，2018，25（11）：2070?2074.

[4] 閤大海，李元香，龚文引，等.一种求解约束优化问题的自适应差分进化算法[J].电子学报，2016，44（10）：2535?2542.

[5] 张贵军，王柳静，周晓根，等.基于共轭增强策略的差分进化算法[J].控制与决策，2017，32（7）：1313?1318.

[6] SHARMA H， SHARMA V P， SHARMA A. A modified fitness based differential evolution using population based levy flight strategy [C]// 2016 Second International Conference on Computational Intelligence & Communication Technology. Ghaziabad： IEEE， 2016： 707?711.

[7] 孙洁，连畅.基于云计算平台的差分进化算法改进研究[J].现代电子技术，2018，41（17）：163?166.

[8] MANTEGNA R N. Fast， accurate algorithm for numerical simulation of Lévy stable stochastic processes [J]. Physical review e statistical physics plasmas fluids & related interdisciplinary topics， 1994， 49（5）： 4677.

[9] DELAPORTE C. Lévy processes with marked jumps I： limit theorems [J]. Journal of theoretical probability， 2015， 28（4）： 1468?1499.

[10] CHOI T J， CHANG W A. Erratum to： adaptive α?stable differential evolution in numerical optimization [J]. Natural computing， 2017， 16（4）： 1.

[11] 张雪霞，陈维荣，戴朝华.带局部搜索的动态多群体自适应差分进化算法及函数优化[J].电子学报，2010，38（8）：1825?1830.

[12] 呼忠权，王洪斌，李硕.自适应双模式差分进化算法[J].计算机工程与设计，2015，36（8）：2250?2254.