一种具有动态适应性的狼群算法及其应用

余泽泰 余盟 肖人彬 钟卫卫 王玉梅

摘要 为了提高狼群算法的适应能力，使其能在复杂环境下具有较高的寻优精度与速度，提出一种具有动态适应性的狼群算法。首先，提出一种动态分群算法，增强狼群算法的全局适应性;其次，定义一种差异度拟熵，构造自适应步长，提高算法在复杂环境下的精度与收敛速度;使用随机游走环节，增强算法的适应性，缩短计算耗时。在17种测试函数上与其他几种算法进行对比，显示所提出算法具有较好的精度与收敛速度。在三维无人机航线规划问题上验证了该算法的有效性与实用性。

关 键 词 狼群算法;动态适应性;分群;差异度拟熵

中图分类号 TP18     文献标志码 A

Dynamical adaptive wolf pack algorithm and its application

YU Zetai， YU Meng， XIAO Renbin， ZHONG Weiwei， WANG Yumei

（Artificial Intelligence and Automation， Huazhong University of Science and Technology， Wuhan， Hubei 430074， China）

Abstract In order to improve the adaptability of the wolf pack algorithm， and provide it with good performance of search accuracy and speed under complex environment， a dynamical adaptive wolf pack algorithm （DAWPA） is proposed. Firstly， a dynamic clustering algorithm is proposed to enhance the global adaptability. Secondly， a difference pseudo entropy is defined to construct self-adaptive variable step-size， which improves the search accuracy and convergence speed. Random scout method is used to enhance the adaptability and shorten the computing time. Then， DAWPA is applied on 17 benchmarks. Compared with several other algorithms， DAWPA has shown better performance on accuracy and speed. Finally， application of DAWPA on 3D UAV route planning problem has demonstrated its validation and utility.

Key words wolf pack algorithm; dynamical adaptability; clustering; difference pseudo entropy

群智能優化算法是通过模拟自然界中生物种群的行为方式，来求解复杂优化问题的智能算法。相比于传统的优化算法，群智能优化算法在解决一部分NP难问题上展现了良好的效果，得到了大量研究，在解决优化问题上得到了广泛应用。

国内外学者已经提出了多种群智能算法，如粒子群算法（Particle Swarm Optimization， PSO）和人工蜂群算法（Artificial Bee Colony， ABC）。这两种算法得到广泛应用，在优化中展现了独特的优势[1]。然而，面对复杂问题时，它们出现了较严重的早熟现象[2-3]。

为了解决复杂情况下的寻优问题，在狼群捕猎方式的启发下，吴虎胜等[4]提出了一种新的群智能优化算法——狼群算法（Wolf Pack Algorithm， WPA），并基于马尔科夫链证明了该算法的收敛性。由于WPA具有较好的全局搜索能力，自提出就引起国内外学者关注，并被应用于生产调度、图像处理、路径规划、云计算等问题[5]，在高维问题上具有较好的收敛与鲁棒性[6]。同时，针对一些特殊的问题，一系列衍生的应用算法也被开发出来。例如，应用于0-1背包问题的二进制狼群算法（BWPA）[7];应用于TSP问题的离散狼群算法（DWPA）[8];应用于多目标0-1规划问题的元胞狼群算法[9];应用于模糊双层背包问题的改进二进制狼群算法（IBWPA）[10]等。此外，结合BWPA与柔性种群更新策略的柔性二进制狼群算法（FWPA）被应用于解决一系列静态多维背包问题，展现了优秀的性能[11]。

WPA对高维复杂函数的寻优效果较好，可以有效避免早熟现象。然而，基本狼群算法还存在一些不足。面对问题特征较复杂，如当优化目标为兼具高维、耦合特征、多峰等复杂性质的场景，如具有复杂环境的水下三维路径规划问题、高维度多约束的水电站厂内优化运行问题[12-13]，基本狼群算法的适应能力不够强，较易早熟，因此影响了收敛速度与寻优精度[14]，出现了收敛速度慢、求解精度不够高和容易陷入局部最优等问题。为了提高其适应性，文献[15]通过引入精英集策略（Elite Set Strategy）和差分进化改进了WPA的初始解生成方式，提高了面对不同优化问题时的适应能力。文献[6]给出了基于对立学习的初始解优化方案，提出了对立狼群算法（OWPA），既提高了正常情况下狼群算法的局部搜索能力，又提高了复杂情况下种群分布的多样性，具有更好的鲁棒性。文献[16]使用Tent混沌映射初始化狼群，在围攻过程中加入levy飞行方法，提出了一种混沌狼群围捕算法，提高了算法的实时性。文献[17]将混沌理论和反向学习结合起来实现狼群算法的优化，通过优化初始解的方式，提高了面对复杂问题时的全局自适应性。文献[18]基于适应度将狼群分为子群，提出了自适应狼群分组策略，使狼群算法在复杂环境下具有更好的适应能力。针对原始狼群算法游走步长与围攻步长固定、缺乏局部自适应能力的问题，出现了多种基于迭代次数[19]、欧氏距离[20-21]、适应度函数[22]的自适应步长狼群算法，且得到了较充分的研究。文献[23]使用基于迭代次数的自适应围攻步长，将PSO算法中求解当前局部最优的思想引入到游走、召唤行为中，提出一种改进狼群算法，并将其运用于Otsu图像分割中，提高了分割精度且缩短了分割时间。文献[24]在游走行为中加入随机扰动算子，借鉴模拟退火方法改进了围攻过程，提高了算法的全局搜索能力。文献[25]在基本狼群算法的基础上，增加了二次游走与人工狼变异的环节，在应用问题上获得了较高精度。

本文在以往研究的基础上，提出一种具有动态适应性的狼群算法（Dynamical Adaptive Wolf Pack Algorithm， DAWPA）。在狼群的群体分工上，通过使用一种动态分群算法，根据环境与狼群分布动态调整子群数量，使算法的全局搜索更充分。在围攻环节中，定义一种差异度拟熵，构造自适应的围攻步长。对游走环节，使用随机游走策略代替贪婪策略，从而增强算法的适应性。使用17种测试函数，通过与其他6种群体智能算法进行对比，显示DAWPA具有较好的收敛精度与速度。最后，将DAWPA算法应用到复杂三维环境的无人机航路规划问题上，验证了该算法的有效性与实用性。

1 基本狼群算法

狼群算法（WPA）通過模拟狼群捕食行为及其猎物分配方式，抽象出游走、召唤、围攻3种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制。其中，游走行为对应于探狼的贪婪搜索，在游走方向中挑选猎物气味最浓的方向前进。探狼的位置更新规则如下式：

[xpid=xid+sin2π×p/h×stepa]， （1）

式中：[xid]为探狼i在第d维的当前位置; [xpid]为探狼i向第p个方向前进后在第d维所处的位置;h为最大前进方向;[stepa]为游走步长。

召唤行为是头狼发起召唤，人工狼向头狼靠近的过程，人工狼的位置更新方式遵从以下公式：

[xi′=xi+stepb?xlead-xi/xlead-xi]， （2）

式中：[xi]为人工狼i更新前的位置;[xlead]为头狼位置;[stepb]为围攻步长;[xi′]为人工狼i更新后的位置。当人工狼与头狼距离小于给定阈值时，人工狼以头狼位置作为猎物位置，向其发起围攻。每次人工狼的位置发生变动后，若适应度高于头狼，位置更新的人工狼将会成为新的头狼。通过人工狼与头狼之间的互动，不断更新狼群的位置，从而逼近最优解。围攻行为根据下式调整人工狼位置：

[xi′=xi+λ?stepc?xlead-xi]， （3）

式中：[λ]为[-1，1]之间均匀分布的随机数;[stepc]为人工狼的围攻步长。

模拟自然界弱肉强食的环境，WPA设置了淘汰弱者的狼群更新机制，并随机生成新的人工狼进行补充，以保持狼群数量的稳定。

2 具有动态适应性的狼群算法

为了提高基本狼群算法的适应能力，DAWPA首先对狼群群体的分工方式进行调整。WPA采取单一头狼产生规则，当应用环境复杂时，单头狼模式难以有效搜索多个局部最优解。文献[18]采取的分群方法，虽然增强了算法的适应性，但该算法仅根据适应度进行分群，没有考虑狼群在解空间中的分布情况。为了使子群的划分合理，除了以适应度的大小挑选子群头狼外，还需根据头狼间的距离进行筛选，使分群后子群间距离最大化。此外，还需根据环境不同与狼群分布的变化，动态调整子群划分，以提高算法的动态适应性。

在基本狼群算法中，围攻行为的步长是固定值，不具有自适应能力。在局部开发上，自适应步长可以增强算法局部的自适应能力。目前，有基于算法迭代次数与以欧式距离为参数的自适应步长方法。基于迭代次数的自适应步长具有动态的自适应能力，随着迭代次数的增加，步长逐渐减小。但该方法不具有环境自适应性，对于不同的解空间情况采取的是相同的步长大小，削弱了算法的适应能力。以欧式距离为参数的自适应步长在特征可分时具有环境自适应性，但在实际应用中，问题特征的各个维度之间存在相关性时，欧氏距离就不再适用。

为了增加自适应步长的适用范围，必须使用一种能处理耦合特征的步长调节参数。围攻过程反映了头狼将猎物信息传递给人工狼，细化指导其捕猎的过程，可以考虑用熵对头狼与人工狼之间的信息差进行衡量，随信息差的减小而逐渐减小围攻步长。然而，Shannon定义的熵不能衡量序列信息。因此，DAWPA设计了一种差异度拟熵，其具有区分序列的能力。通过对头狼和人工狼的差异度进行拟熵计算，衡量其信息差，进而构造出自适应步长。

最后，为了增强算法的全局搜索能力，DAWPA对WPA的游走策略进行了调整。WPA的游走环节采取的是贪婪策略，探狼向猎物气味浓度最高的方向前进。为了增强算法避开局部最优的能力，DAWPA使用随机游走环节以增强其随机性，当应用环境的适应度函数计算复杂时，可以有效提高算法的全局搜索能力。

2.1 动态分群策略

在自然界中，狼群具有领域性。在环境复杂的情况下，分布较广的狼群往往会被环境分割成数个子群。被环境分隔的每个狼群的活动范围较为固定，且遵循各自头狼的领导。模拟自然界中狼群的领域性，针对复杂的解空间环境，提出如下的动态分群策略。

Step 1：完成狼群的初始化后，设狼群中共有m只狼，计算m只狼对应的适应度，取适应度最高的个体作为子群1的头狼。为了获得子群的头狼，取适应度前5%的狼个体组成头狼候选集。除了考虑适应度外，新的子群头狼应与原来的各个头狼具有较远的距离，使各子群对解空间的探索更充分。由于各个头狼之间距离之和随头狼数量增加而增加，因此选取新头狼的距离阈值应与头狼数量有关。具体来说，从头狼候选集中选取满足的人工狼，将其作为新子群的头狼。

[i=1udi≥23udmax]， （4）

式中：u为现有子群数;[di] 指当前人工狼与现有的第i个子群头狼的欧式距离;[dmax]指子群1的头狼到解空间边界距离的最大值，代表了解空间中相对大的距离，从而可以将其作为距离阈值。

Step 2：由式（4）可以获得u个子群头狼，使用kmeans聚类方法，将m只狼划分为u个子群。

Step 3：对u个子群的人工狼分别进行游走、召唤、围攻操作。

Step 4：对Tmax次迭代的狼群算法，则在寻优过程中间隔Tmax/10次迭代完成一次“分裂-合并”的子群动态调整。

a）子群分裂：将每个子群适应度仅次于头狼的人工狼作为头狼候选集，选取满足式（4）的人工狼作为新子群的头狼。

b）子群合并：对每个子群计算距离[di]，若其不满足式（4），则将其与距离最近的子群合并。合并的子群头狼为原有两个子群中适应度大的头狼。

Step 5：完成“分裂-合并”操作后，重新使用kmeans算法进行聚类操作。

在简单问题中，狼群间的适应度与在解空间中的分布差异不大，狼群不会被划分为多个子群，整个狼群一起进行捕猎。而在复杂问题中，问题的解空间环境往往呈现出高维、多峰的性质，求解过程中可能出现多个接近的局部最优解，动态分群策略将会根据狼群自身的适应度与分布情况，动态地调整子群的数量，各个子群可以同时探索多个局部最优解。基本狼群算法只有单头狼，所有的人工狼都接受其指导，向唯一的局部最优解方向探索;DAWPA采取的动态分群策略，不固定子群的数量与范围，随着实际问题与当前状态的变化进行不同的分群，使狼群算法具有了动态的适应能力。

2.2 基于差异度拟熵的自适应围攻行为

设两头人工狼的位置向量分别为a， b，则它们的差异度向量定义为：

d={di}={ai-bi}， i=1，…，n.

借鉴文献[26]定义的拟熵（pseudo entropy），定义一种差异度拟熵如下：

定义1

[PE=-k=1ndkpke1-pk]， （5）

式中， [pk0≤pk≤1] 为k在[dk]中的频率。式（5）定义的差异度拟熵随两个个体之间相对信息差的减小而增大，当两个个体完全一致，即信息差为0时，差异度拟熵取得最大值为0。

差异度拟熵将差异度向量作为系统，通过衡量差异度的混乱程度，聚合了原个体向量间各个维度的综合信息，从而可以将其作为自适应步长的控制参数，构建自适应的围攻行为。

[xi′=xi+λ×stepc×xlead-xi]， （6）

式中：[stepc=21+ePE-1];[λ]为[-1，1]之间的随机数。使用sigmoid函数可以使步长调节更为平滑，同时将差异度拟熵映射为[0，1]的步长。

通过式（6），以差异度拟熵为参数进行自适应步长控制，可以将头狼和人工狼各个维度的信息差进行有效聚合，使人工狼更可能找到最优解。由于差异度拟熵统计了差异度向量的元素，反馈的控制参数不易受到特征维度与特征关系的影响，因此在高维、特征存在耦合的情况下精度更高。

2.3 游走环节的随机化

在基本狼群算法的游走过程中，探狼分别向h个方向游走，选择气味最浓的方向前进。这意味着游走过程中需要计算m×h次人工狼的适应度。在实际应用问题中，多次适应度函数的计算使游走环节耗時巨大。游走行为本质上是一种随机搜索过程，是狼群算法跳出局部最优解的重要环节。由于探狼主要由上一次迭代过程中向头狼发起围攻的人工狼组成，距离头狼较近，选择适应度最高的方向游走，探狼将继续靠近头狼，导致狼群进一步陷入局部最优解。因此，为了使算法跳出局部最优解，设置随机游走环节，人工狼按照下式更新位置：

[xi′=xi+sin2π×randi1，hh×stepa] （7）

式中，[randi1，h] 指从1到h之间的一个随机整数。该游走行为代表在h个方向中随机选取一个方向前进。在随机游走中，不进行适应度的计算，这意味着在游走过程中不进行头狼替换的操作，保留原有头狼进入召唤过程。

随机游走策略在一段时间内保留了原有头狼的指导，避免反复更换头狼而带来搜索不彻底的问题，使人工狼对解空间的探索更充分，避开了局部最优，因此具有提高全局搜索的适应性的效果。同时也大大减少了适应度计算的耗时，加快了算法的效率。

2.4 综合效果分析

上节分别介绍了DAWPA所使用的3种技术的作用。在DAWPA的寻优过程中，3种技术之间相互作用，其效果互相影响，弥补了部分缺点，增强了算法效果。所提出技术对算法性能的作用如图2所示。其中，红色实线代表正面效应，绿色虚线代表负面效应。

动态分群策略强了算法的全局搜索能力，通过将狼群根据环境划分为子群，提高了种群分布的多样性进而增加了覆盖全局最优解的概率，但其精确度不足。

在进行粗略的全局搜索后，围攻过程可以扫描邻近区域，提高算法精度。自适应的围攻进一步增强了复杂函数环境下的寻优精度。然而，自适应步长的引入增加了计算耗时。

随机游走环节替代了WPA的贪婪游走，减少了重复计算适应度函数与头狼更新的过程，避免狼群因过于频繁地更换头狼导致搜索不充分。此外，随机游走环节显著减少了计算耗时，抵消了自适应围攻的负面效应。

3 DAWPA实现与性能测试

3.1 DAWPA流程

DAWPA的流程图如图3所示，其算法步骤如下。

Step 1： 狼群初始化。在解空间中随机初始化狼群的空间坐标，计算适应度获得子群1的头狼。

Step 2： 动态分群环节。根据适应度获得头狼候选集，根据式（4）选出子群头狼，使用kmeans算法分群。

Step 3： 随机游走环节。根据式（7），令人工狼进行随机游走，更新其坐标。

Step 4： 各子群的召唤行为。对不同的子群分别进行围攻，各子群的人工狼分别向各自的头狼靠近，若人工狼适应度大于头狼，则其成为新的头狼。人工狼的位置更新如下式：

[xki′=xki+λbxklead-xki ，]                       （8）

式中：[xki]為第k子群的第i只人工狼; [xki′]为其经过召唤行为后的位置;[λb]为固定召唤步长;[xklead]为第k子群的头狼。

Step 5： 基于差异度拟熵的自适应围攻过程。对于每个子群的每只狼，根据式（6）可计算出自适应的围攻步长，向猎物发起围攻。

Step 6： 子群种群更新。对种群中适应度差的个体进行淘汰，并产生等量的随机新个体。

Step 7： 群体的“分裂-合并”行为。在一定的间隔下，在各子群内部挑选头狼候选，进行分裂;对子群头狼之间的距离进行计算，根据结果进行合并。

Step 8： 重复过程3-7，直至到达最大迭代次数或算法精度满足阈值。

为了更好地解释DAWPA算法流程，提供其伪代码如下。

Algorithm 1. Pseudo code of DAWPA

Input： the parameters of DAWPA including population size n， step coefficient S， distance determinant coefficient dnear.

Output： the best objective value.

1. Generate initial population of wolves Xi = {xi1， xi2， …， xij， …， xin}

2. Evaluate the fitness of whole population o and select the initial lead wolf Ylead = max{Yi}

3. Clustering method

4. Select wolves with top 5% fitness as leader wolf candidates

5. group_number：=1

6. for candidates i=1;i

7.  if candidate i satisfies Eq. （4） then

8.   group_number++

9.  endif

10. end for

11. Generate subgroups using k-means（group_number）

12. Set iteration counter for initial population g：=0

13. while g

14.  for i=1;i

15.   Scouting behavior

16.   Takes a step towards direction p as in Eq. （7） and update positions of subgroup i

17.   Summoning behavior

18.   if Yij > Yi_lead then

19.    renew lead wolf i and restart the summoning behavior

20.   else if Yi ≤ Ylead & dis ≤ dnear then/*dis is the distance between Xlead and Xi*/

21.    wolves from subgroup i move to lead wolf i with the moving operator

22.   else

23.    update their positions as in Eq. （8）

24.   endif

25.   Besieging behavior

22.   if Yi > Ylead then

23.    renew the lead wolf

24.   else if Yi ≤ Ylead

25.    wolves move to the lead wolf with the moving operator

26.   else

27.    update their positions as in Eq. （6）

28.   endif

29.  end for

30.  Split and Merge

31.  for i=1;i

32.   if wolf x2 satisfy Eq. （4） then/*x2 refers the wolf that has second highest fitness in subgroup i*/

33.    divide group i to 2 subgroups using k-means method

33.   endif

34.  end for

35.  for i=1;i

36.   if xilead does not satisfy Eq. （4） then

37.    subgroup i merges with the nearest subgroup

38.   endif

39.  end for

40.  g++

41.  Restart the scouting， summoning and besieging behaviors

42. end while

3.2 测试函数与参数设置

3.2.1 测试函数

参考文献[27-28]，将DAWPA在17个测试函数上进行10次重复测试。选取的测试函数包含了近年来研究中常用的单峰、多峰、可分、不可分、不同维度等多种类型的函数，以测试算法在多种环境下的表现情况差异[29-32]。

函数与特性如表1所示，U（unimodal）表示单峰函数，M（multimodal）表示多峰函数，S为可分（separable），N为不可分（non-separable）。单峰为在定义域内无局部极值，只有全局最优值的函数;多峰为有多个局部极值的函数，一般的算法较易陷入局部最优值，因此可以用来检验算法的全局搜索和避免過早收敛的能力;含有N维自变量且能表示为N个单变量函数之和的函数为可分函数;反之则为不可分函数。

3.2.2 比较算法及参数设置

本文使用人工蜂群算法（ABC）[33]、布谷鸟搜索算法[34]与4种改进狼群算法进行比较。3种狼群算法分别为基于欧氏距离的自适应改进狼群算法（IWPA）[21]、引入趋向游走行为和死亡概率的改进狼群算法（Chemotactic behavior and Death probability WPA， CDWPA）[35]和基于levy飞行的动态狼群算法（Dynamic wolf pack algorithm based on Levy Flight， LDWPA）[36]进行比较。此外，使用一种较新颖的改进PSO算法，prey-predator PSO （PP-PSO）算法进行比较，该算法在CEC2017测试函数集上展现了比其他10种PSO衍生算法更好的性能[37]。为方便读者阅读，将结果分两组进行展示。其中WPA的改进算法（包括DAWPA， IWPA， CDWPA， LDWPA）为一组，其他算法为一组（包括DAWPA， CS， ABC， PP-PSO）。本文统计4个寻优性能指标，分别为最优值（best），平均值（mean），标准差（SD）与平均耗时（average time-cost）。

实验的最大迭代次数为2 000次，初始种群数目都设为100，精度阈值为1×10-6，即小于1×10-6的精度误差均可视为0。各算法参数见表2.测试环境为i7-6500U CPU @ 2.50GHz 2.59GHz， Matlab R2018a。测试结果见表3和表4。

3.3 结果分析

本节将从算法精度（包含3.3.2节统计分析）、速度-稳定性能与收敛速度比较三方面，对表3、表4的结果进行分析。

为了方便读者理解，下面对性能指标的含义进行简要介绍。“Best”为寻优全程中算法取得的最接近标准值的结果。“Mean”为寻优过程中，所有迭代的平均结果。“SD”为计算结果的标准差，其代表了算法的稳定性能。“average time-cost”为每次寻优（2 000次迭代）的平均耗时。

3.3.1 算法精度分析

表3、表4中的最优值与平均值反映了算法的寻优精度。从低维、可分、单峰的函数，如F1-5的结果来看，DAWPA的寻优精度与其他算法的结果接近。对于低维、不可分、多峰函数，例如F8-9，DAWPA的算法精度与CS， ABC， PP-PSO， CDWPA， LDWPA算法接近，而IWPA则相对较低。对于高维、可分、单峰函数，包括F6-7，DAWPA，ABC和IWPA算法比CS算法略有优势，同时精度远高于PP-PSO算法与LDWPA算法。对高维、可分、多峰函数，如F11，4种WPA改进算法具有明显优势，显示其避免陷入局部最优的能力比其他算法强，且DAWPA算法精度优于其他3种WPA改进算法。CS， ABC和PP-PSO算法的优化基于适应度，采取贪婪策略进行更新。但当面对多峰函数时，单纯依赖适应度的更新机制极易陷入局部最优解，因此其算法精度不佳。而WPA改进算法采用了游走-召唤-围攻的做法，由可变的头狼对其他人工狼进行指导，对全局信息与头狼附近的局部信息都进行了探索，因此在多峰高维问题上精度较好。相对于其他WPA改进算法，DAWPA加入了分群策略，将解空间中被多个峰分隔的子群进行适当的分群，分别由各自的头狼召唤、围攻，同时有间隔的进行子群的合并-分裂，使多个较优的解空间领域得到充分探索，获得了最好的算法精度。

此外，对多峰不可分的高维函数，如F16-17，其反映了算法对不可分的维度信息的处理能力。计算结果的比较表明，DAWPA的算法精度高于WPA改进算法且远高于PP-PSO、ABC和CS算法。这证明采用差异度拟熵的自适应围攻环节对不可分的维度信息处理能力更强，提高了算法的精度。

3.3.2 统计分析

3.3.1节中的分析显示DAWPA相对于其他算法在复杂函数寻优上具有更好的性能。为了进行进一步的统计分析，本节采取无参数Friedman test分析复杂函数上的平均精度，以测试DAWPA相对其他算法的精度优势是否显著[38]。算法平均精度为算法平均结果与标准值的差值的绝对值。原假设认为DAWPA与比较的算法的性能无显著差异，当p值小于0.05时拒绝原假设且置信度为95%。

为了应用F-test，首先选取多个复杂函数，并将其划分为两类。将函数维数大于等于30且小于等于100的函数划分为中等维数函数（Mid-dimensional），将函数维数高于100的划分为高维函数（High-dimensional）。函数的划分如表5所示。

将表3、表4中的平均结果（mean）与标准值的差值的绝对值作为精度指标。借鉴文献[39]，对每个算法分别计算中等维度函数与高维函数的精度指标的平均值（mean）与中位数（median）。

基于该平均值与中位数，使用Matlab进行F-test，计算p值为0.02<0.05，即可以以95%的置信度拒绝原假设，显示DAWPA算法对其他算法的精度优势具有显著性。指标及计算结果如表6所示。

3.3.3 速度-稳定性能分析

表3、表4中的标准差与耗时分别体现了算法的稳定性和快速性。对于智能算法而言，其速度-稳定性能之间的平衡对算法的应用影响巨大，因此对这两个指标同时进行分析。由于各个函数复杂程度不同，不同函数的寻优标准差之间存在数量级的差异。为了直观展示DAWPA相对于其他算法的寻优标准差的情况，使用对数标准差比，即DAWPA的标准差与其他6种算法标准差的比值的对数作为特征，与算法耗时一起展示。对于标准差比值分母为0的情况，若分子也为0，将比值标为1;若分子大于0，将比值标为10 000，则取对数后为4。结果如图4a）和4b）所示。

在稳定性方面，对于低维、单峰函数， DAWPA的稳定性相对于ABC算法、CS算法较差，与CDWPA和LDWPA互有优劣但较为接近，好于IWPA算法。对于高维、多峰尤其是不可分的复杂函数，如F11、F16、F17，比值曲线出现了明显的下三角，说明DAWPA在复杂函数上的稳定性显著好于其他算法，不易受到干扰。在7种算法中，对于高维的复杂函数，DAWPA拥有最好的稳定性。这是因为这5种算法本质上都属于随机搜索算法，而当搜索进入到局部最优解时，其他算法基于贪婪的更新策略都容易陷入局部最优，尽管都加入了一定概率的跳出局部最优的操作，但算法稳定性仍然会受到明显的影响。而DAWPA使用了分群的策略，多个子群同时探索，有更大概率求得全局最优值，算法稳定性得到了提高。从计算耗时上看，DAWPA在低维函数上计算耗时较大，但在高维函数上显著缩短了耗时，与其他WPA改进算法相比，具有明显优势。一方面这是由于分群策略的使用加快了算法求得全局最优解的速度，抵消了计算耗时，另一方面是因为随机游走环节，相对于WPA的其他改进算法的游走环节减少了适应度函数的计算，因此大幅度减少了计算耗时。

3.3.4 算法收敛情况分析

速度-稳定性能分析显示，与非WPA改进算法相比，DAWPA具有更好的稳定性，但计算耗时较多。本节通过对收敛过程进行分析，确定耗时较多的原因。由于CDWPA与LDWPA算法的耗时较大，该分析仅涵盖DAWPA， CS， ABC， IWPA， PP-PSO5种算法。

将寻优误差随迭代次数的变化绘制成收敛曲线，选择一系列高维函数，包括F6， F7， F11，与F17，绘制5种算法在不同函数上的收敛曲线，如图5。

以高维、不可分、多峰函数F17为例，5种算法的收敛曲线如图6所示。在100代左右，IWPA算法就基本收敛，其精度停留在1×10-4级别，显示其可能陷入了局部最优。250代左右，DAWPA算法到达全局最优，达到了更高的寻优精度。2 000代后，ABC与CS算法仍然未能收敛到全局最优解。PP-PSO算法在寻优初期快速下降，但很快陷入局部最优解。

图5所示其他收敛曲线也显示DAWPA在速度与精度上具有优势。IWPA的收敛速度与DAWPA接近，但精确度较差。ABC算法与DAWPA算法在F16上达到了接近的精度，但在F11， F17上性能较差。

分析结果说明，在复杂函数上，DAWPA基于游走-召唤-智能圍攻的寻优过程，相对于PP-PSO、ABC算法和CS算法，能更好地对解空间进行搜索，在寻优能力上有明显优势。在多峰不可分函数上，与IWPA的对比证明，DAWPA基于差异度拟熵的智能围攻过程，对不可分的函数特征有更高的寻优精度。

综上所述，DAWPA在高维不可分多峰函数上，用一定的计算耗时，换取了明显的寻优精度、稳定性的提升。在围攻过程中，DAWPA的动态分群过程和差异度拟熵的计算量大于其他改进WPA算法，花费了较多时间，因此在简单函数上整体耗时较长;但在如F17等复杂函数上耗时明显缩短。原因是DAWPA通过动态分群，减小了陷入局部最优的可能;随机游走环节减少了适应度函数计算的大量耗时;使用差异度拟熵，对头狼和人工狼的相似度进行了更合适的度量，提高寻优精度的同时，在更少的迭代次数内收敛到最优值，抵消了计算的耗时。测试结果证明，DAWPA算法具有更强的适应能力，不易陷入局部最优解。同时，动态分群与随机游走环节加快了算法收敛到全局最优值的速度，较PP-PSO、ABC算法、CS算法和其他改进WPA算法有明显的优势。

4 DAWPA的实际应用

复杂地形三维航路规划是指在复杂三维地形环境下，无人机自主规划一条航线躲避障碍物，同时尽可能减少航程。相比于二维航路规划，三维情况下搜索空间过大，快速拓展随机树[40]、A*算法[41]等传统二维航路规划算法的计算时间过长。基于模拟流体流动的思想，文献[42]提出了基于扰动流体动态系统（IFDS）的三维航路规划方法，该方法具有光滑的航路特性和快速性，但产生的流线存在局部陷阱或可能停留于驻点。为了解决流线缺陷，文献[43]提出了改进扰动流体动态系统算法（IIFDS）。在IIFDS算法中，需要对反应系数进行优化，以产生最优航路。多种群智能优化算法在对反应系数进行寻优时，寻优效果随维度增长而下降，且容易陷入局部最优解[42]。为了验证DAWPA具有的动态适应性，本文将DAWPA应用于无人机航路规划，对复杂三维地形下IIFDS算法的反应系数组进行寻优，规划出较优航线。IIFDS模型参见文献[42]。

4.1 复杂地形下的三维航路规划

在IIFDS模型中，排斥反应系数[ρ]、切向反应系数[σ]与切向方向系数[θ]的选取影响了最终航线的方向、形状与长度。本文使用DAWPA，对其进行优化以获得较优航线。首先定义适应度函数J。考虑航路长度代价[J1]与障碍物威胁代价[J2]。

[J=μ1J1+μ2J2，]

式中，[μ1，μ2∈0，1]为代价权重系数，有[μ1+μ2=1]。

其次，对于狼群的初始化，设定参数范围[ρ∈0.1，30、σ∈0.1，30、θ∈-π，π]， 初始化狼群规模N，则[Xi=ρ1，σ1，θ1，...，ρK，σK，θK，i=1，2，...，N]，维度D=3K。

基于3.1节的算法流程，设定规划空间为[10×10×3]，随机产生10个不同类型的障碍物，如图7所示。障碍物高度不一，可以测试算法权衡左右绕行或拉升避障的能力;有单峰障碍物，也有两个障碍物叠加的多峰障碍，更加贴近实际地形，也增加了难度。

对图7的地形，设定无人机起点为（0，0，0），终点为（10，10，0.5）。为了无人机的安全，设置代价权重系数[0.3，0.7]，代表较高的避障权重。使用DAWPA、CS算法、ABC算法、PP-PSO算法、IWPA算法、CDWPA算法与LDWPA算法进行比较，设置种群规模N=100，最大迭代次数t=100，进行50次重复实验，并选取其中适应度最好的航线结果进行比较。

将使用6种算法所得到的航路按照第3节的分组方式分两组绘制，如图8a）、图b）、图8c）和图8d），对应的路径信息如表7所示。对于不可行路径，其代价记为-。

DAWPA、CS、IWPA和LDWPA算法生成的航线都能在复杂三维地形中避开障碍物到达终点，但ABC、PP-PSO与CDWPA算法生成的路径未能避开部分障碍物，说明这3种算法未能找到合适的排斥反应系数和切向反应系数。在7种算法生成的路径中，DAWPA生成的路径的长度代价与避障代价均小于其他算法，路径也较为平滑，更加适用于无人机的飞行。

在复杂三维地形下的航路规划问题中，待优化个体为针对各个障碍物的排斥反应系数、切向反应系数和切向方向系数。由于可能的航线不止一条，该问题有着多峰函数性质。因此，DAWPA的动态分群策略有助于同时探索多条较优路径，从而更快地找到最优路径。另外，对于一条航路，避开不同障碍物的角度不是完全独立的，例如，航线穿过两个障碍物之间时，对其中一个障碍物避障角度过大会导致无人机进入到另一个障碍物中，引起避障代价的提高。在航线规划中，各个维度之间存在一定的联系，优化目标具有不可分函数的特性。DAWPA的优势在于，使用差异度拟熵对所有维度信息进行统计，因此对不可分函数的局部信息有更强的感知能力。综上所述，对于航路规划问题，DAWPA拥有更好的优化效果。

5 结论

本文针对基本狼群算法缺乏适应性的问题，提出了一种具有动态适应性的狼群算法DAWPA，以提高狼群算法在实际应用中的表现。

通过引入动态分群策略，种群的分布可以根据优化环境进行动态调整;使用差异度拟熵改进的围攻过程提高了复杂环境下的寻优精度;随机游走环节增强了全局适应性，并减少了计算耗时，从而抵消了前两个技术带来的较高的时间代价。在测试函数集上与其他6种算法比较的仿真实验体现了DAWPA在搜索全局最优与快速收敛上的能力。此外，在三维无人机路径规划问题上，DAWPA展现了比其他6种算法更好的优化性能，获得的飞行路径航程更短且能良好避障，具有实用性。

本文定义了一种差异度拟熵，具有度量耦合函数特征的相似度与序列信息的能力，拓展了自适应步长算法，理论上对优化目标具有不可分特性的相似性度量具有通用性，可以将其引入其他需要不可分函数相似性度量的智能算法中。另外，本文提出的动态分群策略提供了一种改进的初始解生成方法。由于采取了动态分群的策略，DAWPA在复杂函数上较强的处理能力，可以应用于其他复杂结构问题的寻优，如多水下自主航行器的动态任务分配问题等。下一步可以考慮针对具体问题，进一步优化分群策略，使其适用于更多应用场景。

参考文献：

[1]    GUPTA A，SRIVASTAVA S. Comparative analysis of ant colony and particle swarm optimization algorithms for distance optimization[J]. Procedia Computer Science，2020，173：245-253.

[2]    ALFI A，MODARES H. System identification and control using adaptive particle swarm optimization[J]. Applied Mathematical Modelling，2011，35（3）：1210-1221.

[3]    SQUILLERO G，TONDA A. Divergence of character and premature convergence：a survey of methodologies for promoting diversity in evolutionary optimization[J]. Information Sciences，2016，329：782-799.

[4]    吴虎胜，张凤鸣，吴庐山. 一种新的群体智能算法：狼群算法[J]. 系统工程与电子技术，2013，35（11）：2430-2438.

[5]    刘聪，费炜，胡胜. 狼群算法的研究与应用综述[J]. 科学技术与工程，2020，20（9）：3378-3386.

[6]    LI H，WU H S. An oppositional wolf pack algorithm for Parameter identification of the chaotic systems[J]. Optik，2016，127（20）：9853-9864.

[7]    吳虎胜，张凤鸣，战仁军，等. 求解0-1背包问题的二进制狼群算法[J]. 系统工程与电子技术，2014，36（8）：1660-1667.

[8]    吴虎胜，张凤鸣，李浩，等. 求解TSP问题的离散狼群算法[J]. 控制与决策，2015，30（10）：1861-1867.

[9]    马龙，卢才武，顾清华，等. 多目标0-1规划问题的元胞狼群优化算法研究[J]. 运筹与管理，2018，27（3）：17-24.

[10]  WU H S，XUE J J，XIAO R B，et al. Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm[J]. Frontiers of Information Technology & Electronic Engineering，2020，21（9）：1356-1368.

[11]  WU H S，XIAO R B. Flexible wolf pack algorithm for dynamic multidimensional knapsack problems[J]. Research，2020，2020（11）：1-13.

[12]  ZHANG L Y，ZHANG L，LIU S，et al. Three-dimensional underwater path planning based on modified wolf pack algorithm[J]. IEEE Access，2017，5：22783-22795.

[13]  李励，赖喜德，陈小明. 基于改进狼群算法的水电站厂内优化运行研究[J]. 水电能源科学，2019，37（6）：164-168.

[14]  CHEN Y B，MEI Y S，YU J Q，et al. Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm[J]. Neurocomputing，2017，266：445-457.

[15]  CHEN X Y，TANG C J，WANG J，et al. Improved wolf pack algorithm based on differential evolution elite set[J]. IEICE Transactions on Information and Systems，2018，E101. D（7）：1946-1949.

[16]  周璟. 混沌狼群围捕算法的车间机器人导航路径规划[J]. 机械设计与制造，2020（1）：251-255.

[17]  惠晓滨，郭庆，吴娉娉，等. 一种改进的狼群算法[J]. 控制与决策，2017，32（7）：1163-1172.

[18]  张强，王梅. 自适应分组差分变异狼群优化算法[J]. 华东师范大学学报（自然科学版），2017（3）：78-86.

[19]  ZHU Y，JIANG W L，KONG X D，et al. A chaos wolf optimization algorithm with self-adaptive variable step-size[J]. AIP Advances，2017，7（10）：105024.

[20]  王盈祥，陈民铀，程庭莉，等. 基于差分进化的改进狼群算法研究[J]. 计算机应用研究，2019，36（8）：2305-2310.

[21]  郭立婷. 基于自适应和变游走方向的改进狼群算法[J]. 浙江大学学报（理学版），2018，45（3）：284-293.

[22]  颜学龙，汪斌斌. 自适应狼群算法优化ELM的模拟电路故障诊断[J]. 计算机工程与科学，2019，41（2）：246-252.

[23]  曹爽，安建成. 改进狼群优化算法的Otsu图像分割法[J]. 微电子学与计算机，2017，34（10）：16-21.

[24]  张举世. 改进的狼群优化二维Otsu阈值分割算法[J]. 电力学报，2020，35（1）：40-45.

[25]  李靖宇，王磊，江克贵，等. 基于改进狼群算法的概率积分法模型参数反演方法[J]. 采矿与岩层控制工程学报，2021，3（1）：79-86.

[26]  LI C，MA H，ZHOU Y，et al. Similarity analysis of DNA sequences based on the weighted pseudo-entropy[J]. Journal of Computational Chemistry，2011，32（4）：675-680.

[27]  薛俊杰，王瑛，李浩，等. 一种狼群智能算法及收敛性分析[J]. 控制与决策，2016，31（12）：2131-2139.

[28]  WU H S，ZHANG F M. Wolf pack algorithm for unconstrained global optimization[J]. Mathematical Problems in Engineering，2014，2014：1-17.

[29]  MOAZZENI A R，KHAMEHCHI E. Rain optimization algorithm （ROA）：a new metaheuristic method for drilling optimization solutions[J]. Journal of Petroleum Science and Engineering，2020，195：107512.

[30]  JAIN L，KATARYA R，SACHDEVA S. Opinion leader detection using whale optimization algorithm in online social network[J]. Expert Systems With Applications，2020，142：113016.

[31]  NAIK A，SATAPATHY S C，ABRAHAM A. Modified Social Group Optimization—a meta-heuristic algorithm to solve short-term hydrothermal scheduling[J]. Applied Soft Computing，2020，95：106524.

[32]  CHOU J S，NGUYEN N M. FBI inspired meta-optimization[J]. Applied Soft Computing，2020，93：106339.

[33]  KARABOGA D，BASTURK B. A powerful and efficient algorithm for numerical function optimization：artificial bee colony （ABC） algorithm[J]. Journal of Global Optimization，2007，39（3）：459-471.

[34]  CUEVAS E，REYNA-ORTA A. A cuckoo search algorithm for multimodal optimization[J]. The Scientific World Journal，2014，2014：497514.

[35]  鲜思东，李堂金. 基于改进狼群算法的模糊时间序列预测模型[J]. 控制理论与应用，2020，37（7）：1637-1643.

[36]  韩忠华，刘约翰，李曼，等. 改进狼群算法求解模具在模台上组合分配问题[J]. 系统仿真学报，2021，33（1）：127-140.

[37]  ZHANG H R，YUAN M，LIANG Y T，et al. A novel particle swarm optimization based on prey-predator relationship[J]. Applied Soft Computing，2018，68：202-218.

[38]  DEMSAR J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research，2006，7：1-30.

[39]  TANWEER M R，SURESH S，SUNDARARAJAN N. Self regulating particle swarm optimization algorithm[J]. Information Sciences，2015，294：182-202.

[40]  ZUCKER M，KUFFNER J，BRANICKY M. Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings 2007 IEEE International Conference on Robotics and Automation. April 10-14，2007，Rome，Italy. IEEE，2007：1603-1609.

[41]  YANG H I，ZHAO Y J. Trajectory planning for autonomous aerospace vehicles amid known obstacles and conflicts[J]. Journal of Guidance，Control，and Dynamics，2004，27（6）：997-1008.

[42]  WANG H L，LYU W T，YAO P，et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[J]. Chinese Journal of Aeronautics，2015，28（1）：229-239.

[43]  姚鵬，王宏伦. 基于改进流体扰动算法与灰狼优化的无人机三维航路规划[J]. 控制与决策，2016，31（4）：701-708.