人工蜂群算法及其在路径寻优问题上的应用*

郝 辉，李雪瑞，张雨森

（火箭军工程大学作战保障学院，西安 710025）

0 引言

多旋翼无人机（multirotor unmanned aircraft，MUA）是指具有3 个及以上旋翼轴的旋翼飞行器，它具备垂直起降、悬空停留飞行以及起飞无需机场跑道等多种固定翼无人机所没有的飞行特点。

人工蜂群算法是一种现代启发式智能搜索算法［1］，与其他群智能算法相比，其优点包括：1）算法的寻优能力较强。人工蜂群算法是一种广义的邻域搜索算法，通过3 种蜂不同情况下的转化，借助启发式的搜索策略，不仅能高效进行局部搜索，其算法本身还具有全局寻优的能力；2）算法适应性较强。人工蜂群算法由于具有全局收敛能力，因此，算法对寻优函数和初值无特殊要求，参数可设置的范围较广。结合旋翼无人机航迹规划这一多约束条件的组合优化问题，由于在各约束条件间存在耦合，虽然采用过很多人工智能算法解决，但最终难以避免算法陷入局部最优解和进化停滞的实现结果，因此，有很多研究会根据实际问题提出一些改进算法。

在人工蜂群算法优化精度和收敛速度方面，引入单纯性算子以减少传统人工蜂群算法陷入停滞现象［2］；引入混沌思想增强其摆脱局部最优值的能力［3］；加入淘汰规则并改变新的搜索策略，利用蜜蜂个体的差分进化提高算法的全局寻优能力［4］；结合贪婪子路径交叉算子提高算法准确性［5］；采用一种模拟离子运动规律来更新蜂群的策略，以提高传统人工蜂群算法在路径规划中的收敛速度和搜索能力［6］。

在提高种群多样性以及避免过早收敛方面，可通过选取新的选择策略，例如：比赛选择策略、等级选择策略等［7］，或通过随机动态局部搜索算子帮助算法逃离束缚，从而加快搜寻最优解［8］；引入变异步长的改进方案以实现在整个搜索域的精确搜索［9］；通过完善适应度评价机制和迭代更新参数来提高人工蜂群算法的适应力［10］；结合K-MEANS 算法和邻域动态搜索方法来提高人工蜂群算法在机器人路径规划中的搜索能力［11］；引入混沌映射产生初始解和反轮盘赌机制，并结合等距分布式并行搜索与全局更新机制中的势场作用来提高人工蜂群算法的路径寻优的质量［12］。

本文以人工蜂群算法为基础，结合旋翼无人机飞行机动性能相关特点，建立了基于人工蜂群算法的旋翼无人机路径寻优模型，通过蜜源邻域搜索模型、选择机制和判定准则，增强算法结果的可靠性，最后对研究结果进行统计与分析，以改进算法来提高算法性能。

1 改进人工蜂群算法原理

人工蜂群算法，建立在蜜源、收益度、采蜜蜂、观察蜂和侦察蜂等基本概念之上，各涵义如表1 所示。

表1 算法相关名词解释Table 1 Explanation of terms related to algorithm

人工蜂群算法的基本原理步骤如下：

1）在n=0 时刻，系统将随机生成NS个（蜜蜂种群数量）可行解，即Xi为：

2）第n 步时，采蜜蜂种群表示为X（n），并在当前解向量所对应的位置附近进行邻域搜索得出新解，搜索公式为：

3）对采蜜蜂在邻域搜索阶段产生的新解和原解，用贪婪准则进行取舍，留给下一代蜜蜂种群使用，其替代概率的计算式为：

选择贪婪策略将使得整个种群中的优质解得以保留，种群进化的方向不会发生退化，且TS分布与时刻n 无关。

4）各个观察蜂利用采蜜蜂共享的蜜源信息计算跟随概率，与采蜜蜂一起对蜜源进行邻域搜索，选择概率的计算式为：

其中，fiti是第i 个解的目标函数值；而Ne为设定的蜜源数量。该计算式TS1表示概率分布与n 时刻也无关。

5）重复第2）步与第3）步，并记下种群最终更新后达到的最优适应度值，以及相应的参数。

6）当在一个蜜源位置周围的搜索次数变量Lin持续累加，但仍然没有更改蜜源位置时，系统将再进行一次迭代，并随机初始化，见第1）步；

7）达到最大迭代次数后输出解向量，否则转向第2）步。

2 旋翼无人机路径寻优问题分析

2.1 路径规划飞行环境模型建立

为了方便计算，本文将规划区域进行简化处理，用圆形区域进行表示，如图1（多边形区域可以由多个圆来组合表示），其中，黄色区域表示威胁区域，无人机在必要时可以穿越通过，红色区域表示障碍区域，无人机在飞行过程不能穿越。在同一高度下，利用各种威胁（障碍）在该平面的外接圆进行威胁区域或障碍区域的建模，此时，只需确定威胁（障碍）区域的中心坐标（xi，yi）和其覆盖的半径ri，即可用式（6）来建立威胁（障碍）区域的数学模型：

图1 旋翼无人机路径寻优环境模型示意图Fig.1 Schematic diagram of route optimization environment model for rotor unmanned aircrafts

式中，（x，y）表示平面任意一点的坐标。

为了区分不同的威胁类型，按照其对旋翼无人机的威胁程度，区分1、2、3 这3 种不同的威胁等级，由低到高威胁程度依次增大，并将其考虑至目标函数的计算中。

因此，旋翼无人机路径寻优环境模型即由威胁（障碍）区域和若干路径点组成，如图2 所示。已知起点S 和终点T、以及若干威胁（障碍）区域，路径规划的任务就是要从起点至终点找出一条能避开威胁（障碍）且满足目标函数较小的最优或次优的无人机路径，相应的坐标转换计算公式为：

图2 旋翼无人机路径寻优模型示意图Fig.2 Schematic diagram of path optimization model for rotor unmanned aircrafts

式中，θ 为直线ST 与原直角坐标系中的x 轴的正向的逆时针方向夹角；（x'，y'）为新坐标系下的点坐标；（x，y）为对应点在原系下的坐标；（xS，yS）和（xT，yT）分别为路径规划的起点和终点在原系下的坐标。

2.2 旋翼无人机路径寻优约束条件分析

对多旋翼无人机飞行过程中的飞行约束条件进行建模时，为充分保证规划结果的可行性与可靠性，结合旋翼无人机的飞行特点，从其自身的使用要求与物理限制的角度出发进行考虑，主要有以下几个方面。

2.2.1 最小和最长路径长度（Lmin和Lmax）

根据旋翼无人机的初始导航偏差修正的要求，考虑旋翼无人机的最小路径长度Lmin。对于这一约束只需要使得起点至终点连线ST 线段的等分间隔pi-1pi的距离均大于最小路径长度即可：

由起点至终点的路径有一个最长路径长度Lmax，其约束条件的模型为：

2.2.2 端点约束

根据路径规划任务的相关要求，在本文中，选择固定端点方向的一定范围，使得规划结果的路径总是分布在由起点至终点的连线附近。

2.3 旋翼无人机路径寻优目标函数模型分析

2.3.1 威胁（障碍）区域代价

将飞行环境中的威胁区（障碍物）进行简化处理，取与雷达威胁模型相似的圆形数学模型，认为当无人机处于威胁（障碍）圆域内部时，无人机将受到严重威胁。威胁区域对空间中任意一点的威胁代价用式（11）进行计算：

式中，fi（pi）表示第j 个威胁区对空间中任意一点pi的威胁值；Kj表示第j 个威胁区的威胁等级；dij表示空间中点pi到第j 个威胁区中心点的距离；a，b 为大于1 的威胁补偿系数，为常数。区分高、中、低3 个等级的威胁区，其威胁等级参数依次为3、2、1。而对于障碍物的简化模型圆域，则认为无人机不能穿过圆域，只能绕过障碍物飞行，即常数a 为一个无穷大的数。

由于在进行路径寻优是将路径分成由若干路径点连接而组成的路径段，因此，对于计算威胁（障碍）区域的代价，需要依次对每个路径段上的每一点相对于每一个威胁（障碍）区的代价值进行计算，再进行求和，即为总路径的代价。

式中，fi为路径上各点的威胁（障碍）区代价。为计算方便，每段路径通过采取样点的方式进行简化处理来计算路径段的威胁（障碍）代价［17］，具体做法如图3 所示。

图3 子路径威胁计算示意图Fig.3 Schematic diagram of sub-route threat calculation

将每一个路径段进行10 等分，取1/10 处、3/10处、5/10 处、7/10 处、9/10 处这5 个位置节点的坐标，分别计算各威胁区域对这些点的威胁代价函数值，再求和取均值作为该段路径相对于飞行环境中所有威胁区域对每一点的威胁代价函数值的平均值，再乘以该段路径长度，即为该段路径的威胁代价函数数值，计算式如下：

式中，N 为威胁区域总个数；li为第i 段路径的长度。而对于障碍物区域的代价计算同理，在此不作赘述。

2.3.2 转向代价

无人机在经过转向时必然会进行转向或者垂直运动，这又会使得无人机造成不必要的耗时，因此，将相邻两端的路径段的夹角作为目标函数的一项因素，如图4 所示，求出在整个路径中，无人机的转向角度总和，并且使得其函数值最小，计算如下。

图4 子路径转向角计算示意图Fig.4 Sub-path steering angle calculation diagram

2.3.3 耗电（耗油）代价

旋翼无人机在任务过程中的耗电（耗油）量由飞行距离与飞行速度决定，但在本文中，认为无人机在整个飞行过程中保持匀速飞行，因此，对于将路径最短作为耗电（耗油）代价即可。

综上所述，在路径规划的目标函数为：

3 路径规划算法

3.1 蜜源初始化

本文将无人机路径用矢量法进行表示。初始时刻，蜜蜂均为侦察蜂，随机搜索蜜源，即在n=0 时刻随

上述各行向量所代表的路径点共同构成一条路径，分别计算这些路径的目标函数值，并进行排序，取目标函数值前一半较小的前半数路径所对应的蜜蜂作为初始的采蜜蜂种群。

3.2 动态评价选择机制

引入动态评价机制［18］。通过蜜源邻域搜索后的“蜜源”动态变化情况来改进观察蜂跟随机制，使得每次蜜源的更新建立在有连续优化的历史基础上，让蜜源的更新迭代指导蜂群算法的寻优过程。蜜源动态评价的评估积分值为DE1（i）和DE2（i）。蜜源的位置i 被更优的蜜源位置替换时，DE2（i）按照式（21）进行计算，此时，DE1（i）被赋值为0；而当蜜源的位置i 保持不变时，DE1（i）按照式（22）进行计算，DE2（i）赋值为0。

式中，DE1（i）为蜜源位置邻域内被连续搜索但并没有接受新的蜜源位置的次数，DE2（i）为蜜源i 位置邻域内被连续搜索并且接受新的蜜源位置的次数，lim it 为搜索限定次数（动态更新限制参数）。

根据上述动态评价准则，建立动态评价函数F（i），当蜜源的DE1（i）=0 时，说明蜜源已经被连续优化多次，认为蜜源仍然具有很大的活力，其位置附近可能还会存在更优的蜜源，需要在其邻域内进行搜索；而当蜜源的DE1（i）≠0 时，说明蜜源在该位置附近已经连续被搜索多次但并没有更新蜜源的位置，此时可能已经达到局部最优，蜜源已经失去了活力，需要及时跳出该区域，不应该再进行蜜源的开发。通过动态评价函数F（i）计算蜜源的累加值，以50 分作为标准基础值，当被连续优化的蜜源积分超过50 分时，说明该蜜源被观察蜂选中跟随的概率会较大一些；当未被连续优化的蜜源个体积分少于50 分时，跟随的概率会较小一些。观察蜂的跟随概率计算如下式。

3.3 新蜜源的搜索

传统的人工蜂群算法在对蜜源进行邻域搜索时并不能利用已有的最优蜜源信息，仅仅只是考虑解空间的范围，使得算法的性能较差。ZHU 和KWONG 参照粒子群算法提出全局人工蜂群算法，利用每次迭代完成后产生的一个较优解作为一个暂时的全局最优值，来引导蜜蜂种群对蜜源的邻域搜索［19］，其搜索式如式（25）。算法过程中通过调节β 的值来增强算法的寻优能力。

因此，本文在算法设计中，经过初始化之后，对于蜜源的邻域搜索采用下式进行，通过对蜜源的邻域搜索操作，以临时的最优蜜源来引导蜂群整体寻优。

3.4 Metropolis 准则

Metropolis 准则的一个优势在于对于一个新状态的替换是以一定的概率进行的，基于此，算法更容易跳出局部最优，概率Pij定义如下：

其中，i 为当前状态，j 为其邻域中的一个状态，其目标函数值分别为f（i）和f（j），当前温度为T。可见，当邻域新解优于当前解时，当前解将被无条件替换；反之，当前解将以一定的概率被新解替换。

由于人工蜂群算法在更新种群中被淘汰的采蜜蜂随机初始化以执行全局探测任务，在观察蜂分配中由于要和进化多代的采蜜蜂进行比较，随机化个体胜出的概率很小，很难在下一代存活［19］。根据Metropolis 准则的替换概率计算式可以看出，引入Metropolis 准则可以使算法既具备跳出局部最优解的能力，又具备探索全局最优的能力，使得在迭代循环的次数增加后，算法可以在较优蜜源附近的局部空间内进行更加精确的搜索［19］。蜜蜂放弃当前蜜源转变为侦察蜂的转移概率计算如下：

式中，o 表示当前所处的蜜源；n 表示开采到的新蜜源；降温函数为：

式中，σ 为退火函数系数，一般取0.8 左右。

3.5 旋翼无人机路径寻优算法步骤

根据上述分析，整个算法流程图如图5 所示。

图5 旋翼无人机路径寻优算法流程图Fig.5 Flow chart of route optimization algorithm for rotor unmanned aircrafts

算法的具体步骤如下所示：

1）蜂群初始化：蜜蜂种群的总数为NP（观察蜂、采蜜蜂各占一半），单次迭代的最大搜索次数为Limit，迭代搜索记录量为iter=0，最大迭代次数为maxCycle 以及对应的路径点数量、Metropolis 参数；

2）坐标系的转换，等分路径规划的起点终点的连线线段，各路径点在过每一个等分点的垂线进行选择，由这些点到连线线段的距离所组成的向量便可构成一条路径的解向量；

3）初始化蜜源。根据初始化函数生成一个D·NP 矩阵表示初始蜜源，矩阵中每一行表示一条路径，而每一条路径中的每个数是在前一个数的基础上按照相应的搜索策略而随机产生的，随后计算每一条路径的目标函数值；

4）确定采蜜蜂，并由采蜜蜂进行邻域搜索；

5）对于新蜜源，按照Metroplis 准则判定其被接受的概率，并根据动态评价指标计算观察蜂跟随采蜜蜂的概率；

6）采蜜蜂放弃当前蜜源，转换为侦察蜂再次随机搜索新蜜源；

7）经过上述操作后对路径进行更新；

8）对更新后的路径计算路径的目标函数值，找出本次的最优路径并记录；

9）判断循环条件，若满足终止条件，则推出算法，反之，再次进行循环执行步骤4）；

10）进行坐标反算并输出算法结果，算法结束。

4 路径寻优结果仿真及分析

4.1 路径寻优结果仿真

利用python 编程仿真，对上述设计算法的可行性进行验证，算法初始参数值为：初始化蜜蜂总数为40（侦察蜂数量设置为10），路径点总数为21，最大迭代次数为600，单次迭代的最大搜索次数为8，单个路径点的搜索范围为［-20，20］，威胁（障碍）区的主要参数如表2 所示。

表2 仿真案例的威胁（障碍）区主要参数Table 2 Main parameters of threat（obstacle）zone of simulation case

路径寻优算法结果如下页图6 所示，收敛曲线如图7 所示。通过仿真结果能够明显看出，该算法完全可以实现对障碍区域的规避，以及针对威胁区域威胁代价的计算和其他区域计算结果进行比较，从而综合选择最优路径结果；通过收敛曲线图，算法具有较快的收敛速度，算法性能较好。

图6 旋翼无人机路径寻优算法仿真结果示意Fig.6 Schematic diagram of simulation results of route optimization algorithm for rotor unmanned aircrafts

图7 旋翼无人机路径寻优算法收敛曲线Fig.7 Diagram of simulation result of path optimization algorithm for rotorcraft

4.2 路径寻优结果分析

4.2.1 起点和终点变化对航迹规划的影响

为研究算法的灵活性，通过选择不同的起点与终点，检验算法在同一环境下对不同规划任务（不同的起点与终点）的规划性能。为此，保持规划环境不变，改变起点与终点，并对各个不同的起点与终点下其规划航迹的可行性进行判断。

表3 二维环境下的起点与终点变化时算法参数Table 3 Algorithm parameters when the starting points and the ending points change in two-dimensional environment

规划环境与图6 所示环境相同，依据环境特点选定4 组不同的起点与终点坐标，各组坐标关系如表4 所示。

表4 二维环境下不同的起点和终点组合Table 4 Different combinations of starting and ending points in two-dimensional environment

在二维航迹规划环境下分别对上述4 组起止点进行航迹规划，每组运行15 次，图8 是各情况下的最优航迹仿真结果。根据仿真结果可以看出，利用本文上述分析的人工蜂群的二维航迹规划算法，在起点和终点变化时，都可以找到最优航迹，同时，根据各组坐标的关系可以得出，针对二维规划环境，此算法可以适用于已知规划环境下的全方位航迹规划。

图8 起点和终点变化时的算法仿真结果Fig.8 Algorithm simulation results when the starting points and the ending points change

图9 两种算法优化过程比较Fig.9 Comparison of optimization processes of two kinds of algorithms

4.2.2 算法评价

对于算法的评价一般从高效、健壮、可读和正确性等方面进行考虑。结合本文的研究内容以及人工蜂群算法的相关特点，引入稳定性和误差率两个指标对航迹规划算法进行评价［20］，利用传统的人工蜂群算法与本文的改进算法在同一规划环境下进行航迹规划，算法各自的参数均相同，分别运行20 次，统计算法运行结果如表5 所示，并展开分析。

表5 同一规划环境下两种算法寻优结果统计Table 5 Statistics of optimization results of two algorithms under the same planning environment

1）稳定性

表6 列出了对两种算法分别运行20 次以后的目标函数值的统计分析结果，其中，样本最大值为Smax，最小值为Smin，样本绝对误差表示如下：

表6 算法稳定性分析统计结果Table 6 Statistical results of algorithm stability analysis

样本均值的计算式为：

样本标准差的计算式为：

图10 两种算法优化航迹比较Fig.10 Comparison of optimized tracks of two algorithms

通过分析可以看出，本文所提出的人工蜂群算法无论是从寻优结果的角度，还是寻优的稳定性角度均优于传统的人工蜂群算法，算法具有相当大的可靠度，能够达到预期目的。

2）误差率

为研究算法对问题的优化程度，本文引入误差率的概念，即样本均值对理论优化值的偏离程度，若误差率越小表示算法所求解越接近理论最优值，误差率计算公式为：

式中，S*是理论最优值，在文中用样本结果中目标函数最小值作为理论最优值。各算法的规划误差率如表7 所示。

表7 算法误差率分析统计结果Table 7 Statistical results of algorithm error rate analysis

通过分析可以看出，本文所提出的人工蜂群算法，从寻优误差率的角度看明显优于传统的人工蜂群算法，算法的误差率极低，性能达到预期目的。

5 结论

本文利用人工蜂群算法对旋翼无人机的路径寻优问题进行研究分析，基于人工蜂群算法基本原理和旋翼无人机飞行性能分析，通过算法的设计，分别研究了旋翼无人机的路径规划问题，并对算法作出必要的分析与评价。

针对无人机飞行环境中可能遇到的各种威胁与障碍，本文主要利用圆形对环境进行简化，区分威胁与障碍两类区域，并将每个威胁类区域划分为1、2、3 三类等级，对应由低到高威胁程度依次增大。综合分析旋翼无人机飞行过程中的约束条件（包括最小和最长路径长度、转向代价、能源供应和威胁代价等），以距离最短、威胁代价最小和转向代价最小为目标，并通过加权的方法，根据任务性质的不同对上述3 个目标因子分配不同的权重，以此建立旋翼无人机路径规划问题的目标函数，并采用路径分节处理的方式解决路径问题，在处理过程中进行坐标转换，以起点与终点连线为轴建立直角坐标系以简化计算。在仿真过程中，针对算法开发能力和全局性较弱这一缺点，采用动态评价选择机制与Metropolis 准则，提高了路径求解的准确性。