狼群算法的研究与应用综述

刘 聪，费 炜，胡 胜

(湖北工业大学电气与电子工程学院，武汉 430068；湖北太阳能高效利用协同创新中心，武汉 430068)

群智能优化算法通过模拟自然界的规则而演化出的一种新兴的计算技术，已成为越来越多学者关注的焦点。众多群智能优化算法相继问世，如蚁群算法[1]、粒子群算法[2]、细菌觅食算法[3]、人工鱼群算法[4]、萤火虫算法[5]、蝙蝠算法[6]等被成功的应用到各个领域。狼群算法(wolf pack algorithm,WPA)最早由Yang等[7]提出，Liu等[8]在2011年提出了一种新的狼群算法(wolf colony algorithm,WCA)来解决优化问题。WCA模拟了自然界中狼的狩猎方式，抽象出了狼的搜索行为、围攻行为和更新行为这三种智能行为。与粒子群算法和遗传算法相比，WCA具有敏感参数少、鲁棒性强、收敛速度快、精度高等优点。狼群算法因具有相对较好的性能得到了学术界的普遍关注，成为求解非线性优化问题的另一种有效算法，已在路径规划[9-11]、图像处理[12-13]、生产调度[14-15]、电力系统[16-17]、神经网络[18-20]、移动通信[21]、无线传感器网络[22]、云计算[23]等方面取得了较好的应用。

狼群算法在实际应用中存在“早熟”、算法较复杂、参数较多等缺点。进些年来，有很多学者针对其缺点进行了改进，并提出了性能更强的改进型狼群算法。

1 狼群优化算法

1.1 算法原理

狼群具有很森严的等级体系，在捕食猎物时狼群首领会先分配各狼任务而后相互配合行动。假设搜索空间的维数为D，狼群的个体数为n，则第i只狼的位置为

Xi=(Xi1,Xid,…,XiD)，1≤i≤n；1≤d≤D

(1)

1.2 狼群的行为描述

1.2.1 搜索行为

为了增加发现猎物的机会，q匹人工狼被分配到猎物活动范围内进行搜索。假设人工狼的位置为P0,则P0周围的h个搜索位置会被计算从而得出最优搜索位置P1。如果P1比当前的位置P0更好，则人工狼会移动到位置P1，假设猎物活动的范围内共有q匹狼，处于搜索状态的人工狼的最大数量为maxdh,则第i匹处于搜索状态的人工狼的位置为XXi，第j个搜索位置用Yj表示，存在：

Yj=XXi+randn·stepa

(2)

式(2)中:randn是区间[-1,1]服从统一分布的一个随机数；stepa为搜索步长；如果处于搜索状态的人工狼的数量超过maxdh或者当前的搜索位置优于最优搜索位置，则搜索行为结束。

1.2.2 围攻行为

(3)

式(3)中:stepb为围猎步长；k为迭代次数；第d个位置的范围为[Xmind,Xmaxd]。

1.2.3 更新行为

狼群的分配规则是先把食物分配给强壮的狼，然后分配给虚弱的狼，虚弱的狼会因为没有食物而饿死。这样的分配规则可以保证强壮的狼下次能够继续捕食，从而提高狼群的适应性。

1.3 狼群算法的具体步骤

(1) 初始化。初始化个体的数量n,最大迭代数maxk,处于搜索状态的人工狼的数量q,搜索区域h,处于搜索状态的人工狼的最大数量maxdh,搜索步长stepa,围猎步长stepb,位置最差的人工狼的数量m以及第i个人工狼的位置Xi。

(2)搜索行为。选择q个位置最优的人工狼作为搜索状态的人工狼，根据式(2)计算出其位置。

(3)找出围猎范围内处于搜索中的人工狼的最优位置，根据式(3)更新每匹人工狼的位置。

(4)根据人工狼群的分配规则更新狼群，从狼群中移除m个处于最差位置的人工狼，然后随机产生m个人工狼进行补充。

(5)判断是否符合终止条件。如果当前的迭代数达到了最初设立的最大迭代数maxk，则输出最优人工狼的位置，否则返回步骤(2)。

1.4 狼群算法的性能比较

将狼群算法和其他群智能优化算法进行比较，结果如表1所示。

表1 狼群算法和其他算法的比较Table 1 Comparison of wolf pack algorithm and other algorithms

2 狼群算法的改进策略

狼群算法虽然诞生的时间不长，但是其优异的性能使得它在多个领域已经取得不错的应用成果。研究表明群智能仿生算法大多存在“早熟”的问题，而且基本的狼群算法虽然收敛速度快，但是求解精度不高，易陷入局部最优。为了提高狼群算法的性能，众多学者提出了各自的改进策略。

2.1 改进算法规则的狼群算法

2.1.1 具有全新规则的狼群算法

吴虎胜等[24]于2013年提出了全新的狼群算法，该算法将狼群分为头狼、探狼与猛狼这三类狼，并抽象出游走、召唤、围攻这三种智能行为，最后提出了胜者为王的头狼产生规则及强者生存的狼群更新机制。

头狼是狼群中的首领，最具智慧和攻击性，负责指挥整个狼群，能根据同伴获得的信息做出既能尽快捕捉到猎物又能避免陷入危险的决策。探狼是狼群派出的少数精锐，其工作就是寻找猎物，经常出没于猎物的活动区域，根据猎物留下的气味进行搜索，始终向着浓度最强的地方前进来不断逼近猎物。猛狼则是探狼游猎过程中的同伴，一旦探狼发现猎物就会发出嚎叫吸引周围的猛狼过来一同围捕食物。

对捕捉到的猎物根据此次狩猎贡献的大小进行分配，即优先将猎物分配给最先发现，最先捕捉到猎物的狼，而后再分给其他狼。这种淘汰机制能最快选出最凶猛的狼，通过淘汰掉虚弱的狼来保证整个狼群寻找食物的能力。与最基本的WPA相比，文献[24]添加或更改了如下规则和行为。

(1)头狼产生规则。在初始搜索空间中，具有最佳目标函数值的人工狼为头狼，头狼不执行游走、召唤、围攻这三种行为而是直接进入下次迭代中，直到被其他更强的狼替换。

(2)游走行为。探狼向第p个(p=1,2,…,h)方向分别前进一步并记录下当前位置的猎物的气味浓度，然后退回到原位置，则探狼i在d维空间中的位置为

(4)

(3)召唤行为。头狼发现猎物后通过嚎叫吸引猛狼靠近，这就是召唤行为。设猛狼的奔袭步长为stepb,则经过k+1次迭代后，猛狼在d维搜索空间的位置为

(5)

(4)强者生存的更新机制。这是猎物分配的规则，表现力强的狼优先获得食物，表现差的狼则没有食物。保留狼群中表现力强的狼，淘汰表现较差的狼，然后随机补充一定数量的人工狼。

该算法和最基本的WPA相比有较好的全局收敛性和计算鲁棒性，在高纬度的复杂函数求解中表现出色。狼群捕猎模型如图1所示。

图1 狼群捕猎模型Fig.1 Wolf hunting model

2.1.2 基于领导者的狼群算法

文献[25]提出了基于领导者策略的狼群算法。狼群中的领导狼即头狼是不断变化的，每次捕食分配过后都会根据更新机制在最为凶猛的几只狼中产生新的领导者。在捕食过程中，其他狼会向着领导狼的位置靠近，当有狼发现猎物时会通过嚎叫吸引其他狼靠近，然后在领导狼的指挥下围攻猎物。与最基本的WPA相比，改进的核心内容如下。

(1)领导狼的更替。在人工狼群中选取最优的q匹狼作为领导狼的竞争者，这q匹狼在h个方向进行搜索，如果竞争狼当前的位置为P0，P1是P0附近的一个位置且优于P0,则竞争狼会向P1方向移动，在整个搜索行为结束后，选出最优位置的那匹狼作为领导狼替换掉以前的领导狼。

(2)向领导狼方向移动。在搜索猎物的过程中，其他狼会向着领导狼的方向移动，若某狼发现猎物但是其所处的位置是远离领导狼的，则该狼停止此次搜索行为。设第i只狼在d维搜索空间中的位置为

zid=xid+rand·stepb(xid-xld)

(6)

式(6)中:rand为区间[-1,1]中的一个随机数；xid为第i只狼的位置；xld为领导狼的位置。

该算法在求解精度和收敛速度上相比最基本的WPA有一定的提高，其不容易陷入局部最优。

2.1.3 基于改进搜索策略的狼群算法

李国亮等[26]在文献[24]的基础上，改进了游走行为和召唤行为，提出了一种游走与召唤相交互的搜索策略，增加了狼群之间的信息交流，此外还提出了一种自适应的围攻策略。其改进的核心内容如下。

(1)交互游走行为。借鉴文献[27]中提出的搜索方式，从而提出了人工狼的交互游走行为，如式(7)所示：

(7)

式(7)中:φi,d为[0,1]的随机数；Φi,d为[-1,1]的随机数。

(2)交互召唤行为。猛狼在执行一次普通召唤行为后，接着执行交互游走行为。

(3)自适应围攻行为。将随机步长λ改成了随着迭代次数t值的增加进行线性变化的自适应步长，如式(8)所示:

(8)

式(8)中:ε为因子系数，大小为(0,1)内的一个随机数；v为[-1,1]内的一个随机整数。

交互游走行为既加强了人工狼的局部搜索能力，又提高了狼群的全局搜索能力。交互召唤行为则加快了算法的收敛速度和求解精度。自适应围攻行为则提高了猛狼的局部寻优能力。

2.1.4 基于其他改进规则的狼群算法

文献[28]也提出了探狼更新规则，通过引入相位因子来改善探狼的搜索灵活性，同时又提出了围攻半径的思想来跳出局部最优，使算法的精度更高。文献[29]将自适应惯性权重、自适应步长以及自适应视野引入到基本狼群算法中形成了改进的狼群算法，提高了算法的收敛速度和求解精度。文献[30]改进了游走行为、召唤行为、围攻行为的移动步长，特别是当游走行为的试探方向改进后，每头狼都能根据头狼位置的变化自动调节移动步长、更换游走方向，从而简化参数设定，提高了算法的收敛速度和求解精度。

2.2 混合狼群算法

混合狼群算法就是将狼群算法和其他优化算法(如遗传算法、差分进化算法、粒子群算法等)相结合形成一种混合式算法。混合狼群算法通过利用其他算法的优势来弥补狼群算法本身的性能不足，达到快速解决工程实际问题的目的。

针对狼群算法易陷入局部最优解，收敛速度慢的缺陷，孙闵红等[31]提出了一种将差分进化算法(DE)和狼群算法相结合的混合算法。该算法利用差分进化算法的变异、交叉和选择等步骤来实现跳出局部最优化，提高全局搜索能力的目的从而提高算法的精度。该算法的流程如图2所示。

Yi为猛狼感知到的猎物的气味浓度；Ylead为头狼感知到的猎物的气味的浓度；T为游走次数；Tmax为最大游走次数；dis为猛狼i继续奔袭直到与头狼s间的距离；dnear为判定距离图2 DE-WPA算法流程Fig.2 DE-WPA algorithm flow

随后将该混合算法应用于卫星导航欺骗干扰系统，仿真实验结果验证了该算法的优越性。

文献[32]将Nelder-Mead 算子引入狼群算法中，提出了一种新的混合狼群算法。使用Nelder-Mead 方法的好处在于能够利用群体信息和个体记忆来指导每匹狼能够搜寻到猎物，从而提高了算法的全局搜索能力。在位置x(t)的狼向位置P(t)靠近的公式变更为式(9):

x(t+1)=x(t)+β(r)[P(t)-x(t)]+rand()

(9)

该算法对六个基准函数进行测试，实验结果表明该算法求解精度比其他几种优化算法更高，鲁棒性更强。

曹爽等[33]受粒子群算法(PSO)的启发，将PSO中的思想引入狼群算法的游走和召唤行为中来提高局部搜索精度，采用很多学者提到的自适应化围攻行为来加快收敛速度，最后利用混沌方法对次优解进一步优化，避免陷入局部最优。如式(10)、式(11)用来描述引入PSO思想后的交互游走策略。

(10)

(11)

式中：l为当前的迭代数；c1、c2为加速度因子，是非负数；r1、r2为[0,1]的随机数，用来保证狼群的多样性。

交互召唤行为则是猛狼在执行一次召唤奔袭行为后接着执行交互游走行为，即式(10)、式(11)描述的过程。

文献[34]针对经典的0-1背包问题，将量子行为引入到狼群算法中，提出了量子狼群算法。参照量子编码的方式，定义了种群中粒子的概率位置和准确位置，然后通过量子旋转门控制人工狼概率位置向全局最好位置逼近，接着以量子塌缩实现了概率位置向准确位置的映射，该算法同时兼顾了算法的导向性与随机性。实验结果表明该算法在求解高纬度0-1背包问题时有良好的表现。

文献[35]将禁忌搜索方法与狼群算法相融合，提出了一种基于禁忌搜索机制的狼群算法。论述了历史次优解的概念，通过历史次优解来帮助跳出局部最优，该算法在收敛速度和求解精度上相对于其他算法有很大的提升。

2.3 基于Levy飞行和混沌优化方法的狼群算法

狼群算法在初始化过程中存在很大的随机性，会导致初始种群分布不均匀，降低了算法的性能。为了弥补这一缺陷，文献[36]提出了一种基于Tent混沌映射与Levy飞行的改进狼群算法。应用Tent混沌映射策略来提高种群个体的质量从而消除种群分布不均的影响。针对围攻行为存在收敛过快的问题，加入Levy飞行策略来帮助跳出局部最优。

2.3.1 基于改进Tent混沌映射的种群初始化

Tent映射又称帐篷映射，是一种分段式的线性映射函数。Tent映射结构较简单，映射结果的分布密度比较均匀，具有较好的遍历性。其表达式如式(12)所示：

(12)

Tent映射虽然具有较好的遍历性，映射分布比较均匀，但是仍存在一小部分区间内比较稀疏的现象，因此作者对其进行改进，改进后的Tent映射如式(13)所示：

(13)

用改进后的Tent混沌映射产生的序列值代替狼群初始化公式产生的随机变量，可以使得种群个体在解空间中的取值趋向均匀。

2.3.2 基于Levy飞行的围攻行为

Levy飞行搜索是指动物在很长一段时间里在某个短距离的范围内来回搜索，偶尔伴有长距离的搜索，这两种搜素轨迹相互穿插交织在一起。研究表明，在一个较大空间和有限个搜索者的环境内，Levy搜索策略是一种效果较好的搜索策略。Levy飞行的运动轨迹的长度是随机变化的，其没有固定的分布函数。Levy飞行的步长变化分布密度函数L(s)为

L(s)～|s|-1-β

(14)

(15)

(16)

将Levy飞行产生的随机步长作为围攻行为的步长，并以当前种群最优解Pbest(t)作为目标索引值，则有:

Pi,d(t+1)=Pbest(t)+rands|Pbest(t)-Pi,d(t)|

(17)

式(17)中:s为Levy飞行产生的随机步长。

通过对六个复杂标准函数进行测试，表明文献[36]提出的一种基于Tent混沌映射与Levy飞行的改进狼群算法具有较快的收敛速度和较高的求解精度。

2.4 基于多种群的协同进化狼群算法

文献[37]为了增强狼群个体中彼此的信息沟通能力，提出了一种基于混沌小生境的狼群算法。利用混沌小生境技术将狼群分为多个子狼群，每匹人工狼由混沌映射产生，这样可以避免各个子狼群中头狼的相互干扰，消除单一头狼引起的“早熟”现象。

2.5 基于离散空间的狼群算法

文献[38]通过定义反转算子，对人丁狼的位置和智能行为重新进行整数编码设计，并结合概率近邻初始化方法，提出了一种求解旅行商问题的离散狼群算法。旅行商问题(traveling salesman problem,TSP)问题属于非确定性多项式(nondeterministic polynomially,NP)难题，是评价离散空间寻优性能的有效准则。该算法和其他5种智能优化算法相比，在求解精度，计算鲁棒性等方面有一定提高。

文献[39]则针对NP难题中的又一经典问题——多选择背包问题，提出了一种基于离散空间的狼群算法。与文献[22]的思路类似，文献[39]也是将人工狼先进行编码，而后重新定义狼群的游走、奔袭和围攻行为以及其步长，最后将学习机制引入离散狼群算法中。该离散狼群算法成功实现了对离散问题的求解。

2.6 基于多目标优化的狼群算法

马龙等[40]针对多目标0-1规划问题,提出了一种元胞狼群优化算法。该算法将元胞自动机中的元胞、邻居元胞与狼群算法的局部空间搜索相组合，成功实现了对多目标优化问题的求解。综上所述，狼群算法的改进策略如表2所示。

表2 狼群算法的改进策略Table 2 Improved strategy of the wolf pack algorithm

3 狼群算法的应用

狼群算法是一种比较新的群智能优化算法，自问世以来就获得了学者们的广泛关注。目前，许多外文文献主要是基于工程实践的研究，描述纯算法理论的研究文章较少。狼群算法的应用范围宽广，如路径规划、图像处理、生产调度、电力系统、人工智能等方面，但技术尚不成熟，相关研究文献相对较少。

3.1 路径优化

无人机(UAV)是近年来研究的热点。路径规划器是无人机自主控制模块的关键部件。文献[41]将改进的狼群算法用于计算旋翼无人机在包括真假三维空间在内的复杂三维空间中的准最优轨迹。实验结果表明，在相同条件下改进后的狼群算法产生的轨迹远优于基本算法、遗传算法和禁忌搜索方法。文献[42]通过建立自主水下航行器约束条件下的水下环境威胁模型，提出了一种基于改进的狼群算法的dubins路径规划方法。仿真结果表明，改进后的狼群算法在高精度、高维、多峰函数中具有较高的收敛速度和良好的局部搜索能力，也不会过早地收敛。

3.2 PID控制

文献[43]提出了一种改进的狼群算法，用于PID控制器的参数搜索，实验表明该算法具有较好的收敛性和鲁棒性。文献[44]运用狼群算法来解决自抗扰控制器的参数优化问题，将其应用到机器人的手眼协调控制系统中，通过仿真实验证明了算法的有效性。

3.3 图像处理

分形图像压缩是近年来发展起来的一种自然图像编码工具。文献[45]将狼群算法用于分形图像压缩的研究。结果表明，与穷举搜索方法相比，该方法大大缩短了编码时间，获得了较好的压缩比。文献[46]为了提高图像分割的准确性和分割速度，利用狼群算法来优化Snake模型中的能量函数。仿真结果表明该优化方法在图像分割的准确性和分割速度上有一定的提高。

3.4 工业生产与调度

文献[47]探讨了水电站的优化运行问题，改进了狼群算法的围攻行为从而提出了一种改进的狼群算法用于水电站优化调度。仿真结果表明，改进的狼群算法是优化水电站运行的一种新的有效方法。文献[48]将改进的狼群算法应用于JTangFlow工作流管理系统中，取得了良好的效果。工作流管理系统(WFMS)方便了业务流程的日常操作，近年来得到了广泛的应用。文献[49]提出了一种改进的狼群算法，对物流配送中心选址问题进行了实验研究。通过与其他智能算法的仿真实验对比，证明了该方法的有效性和可行性。文献[50]将狼群算法应用到单位线优化率定中，提出了一种单位线自动优化率定的新方法。用同倍比修正法来处理水量平衡约束;采用具有动态罚因子的罚函数法处理单位线的不合理波动。实验结果证明了提出的单位线自动优化率定的狼群算法的有效性。文献[51]运用基于领导者策略的狼群算法对北方某河流水质进行了综合评价，为地方政府治理河水污染等方面提供了科学依据。

3.5 电力系统

文献[52]提出了一种锂离子电池充电控制策略，将狼群算法应用于充电过程中，寻找最优充电电流。利用这种仿生算法，节省充电过程中的冗余能量，同时更有效地控制充电过程，减少时间和成本。文献[53]将改进的人工狼群算法用于局部阴影条件下最大功率点的跟踪。与人工蜂群算法(ABC)和粒子群优化算法(PSO)进行比较，表明了该算法的优越性。文献[54]将多特征狼群优化算法和模糊C-均值无监督聚类相结合应用于电机的故障检测，通过实验结果的比较，验证了该算法的优越性。

3.6 神经网络

文献[55]提出了一种基于神经网络的狼群优化协同频谱感知算法。该算法以自组织神经网络协同频谱感知算法为基础，阐述了训练样本的生成和训练神经网络。并利用狼群优化方法对神经网络训练后的权值矩阵进行优化。仿真结果表明，基于狼群优化自组织神经网络的频谱感知算法具有较好的性能。文献[56]基于小波神经网络,将狼群算法与改进的梯度下降算法相结合,用于短时交通流预测。仿真结果表明提出的方法在短时交通流预测在稳定性和精度上都具有良好的性能。文献[57]针对当下笔迹鉴定识别率低、速度慢的问题，提出了一种结合概率神经网络和狼群算法的混合算法。实验结果表明用该方法进行笔迹的鉴定可以提高识别率和识别速度。

3.7 网络通信

文献[58]针对Web服务组合问题，提出了一种改进的狼群算法。实验结果表明，改进的狼群算法跟传统的优化算法相比在效率和性能上有一定的提高。文献[59]研究了球形译码算法的优化问题，首先讨论了初始搜索半径对球形译码过程的影响，然后使用狼群算法来寻找优初始搜索路径。仿真结果表明，基于狼群算法的球形译码算法能有效降低球形译码算法的计算复杂度。文献[60]探讨了光纤陀螺仪的随机漂移误差对导航系统精度的影响，采用狼群算法来优化陀螺随机漂移模型，使其更加精确，实验结果表明相对于传统的时间序列分析法，利用狼群方法进行优化的方案在精度上有很大提高。

4 结论与展望

虽然狼群算法在解决复杂优化问题上相较于其他仿生智能算法有很多优势，但该算法在解决实际问题的过程中也暴露出许多不足。因此，狼群算法未来的研究工作可以从以下方面展开。

(1) 对参数较敏感，参数值的设置容易影响狼群算法的性能。如何根据不同的问题，正确设置各个参数值的大小或自适应设置参数值的大小，从而使参数值设置不理想的情况最小化，影响狼群算法的性能。

(2) 后期收敛速度明显下降，归咎于猛狼发起的低效率围攻行为，围攻强度的大小体现了狼的局部搜索能力，如何平衡或加强狼群算法的全局搜索能力和局部搜索能力，进一步提高狼群算法的搜索效率，将是以后研究的重点之一。

(3) 狼群算法作为一种仿生智能算法，具有明显的生物社会特征和相对较弱的数学支持，需要深入的理论分析和数学证明。

狼群算法作为一种比较新的自然启发式群智能优化算法，具有较强的全局和局部搜索能力、较高的种群多样性和较强的鲁棒性等优点，因此被广泛应用于工程实践和解决生活实际问题。首先系统的阐述了狼群算法的基本原理，然后归纳了狼群算法的优缺点及改进策略，接着列举了热门的应用领域，最后对狼群算法的未来研究进行了展望。狼群算法从提出到现在不足十年时间，算法本身在不断改进和发展，其理论研究和工程应用有了很大进展，理论研究在逐渐走向成熟。