基于群智能的路径规划算法（五）——狼群算法

   本系列文章主要记录学习基于群智能的路径规划算法过程中的一些关键知识点，并按照理解对其进行描述总结和进行相关思考。

   主要学习资料是来自 小黎的Ally 的 《第2期课程-基于群智能的三维路径规划算法》，视频链接如下（点击链接可跳转）：

   https://space.bilibili.com/477041559/channel/seriesdetail?sid=863038

   本篇参考文献：

   刘永兰,李为民,吴虎胜,宋文静.基于狼群算法的无人机航迹规划[J].系统仿真学报,2015,27(08):1838-1843 （点击可跳转）

   本篇文章是本系列的第五篇文章 ：狼群算法

本系列文章链接 （点击可跳转）：

—————————————————————————–

   基于群智能的路径规划算法（一）——粒子群算法

   基于群智能的路径规划算法（二）——蚁群算法

   基于群智能的路径规划算法（三）——遗传算法

   基于群智能的路径规划算法（四）——人工蜂群算法

   基于群智能的路径规划算法（五）——狼群算法

   基于群智能的路径规划算法（六）——人工鱼群算法

—————————————————————————–

   一、狼群算法简介

   狼是一种群居性动物，社会分工明确，通过承担各自的责任与团结协作，共同促进整个狼群的生存与发展。狼群算法（(Wolf pack algorithm ，WPA）采用了基于人工狼主体的自下而上的设计方法和基于职责分工的协作式搜索路径结构。

   狼群算法是一种以群体智能为基础的优化算法，它最早见于 1970年美国著名狼研究专家 Mech 出版的一本专著中，该专著详细描述了狼群生态和狼群群体行为等内容。后来许多学者以此为研究基础，对狼群的协作捕猎、追捕猎物等行为展开了大量研究

   狼的社会分工有头狼、探狼和猛狼:

   头狼:将当前离猎物气味浓度最高（适应度最优）的狼作为头狼，起指挥狼群行动的作用，头领狼召唤其他狼向猎物靠近，具有指挥狼群行动的能力，在搜寻过程中头狼的角色是动态变化的。

   探狼︰初始时，狼群会派出一部分狼作为探狼，在环境四周搜寻猎物。探狼在搜寻过程中如果发现猎物气味浓度更高，就作为头狼，呼唤其他的狼进行围捕行为。后期，比较不同的探狼猎物的适应度，选择适应度较高的作为头狼。

   猛狼:猛狼感应到头狼呼唤，就立刻向头狼位置奔袭，在奔袭的过程中，若是发现猎物的适应度更高，则立刻替代原来的头领狼，指挥其他狼行动。

   二、将狼群算法应用于路径规划

   针对狼群的整个捕猎活动，狼群算法从中抽象出3种智能行为(即游走、召唤和围攻)，“胜者为王”的头狼产生规则，以及“强者生存”的狼群更新机制:

   （1）游走行为:在解空间中，除头狼之外最佳的S匹人工狼视为探狼，分别计算每只探狼搜索的猎物适应度，若大于头狼的适应度，则该探狼变为头狼，重新发起召唤行为。否则探狼向h个方向按照游走步长前进一步

   其中，Xid是当前第i只探狼在d维度上位置，step（d，s）是探狼移动的步长，h是设定的方向个数，p是某个方向（p取值为 1 ~ h），比如取h为36，则相当于将360度分成36份，即每间隔10度选取一个移动方向。sin（2πp/h）可以理解成某个方向。

   （2）召唤行为:游走行为结束后，会产生头狼，头狼利用嚎叫方式发起召唤行为，将周围的M匹猛狼迅速向其所在的位置召集，猛狼以奔袭步长快速向头狼靠近，并搜索猎物。猛狼奔袭过程中，若猎物适应度更高，则令猛狼代替头狼。当猛狼与头狼的距离小于阈值时，转为围攻行为。

   其中，Xjd是当前第j只猛狼在d维度上位置，step（d，b）是猛狼移动的步长，其后面的式子表示当前猛狼沿着朝向头狼的方向进行移动

   （3）围攻行为:猛狼感应到头狼呼唤，就立刻向头狼位置奔走，在奔走的过程中，若是发现猎物的适应度更高，则立刻替代原来的头狼，指挥其他狼行动。

   其中，Xid是当前第i只猛狼在d维度上位置，step（d，w）是猛狼移动的步长，其后面的式子表示当前猛狼沿着朝向头狼的方向进行移动

   注：围攻行为和召唤行为，其实都是猛狼响应头狼的召唤，向头狼位置移动，只是在召唤阶段以较大的步长移动，在距离头狼较近时，转而执行围攻行为，以较小的步长移动，以防止步长过大，跨过头狼的位置。

   （4）基于狼群算法的无人机航迹规划论文中设定的人工狼的游走步长、奔袭步长和围攻步长的关系为:

   其中：C 表示步长因子，代表了人工狼在解空间中的搜索精细程度。Md ， md 为待寻优的第 d 维变量空间的最大值和最小值。

   三、算法流程

   四、编程实现思路

   对 小黎的Ally 提供的程序 的实现思路总结如下：

   首先初始化种群，按照正态分布随机生成每只狼的初始位置，即每只狼对应的路径的关键点位置，然后使用B样条曲线对关键点进行拟合获得每只狼对应的路径，然后依然把路径的长度作为衡量指标，计算每只狼的适应度，然后判断是否更新全局最优。

   然后选择其中适应度最小的S_num只狼作为探狼（在本程序中适应度越小代表的路径越优），其余的狼作为猛狼。至此初始化部分结束。

   开始进行循环迭代，在每次迭代中，每只探狼首先进行游走行为，按照上文介绍的公式计算出每只探狼，沿着h个方向游走后的位置，并拟合成路径计算适应度，将每只探狼当前位置的适应度和分别沿着h个方向移动后位置的适应度，进行比较，选取最优的一个作为当前探狼的位置。并与头狼的适应度进行比较。若头狼的适应度更优，则下一只探狼继续执行上面介绍的游走行为操作，若当前探狼的适应度比头狼更优，则终止所有探狼的游走行为，并将当前探狼作为新的头狼，发起召唤行为。

   头狼发起召唤行为后，所有的猛狼开始朝头狼位置奔袭。该部分内容包含三个重要的循环，第一层循环是依次对每只猛狼进行操作，第二层循环是根据标志位判断是否结束当前猛狼的循环，首先当前猛狼按照上文介绍的移动公式向头狼方向移动，得到新的位置后，拟合成路径，然后计算适用度，并与头狼位置的适应度进行比较：

   分支① ：若当前猛狼的适应度更优，则当前猛狼退出循环（即终止第二层循环中当前猛狼的循环），并将当前猛狼作为新的头狼，对本次迭代还没执行响应头狼召唤的剩下的猛狼继续朝新的头狼执行响应召唤行为。

   分支② 若当前猛狼的适应度不如头狼的适应度优，则判断当前猛狼的位置是否已经到达围攻临界距离，即与头狼之间的距离是否已经小于设定的界限，若不小于，则当前猛狼继续进行循环（即本部分的第二层循环），继续执行响应召唤行为，朝头狼以大步长移动。直至当前猛狼的适应度优于头狼的适应度，即转而执行上面分支①中介绍的操作，或者直至当前猛狼与头狼直接的距离小于了设定的界限，则当前猛狼转而执行围攻行为，即当前猛狼进行本部分的第三层重要循环，在每次该层循环中，当前猛狼以较小的步长向头狼移动，并计算移动后位置的适应度，并与头狼位置的适应度进行比较,若当前猛狼的适应度更优，则转而执行上面的分支①，若头狼的适应度更优，则当前猛狼进行围攻行为的次数累加1，继续进行第三层循环，执行围攻行为，直至满足上面分支①，直接结束当前猛狼的第三层循环，即不再执行围攻行为，并终止当前猛狼的第二层循环，或者当前猛狼执行围攻行为的次数达到设定的上限，则依次结束当前猛狼的第三层循环和第二层循环 （重要标记处） 转而在第一层循环下，对一只猛狼进行处理。

   直至所有的猛狼都执行完上面的操作后，第本部分的一层循环结束。然后按照优胜劣汰的准则对整个狼群进行更新，即将所有的探狼和猛狼按照适应度进行排序，将适应度更优的那部分狼（比如说狼群的一半）作为新的探狼，剩下的狼被淘汰掉，并随机生成新的猛狼对狼群进行补充，计算新生成的狼的适应度，并判断是否更新全局最优。

   至此，本次迭代完成，开始进行下一次迭代，直至迭代次数达到设定的数值，结束程序。

   注意：小黎的Ally 提供的程序中，在上文的重要标记处存在bug，即当当前猛狼执行围攻行为的次数达到设定的上限，则会结束当前猛狼的第三层循环，并继续进行第二层循环，转而继续进行第三层循环。。。。循环卡死。。。即该种情况下，没有正常退出当前猛狼的第二层循环。只需要在while T < T_max 的end与if d < d0的end之间加一个break；即可解决以上bug。

   五、运行效果示例：

   以上视频采用了7倍速，虽然视频时长2分钟左右，实际程序运行14分钟左右，可以看出每次迭代耗时较多，但路径质量较优，经过少量的迭代次数，就可以找到近似最优解的路径，只是耗时有点多。

   此外，以上视频中程序卡在了第45代中，卡在了上文介绍的程序bug中。

   上面的示例中1~45代的最优适应度如下，可以发现基本上路径在不断的优化，基本上可以认为没有陷入局部最优。

第1代:最优适应度 = 208.4199
第2代:最优适应度 = 208.128
第3代:最优适应度 = 207.0074
第4代:最优适应度 = 206.1984
第5代:最优适应度 = 205.8308
第6代:最优适应度 = 186.3573
第7代:最优适应度 = 173.9196
第8代:最优适应度 = 172.8788
第9代:最优适应度 = 168.9278
第10代:最优适应度 = 168.7216
第11代:最优适应度 = 168.3
第12代:最优适应度 = 167.5668
第13代:最优适应度 = 167.2755
第14代:最优适应度 = 167.0855
第15代:最优适应度 = 166.6161
第16代:最优适应度 = 166.3211
第17代:最优适应度 = 165.8604
第18代:最优适应度 = 165.3448
第19代:最优适应度 = 163.9491
第20代:最优适应度 = 163.71
第21代:最优适应度 = 163.6016
第22代:最优适应度 = 163.1638
第23代:最优适应度 = 162.7723
第24代:最优适应度 = 162.5581
第25代:最优适应度 = 161.6177
第26代:最优适应度 = 161.448
第27代:最优适应度 = 161.4429
第28代:最优适应度 = 161.3665
第29代:最优适应度 = 161.2742
第30代:最优适应度 = 161.2477
第31代:最优适应度 = 161.2337
第32代:最优适应度 = 161.1573
第33代:最优适应度 = 161.1546
第34代:最优适应度 = 161.1469
第35代:最优适应度 = 161.1243
第36代:最优适应度 = 161.0154
第37代:最优适应度 = 160.9978
第38代:最优适应度 = 160.985
第39代:最优适应度 = 160.9603
第40代:最优适应度 = 160.9597
第41代:最优适应度 = 160.9427
第42代:最优适应度 = 160.9141
第43代:最优适应度 = 160.9133
第44代:最优适应度 = 160.9124
第45代:最优适应度 = 160.9118

   另一个示例的最优适应度变化：