四种智能仿生学算法的无人机航路规划应用对比

王怡翔，李姮，王家怡，张祖铭，叶朝洁，蔡洋洋

（1.桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004；2.桂林电子科技大学 电子工程与自动化学院，广西 桂林 541004；3.桂林电子科技大学 生命与环境科学学院，广西 桂林 541004）

0 引言

随着无线电控制技术的发展与计算机技术的兴起与融合，轻小型无人机在环境监测、地质勘探、城市规划以及安防巡检等众多工业领域具有广阔的发展空间[1]。执飞不同工作任务的工业无人机工作环境错综复杂，合理快速的航线路径规划可增强无人机在不同应用环境的时效性、安全性和适应性。而如何根据外部环境信息为无人机寻求一个或多个相对最优航迹路线，躲避障碍和威胁区域，是实现无人机航路规划的关键。

基于生物群体社会学以及自然规律的智能仿生学算法具有较强的自适应能力，可解决复杂优化等问题。将这些生物群体行为融入到航路规划问题的求解过程中，用以进一步提高无人机航路规划的性能。其中常见的智能仿生学算法主要包括粒子群算法[2]、遗传算法[3]、蚁群算法[4]以及人工蜂群算法[5]等。本文分析常见的智能仿生学优化技术的算法原理，对基于智能仿生学算法无人机航路规划进行归纳整理。综合比对各类优化算法的优缺点，为无人机航路规划提供参考。

1 基于粒子群算法的无人机航路规划

粒子群算法是受飞鸟集群觅食活动规律启发而提出的一种智能仿生演化算法。该算法以随机全局搜索为特征，将搜索空间的飞鸟群抽象为粒子，每个粒子包含有适度函数、确定飞行方向的位移矢量和确定距离的速度矢量等参数变量，算法实现过程如图1所示。该算法通过反复迭代更新粒子群，以群体粒子之间的合作与竞争产生的群体智指导优化搜索，求解输出最优路径。

图1 粒子群算法流程

粒子群算法具有简洁性、易实现、高精度、参数便于调整、运算速度快等优点，因而在无人机飞行路线规划中得到有广泛应用。徐利峰等[6]采用混合粒子群算法对植保无人机路径点进行排序，为农作物喷药的全自动化提供新方向；Góez等[7]采用粒子群优化算法分段改变惯性权重，并采用微控制器对算法改进，为无人机在线航路规划技术提供解决方案。

在规划航路的过程中，粒子群算法因算法随机性较差，导致在迭代过程中容易陷入局部最优，使得无人机避障系统无法选取全局最优解。如何优化粒子群算法，尽可能避免迭代过程陷入局部最优值，使之适用于无人机航路规划是当下粒子群算法的研究热点，目前已有众多研究者对此进行优化。赵艳丽等[8]将柯西分布扰动引入量子粒子群算法，提高算法的收敛速度与搜索能力；方群等[9]通过惯性权值改变算法，提高了无人机三维航迹规划算法的稳定性，同时避免算法陷入局部最优；张建南等[10]将自然选择思想与粒子群算法结合，同时引入惯性权重，缩小了最优航线的搜索范围，为避免算法陷入局部最优值提供解决方案。

与其他算法相比，粒子群算法易于建模且便于计算，主要用于实现复杂环境下无人机的最优航路规划，但是粒子群算法的输出结果易陷入局部最优值。对该算法在无人机避障的应用场景中进行改进与优化是当下的热点问题。

2 基于遗传算法的无人机航路规划

遗传算法是基于生物进化论的自然选择和遗传学机理求解最优解的智能仿生进化算法，以随机全局搜索为特点，基于“适者生存”的原则，完成“优胜劣汰”的自然选择并提高种群适应度，其算法实现如图2所示。该算法通过计算分析无人机航路关键参数的约束条件，采用对基因编码种群初始化、对个体性能评价的适应度函数构造与解码分析的三步骤运算，可在迭代过程中实现自适应，计算输出无人机最优运行轨迹。

图2 遗传算法实现流程

遗传算法作为一种非确定性的拟自然全局搜索算法，算法简单可解决非线性问题，为复杂系统的优化提供了一种新方法。目前，众多研究者将遗传算法融入到无人机航路规划中：王娜等[11]将遗传算法应用到农用无人机航路规划中，避免了无人机误撞障碍物的现象发生；方伟等[12]采用左、右部分匹配交叉法改良染色体交叉方式，并且采用翻转突变法与两点交换法提高染色体变异的多样性，有效解决了无人机对海侦察航路规划问题；Vahid等[13]将并行遗传算法应用于多维控制器环境中，实现无人机平滑航路规划。

在无人机避障场景中，遗传算法的局部寻优精度较低，稳定性较差。针对此问题，众多学者充分利用遗传算法具备良好扩展性的特点，将其与其他算法进行融合，为算法的改进提供新的解决方案：鱼佳欣等[14]引进移民算子与人工选择算子实现多种群协同进化，提高了无人机航路规划的效率以及稳定性；李楠等[15]通过对自适应度高的个体进行复制增加改进选择过程，提高寻优精度的同时增快了算法的迭代速度，为无人机三维航路的避障及航路规划提供解决方案；Yuan等[16]采用优良点集算法改良种群初始化，降低无人机航路规划陷入局部最优的风险。

遗传算法在无人机航路规划中具备良好的扩展性，可与其他算法相结合且不受到应用领域限制，具备快速搜寻能力。但是遗传算法实现过程复杂，搜索效率相对较低，其最终结果对变异率、交叉率以及适应度等参数具有较强的依赖，因而如何在加快求解速度的同时提高优良个体的保留率是当下基于遗传算法的无人机航路规划中需解决的问题。

3 基于蚁群算法的无人机航路规划

蚁群算法是来源自蚂蚁集体寻径觅食行为启发而提出的智能仿生学算法。该算法模拟蚂蚁选择最短路径的行为过程，其采用分布式种群搜索策略求解问题的最优解，算法流程如图3所示。该算法实现主要分为数据初始化、信息素更新以及路径选择3个部分。其中数据初始化负责实现环境变量的设置以及新代蚂蚁的生成；信息素更新依赖预先设置的限制性条件，满足率越高，信息素生成越多。其中信息素是蚁群之间进行沟通的化学物质，负责导向蚁群的行进路线；以路径上的信息素含量为依据进行路径选择，对于信息素含量越高的路径，该路径的被选择概率越大，最终通过循环判断实现最优航线的确定。

图3 蚁群算法实现流程

蚁群算法是无人机航路规划中的常用算法，在无人机航路规划已取得广泛应用：唐立等[17]将泰森多边形作为算法的初始解，以躲避山区障碍物为限制性条件，提高无人机在山区对障碍物的躲避能力；王宇等[18]将无人机在二维坐标的作业路径离散化并采用插值的方式求取其三维作业航迹，提高了植保无人机应对含有障碍物的复杂地形的适应能力；袁梦婷等[19]采用综合启发的方式改良蚁群算法的状态转移函数，通过离散化的方式规划无人机遇到障碍时的解脱路径；Guo等[20]在信息素更新规则中加入碰撞威胁代价和路径长度，解决了传统蚁群算法仅可优化单个目标的问题，为无人机在复杂环境下障碍躲避提供一种可行有效的解决方案。

蚁群算法采用局部正反馈机制，不易陷入局部最优，但是该算法收敛速度较慢，寻优时间较长。提高蚁群算法的收敛速度，降低算法运行时间是此算法的未来发展方向。众多研究者对于该算法应用于无人机航路规划中提出对应的解决方案：曹建秋等[21]使用A*算法实现初始化并且采用Dubins曲线对三维路线进行平滑处理，提高了收敛速度的同时实现可针对多目标的无人机三维航路规划；Yang等[22]将蚁群算法应用到数字地形建模，在保证不损坏模型的情况下，大幅提高了图像采集的工作效率。

蚁群算法采用了分布式正反馈机制感知局部信息，与其他智能仿生学算法相比，蚁群算法的计算效率高，更适用于三维地图的无人机航路规划。但是该算法的收敛性易受到初始化参数的影响，容易出现停滞现象。

4 基于人工蜂群算法的无人机航路规划

人工蜂群算法是启发于蜂群自发性分工协作高效采蜜行为而提出的智能仿生学算法。该算法将蜜源的位置作为问题的可行解，模拟蜜蜂采蜜机理可实现局部寻优。蜂种之间的身份转换是该算法的核心部分，其实现原理如图4所示。在算法中设置了观察、侦察以及采蜜共三个不同类型的蜂种，其中采蜜蜂负责招募观察蜂并收集问题的可行解；观察蜂可接收采蜜蜂传播的信息，随机跟随一只采蜜蜂并实现身份转换加入其中；侦察蜂随机生成满足条件的可行解，可实现结果的多样性。

图4 人工蜂群算法蜂种转换原理

人工蜂群算法只以适应度函数作为搜索过程中的进化依据，具备易于操作、搜索精度较高、控制参数简单、鲁棒性较强的特点。目前人工蜂群算法已被广泛应用于无人机航路规划中：徐流沙等[23]采用差分进化算法对侦察阶段进行改良，为高维度无人机航线规划提供了有效的解决方案；Ding等[24]提出了一种概率缩放自适应人工蜂群算法，实现无人机避障的同时极大地减少了燃油的消耗。

人工蜂群算法参数依赖性较低，算法实现相对简单，但是该算法在后期存在易陷入局部最优且收敛速度慢等问题。如何对算法进行优化，提高后期收敛速度是当前人工蜂群算法的热点问题。目前已经有众多研究者对该算法在无人机避障的应用中进行改良：刘琨等[25]将禁忌搜索策略引入到侦察蜂中的搜索阶段，避免算法提前陷入局部最优解，提高了无人机的避障能力；王庆海等[26]通过引入动态评价策略以及Metropolis准则，有效改进了传统算法后期收敛速度较慢的问题，提高了无人机三维航线规划的鲁棒性以及收敛速度。

在无人机航路规划的应用场景下，人工蜂群算法相比于其他智能仿生学算法，具有操作简单、稳定性较强以及应用范围广等优点。然而该算法在迭代的过程同样会陷入局部最优，对此类问题的解决是当下基于人工蜂群算法的无人机航路规划的关键。

5 结语

相比于其他优化算法，智能仿生学算法具有鲁棒性强、灵活性高以及优化结果全面等优点，目前此类算法在无人机航路规划中得以广泛应用。综上所述，4种常见的智能仿生学算法，都适用二/三维度，都是全局搜索方式。优点方面，粒子群算法复杂度低，具有记忆性，航路规划速度快；遗传算法具有扩展性，适合复杂航路规划，搜索能力强；蚁群算法采用正反馈机制，鲁棒性强，航路规划准确度高；人工蜂群算法操作简单，易于实现，参数依赖性低。缺点方面，粒子群算法不确定性较大，容易陷入局部最优，航路规划准确性低；遗传算法寻优精度低，稳定性差，控制参数较多，航路规划速度慢；蚁群算法收敛性较低，航路规划速度慢，易出现停滞现象；人工蜂群算法易陷入局部最优。

智能仿生学算法在满足限制性条件的同时可实现无人机航线的规划，但是无人机航路规划实现会受到包括气象，地势以及飞行高度等限制性飞行条件约束，存在多样性与不确定性。单一的智能仿生学算法因算法原理不同导致本身性质有所差异，只能在特定条件下做出最优航路规划决策。组合优化算法将不同的智能仿生学算法进行调整与融合，可以提高算法的适应度，是未来无人机航路规划的发展趋势。