面向改进天牛须搜索策略的狼群算法

周建新，谢志伟

（华北理工大学电气工程学院，河北唐山 063210）

1 引言

元启发式算法是一种基于所认识的自然现象或过程启迪而模拟求解优化问题的新型智能算法，如蚁群算法（ACO）［1］、人工蜂群算法（ABC）［2］等。狼群算法（WPA）［3］是一种提出的新型群体智能优化算法，该算法具有并行性、全局收敛性与鲁棒性，但存在收敛慢、易陷局部最优等问题。

针对此类问题，众学者提出各自的改进与应用。文献［4］提出了基于高斯扰动和混沌初始化的狼群算法。文献［5］提出将文化基因融入狼群算法并应用于路径问题。文献［6］借鉴量子编码形式提出了量子狼群算法。文献［7］以自适应步长增强搜索灵活性与莱维飞行策略扩大后期搜索范围而增强其全局搜索能力。尽管大量研究对WPA的性能有一定改善，但仍存在收敛速度慢、精度不高、易陷局部最优以及大多改进算法复杂度过高，运行速度较慢等问题。对于狼群算法在收敛速度、寻优精度与易陷局部最优方面的缺欠。这里将天牛须搜索算法（BAS）［8］中天牛以单一个体进行搜索改进为以天牛群体进行搜索，并增加自适应变步长与天牛两须相关联，再将改进后的天牛须搜索策略引入WPA的游走行为中。天牛群的每一个体皆具有简易运算与快速收敛的能力，不仅能够优化WPA的收敛速度与精度，还能减少局部最优的情况发生。

2 狼群算法

狼群算法起源于对狼群的捕食行为与分配猎物方式的研究而开发形成的新式群体智能算法［3］。WPA主要由游走、召唤、围攻三种行为与更新机制组成。

2.1 游走行为

探狼感知猎物气味，并沿各方向趋近于猎物，该行为可视为WPA的全局开发能力。

式中：xlid—探狼的空间位置；

—游走步长；

L—选取的探索方向个数；

l—第i匹探狼在第l个方向探索前进。

2.2 召唤行为

头狼召唤猛狼向当前头狼位置移动，该行为展现出狼群的信息交互共享机制。

式中：d—猛狼与头狼间的判定距离；p—第p个待寻优变量；ρ—距离判定因子。

2.3 围攻行为

猛狼联合探狼紧密围捕以求将其猎获，该行为可视为WPA的局部搜索能力。

式中：r—［−1，1］之间的随机数；

—攻击步长；

—猎物的空间位置。

式中：S—步长因子。

一般来说，S为［n/(2 ×β)，n β］之间的随机整数，其中，为群体更新比例因子。

3 基于改进策略的狼群算法

3.1 天牛须搜索算法

天牛须搜索算法是基于天牛依赖其两须确定搜索方向直至寻得食物的新型智能算法［8］。天牛须搜索算法归属单体智能算法，具有运算快、可跳出局部最优的优点［9］。BAS步骤为：

（1）向量归一化

式中：k—空间维度；rand（k，1）—随机产生的k维随机向量。

（2）左右须及其适应度更新

式中：d（t）—天牛第t次迭代时两须的距离；

f(•)—两须的适应度值；r=2。

（3）天牛位置更新

式中：δ—步长因子。

（4）判断更新后的适应度值是否优于前次迭代的适应度值，是则更新天牛位置，否则回转步骤（2）当到达迭代次数后输出最优值。

3.2 改进狼群算法的结合机制

针对天牛须搜索策略步长因子过小会导致前期搜索速度过慢，过大则导致陷入局部最优的困境，可将搜索距离d与步长δ用数学模型相关联，使步长可匹配维数增长的适应度函数。

式中：c1、c2—需要调整的常数。

以式（11）、式（12）取代式（9），采用搜索距离与步长关联的变步长方式更新天牛位置以期望前期具有较快的寻优速度同时还可以保证后期能够拥有更佳的寻优精度。

BAS 更注重于过程搜索，而WPA 更关注精细搜索。对于WPA来说，其局部开发能力在猛狼的围攻行为中得到展现，其全局搜索能力表现于探狼的游走行为中，但探狼以贪婪式游走策略前进会导致陷入局部最优的困境而削减算法的全局搜索能力。针对该上述欠缺，这里在此将赋予BAS种群特性，即多只天牛同时在目标空间中搜索，并以自适应变步长的方式更新天牛位置，将改进的天牛须搜索策略取代WPA的游走行为（即式（6−8、10−12）取代式（1）），以BAS具有提高狼单个体寻优的速度和全局寻优能力的特点，在保留其运算便捷，摆脱局部最优的同时以期在高维也能快速精准寻优。依据BAS与WPA的优势，以期提高算法的全局搜索能力以及收敛速度，更好地发挥WPA的性能，其算法的主要步骤如下所示：

（1）初始化算法所需的所有参数。

（2）将探狼等效成天牛，且计算出天牛左右须的位置适应度及天牛位置。

（3）生成天牛位置的更新规则且得出天牛的个体最优值与全局最优值，而后式（11）、式（12）进行步长变换。

（4）判断是否满足天牛须的迭代终止条件，是则输出全局最优值并执行下一步；否则回转到步骤（2）。

（5）猛狼向猎物奔袭，若，则；若，则猛狼保持奔袭至与头狼的距离不大于判定距离后执行下一步。

（6）执行围攻行为，且以式（4）更新参与围攻行为的所有人工狼的位置。

（7）以“胜者为王”规则更新头狼位置后，再以“强者生存”机制更新狼群群体。

（8）判定优化精度或最大迭代次数是否达到要求，是则输出头狼位置，即为最优解；否则回转步骤（2）。

综上所述，基于天牛须搜索策略的狼群算法的流程图，如图1所示。

图1 BWPA流程图Fig.1 BWPA Flowchart

4 测试仿真及结果分析

4.1 基准测试函数

为了评估创新式智能算法的性能，选取benchmark［10］测试函数的部分函数进行性能测试。其中，F1−F3为只存在一个全局最优值的单模态函数，用以评定算法的局部探索能力；F4、F5为存在多个最优值的多模态函数，用以评定算法的全局开发能力，并同时与ACO、WPA、BAS等先进算法进行仿真比较分析。F1−F5基准测试函数详情，如表1所示。

表1 基准测试函数表Tab.1 Benchmark Function Table

4.2 多种智能算法的对比分析

将BWPA运算结果与其他智能算法的运算结果进行对比分析。在仿真测试中，应设置相应初始参数以保证各智能算法的对比有效性，其中，各算法种群大小为45，迭代次数为700，其他参数，如表2所示。

表2 参数设置表Tab.2 Parameter Setting Table

为了增强该实验的可靠性及信服力，在同一条件下，进行多次重复仿真并记录数据的最值、平均值与标准差值。在处理最小值问题的情况下，平均值越小，其算法性能越优越；标准差值越小，其算法越具有稳定性，其实验仿真结果，如表3所示。为了更直观地表明BWPA在优化过程中的性能，绘制出各算法在50维搜索空间中的收敛曲线，如图2所示。

表3 各智能算法50维度的基准函数对比Tab.3 Comparison of Benchmark Functions of 50 Dimensions of Each Intelligent Algorithm

图2 各算法收敛曲线（50维）Fig.2 Convergence Curve of Each Algorithm（50 Dimensions）

据表3所得数据分析得，在5例仿真测试中，BWPA寻优精度皆取得最优成果。此外，BWPA在所测试的维度中，对于函数F4取得了理论最优值，对于函数F1、F2、F5所求得的最优解标准差值都为0，极近似于理论值。因此，该表证实BAS能改善WPA的局部搜索能力以及狼群的品质，提升算法的全局开发能力，并且BWPA更具有优越的性能及稳定性。

蚁群算法（ACO）、传统WPA和改进BAS和BWPA在50维度的收敛曲线对比图，如图2所示。从图中可以看出BWPA的收敛速度普遍比其他算法快，这是由于引入天牛须搜索策略在迭代前期确定更优搜索方式与加入自适应步长使算法具有较快收敛的特性。由图2所示，式F1~F5的收敛曲线依次，如图2（a）~图2（e）所示。BWPA能够在更少的迭代次数内到达寻优精度表明其寻优的快速性优于原算法。其次，BAS的收敛曲线稍凸，而WPA的收敛曲线更平滑，可表明其能够能更快速地摆脱局部最优的困境。再者，BWPA的收敛曲线始终在WPA的下方，可表明BWPA寻优快并且具有更佳的寻优精度。最后，图2（c）明显地表明了BWPA继承了BAS摆脱局部最优的优点，图2（d）的断线说明其已经寻得理论最优值。

因此，综合表3的数据与图2的收敛曲线可知，在此维度下，种群性的BAS可以强化WPA，有效地增强狼群的适应度与性能，比其他智能算法更具备显著的竞争优势。

4.3 更高维度的测试仿真

为了考察BWPA不同维度下的普遍适用性，增强该算法的信服力，将函数F1~F5的维度改变为1000，其他参数设置不变，进行多次重复仿真，得到1000维度的数据，如表4所示。收敛曲线，如图3所示。并对所得结果进行分析。

表4 各智能算法1000维度的基准函数对比Tab.4 Comparison of Benchmark Functions of 1000 Dimensions of Each Intelligent Algorithm

图3 各算法收敛曲线（1000维）Fig.3 Convergence Curve of Each Algorithm（1000 Dimensions）

据表4分析得，BWPA 在该维度仍皆取得最优成果。此外，BWPA在所测试的两个维度中，对于函数F4都取得了理论最优值，对于函数F1、F2、F5所求得的最优解标准差值都为0。

极度接近于理论值。另一方面，按照同一测试函数的不同维度的角度分析，可得知BWPA在较高维度的收敛精度有可能比较低维度更好（如F3），该情况可表明BWPA 在较高维度BWPA 仍具备良好的性能及优异的稳定性。

据图3所示，F1~F5的收敛曲线依次，如图3（a）~（e）所示。该算法的表现在较高维度与较低维度相似。当求解过程变得更复杂时，BWPA仍能具备最快的收敛速度且避免落入局部最优的优势。因此，BWPA在较高维度中仍存在较大的竞争优势。

综上所述，不管BWPA处于低维度或较高维度，其比传统的WPA或改进的BAS具有更强的性能与稳定性，更佳的寻优速度与寻优精度，证明自适应变步长种群化的天牛须策略优化狼群算法中过于贪婪的游走行为是可行且有效的。

5 结论

WPA是一种较为新颖的群智能算法，在处理复杂函数优化问题时难免具有收敛速度比较慢且极易陷入局部最优的特点。经具体分析，该缺陷的源点大部分在于狼群算法过于贪婪的游走行为。因此，这里以改进自适应变步长的天牛须搜索策略取代狼群算法的游走行为。由5个基准测试函数仿真测试结果可证实提出的改进算法在处理复杂函数优化问题上更具备竞争能力。下一步研究内容应为将BWPA应用于约束优化问题和更复杂的实际工程问题。