基于改进人工蜂群算法的无人机路径规划研究

Research on UAV Path Planning Based on Improved Artificial Bee Colony Algorithm

摘要: 针对传统无人机路径规划算法存在收敛速度慢、效率低以及易陷入局部最优的缺点，本文提出了一种改进的人工蜂群路径规划算法。首先利用佳点集的方式生成初代蜜源位置，保证蜜源信息的多样性和均匀性；接着在采蜜蜂搜索机制中引入自适应动态调节因子，加强了算法前期的全局寻优能力和后期的局部寻优能力；最后，采用大步长搜索机制加强侦查蜂的寻优效果。仿真结果显示，改进后的算法寻优能力得到了显著的提高。

Abstract: Aiming at the shortcomings of traditional UAV path planning algorithm, such as slow convergence speed, low efficiency and easy to fall into local optimum, this paper proposes an improved artificial bee colony path planning algorithm. First, the location of the first-generation nectar source is generated by the method of good point set to ensure the diversity and uniformity of nectar source information; then, an adaptive dynamic adjustment factor is introduced into the bee-picking search mechanism, which strengthens the global optimization ability in the early stage of the algorithm and the local search in the later stage. Finally, a large-step search mechanism is used to enhance the optimization effect of scout bees. The simulation results show that the optimization ability of the improved algorithm has been significantly improved.

1. 引言

近年来，无人机因其具有体积小、机动性强、便于携带多种传感器等优点，被广泛应用到了多个领域。面对复杂的任务环境，无人机能否顺利完成任务的关键在于规划一条航程短、威胁代价低、可飞行的路径，而要实现这个目标，无人机必须具备自主飞行能力，根据实时的环境数据做出实时的判断规避各种障碍物，从而可以实现动态路径规划。这个过程中，无人机路径规划算法的研究尤为重要。

目前，无人机路径规划算法主要分为两类，一类是经典的无人机路径规划算法，另一类是启发式无人机路径规划算法。经典的无人机路径规划算法主要包括人工势场算法(APF) [1]、模糊逻辑算法 [2]、快速扩展随机树算法(RRT) [3] 等，这一类算法主要适用于静态路径规划，面对突发的状况不能做出及时的反应，实用性比较差。启发式无人机路径规划算法主要包括A*算法 [4]、蚁群算法(ACO) [5]、粒子群算法(PSO) [6]、人工蜂群算法(ABC) [7] [8] [9] [10] [11] 等，这一类算法主要适用于动态路径规划，面对突发状况可以做出实时判断，规避掉障碍物，实时性和实用性都比较强。

人工蜂群算法(Artificial Bee Colony, ABC)于2005年被Karaboga提出，该算法具有全局寻优能力强、鲁棒性好、结构简单等优点，经常被应用于各种寻优问题中。但是面对相对复杂的环境，该算法也暴露了一些问题，比如局部寻优能力弱、耗时长、易早熟等问题。针对这些问题，学者们进行了大量的研究。文献 [7] 中，夏瑞等人通过改进蜜源的产生方式，以及优化下一个节点的产生结果，有效地提高了算法的搜索效率。文献 [8] 中，刘刚等人在传统人工蜂群算法基础上，对蜜源初始化方法进行改进，并提出了随机搜索与最优蜜源引导相结合的位置更新方式，提高了算法的收敛速度、稳定性以及局部寻优能力。文献 [9] 中，伍鹏飞等人通过使用Zaslavskii混沌映射公式对蜜源选择、搜索策略进行改进，改进后的算法在耗时以及寻优效果上得到了一定的提高。文献 [10] 中，华珊珊通过锦标赛算法实现选择过程，并提出了三种跟随蜂邻域搜索算法，提高了算法的收敛性。文献 [11] 中，杜康宇等人利用PSO中粒子位移的更新方式，改善了跟随蜂的搜索方式，提高了算法局部的搜索能力。

本文针对ABC算法局部搜索效率低、易早熟、收敛慢等问题，提出一种改进的人工蜂群算法。首先利用佳点集的方式生成初代蜜源位置，保证蜜源信息的多样性和均匀性；接着在采蜜蜂搜索机制中引入自适应动态调节因子，加强了算法前期的全局寻优能力和后期的局部寻优能力；最后，采用大步长搜索机制加强侦查蜂的寻优效果。仿真结果显示，改进后的算法寻优能力得到了显著的提高。

2. 三维环境建模

本文研究的环境模型为三维山地模型，考虑到实际山地环境中状况，本文使用三维高程图法对三维空间进行建模。三维高程图法是一种基于数学中指数函数形式的一种建模方式，通过使用指数函数数学模型图代替实际的山峰山谷，其山峰地图数学模型具体表示为：

$z\left(x,y\right)={\displaystyle {\sum }_{k=0}^n{h}_k}\exp \left[-{\left(\frac{x-x_k}{c}\right)}^2-{\left(\frac{y-y_k}{d}\right)}^2\right]$ (1)

其中，n表示山峰山谷的总个数；h_k为第k个山峰的高度；(x_k,y_k)表示第k个山峰的中心坐标；c和d分别代表第k个山峰沿x轴和y轴方向的坡度。

3. 人工蜂群路径规划算法

3.1. 基本人工蜂群算法

人工蜂群算法是一种模拟自然界中蜜蜂采蜜行为的优化算法。它的基本原理是蜜蜂在采蜜的时候，蜂群被分为采蜜蜂、跟随蜂和侦查蜂，采蜜蜂根据之前记忆中的蜜源信息进行邻域搜索，当完成这个过程后，采蜜蜂回到蜂房中与跟随蜂共享蜜源信息，跟随蜂根据轮盘赌法的方式选择其中一处蜜源进行邻域搜索，并将新搜索到的蜜源信息与之前的比较，若新蜜源量多与之前的蜜源量，则替换之前的蜜源信息，完成角色互换；反之，保持不变。当蜜源信息陷入局部最优时，侦察蜂启动，进行新一轮的邻域搜索，直到找到最优蜜源信息。具体的实现步骤为：

1) 生成初始蜜源位置。在D维空间中，随机生成N个蜜源位置 $X_i=\left(x_{i1},x_{i2},\cdots ,x_{iD}\right)$，生成的公式为：

$x_{ij}=x_{\min j}+rand\left(x_{\max j}-x_{\min j}\right)$ (2)

公式中，x_ij为第j维空间第i个蜜源位置，rand为随机数(0, 1)，x_{min j}和x_{max j}分别是第j维空间的上下界。

2) 采蜜蜂进行邻域搜索。采蜜蜂在初始蜜源周围进行邻域搜索，完成蜜源的更新，搜索方式为：

$y_{ij}=x_{ij}+rand\left(x_{ij}-x_{kj}\right)$ (3)

其中，y_ij代表新的蜜源位置，k是除了i之外的另一个采蜜蜂编号。

3) 跟随蜂跟进搜索。跟随蜂根据采蜜蜂提供的蜜源信息采用轮盘赌法的方式进行跟进搜索，蜜源量越大的蜜源越容易被选择，被选择的概率P_i为：

$P_i=fitnes{s}_i/{\displaystyle \underset{i=1}{\overset{N}{\sum }}fitnes{s}_i}$ (4)

其中，P_i为第i个蜜源被选择的概率，fitness_i为第i个蜜源的适应度值，与蜜源量息息相关，蜜源量越多，适应度值越大。

4) 侦查蜂全局搜索。当某一蜜源位置连续Ns次没有变化时，跟随蜂转换为侦查蜂，跳出局部最优进行全局搜索，以(2)式随机更新蜜源位置。

3.2. 改进人工蜂群算法

3.2.1. 改进蜜源生成方式

传统人工蜂群算法第一代蜜源位置都是随机生成的，均匀性多样性较差，前期耗时较长，需要扩大搜索空间，迭代多次才可以找到最优位置。针对这种现象，本文采用佳点集的方式初始化第一代蜜源位置。佳点集是一种效率高、均匀性较好的选点方式，利用佳点集的这种优势，可以使初代蜜源位置更加均匀、更加具有多样性。

3.2.2. 改进采蜜蜂邻域搜索机制

初代蜜源位置生成后，采蜜蜂在蜜源位置周围进行随机的搜索，行为目的性比较盲目，寻优效果较差。本文在采蜜蜂搜索公式(3)中引入一个自适应动态调节因子β，以改善算法前后期的寻优效果。自适应动态调节因子β与改进后的公式为：

$\beta =\frac{iterMax-iter}{iterMax}$ (5)

$y_{ij}=x_{ij}+\beta \ast \left(x_{ij}-x_{kj}\right)$ (6)

其中，iterMax为最大迭代次数；iter为当前迭代次数。迭代初期，iter比较小，β比较大，y_i比较大，全局搜索能力比较强；迭代后期，β趋近于0，y_ij相对比较小，局部搜索能力比较强，很好的可以满足算法前后期的寻优。

3.2.3. 改进侦查蜂搜索机制

侦查蜂搜索时，抛弃原来的蜜源位置，从新进行随机搜索，既耗时也不利于得到更好的寻优效果。针对这种现象，本文提出一种大步长搜索方式，既可以跳出局部最优，也可以扩大搜索范围。大步长搜索公式为：

$x_{ij}=x_{ij}+\left(2\ast rand-1\right)\ast 0.5maprange\left(j\right)$ (7)

其中，maprange(j)表示第j维空间的搜索范围。

3.3. 改进后人工蜂群算法的步骤

步骤1：初始化相关参数，主要包括路径起始点、终点、最大迭代次数iterMax、蜂群总数N等。

步骤2：利用佳点集的方式生成第一代蜜源位置。

步骤3：采蜜蜂利用公式(6)在第一代蜜源位置进行邻域搜索，并更新蜜源位置。

步骤4：跟随蜂根据采蜜蜂提供的蜜源信息，利用轮盘赌法的方式完成邻域搜索，并更新蜜源位置。

步骤5：当某一蜜源位置Ns次没有更新时，抛弃该蜜源位置，侦查蜂利用大步长方式(6)从新更新蜜源位置。

步骤6：重复步骤1至5，直到达到最大迭代次数。

步骤7：完成迭代，输出迭代最优值。

4. 仿真结果分析

为了验证改进后人工蜂群算法的实用性与进步性，将改进后的算法与原来的算法在MATLAB 2016进行仿真对比。实验参数设置为：无人机飞行空域设置为100 × 100 × 100；地图山峰数量为20座；路径规划起点为(1, 1, 1)，终点为(95, 100, 50)；蜂群总数N = 100只，采蜜蜂和跟随蜂分别为50只；侦查蜂启动阈值Ns = 5次；最大迭代次数iterMax = 50次。

为了避免仿真实验数据的偶然性，本文在设计相同参数的情况下重复进行了60次仿真实验，仿真效果如图1、图2所示，相关对比数据如表1所示。

Table 1. Data comparison table of simulation results before and after ABC improvement

表1. ABC改进前后仿真结果数据对比表

Figure 1. Traditional ABC path planning renderings and optimal fitness curve

图1. 传统ABC路径规划效果图及最优适应度曲线图

Figure 2. Improved ABC path planning renderings and optimal fitness curve

图2. 改进ABC路径规划效果图及最优适应度曲线图

根据图1与图2中路径规划对比可知，传统的ABC规划的路径较长，飞行区域较大，耗时较长，平滑性较差；而改进后的算法路径规划效果明显的得到了改善，其不论是路径长度，还是飞行区域、平滑性等都得到了一定的提升。根据图1与图2中最优适应度图对比可知，相较于传统ABC，改进后的ABC得到的最优适应度值明显减小了，最优适应度值越小路径越短，因此改进后的算法路径规划效果更好。

根据表1中ABC改进前后仿真结果数据可知，传统ABC找到最优路径的最大迭代次数为50次，平均迭代次数为36次，最优适应度值为170，平均适应度值为185；而改进后的ABC最大迭代次数为49次，平均迭代次数为41次，最优适应度值为154，平均适应度值为176。通过这些数据分析可知，ABC改进前后找到最优解时最大迭代次数几乎没有变化，而平均迭代次数改进后的算法较改进前的多了5次，说明改进后算法后期更容易跳出局部最优，更容易找到最优解；最优适应度值改进后的算法较改进前的算法少了16，平均适应度值少了9，说明改进后的算法规划的路径更短、实用性更强。总体而言，改进的ABC较传统ABC无人机路径规划效率更高，路径更加短、更加平滑。

5. 结论

本文提出了一种改进的人工蜂群无人机路径优化算法。首先通过三维高程图的方式进行三维环境建模，验证算法的可行性；接着利用佳点集的方式生成初代蜜源位置，保证蜜源信息的多样性和均匀性；然后在采蜜蜂搜索机制中引入自适应动态调节因子，加强算法前期的全局寻优能力和后期的局部寻优能力；最后，采用大步长搜索机制加强侦查蜂的寻优效果。改进后的算法无论是在寻优精度，还是在寻优效率上都得到了一定的提高。但是，本算法只适用单无人机的路径规划，并不适用于多无人机的任务需求，同时面对更加复杂的环境路径规划效率还不够。因此，在接下来的工作中，可以将本优化算法拓展到更复杂、更真实的应用场景和多无人机的任务规划中。

基金项目

2021年天津市研究生科研创新项目(2021YJSS224)。

NOTES

^*通讯作者。