贺井然，何广军，于学生

（1.空军工程大学防空反导学院，西安 710043；2.解放军95607 部队，成都 610066）

0 引言

在解决无人机的路径规划问题方面，学者提出了如人工势场法、模拟退火法、模糊逻辑法等算法［1］。肖玉婷等［2］提出了一种基于分块优化思想的覆盖路径规划方法，将大规模环境分块优化，减小了计算量，能适应多种形状区域；刘畅等［3］人提出了一种基于模糊推理机制的逻辑架构设计，运用可变自主OOADA 循环动态分配人机权限，实现了复杂威胁环境下实时航迹规划。近年来，蚁群算法、粒子群算法等群智能算法也被用于解决无人机路径规划的问题［4-5］。夏瑞等［6］提出一种基于人工蜂群算法的非确定性双向规划机制搜索算法，大大提高了产生航迹的质量；王庆海［7］引入动态评价策略、模拟退火准则和复合型优化算法结构，对人工蜂群算法进行改进，提高了算法的优化效率；本文采用改进蜂群算法研究无人机路径规划问题。

1 相关算法简介

1.1 人工蜂群算法

人工蜂群算法（ABC）是一种仿生群智能算法，通过模拟蜜蜂寻找花蜜的方式来寻找最优解，以蜜源表示可能存在的解，以蜂蜜量表示解的适应度。初始化阶段，确定种群数量N，蜜源维数D，随机生成初始蜜源，并计算适应度fiti的值。公式如下：

式中，xij表示第i 个蜜源的第j 维，i=1，2，3…，N，j=1，2，3…，D，xu表示蜜源允许的最大值，xl表示蜜源允许的最小值，fi表示解对应的函数值。

采蜜蜂阶段，在初始蜜源附近寻找新的蜜源，根据适应度大小选择是否替换蜜源。

观察蜂阶段，根据更新后蜜源的适应度，观察蜂按照轮盘赌规则选择跟随的采蜜蜂，pi表示选取第i 个蜜源的概率。

侦察蜂阶段，如果一个蜜源开采次数达到上限仍然没有更新，则放弃该蜜源，并在解空间中重新寻找蜜源。

1.2 K 均值聚类算法

对于一样本x={xi∈R，i=1，2，…，n}，x 为一个d维向量。可以将样本划分为k 个不同的类别C={C1，C2，…，Ck}，其中，每一个类都有一个聚类中心，聚类中心计算公式如下：

式中，d（xi，Cj）表示聚类中心Cj与类中元素xi的距离，J 表示各类内距的和。

2 改进人工蜂群算法

尽管人工蜂群算法具有良好的全局搜索能力和高鲁棒性等优点，但是该算法容易早熟，后期收敛速度低，针对这些问题，本文使用K 均值聚类算法（KMC）对原始人工蜂群算法进行改进［8］。原始蜂群算法初始种群全部随机生成，因此，需要采用最大最小距离积法对初始种群分散，克服初始种群的随机性。KMC 算法根据样本之间的相似度将样本分为多个类，相同类的样本具有尽可能高的相似度，不同类的样本具有尽可能低的相似度，该算法具有聚类快速，局部搜索能力强的特点，能有效地解决蜂群算法后期收敛速度低的问题。

2.1 最大最小距离积法初始化

原始蜂群算法中，初始种群随机产生，具有很强的随机性，如果初始种群过于密集，会影响算法的全局搜索能力，容易陷入局部最优。本文采用最大最小距离积法对随机种群进行初始化，降低初始种群的随机性。

设需要选取k 个初始点，第1 步在初始种群C中随机选择一个元素x1作为第1 个初始点，然后将x1移动到集合D 中。第2 步计算更新后C 中元素到x1的距离，选取其中距离最大的元素x2移动到D中。第3 步分别计算更新后C 中剩余元素到集合D中每一个元素的距离d，计算C 中元素对应d 的最大值和最小值的乘积，选取其中乘积最大的一个元素移动到D 中，重复此步骤直到选取足够的初始点。第4 步输出集合D。

通过以上步骤，将随机生成地初始种群分散处理，避免了随机生成种群过于密集的问题。

2.2 K 均值聚类改进蜂群算法

K 均值聚类改进蜂群算法（KMC 改进蜂群算法）的基本思想是，将每次人工蜂群算法迭代得到的蜜源作为KMC 算法的初始点，对蜜源进行聚类，聚类完成后再将更新后的中心更新蜜源。将KMC和ABC 两种算法交替执行，直到算法结束。

KMC 改进蜂群算法的步骤如下：

第1 步：设置初始种群数量、采蜜蜂和观察蜂的数量，蜜源最大开采数量、最大循环次数、聚类类别数，其中采蜜蜂和观察蜂各占种群数量的一半，聚类类别数和根据式（1）随机生成初始种群，并运用最大最小距离积法对生成的初始种群进行初始化。

第2 步：对初始化后的种群进行聚类划分，并计算种群的适应度，按照适应度排序，适应度大的一半种群设置为采蜜蜂，另一半设置为观察蜂。

第3 步：按照式（3）在采蜜蜂现有蜜源的领域进行搜索，用适应度高的蜜源更新现有蜜源，观察蜂按照轮盘赌规则跟随采蜜蜂。

第4 步：再次对蜜源进行聚类划分，用新的聚类中心更新蜜源。如果一个蜜源开采次数达到最大次数还没有更新，则放弃该蜜源，对应的蜜蜂转化为侦察蜂。

第5 步：判断是否达到最大循环次数，如果没有则返回第2 步，如果达到则输出适应度最高的蜜源，算法结束。

图1 KMC 改进蜂群算法流程图

3 问题描述

3.1 建立环境模型

无人机在实际执行任务中，往往会遇到非常复杂的环境情况，如楼房、树木等障碍，雷达、敌机等威胁，不适宜飞行的区域等。在模型建立中往往难以准确地表达出不同的环境因素，本文将所有不可飞行区域等效为障碍物表示，这样无人机在复杂环境下的航迹规划问题就简化成了避障路线的问题。

3.2 代价函数

无人机航迹规划就是要找出一条由起点到终点的最优航迹，即无人机按照这一条航迹行动代价最低。无人机的航迹可以看作是多段折线，为了方便建模，将无人机的航迹简化为多个矢量的和。设无人机航迹通过M 个节点，每个节点对应矢量XM，则无人机航迹可以用一组矢量来表示：

式中，X 表示无人机的航迹，Xm表示无人机到达第m 个节点的矢量，（am，bm）表示节点坐标。

无人机在实际执行任务时，受限于携带燃料，作业时间有限。因此，在航迹规划中要求航迹长度尽可能短，以保证无人机有足够的燃料和时间执行相关任务。无人机在节点处需要转向调整，在转向中同样需要耗费燃料，我们希望无人机总体的转向角度较小。由上述可以得出无人机的代价函数如下：

式中，P1表示无人机的距离代价，P2表示无人机的转向代价。|θm|表示无人机在第m 个节点的转向角度的绝对值，cost1表示无人机前进产生的能耗，cost2表示无人机旋转所产生的能耗，ω1，ω2为距离代价和转向代价的能耗系数，取值按文献［9］中由实验方法得到：ω1=0.107 2，ω2=0.010 4。无人机的总代价为：

无人机的总代价为：

4 仿真实例

设种群数量为20，采蜜蜂和观察蜂的数量均为10，最大循环次数为2 000，蜜源开采上限为100，节点数设置为10，在100*100 范围内进行路径规划，起点和终点坐标分别为（0，0）和（100，100）。障碍物数量为8，位置和半径由程序随机给出。仿真结果如图2、图3 所示。

图2 原始蜂群算法最优路径

图3 KMC 改进蜂群算法最优路径

单次寻优的代价函数值如表1 所示。

表1 ABC 算法代价函数值

由表1 结果可知，原始蜂群算法在循环500 次时代价函数值达到最小值16.079 5，其后代价函数没有继续降低。KMC 改进蜂群算法代价函数值在1 700 次循环时达到最小值15.709 6，由于蜂群算法具有随机性，对两种算法分别运行10 次，计算两种算法得出的最优解的平均值。运行结果如表2所示。

表2 多次寻优结果

经过10 次运行，原始蜂群算法得到的代价函数值的平均值为：16.097 56，KMC 改进蜂群算法得到的代价函数值的平均值为：15.890 97。

5 结论

在原本的蜂群算法中嵌入KMC 聚类算法，使种群更新后分布更加分散，降低了随机性对算法的影响，并提高了算法后期的收敛速度。将该算法应用到无人机路径规划问题上，仿真结果表明该算法能有效地解决无人机路径规划问题，求解过程中改进算法收敛速度更快，后期局部搜索能力更强，求出的路径相比原始蜂群算法路径长度更短，转角总和更低，花费代价更小，并且在多次寻优中得到的解的平均质量更好。