采用反向学习和差分进化改进的飞鼠搜索算法

李昀轩，秦亮曦*

(1.广西大学 计算机与电子信息学院， 广西 南宁 530004; 2.广西多媒体通信与网络技术重点实验室， 广西 南宁 530004)

0 引言

随着优化问题难度的增加，近年来出现了许多使用经典优化方法无法在足够的时间或精度内求解的复杂优化问题。然而在自然界中存在着非常丰富的机制和原理，带给研究人员很多的灵感和启发，可以用这些机制和原理设计智能优化算法解决复杂的优化问题。在过去的几十年里，研究人员开发了多种多样的自然启发式的优化算法，通过模仿一些生物行为或物理现象来解决优化问题中的寻最优解的过程。

飞鼠搜索算法(squirrel search algorithm, SSA)是2018年由Jain等[1]提出的一种自然启发式群智能算法。这是一种全新的、功能强大的全局优化算法，其灵感来自于飞行松鼠的自然动态觅食行为。与其他群智能优化算法相比，SSA由于引入了季节变化条件监测，具有更好、更高效的空间搜索能力。此外，该算法设立的森林区域内有3种类型的树(普通树、橡树和山核桃树)，既保持了种群多样性，又增强了算法的探索性。SSA推出后受到了计算智能科学界的重视，因为它们相比于经典的启发式方法，在多模态、离散和非微分的复杂优化问题中具有更大的优势。

虽然SSA具有诸多优点，但仍然存在一些问题，学者们对SSA进行了改进和应用。Ei-ashmawi等[2]采用最优拟合启发式和算子策略的改进飞鼠搜索算法解决装箱问题，同时也是首个将飞鼠搜索算法应用于装箱问题的例子。实验证明，在解决装箱问题上，该算法比其他算法的效果更好。Sanaj等[3]提出了加入跳跃式和渐进式搜索技术的混沌SSA算法(chaotic squirrel search algorithm, CSSA)优化多任务调度问题，与SSA相比其收敛速度和求解精度均有所提高。Wang等[4]提出了一个基于外种群分解和自适应权向量调整的多目标改进飞鼠搜索算法，实验结果表明，此算法在求解多目标优化问题时收敛性和寻优结果有明显优势。Hu等[5]将飞鼠搜索算法与入侵杂草优化相结合，提出了一种混合算法(invasive weed optimization and squirrel search algorithm, ISSA)，相比于SSA，该算法得到了较好的收敛性能和寻优结果。朱群锋等[6]提出一种基于粒子群算法策略改进的飞鼠优化算法(particle swarm optimization squirrel search algorithm, PSOSSA)，引入惯性权重和学习因子,设计了一种新的飞鼠个体位置更新公式，可以实现飞鼠优化算法在全局探索和局部开发之间的平衡，加快了算法的收敛速度。张晓通[7]提出了一种增强搜索能力的SSA算法(enhanced squirrel search algorithm, ESSA)，ESSA通过对满足季节监控条件的普通个体执行反向学习，并对每次迭代产生的较优解个体附近进行混沌搜索，增强了算法的全局勘探能力和局部搜索能力。在应用方面，文献[8-13]都成功地把SSA应用在不同的领域，解决了不同的实际问题。

目前对于SSA算法的研究还较少，此算法还有很大的改进空间。本文中针对SSA算法过早收敛、比较容易陷入局部极值的不足，提出一种采用反向学习和差分进化改进的飞鼠搜索算法(opposition learning and differential evolution improved squirrel search algorithm，ODESSA)。ODESSA主要做了以下两个方面的改进： ①针对SSA容易陷入局部极值的缺点，在SSA中加入差分进化算法中的变异、交叉、选择机制，从而可以使其能跳出局部极值。 ②针对SSA收敛速度较慢和全局勘探能力较弱的缺点，通过引入反向学习策略，扩大搜索范围，同时也加快了算法的收敛速度。

1 SSA基本原理

1.1 SSA的灵感来源

飞行松鼠的智能动态觅食行为是提出SSA的主要灵感来源。飞鼠通过从一棵树滑翔到另一棵树来寻找食物资源，不断改变自己的位置，探索不同的森林区域。它们通过食用橡子来满足日常的能量需求，在满足了每天的能量需求后开始寻找冬天的最佳食物来源(山核桃)。冬季时它们变得不活跃，而到了冬季末，飞鼠再次活跃起来。这是一个重复的过程，并持续到飞鼠的生命终结。

1.2 数学模型假设

① 森林中有n只的飞鼠，每1只飞鼠在1棵树上。

② 每只飞鼠都在各自寻找食物，并通过表现出动态的觅食行为来优化利用现有的食物资源。

③ 在森林中，只有普通树、橡树(次优解)和山核桃树(最优解)3种类型。

④ 假设森林区域包含3棵橡树和1棵山核桃树。

1.3 SSA思想简介

SSA的主要参数包括最大迭代次数Itermax、种群规模NP、决策变量的数量n、捕食者存在概率Pdp、标度因子sf、滑动常数Gc，h、a、n分别代表山核桃树、橡树和普通树，而FSh、FSa、FSn分别代表山核桃树、橡树和普通树上的飞鼠。

SSA首先根据公式随机初始化飞鼠的位置，

FSi,j=FSL+rand()×(FSU-FSL),i=1,2,…,NP,j=1,2,…,n，

(1)

式中:FSi,j为第j维度上的第i只飞鼠；FSU和FSL为搜索区域的上界和下界。

通过将决策变量的值代入适应度函数计算单个飞鼠所在位置的适应度值：

fi=fi(FSi,1,FSi,2,…,FSi,n),i=1,2,…,NP，

(2)

式中f为适应度评价函数。

然后，根据飞鼠所在地的适应度值按升序排序，将最小适应值飞鼠的位置视为山核桃树,排在最小适应值飞鼠的后3个位置视为橡树，其余视为普通树。分好类后，飞鼠根据以下3种情况来进行滑翔移动。

情况1：橡树上的飞鼠向山核桃树移动。

(3)

情况2：普通树上的飞鼠向橡树移动。

(4)

情况3：普通树上的飞鼠向山核桃树移动。

(5)

式中：dg根据滑翔空气动力学算出的随机滑动距离；t代表当前迭代轮次；R1、R2、R3是从区间[0,1]上的均匀分布返回值的函数。

飞鼠的觅食行为受到季节变化的显著影响，因此，在SSA中引入了季节变化条件监测机制，以防止算法陷入局部极值。首先计算季节常数及其最小值

(6)

(7)

(8)

式中Levy分布[14]是一种强大的数学工具，可以增强大多数优化算法的全局搜索能力。

2 SSA的改进策略

2.1 利用反向学习策略改进SSA

反向学习(opposition based learning，OBL)的概念[15]是指在搜索最优解的过程中，对当前解和反向解进行同时搜索，把其中更好的解作为问题解，这样能够扩大搜索发范围，并提升算法的搜索效率。根据概率定理，反向解有50%的概率比当前解更加接近问题的最优解。

在动态的一般反向学习策略(dynamic general OBL)中，反向解的计算公式为

(9)

利用公式(9)，根据最初种群使用反向学习策略生成一个反向种群，使用适应度评价函数对比初始种群和反向初始种群中飞鼠个体的适应度，从中选择最优飞鼠个体，使之组成最优初始种群。初始种群的反向种群采用公式(10)生成，

FSO,i,j=(FSU+FSL)-FSi,j，

(10)

式中FSO,i,,j为飞鼠通过反向学习策略生成的反向位置。

在所有飞鼠更新完自己的位置后，利用反向学习策略生成每个种群个体的反向解，生成方法与生成初始反向种群类似。之后把种群个体当前解和其反向解代入适应度评价函数进行比较，从中选择有着更高适应度的解的个体组成新的种群进入下一轮迭代。

2.2 利用差分进化算法改进SSA

差分进化算法 (differential evolution, DE)是一种基于群体进化的算法[16]。它能够记录群体中的最优解，并且在种群内共享信息。DE通过对当前种群的个体进行变异和个体之间的交叉操作产生一个新种群，然后选择目标函数值最优的NP个个体作为下一代种群的个体。首先通过公式(11)对在t代的每一个种群个体进行变异操作, 得到对应的变异个体，即

(11)

然后, 利用公式(12)生成的变异个体实施交叉操作, 生成试验个体, 即

(12)

式中：rand为在区间[0, 1]上均匀分布的随机数;CR为在[0, 1]之间的交叉算子;randi(1,D)为{1,2,…,D}之间的随机量。

最后利用公式(13)进行选择操作，选择目标函数值最优的个体作为下一代种群中的个体, 即

(13)

将差分进化算法应用到SSA的中，每当1只飞鼠个体滑翔到新的位置，找到新的解之后，就对这个解使用变异、交叉和选择操作。

先将飞鼠找到的解通过式(14)变异得到变异后的解。

FSM,i,j=FSi,j+K(FSrand(1,50),j+FSrand(1,50),j)，

(14)

式中:rand(1,50)为区间[0,50]内的随机整数;K=1。

对飞鼠找到的原解和其对应的变异解通过式(15)进行交叉操作，生成新解。

(15)

式中rand为[0,1]区间内的随机数。

最后在原解和新解之间进行公式(16)选择操作，将拥有更优的解个体进入到下一轮迭代。

(16)

2.3 ODESSA流程

ODESSA流程如图1所示。

图1 ODESSA流程Fig.1 Flow chart of ODESSSA

3 ODESSA性能验证

3.1 ODESSA算法参数设置

为了验证ODESSA性能，将其与SSA、PSOSSA、ISSA进行了性能比较。采用12个基准测试函数对所有算法进行了性能测试，为了公平地进行性能比较，消除偶然因素的影响，所有算法均独立运行30次，并计算30次运行结果的平均值和标准差。在ODESSA的参数取值方面，反向学习种群个体数占总数比值P=1，差分进化中的缩放比例因子K=1，CL=0.675，其余的参数取值均与文献[1]的取值相同。其他比较的智能优化算法的参数取值与参考文献[5，6]取值相同。而所有算法的公共参数设置都是相同的，例如种群总体规模NP=50；最大迭代次数Itermax=500。

3.2 基准函数测试

实验所用到的基准测试函数说明见表1，其中F1,F2,…，F6为单峰函数，F7,F8,…，F12为多峰函数。在这些基准测试函数上4种算法得到的30次最优值的平均值和标准差见表2，所有函数的最优值用加粗字体表示。从表2可见，在12个基准测试函数中，ODESSA在其中10个函数上的均值都是最优的，虽然在F6、F8函数上弱于ISSA，但也优于传统的SSA。

表1 基准测试函数说明Tab.1 Description of benchmark function

图2至图7给出了ODESSA与SSA、PSOSSA分别对6个基准函数F2、F3、F8、F10、F11、F12计算函数最优值的过程中，函数最优值的变化曲线。从中可见，ODESSA的收敛速度明显快于SSA和PSOSSA，得到的函数最优值也更优。

表2 4种算法在基准函数上的测试结果Tab.2 Test results of 4 algorithms on benchmark functions

图2 ODESSA、PSOSSA和SSA算法在函数F2上的收敛曲线Fig.2 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F2

图3 ODESSA、PSOSSA和SSA算法在函数F3上的收敛曲线Fig.3 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F3

图4 ODESSA、PSOSSA和SSA算法在函数F8上的收敛曲线Fig.4 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F8

图5 ODESSA、PSOSSA和SSA算法在函数F10上的收敛曲线Fig.5 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F10

图6 ODESSA、PSOSSA和SSA算法在函数F11上的收敛曲线Fig.6 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F11

图7 ODESSA、PSOSSA和SSA算法在函数F12上的收敛曲线Fig.7 Convergence curves of algorithm ODESSA, PSOSSA and SSA on function F12

ODESSA与OSSA、DESSA 在基准测试函数上的测试结果见表3。从表3可见，ODESSA在所有的基准函数上都取得了最优的平均值。

3.3 实验结果分析

从ODESSA与SSA、PSOSSA和ISSA基准函数测试实验结果可以得出，在12个基准测试函数中，ODESSA在10个基准测试函数上都取得了最优的均值，尽管在F6、F8函数上弱于ISSA，但也优于传统的SSA算法和其他的对比算法，ODESSA也比改进前的SSA收敛速度更快，因此ODESSA有着良好的函数寻优性能。ODESSA之所以能在基准测试函数寻优中取得优异的结果，是因为ODESSA算法把差分进化中的变异、交叉、选择机制应用于SSA，使其种群中的个体具有了多样性，从而不容易陷入局部极值，这就使得ODESSA在多峰函数寻优上有着非常突出的优势，也使得算法有着更大的机率找到全局最优解。而且ODESSA的反向学习策略扩大了算法的搜索范围，加快了算法的收敛速度，使得算法能够更快地接近问题的最优解。而ODESSA因为同时使用了反向学习策略和差分进化2种机制对算法进行改进，相比与OSSA、DESSA有着更强的全局搜索能力，所以拥有更好的寻找全局最优解的能力。

表3 ODESSA与OSSA、DESSA在基准函数上的测试结果

4 结语

本文针对SSA求解精度不高、收敛能力不足等缺点，对SSA进行了改进，提出了采用反向学习和差分进化算法改进的飞鼠搜索算法(ODESSA)。通过在飞鼠种群个体的搜索过程中引入差分进化中的变异、交叉、选择机制和反向学习的策略，不仅提高了算法的求解精度，加快了算法的收敛速度，而且进一步加强了算法跳出局部极值的能力，扩大了算法的搜索范围，使得算法具有了更快的收敛速度，也使飞鼠种群个体能够更容易找到全局最优解。将ODESSA与SSA、PSOSSA、ISSA算法在12个基准函数上进行了寻优能力测试，结果显示，ODESSA在其中10个基准测试函数上达到了最佳的寻优结果，而且在收敛速度上也优于比较的算法。再通过将ODESSA与OSSA、DESSA进行算法寻优能力实验，证明了算法改进策略的有效性。

虽然ODESSA有着优秀的寻优能力，但该算法仍然有广阔的改进空间，在未来的研究中我们将会融入更多的算法机制来提高ODESSA的性能。除此之外，我们还会将ODESSA应用到的各个领域当中，解决更多的现实问题。