莱维飞行和反馈策略的自适应被囊群算法

梁建明，何 庆

1(贵州大学 大数据与信息工程学院，贵阳 550025) 2(贵州省公共大数据重点实验室，贵阳 550025)

1 引 言

近年来元启发算法引得越来越多的学者关注和研究，在不断的探索和研究的过程中，也诞生了许多群体智能优化算法.如鲸鱼优化算法(WOA)[1]、蝗虫优化算法(GOA)[2]、蝴蝶优化算法(BOA)[3]、黏菌优化算法(SMA)[4]、正余弦优化算法(SCA)[5]等.

被囊群算法(Tunicate Swarm Algorithm，TSA)[6]是Satnam Kaur等在2020年9月提出的一种新型元启发优化算法，它的灵感来自以海洋被囊动物在导航和觅食过程中的喷射推进及其群体行为.其优点在于操作简单，调整的参数少以及跳出局部最优的能力强.在文献[6]中仿真结果表明，与其他群智能算法相比，TSA算法能较快地找到最优解.使用该算法可以解决具有未知搜索点的实际案例研究，Abhishek Sharma等[7]采用TSA来估计标准温度条件下光伏电池组件未知参数的最优值，有效的证实了TAS运用在光伏电池中提取最优参数的优越性；Tamer Fetouh等[8]将TSA运用到配电系统中寻找最优解以提供定量和定性的电力服务，降低能耗；D.Anand Joseph Daniel等[9]将TSA算法运用到特征选择中，解决了由于特征集较大而引起的可扩展性问题.

虽然TSA的局部开发能力强，但是对于全局探索能力却不足，从而导致寻优精度不高，收敛速度慢[10].为此，针对这些问题.Li等[11]使用混沌初始化、全局搜索向量和莱维飞行对TSA算法改进，并运用于解决动态经济排放调度问题.

为了提高算法的收敛速度，文献[12]利用群体协同机制，增强蝴蝶算法逃离局部最优的能力；文献[13]通过引入控制概率Pc决定算法进入前半段还是后半段探索.所以这有助于算法前期需进行大范围全局探索，后期需进行小范围的局部开发并避免算法过早收敛.文献[14]通过使用混沌映射初始化种群位置，加快鲸鱼算法的收敛速度.

上述策略对于改进算法全局探索能力不足、寻优精度不高和收敛速度慢具有一定的效果，但是在TSA中却达不到很好的预期，为此本文将改进的策略融入标准的TSA算法中，提出莱维飞行和反馈策略的自适应被囊群算法.首先通过分析和实验确定莱维飞行参数，使之适应TSA算法；反馈策略改进种群位置更新公式，增强算法逃离局部最优的能力和加快算法收敛的速度；受文献[13]的启发，我们舍弃原有的等式，采用分段式的概率分配，实现在位置更新处权重自适应，提高算法对全局搜索和局部搜索能力，避免算法早熟.

2 被囊群优化算法

被囊群算法是对海洋中被囊动物的觅食行为进行建模.被囊动物是利用其自身的两种行为来寻找食物来源，即寻找最佳.觅食行为包括喷射推进和群体智能.为了对喷射推进行为进行数学建模，被囊动物应满足3个条件，即避免搜索种群之间的冲突、向最佳搜索个体的位置移动以及保持与最佳搜索个体的距离.最后，群体会根据个体的最优解更新位置.

(1)

PD=|Fbest-rand-P(x)|

(2)

(3)

其中，式(1)表示避免搜索种群之间的冲突行为.rand、c1、c2、c3是[0，1]上服从均匀分布的随机数，Vmin、Vmax分别是表示初始的相互作用速度范围，一般设定Vmin=1、Vmax=4.式(2)计算个体与食物之间的位置，其中Fbest为食物位置，P(x)为个体当前位置.式(3)表示个体向最优位置收敛，其个体的位置更新为P(x).

被囊群是由被囊动物所构成，是群体性的动物.所以在完成个体运动行为建模之后，接下来就是对群体行为的建模.

群体行为：

(4)

式(4)表示保存前一个最优解和当前最优解，通过这两个解完成对当前位置的更新.

由上述分析可知TSA算法的基本实现步骤如下：

Step1.初始化种群P;

Step2.初始化种群参数，边界条件;

Step3.计算每个个体的适应度值；

Step4.搜索最佳个体的位置;

Step5.根据群体行为更新每个个体位置；

Step6.调整超出给定搜索空间边界的个体位置；

Step7.计算更新后的群体每个个体的适应度值，如果适应度优于之前，则更新；

Step8.如果满足停止条件，则停止算法，否则重复步骤如果满足停止条件，则停止算法，否则重复步骤Step 5-Step 8；

Step9.返回最优值；

3 LSATSA算法

3.1 融入反馈策略位置更新

本文在搜索种群空间中随机选出一只被囊动物，得到随机被囊动物的反馈信息，然后再结合最佳位置去更新个体位置.通过不断地迭代，最终找到食物.如果选择的随机被囊动物离食物近，那么它反馈给其他被囊动物的信息是有利于个体位置更新的，则在更新位置时加入反馈的信息；反之，如果随机被囊动物离食物远，那么反馈回来的信息对当前位置更新没有帮助.

建立的数学模型如下：

(5)

b=Fmax+rand(Fmax-Fmin)

(6)

(7)

式用β是共享系数，平衡位置更新时反馈信息的大小.γ为反馈数，随着迭代次数的增加，呈现递增趋势，能够加快被囊动物之间的信息交流；R(x)为随机被囊动物个体；F为计算被囊个体适应度；t表示当前迭代次数.

反馈策略可以借助随机个体的信息帮助自身更快的完成最佳位置的探索，有效的避免了算法陷入局部最优的风险.而且在迭代的初期，这样的反馈策略，使得算法增强了探索开发能力，可以避免算法早熟现象.

3.2 莱维飞行策略

莱维飞行是服从莱维分布的随机搜索的，是一种短距离的搜索与随机较长距离的行走相间的行走方式，模拟自然界动物和昆虫觅食的一个随机游走过程.莱维分布是由法国数学家莱维提出的一种概率分布，在自然界中很多动物的运动轨迹均服从莱维分布[15].

由于莱维飞行机制，使得个体位置的变化更加灵动，所以可以避免算法陷入停滞状态.其使用引入莱维飞行的位置更行如下：

(8)

式(8)中L(β)的数学式如式(9)所示：

(9)

式(9)中μ和v是[0，1]上的随机数，均服从正态随机分布.相较于原L(β)，式(9)简化了参数，但是能达到与原L(β)相同的效果.

改进后的L(β)以及α的选取的莱维飞行算法更适用于运用到被囊群算法中.不仅增强了算法的全局开发能力，同时也减小了算法陷入局部最优的风险.

3.3 自适应权重

在标准的被囊群算法中，可以看出被囊动物的位置更新公式主要受个体当前位置、上一代个体位置和一个[0，1]之间的随机参数决定的.这个参数的大小影响着算法的探索能力和开发能力.因为当这个随机数越大，个体位置更新的步长越小，越有利于对种群空间的探索能力；当这个随机数越小，个体位置更新的步长越大，越有利于算法的开发能力.由于原被囊群算法使用的是随机数，这就使得算法在计算被囊动物的位置的时候会产生盲目性.正因为这种盲目性，使得算法在迭代的初期和后期不能很好的完成探索和开发.

针对以上问题，本文在被囊群算法的群体行为中加入自适应权重值.在更新个体位置时，使用自适应权重代替原被囊群算法中的随机数.具体的数学表达见式(10)：

(10)

在被囊群算法的群体行为中引入自适应权重值的个体位置更新公式为：

(11)

算法迭代中前期，自适应权重值随时间逐渐减小，位置更新权重整体增大，更新步长增大，算法在前期具有较强的探索能力；算法迭代中后期，自适应权重值随时间逐渐增大，位置更新权重整体减小，更新步长减小，算法在后期具有较强的开发能力.

3.4 LFATS算法流程

本文将莱维飞行、反馈策略和自适应函数融入到标准的被囊群算法中，使得算法具有较强的全局搜索能力和局部开发能力，而且有效的降低了算法的盲目性.当陷入局部最优的时候，改进的算法还具有跳出局部最优的能力.较标准的被囊群算法来说，改进后的被囊群算法整体上效果更优.算法的流程图如图1所示.

图1 算法流程图Fig.1 Algorithm flow chart

Step1.初始化种群P;

Step2.初始化种群参数，边界条件;

Step3.计算每个个体的适应度值；

Step4.根据式(7)加入反馈策略更新个体位置；

Step5.根据式(10)计算自适应权重值c；

Step6.在原位置更新处融入式(8)莱维飞行机制和自适应权重共同更新个体位置；

Step7.根据群体行为更新每个个体位置；

Step8.调整超出给定搜索空间边界的个体位置；

Step9.计算更新后的群体每个个体的适应度值，如果适应度优于之前，则更新；

Step10.如果满足停止条件，则停止算法，否则重复步骤如果满足停止条件，则停止算法，否则重复步骤Step 6-Step 10；

Step11.返回最优值.

3.5 算法时间复杂度分析

在TSA算法迭代初期，假设种群规模为n，空间维度为d.则算法初始化的时间复杂度为O(n×d)，计算适应度的时间复杂度为O(Tmax×n×d)，算法在迭代过程之中的时间复杂度为O(N)，N为被囊动物喷射推进行为的次数，最终TSA算法的时间复杂度为O(Tmax×n×d×N).

LFATS算法在原算法中添加了反馈策略、莱维飞行和自适应权重.LFATS算法初始化的时间复杂度为O(n×d)，加入反馈策略的时间复杂度O(n×d)，加入莱维飞行和自适应权重模拟被囊动物的喷射推进时间复杂度为O(N)，所以最终O(Tmax×n×d×N)的时间复杂度为O(Tmax×n×d×N)，与原算法的时间复杂度相同，那么添加的这些策略机制不会对算法带来负面影响.

3.6 算法空间复杂度分析

TSA算法的空间复杂度被定义为初始化过程中的最大空间量，即O(n×d).同理LFATS算法的空间复杂度为O(n×d).

4 实验仿真与分析

本文采用MATLAB R2018b进行试验，运行环境为64位Windows 10操作系统，处理器类型为 Intel(R)Pentium(R)CPU G4560.仿真程序中算法参数设置：种群规模N=30，最大迭代次数Tmax=500，空间维度D=30.

实验采用6个基准测试函数，这6个基准函数有单峰函数也有多峰函数.如表1所示.函数1-4为单峰函数，最优解就是局部最优值.函数5-6为多峰函数，最优解能够验证算法是否具有跳出局部最优能力.

表1 基准测试函数Table 1 Benchmark function

实验1.为了验证算法的有效性和鲁棒性，使用如表1所示的6个基准测试函数作为算法的目标函数，将本文算法与标准TSA、WOA、ITAS[11]、蚁狮优化算法(ALO)[16]和SCA做比较.此外，为了直观地观察引入策略的可行性，将3种策略引入到对比实验中.为了实验的公平性，对比算法的参数与原文献中保持一致，本文算法参数设定如2、3节所示.

表2 不同算法寻优结果对比Table 2 Comparison of results of algorithms

实验中种群设置为30，最大迭代次数为500，每个算法独立运行30次.

实验通过表2中的最优值、最差值、平均值、方标准、平均收敛时间差5个性能指标来评估各算法性能.

表2中的平均值和最优值反映了算法的收敛速度和寻优精度.不管是在单峰函数还是多峰函数上，可以明显看到，改进的被囊群算法的平均值和最优值优于WOA、ALO和SCA，说明改进的被囊群算法在收敛速度和寻优精度上优于其他的优化算法.F1-F4单峰函数上，LFATSA有很强的寻优精度和收敛速度.在F1和F3上找到了理论最优值，在F3和F4上找到的最优值在数量级上已经非常接近理论最优值.由于F5和F6是多峰函数，在求解时会有一定的困难，所以LFATSA效果在多峰函数上的效果没有单峰函数的好，但是收敛速度和寻优精度却是优于WOA、ALO和SCA.LFATSA在F6上的最优值与WOA的最优值相等，但是LFATSA的平均值要优于WOA，所以LFATSA的收敛速度要比WOA、ALO和SCA快.F2到F3维度上增加，WOA、ALO和SCA收敛速度和寻优精度表现得很差，从负数量级到正数量级的跳跃.而LFATSA却能在F4上寻找到理论最优值，表明LFATSA算法在处理高维和低维函数上有更好的效果.为了验证引入的机制对于TSA的收敛速度和寻优精度是否有帮助.本文还使用LTSA、FTSA、ATSA来与TSA做比对，验证其加入机制的效果.从表中明显看出，在F1-F4上LTSA、FTSA、ATSA的收敛速度和寻优精度都是优于TSA的，甚至在F3中FTSA找到了理论最优值.由于多峰函数的特性，使得求解最优值有一定的难度.虽然在F5和F6上部分值与TSA相等，但是整体上LFATSA还是优于TSA.所以说明引入的机制不同程度上对TSA性能上有较大的提升.

表2中的标准差可以衡量算法的稳定性和跳出局部最优的能力.从表中的数据可以看出，不管是单峰函数还是多峰函数，LFATSA算法的标准差都远小于WOA、ALO和SCA的标准差.而且在F1、F2、F3、F4、F6上都达到了最优值.所以在与对比算法相比，LFATSA稳定性和跳出局部最优的能力要更佳.同样，LTSA、FTSA和ATSA三者的标准差都要低于TSA的标准差，所以验证了引入三者对于改进TSA算法的稳定性和跳出局部最优的能力有很大的增强.值得注意的是，标准的TSA算法在F1、F3、F6上的标准差为理论值，所以TSA算法也具有跳出局部最优的能力.但是在F2、F4、F5上表现得不是很明显，说明标准的TSA算法也存在这陷入局部最优的风险.但是从表中得知F2、F4、F5上的LTSA、FTSA和ATSA上的都要优于TSA，所以使得LFATSA的稳定性和跳出局部最优的能力要强于标准的TSA.

此外，与其他改进的TSA算法ITSA相比，本文所提出的算法在各个基准函数的性能评估上优于ITSA.

最后，从算法的平均耗时分析，所有算法中ALO平均收敛时间最长，达到几百秒.从收敛曲线可以看出，每一个策略对于原算法性能有着不同程度的增强，引入更多策略，扩大了算法的搜索范围以及找到更多的解，所以改进算法的平均耗时要大于标准的TSA算法.但相较于其他对比算法，本文改进算法的平均收敛时间要更小，所以算法增加的时间在可接受的范围之内.

图2(a)～图2(d)上是各算法在单峰函数的平均收敛曲线.明显观察到TSA算法还有其改进的算法的收敛速度和寻优精度都要优于其他3种对比算法，尤其LFATSA性能更要远超于WOA、ALO和SCA.LFATSA与LTSA、FTSA、ATSA和TSA相比，寻优精度依次是LFATSA、FTSA、LTSA、ATSA，最后是TSA.其四者的收敛速度和寻优精度都要高于标准的TSA算法，直观的说明了3种策略提高了被囊群算法有效性.

图2(e)和图2(f)上是各算法在多峰函数的平均收敛曲线.在多峰函数F5上，所有的算法都未能找到最优值，但是在算法迭代的后期LFATSA算法的寻优效果要比其他算法好.虽然在迭代中期靠后一点WOA收敛速度要优于LFATSA，但是在迭代的前期和迭代的后期，算法的收敛速度都要好于其3种对比算法，ALO和SCA效果最差.在多峰函数F6上所有的算法也都没能寻找到最优值，但是LFATSA、FTSA、LTSA和ATSA的收敛速度都要优于TSA、WOA、ALO和SCA，寻优精度上LFATSA和LTSA要略优于其他算法.

从引入3种机制的角度上分析收敛曲线.在图2(a)～图2(f)中LFATSA、FTSA、LTSA和ATSA曲线下降速度快并且寻优精度高说明引入的莱维飞行和反馈策略能够增强算法跳出局部最优的能力，致使算法能够在迭代的前期有较快的收敛速度.在接下来迭代的过程中，LFATSA能够继续保持寻优，说明了自适应权重的引入对于算法的探索能力有一定程度的提升.因为算法迭代后期，自适应权重值增大，算法整体权重值减小，更新步长减小，算法这时具有探索能力.在图2(a)～图2(d)上LFATSA收敛速度更快、寻优精度更高，说明引入的莱维飞行、反馈策略和自适应权重增强了算法跳出局部最优的能力和全局搜索能力，其他对比算法却出现了停滞状态.在F5多峰函数上.LFATSA算法在迭代的后期还有寻优能力，说明引入的自适应权重提高了算法的开发能力.

图2 测试函数平均收敛曲线Fig.2 Average convergence curve of test function

实验2.本文选取了CEC2014上的部分函数进行了验证选取上的CEC2014部分函数如表3所示.参数设置如下：种群规模为30，CEC2014函数的搜索维度设为30，迭代次数500，独立运行30次.实验结果如表4所示.

表3 CEC2014函数(部分)Table 3 CEC2014 function(part)

表4 CEC2014 测试函数的结果对比Table 4 Comparison of CEC2014 test function results

表4记录了LFATSA、TSA、WOA、ALO、和CSA算法的在CEC2014部分函数上测的平均值和标准差.由于CEC2014函数的复杂性，在寻找最优值上有一定的困难.由表4可知，在CEC5、CEC6、CEC16上，LFATSA算法的平均值和标准差都要低于其他算法.在CEC16和CEC26上，LFATSA性能略低于TSA算法，但是却优于其他对比算法.在CEC24上，LFATSA的平均值大于TSA，但是LFATSA的标准差要比TSA的更小.综上所述，改进后的被囊群算法的综合性能要优于其他算法，具有良好的鲁棒性和有效性.

此外本文还运用Derrac等在文献[17]中提出Wilcoxon秩和检验方法，对改进算法性能进行评估.使用Wilcoxon秩和检验方法来验证本文改进算法在每个函数上独立运行30次的结果是否在统计上与其他算法存在显著性的差异.并且在5%的显著性水平下进行.当p值>0.05时，接受H0假设，表明两种算法没有显著性的差异；当p值>0.05时，拒绝H0假设，表明两种算法具有显著性的差异.

表5给出了LFATSA与TSA、LTSA、FTSA、ATSA、SCA、WOA、ALO的秩和检验中计算的p值，由于算法不能和本身作比较，所以在表中“Na”表示不适用，为了更明显观察判定结果，“+”、“-”，“-”表示LFATSA算法性能优于，劣于和相当于对比算法.

从表5看来，LFATSA算法在函数F5上性能低于FTSA和ATSA外.在其他位置上都优于其他算法，总体上LFATSA算法的性能与其他算法有着显著性的差异.

表5 基准函数 Wilcoxon 秩和检验的p值Table 5 p value for Wilcoxon′s rank-sum test on benchmark function

5 结束语

为了增强标准的TSA算法的收敛速度和寻优精度已经跳出局部最优的能力，本文在标准的TSA算法上引入了莱维飞行机制、反馈策略和自适应权重，提出了基于莱维飞行和反馈策略的自适应被囊群算法(LFATSA).莱维飞行使得被囊动物个体位置的变化更加灵动，当算法陷入局部最优的时，算法就具有了跳出局部最优的能力；其次，反馈策略中引入一个随机被囊动物，将随机被囊动物的信息反馈给当前被囊动物.通过这种反馈方式，可以更好的引导算法朝着最优值前进；再次，自适应权重机制使得算法在迭代前期和迭代后期的探索能力和开发能力都有增强.为了验证改进算法的鲁棒性和有效性，本文将改进算法与其他算法及单独改进的TSA算法应用于基准测试函数和CEC2014函数上进行寻优，通过平均值和标准差等指标对算法性能进行评估.另外，为了更好的评估改进算法的性能，本文还使用统计检验Wilcoxon对算法进行显著性分析.试验结果表明LFATSA算法具有很好的性能，收敛速度快和寻优精度高，探索能力和开发能力得到增强.

在后续的研究中，可以考虑使用其他的策略更好的改进算法，使得算法在多峰函数上表现得更佳并能使用到实际工程运用中，解决更多工程问题.