基于自适应步长和莱维飞行策略的改进狼群算法

李彦苍，徐培东

（河北工程大学 土木工程学院，河北 邯郸 056038）

群居是一种常见的自然现象，在群居中，社会群体能够适应自然选择原则，在物种内部竞争中生存下来。大雁向南迁移，鱼成群结队游荡在水中搜索食物和蚁群在信息素浓度的帮助下选择最短路径，它们通过减少自身能量消耗增加集体利益，是长期自然选择的结果[1-4]。这些集群行为表现为群体的自组织、自适应和团队协作，能够增强群体对环境的整体适应性。群智能算法是一种模拟自然生物进化或觅食行为的一种算法[5]。受动物群体现象启发，人们开发了许多优化计算方法解决复杂问题。常见的群智能算法主要有粒子群优化算法[6]、蚁群优化算法[7]、人工鱼群算法[8]、人工蜂群算法[9]。蝴蝶算法是O’Neil 等[10]模仿蝴蝶觅食行为提出的自然启发式优化算法；果蝇算法是Pan 等[11]基于果蝇觅食行为提出的全局优化方法；花粉算法是Yang 等[12]模拟自然开花植物自授粉和异花授粉生物学特性提出的随机全局优化算法；鸡群算法是Meng 等[13]通过模拟鸡的等级和行为提出的优化算法。鸟类、鱼类、蚂蚁和蜜蜂等，它们通过不断适应环境和相互合作，表现出强大的群体智能，给人类提供许多解决复杂问题的新思路，提高处理优化问题的能力，有效推动计算智能的发展，但在计算精度方面仍需进一步研究。

狼群算法（wolf pack algorithm，WPA）是吴胜虎[14]于2013 年提出的一种新的群智能算法。该算法在进行优化问题求解时，具有较好的寻优性能，但算法也存在一些不足之处：收敛速度慢、收敛精度不高、鲁棒性低等[15]。文献[16]针对后期收敛速度慢的问题，引入交互式步行运动，提出具有领导策略的狼群搜索算法。文献[17]为解决高维函数优化问题，提出非人工狼群算法（uncultivated wolf pack algorithm，UWPA）。文献[18]采用Tent 混沌序列来启动个体位置，提出结合粒子群的狼群优化算法。文献[19]引入差分进化策略，提出基于差分进化的改进狼群算法（improved wolf pack algorithm，IWPA）。文献[20]引入控制自适应参数a和混沌思想，提出自适应调整的混沌灰狼算法。文献[21]提出改进的灰狼算法，通过添加可调参数，提高算法鲁棒性，同时对几种结构进行分析，获得更好解决方案。改进后的算法在一定程度上提高了精确度和收敛精度。

研究在狼群算法的基础上，对狼的游走行为提出了基于莱维飞行的搜索策略，对召唤、围攻行为时的移动步长提出自适应性改进，使每匹狼每次移动的步长由该狼当前位置和当前头狼位置决定。经过测试，提出的自适应步长和莱维飞行策略的改进狼群算法（levy flight and adaptive step size strategy improved wolf pack algorithm，LWPA），收敛速度加快，收敛精度提高，增强了算法的寻优性能和鲁棒性。最后，使用LWPA 对桁架结构进行优化设计，并与其他算法进行比较。

1 莱维飞行策略和自适应步长的狼群算法

1.1 智能行为和规则的描述

1.1.1 狼群的初始化

设狼群规模为N，搜索空间的维数为D，第i只人工狼的位置可表示为

式中：xmax和xmin分别是搜索空间的最大范围和最小范围；rand ∈(0,1)的一个随机数。

1.1.2 头狼产生规则

在初始解空间中，目标函数值最优的人工狼被选为头狼，每次迭代后更新人工狼的位置。此时如有多个最优人工狼情况，则随机选一个成为头狼。头狼不执行以下智能行为，直接进入迭代，直到被其他更强的人工狼替代。

1.1.3 基于莱维飞行的游走行为

除头狼外选取最佳的S_sum 匹人工狼视为探狼，S_sum 随机取之间的整数，α为探狼比例因子。在实际情况中发现，游走过程中探狼只会盲目跟随头狼并逼近头狼位置的猎物气息浓度，不会关心自己身边是否有更优猎物气息浓度，在算法后期，导致种群丧失多样性，易陷入局部收敛，出现早熟收敛现象。针对这种缺陷，利用莱维飞行对群体中的探狼进行全局搜索。莱维飞行属于随机游动，是一种很好的搜索策略，能扩大搜索范围[22]。新一代的探狼i的计算公式如下

式中:xid(t)表示探狼i在t次迭代第d维的位置；⊕为点对点乘法；c为探狼i位置的随机数，由式（4）决定，Levy(δ)代表随机搜索路径，由式（5）决定。

式中：δ的取值范围一般为1 ＜δ＜3，δ取1.5，Xbest表示历史最优探狼位置，u和v服从式（6）所示的正态分布

σu和σv取值为

此时，探狼感知的猎物气息浓度函数值为Yip，选择最大的猎物气息浓度函数值，若大于当前函数值Yi，则向Yip的方向前进一步，同时更新探狼状态，重复以上游走行为，直到某匹探狼i的函数值Yi＞Ylead或游走次数达到最大游走次数T1max。

1.1.4 奔袭行为

在基本的狼群算法中，狼群位置变动是由步长step 决定的，对于每一个固定的D维空间，相应的[dmin,dmax]是固定的，因而每一次迭代对应的步长step 是固定的。如果step 过大，会影响算法优化的准确度；如果step 过小，影响算法的收敛速度，当达到最大迭代次数时，最优解还未被找到。借鉴文献[23]，狼i每一次移动的步长由该狼当前位置和当前头狼位置决定，因此在奔袭和围攻行为时采用自适应步长

式（8）中rand 表示[0,1］间的随机数，当狼离头狼距离远时，以较大步长逼近头狼，加快收敛速度，避免不必要的搜索；当离头狼距离近时，以较小步长逼近头狼，提高搜索精细程度。

与以往狼群算法不同，随机选取除头狼外的全部狼群中M＿num 只猛狼参与召唤，而不仅是头狼附近的人工狼。在猛狼奔袭过程中，当某只猛狼感知到其所在位置猎物气息浓度更高时，则替代头狼，重新选取猛狼，进行召唤，直到其所在位置的猎物气息浓度低于头狼位置气息浓度。同时，召唤行为的步长取式（8），猛狼根据式（9）更新当前位置

式中：x*id表示更新后猛狼的位置；xid为当前猛狼的位置；xleadd为头狼的位置。

1.1.5 围攻行为

同时，猛狼联合探狼对猎物进行围捕。移动步长采用式（8），狼群围攻行为由式（10）表示

式中：Gd为猎物在D维空间的位置，λ为区间[-1,1］均匀分布的随机数。

1.1.6 “强者生存”的狼群更新机制

猎物的分配遵循“由强到弱”的原则，即在算法中去除目标函数值最差的R匹人工狼,同时随机产生R匹人工狼，在实际捕猎过程中，每次捕猎的数量都是随机的，这也导致不同数量的弱狼被淘汰。基于此，β取[n(2 ×β),n β]之间的随机整数，β为更新比例因子。

1.2 改进狼群算法描述

Step1 初始化狼群中人工狼的数目N和其所在位置Xi，最大迭代次数Kmax，探狼比例因子α，更新比例因子β，最大游走次数T1max，最大奔袭次数T2max。

Step2 根据头狼产生规则确定头狼。

Step3 探狼按照莱维飞行策略公式（3）～（7）执行游走行为，直到某匹探狼i的函数值Yi＞Ylead或游走次数达到最大游走次数T1max，转Step4。

Step4 猛狼执行奔袭行为，并按照公式（9）向猎物奔袭。在奔袭过程中，若猛狼感知的猎物气息浓度的函数值Yi＞Ylead，则令Yi=Ylead，该猛狼转化为头狼并发起召唤行为；若Yi＜Ylead，则继续奔袭直到某匹猛狼的函数值小于头狼函数值或奔袭达到最大奔袭次数T2max，转Step5。

Step5 按照公式(10)，更新参与围攻的人工狼位置，进行围攻。

Step6 执行狼群的更新机制。

Step7 判断算法是否满足优化精度要求或最大迭代次数Kmax，若满足要求，输出头狼位置，即所求问题的最优解，否则转Step2。

图1 LWPA 算法的基本流程图Fig. 1 LWPA algorithm iteration diagram

2 实验仿真与分析

2.1 基本测试函数与参数设置

表1 中的“U”表示函数为单模态函数，“M”为多模态函数，“S”为可分离函数，“N”为不可分离函数。多模态函数比单模态函数复杂，一般算法难以找到具有多个局部极值的全局最优值，容易陷入局部极值或局部极值之间的振荡[24]。因此，多模态常被用来测试算法的全局搜索性和避免早熟收敛能力[25-26]。由于不可分函数变量之间的关系较复杂，很难找到不可分函数的全局最优值[27-28]。WPA、UWPA 以及IWPA 算法所涉及到的参数分别参考文献[14-19］进行设置。N取50，Kmax取1 000，β取4，α取4，T1max（T2max）取10。

表1 用于测试算法性能的15 个函数Table 1 15 functions for testing algorithm performance

2.2 算法对比验证

为充分计算算法的性能，使用LWPA、UWPA、WPA 以及IWPA 分别对15 个复杂函数进行了100 次连续优化计算[29]。基于表2 的6 种指标对该算法进行评估。当不同的计算结果与最优值之间的误差超过e-3，被认为是一种失败。结果见表2。

表2 4 种算法在15 个测试函数中的结果比较Table 2 Comparison of results of four algorithms in 15 test functions

2.3 LWPA 主要参数分析

LWPA 虽然具有一定优越性，但所涉及的参数也众多，主要参数对算法性能的影响也不尽相同。T1max/T2max分别是狼群在游走/奔袭过程中的最大次数，β是狼群的更新比例系数。根据15 个函数的特性将其分成7 大类，分别改变Tmax和β的大小对这7 种函数进行50 次寻优计算，Tmax和β对算法性能的影响如表3、4 所示。

表3 Tmax 对算法的影响Table 3 Effect of Tmaxon the algorithm

2.4 LWPA 收敛性分析

Markov 链是一种无后效性的随机过程，常被应用于分析收敛性问题。由于LWPA 是基于游走、召唤和围攻3 种智能行为的不断重复，每种行为都与当前的群体状态有关，而与之前无关，因此LWPA 的种群序列为Markov 链。设Qk={X1,X2,…,XN}为LWPA 的第k代种群，其中N为人工狼总数，Xi为第i匹人工狼的状态。

定理1 文献[30]已经证明若一个进化算法满足：1）对可行解空间中任意2 点x1和x2，x2是x1由算法中的各种算子产生且是可达的；2）若种群序列Q1,Q2,…,QN是单调的，则此进化算法是以概率1 收敛于问题的全局最优解。

定理2 LWPA 算法以概率1 收敛于问题的全局最优解。

证明：由文献[14]的推理可知LWPA 种群序列的Markov 链也是遍历链，且LWPA 优化序列是一个有限齐次Markov 链，每次迭代狼群个体位置状态只有遇到更优解时才会更新。因此，LWPA 产生的子代Qk+1中的任意解都不差于Qk中的任意解。由此可知种群序列Q1,Q2,…,QN是单调的，于是由定理1 得证，LWPA 以概率1 收敛于问题的全局最优解。

2.5 结果分析

由表2 各种算法的对比结果可知:

1）对于单峰、低维的不可分函数Eason、Matyas, LWPA 与UWPA 都寻优成功且具有较好性能，接近于最优值，就耗时而言，UWPA 的消耗时间是LWPA 的2 倍，IWPA 和WPA 的精度较差。

2）对于多峰、低维的可分函数Booth、Bohachevs1、Eggcrate，LWPA 的收敛精度明显高于其他3 种算法，达到1e-6 以上，耗时方面，LWPA 和UWPA 的耗时最短，IWPA 次之，WPA 耗时最长；

3）对于多峰、低维的不可分函数Schaffer、Six Hump Camel Back、Bohachevs3、Bridge，WPA 与IWPA 由于陷入局部最优而导致寻优失败，LWPA 与UWPA 寻优成功且LWPA 具有更好的寻优性能，同时，LWPA 的耗时最短，明显少于其他3 种算法；

4）对于单峰、高维的不可分函数Trid6，LWPA 与UWPA 寻优成功且性能较好。耗时方面，除WPA 耗时较长外，其他3 种算法耗时相当；

5）对于单峰、高维的可分函数Sumsquares、Sphere，LWPA 与UWPA 寻优成功，LWPA 的寻优精度明显优于其他3 种算法，达到1e-7 以上，但在耗时方面，UWPA 略优于LWPA；

6）对于多峰、高维的可分函数Rastrigin、Quadric，随着维数的递增，只有LWPA 寻优成功且精度较高，LWPA 与UWPA 的耗时都较短；

7）对于多峰、高维的不可分函数Ackley，只有LWPA 寻优成功，耗时也最短。

就时间复杂度而言，由于探狼在游走过程中，探狼采取莱维飞行的随机搜索策略，扩大搜索范围，增加了运行时间。但在对召唤、围攻行为的移动步长进行自适应性改进，当狼群离头狼较远时，以较大步长逼近头狼；当离头狼距离较近时，以较小步长逼近头狼，实现自适应性的灵活调节，使算法更具灵活性，极大缩短运行时间，搜索效率进一步提高。

综上可知，无论是从精度方面还是耗时方面，基于自适应步长和莱维飞行策略的改进狼群算法在处理函数问题时比其他改进的狼群算法更精确、效果更好，尤其是对多峰、高维的复杂函数，效果更佳。UWPA 的效果次之，IWPA 和WPA 较差。由表3 可知，随着Tmax增大，标准差呈现出先减小后增大的趋势。若Tmax值太小，会导致狼群搜索效率降低，耗时较长，找不到最优解；若Tmax值太大，以至于忽略最优解，达不到所需精度。综上，算法中Tmax取10。由表4 可知，随着β增大，标准差呈现先减小后增大趋势。若β太小，狼群更新数量太多，狼群难以聚集，导致算法优化效果降低；但若β太大时，狼群更新的数量太少，导致狼群多样性的急剧下降，并且容易陷入局部最优。综上，算法中β取4。

表4 β 对算法的影响Table 4 Effect of β on the algorithm

为进一步直观说明LWPA 的优越性，图2 给出了LWPA 与 UWPA、IWPA、WPA 在各测试函数中的收敛曲线图。从图中看出，对于单峰、低维的不可分复杂函数，当算法迭代到300 次时，LWPA 已经找到最优值且趋于稳定，而其他3 种算法迭代到400 次时虽也趋于稳定，但精度较差；对于简单的低维函数，UWPA 在前期搜索中效果最好，但随着后期搜索效率不高，导致耗时长且易陷入局部最优；对于复杂函数，LWPA 的收敛精度明显高于其他3 种算法，当维数增加到30 维、60 维、120 维，甚至200 维时，UWPA、IWPA、WPA 3 种算法寻优效果明显较差，出现前期搜索时间较长，后期陷入局部最优的情况。因此，针对算法在后期容易陷入局部最优问题，LWPA 已经有很好改进。比较可知，与其他3 种改进狼群算法相比，在收敛速度还是收敛精度方面，LWPA 的优化性能都有明显提升，说明改进方向的正确性。

图2 15 个测试函数的收敛曲线图Fig. 2 Convergence curves of 15 test functions

3 LWPA 对桁架结构优化实例

3.1 桁架结构优化模型

1）优化模型

以截面积为设计变量的桁架优化模型问题可描述为

式中：gi(x)为约束函数；p为约束个数。

2）目标函数

式中：W(A)为结构的重量；Ai为第i根杆件的截面积；Li为第i根杆件的长度；γ为材料密度；n为设计变量个数。

3）约束条件

各杆必须满足对强度、刚度、稳定性和截面尺寸要求，约束条件如下

式中：σi为第i杆的轴向正应力；[σ]为材料的许用应力；μj为节点j的位移；μmax为节点j的许用位移；Amin、Amax分别为杆件截面的上限、下限。

3.2 算例1

10 杆平面桁架结构见图3，此桁架有6 个节点，10 个设计变量，如表5 所示。优化目标是获得最小的结构总重量。E=68 950 Mpa，ρ=2 768 kg/m3，全部杆件的许用应力为±172.4 MPa，各杆件截面积的下限为0.645 cm2，上限为258 cm2，工况只有一个，在5、6 号节点作用向下载荷P=4.445 KN 的集中力，可动节点向下的位移约束均5.08 cm，图中l=914.4 cm。

图3 10 杆平面桁架结构图Fig. 3 Plane truss structure diagram of 10-bar

3.3 算例2

25 杆空间桁架结构如图4 所示，该结构有10 个节点，25 根杆件。应力约束为[-275.8,275.8］Mpa，材料的密度ρ=2 768 kg/m3，弹性模量E=68 950 Mpa，1、2 节点的最大竖向位移不能超过dmax=0.889 cm，L=63.5 cm。根据对称性，将25 根杆件分成8 组，即设计变量为8 个，如表6-7 所示。

表6 25 杆空间桁架工况荷载Table 6 Load cases of the 25-bar spatial truss structure

图4 25 杆空间桁架结构图Fig. 4 The 25-bar spatial truss structure

3.4 算法迭代曲线对比

算例1 为无约束优化问题，算例2 为含约束优化问题，通过以上2 种经典算例模型进行优化对比，由表5和表7 的优化结果可知改进后算法LWPA 在优化程度和精度方面表现更加良好，达到减轻重量目的；通过图5 的4 种算法迭代曲线，在初始条件相同情况下， LWPA 算法相较于其它算法在迭代初期的迭代速度更快、全局搜索能力更强，以较快迭代速度寻找质量较好的全局最优解，在寻优迭代过程中算法表现稳定，验证了LWPA 有较高收敛速度和精度，具有其独特优越性。

表7 25 杆空间桁架结构优化结果对比Table 7 Comparison of optimal results for the 25-bar spatial truss structure

图5 2 个算例的寻优迭代曲线示意图Fig. 5 The optimization iteration curve of two examples

4 结 论

笔者在基本狼群算法上引入自适应性步长和莱维飞行搜索策略，避免探狼游走过于盲目，使算法能够在搜索后期扩大搜索范围，避免陷入局部收敛，在提高收敛精度的同时能较好提高收敛速度，达到改进目的。通过仿真实验和方法对比，验证了改进狼群算法的可行性、有效性，并将其运用于桁架结构的优化中，优化结果表明改进后的狼群算法达到了预期重量最轻的目的。该方法可用于求解组合优化问题。虽然对算法的改进有一定成效，但实际工程中的问题复杂多变，今后的研究重点是如何将改进的狼群算法解决更加复杂的工程优化问题。