基于改进人工鱼群优化的蚁群算法无人机自主航路规划

马铭希，吴 军，岳龙飞，闫孟达，余稼洋

(1.空军工程大学 空管领航学院，西安 710051；2.空军工程大学 装备管理与无人机工程学院，西安 710051)

1 引言

蚁群算法(ant colony optimization，ACO)是于20世纪90年代意大利学者M.Dorigo等人受到蚂蚁觅食和返巢等行为的启发，提出的一种随机搜索模拟进化算法。具有参数数目少，设置简单，鲁棒性较强等优点，因此常被用于解决组合优化问题、连续时间系统优化问题等。相比于遗传算法、模拟退火算法、人工势场法、粒子群算法，蚁群算法有记忆性、更适于复杂问题求解、有明显的正反馈机制的优点。但是，在蚁群算法寻优的过程中也存在一些不足。比如，蚁群算法的初始信息素值相同，因此选择下一节点时采用随机选择，导致蚁群算法的收敛速度较慢；同时，蚁群算法容易陷入局部最优甚至出现停滞现象；还有蚁群算法在种群多样性与收敛速度上存在矛盾，当个体分布越均匀，种群多样性就越好，但与此同时收敛速度就越慢，当其分布越集中时，收敛速度加快，但是不利于算法的全局寻优。针对此类问题不少学者开展了相应的研究。

李静等为了增加路径的平滑程度，同时提高全局搜索能力，提出了用Logistic混沌扰动改进信息素的更新方式，但是该算法在初期阶段，没有对初始信息素浓度进行优化，虽然丰富了全局搜索空间，但同时也造成了无效搜索，降低了收敛速度；王苏彧等为加快蚁群算法的收敛速度与寻优能力，提出了基于自适应导向的蚁群算法。但是，该算法在陷入局部最优时并没有适当的策略可以使蚂蚁产生“逃逸”行为，跳出当前的局部陷阱；郭一聪等人利用改进势场法对无人机在三维空间上的飞行路径进行规划，使得传统人工算法中易陷入局部最小、局部路径震荡的问题得到了解决，但是无法避免人工势场法对复杂地形环境不适用性。

因此，针对目前研究中存在的收敛速度慢和全局寻优效果差的问题，本文提出了一种基于改进蚁群算法的无人机自主航路规划方法。首先通过调整对初始信息素浓度的分配，来减少算法初期的无效搜索；而后提出利用人工鱼群算法的视场机制与传统蚁群算法相结合，改变传统蚁群算法中仅依靠概率来选择搜索方向的方式，并通过在路径上添加“天敌”，使蚂蚁跳出局部最优的陷阱；利用Logistic混动扰动模型改进全局信息素搜索能力；再结合A算法改进传统蚁群算法的启发式函数，提升算法的搜索效率。最后，通过仿真实验验证算法的可行性。

2 路径规划地图建模

当无人机在执行任务时，为了简化模型，可将其视为在一定高度上的二维平面中的运动，因此可以运用栅格模型对飞行空域进行构造。栅格法即离散化处理，有着易于实用，便于工程化落地的优点。由于栅格法简单有效，能够适应较多的威胁模型，能够大大降低环境建模的难度。因此，本文采用栅格法对无人机的飞行环境进行简单仿真。将威胁存在范围内的栅格视作不可行栅格，在仿真程序中用1表示；威胁没有覆盖的栅格视作自由栅格，在仿真程序中用0表示。为了进一步简化计算，对威胁覆盖范围进行膨化，即将覆盖区域未满一个栅格的单元，将面积充满。同时，采用序号法和二维直角坐标系对应来对栅格进行标示。如图1所示，以10×10的栅格环境为例进行说明。

图1 栅格坐标与标号关系图Fig.1 Grid coordinate and label relationship

如图1所示，空白栅格表示自由栅格，蓝色栅格表示威胁覆盖的不可行栅格。地图按照从左至右的顺序对栅格进行编码，依次为1,2,3,…，一个编码对应一个栅格，坐标与栅格的标号关系如式(1)所示：

(1)

式(1)中:为取余函数，为向后取整函数，为栅格编号，为每一列栅格的数量，由式(1)所求即为栅格中心点的位置坐标。

通过栅格模型的构建，无人机执行任务进行的航迹规划转化为已知起始点E和目标点S，利用相关算法在自由栅格的集合中寻找有序排列的问题，而这些有序栅格的中心点坐标的连线段构成了无人机飞行的航迹。

3 蚁群算法的基本原理

3.1 基本原理

在自然界中，蚂蚁在觅食的过程中总是能找到食物源和蚁巢之间的最短路径，受到蚂蚁这种行为的启发，意大利学者M.Dorigo等首先提出了一种随机搜索模拟进化算法——基本蚁群算法。它模拟了蚂蚁在觅食和返回蚁巢途中“探索”的行为，即蚂蚁将使用感知到之前蚂蚁释放并遗留在途中的信息素，按照一定的概率选择接下来的路径并释放信息素。在这条路径中的信息素将会影响之后的蚂蚁。随着每条路径上的信息素积累、释放和挥发，引导着一个个蚂蚁进行路径的选择，而蚂蚁也总是趋向于选择信息素含量高的路径，久而久之，在蚂蚁觅食和返巢的路径中将出现一条最短的路径。

而意大利学者M.Dorigo正是利用这一行为特征，将其抽象形成了随机搜索模拟进化算法。假设在出发点和目标点之前存在若干干扰因素，在算法伊始，将只蚂蚁随机的放到个地点，并为相关的路径赋予信息素初值(0)=，每只蚂蚁将按照信息素含量和启发式信息独立的选择接下来的目标。在时刻，第只蚂蚁位于节点，它将以轮盘赌模型的方式选择下一目标节点，其状态转移概率为

其中:allowed为蚂蚁可以在下一步选择的节点集合；为路径(,)的信息素值；为信息素激励因子，它反映了信息素浓度对路径选择的重要性，的大小与重要性成正比；是预期的启发因子，它反映了启发式信息在路径上的重要性。越大则蚂蚁越倾向于选择最短路径；()为启发式值，表示蚂蚁从节点转移到目标节点的期望程度，如下式所示：

其中表示从节点到节点的欧氏距离。同时，每个蚂蚁在选择的路径行进的过程中也会释放出信息素，从而形成信息素的累计，为了防止信息素过多，导致启发信息泛滥，进而导致算法快速结束或者陷入局部最优。因此，在每个蚂蚁完成一次循环后，选择对信息素进行更新，更新公式如下所示：

(+1)=(1-)()+Δ

()

其中：为信息素的挥发系数，1-为信息素残留因子，Δ()为循环路径中的信息素增量，其计算方式如下：

其中：为蚂蚁在本次循环路径中路线的总长度，为循环一周的信息素总量。

在自然界中，鱼往往能够自行或者尾随其他鱼找到营养物质多的地方，人工鱼群算法(artificial fish swarms algorithm，AFSA)正是利用这一现象，创造了这一寻优算法。在人工鱼中封装了自身数据和一系列行为，它能够受到环境的刺激而做出反应。并且它是通过视觉来实现对外界的感知，在人工鱼群模型中：

=+*()

的方式实现虚拟视觉的模拟。其中()为随机函数，用来产生0～1之间的随机数，为步长。主要模拟了鱼类活动中觅食、群聚、追尾等行为，本文主要利用这3种行为中通过视觉探测进而选择行动方向和躲避天敌这2种方式来对蚁群算法进行优化。

3.2 改进蚁群算法

为了缩短基本蚁群算法搜索最优路径的时间，提高搜索路径的质量并且避免蚁群算法出现陷入局部最优的情况，本文对基本蚁群算法做出如下改进。

初始信息素的设定

基本蚁群算法在初始状态下信息素呈现均匀分布的状态，这就使得蚁群算法在搜索路径伊始可能出现与目标点反向的搜索路径，由此导致算法的搜索时间，迭代速度慢。为了解决算法在初期搜索的盲目性，缩短搜索时间，对路径进行预规划。首先，连接初始点E与目标点S，作为预规划路径，如图2所示，但是由于不可行栅格的存在，最优规划路径会在该直线附近波动，初始信息素浓度以预规划路径为中心向两边呈现出高斯分布，如图3所示。

图2 初始规划路径L0图Fig.2 Initial planning path L0

图3 初始信息素浓度分布示意图Fig.3 Schematic diagram of initial pheromone concentration distribution

初始信息素矩阵为，依据Toeplitz规律，沿对角线向两侧呈现正态分布。公式如下：

其中:为调整系数，的取值范围是[,+100]，为方差。由图可知，全局最优路径往往是在起始点与目标点连线附近波动的，因此，信息素浓度的不均匀分配能够减少蚂蚁的盲目搜索，有利于缩短迭代时间。

融合人工鱼群算法的搜索策略和信息素更新原则

1)搜索策略。当前蚁群算法及其优化算法在选择行动方向时仅仅取决于与当前位置相邻点的信息素浓度，这种做法不利于蚂蚁的快速觅食，同时降低了算法的收敛速度。

因此，结合人工鱼群算法的视觉特性以及觅食方式，提出新的觅食选择机制即视场搜索，该机制如图4所示。

图4 视场搜索机制示意图Fig.4 Schematic diagram of the field of view search mechanism

如图4所示，赋予每个蚂蚁一定半径的视场范围，可以使得蚂蚁在接下来的动作中没有障碍的到达下一目标节点。在二维空间内，距离可以用欧式距离来衡量，即：

其中:为蚂蚁现在所处的位置，为蚂蚁下一时刻可以选择的位置。在觅食阶段，每只蚂蚁在各自的视场范围内探测是否存在食物或者同伴占据过的更好地位置，一但发现，将采取如下行为：

=+*()

其中:表示蚂蚁的视场半径，()表示产生(0,1)之间的随机数。

2)局部优化。为了解决蚁群算法具有陷入局部最优解的缺点，在算法中设置迭代阈值，并赋予合适的范围，当迭代次数未超过，而路径长度却没有变化时，人工在蚂蚁视场范围内引入“天敌”。当天敌出现时，蚂蚁的视场变大(选用原视场的2倍)，加速逃离原视场范围，其数学模型如下：

≤(,)≤2

融合logistic混沌模型的全局信息素筛选

蚁群系统中，蚂蚁对于行动路线的选择在很大程度上是由路径上信息素浓度大小决定的。它的迭代过程对于初始状态较为敏感，初始信息素浓度的分布，直接影响了后续蚂蚁行动路线的选择。因此，蚁群系统可以被称为混沌系统。

混沌是来自与非线性动力系统，通过确定性方程获得运动状态的运动过程称为混沌，它是一种既普遍又复杂的现象。Logistic映射是简单的一维混沌映射，其解析式如下：

+1=**(1-)

其中，=0,1,2,…，∈[0,4]称为Logistic参数，{X|i=0,1,2,…}为初始X∈[0,1]时产生的序列。图5给出了不同初值和logistic参数条件的映射序列。

图5 Logistic映射分叉图Fig.5 Logistic map bifurcation graph

在经典蚁群算法中，当所有蚂蚁走完以后算法会把所有路径上的信息素进行更新，但是有些路径过长，会成为系统中的干扰因素，造成蚂蚁的无效搜索，因此要对路径上的信息素进行有选择的更新。

当蚂蚁完成一次觅食后将这次路径记录下来，而后将所有蚂蚁完成得路径按照长度从小到大进行排序，并求出其平均值。对于小于平均值的路径上的信息素进行直接更新；大于平均值的路径进行处理后更新其路径上的信息素。

假设是大于平均路径长度的路径个数，在中任意一条路径上的信息素浓度是，=1,2,3，…，，那么定义混沌变量：

代入Logistic混沌模型的迭代公式中：

+1=**(1-)，=0,1,2,…，

其中:和是条路径中信息素浓度的最大值和最小值，是混沌迭代次数。得到混沌序列：

=(,,,…,)

那么得到新的信息素为

,new=+(-)

因此，结合Logistic混沌模型后蚁群算法的全局信息素更新方式为

启发函数融合A算法

A算法是一种启发式遍历算法，它的估价函数构造为：初始状态到状态的实际代价与状态到目标状态的预估代价之和，数学表达式为

()=()+()

其中:()为从初始状态到目标状态的总代价；()为初始状态到状态的真实代价；()为状态到目标状态的预估代价。

经典蚁群算法的启发式函数中只考虑了当前节点到下一节点的路径作为真实代价，只考虑了局部求解，不利于在全局中寻找最优解。因此，在经典蚁群算法中引入A算法的估价函数，对蚁群算法的启发式函数进行改进。将当前节点与下一节点的距离代价作为真实代价以及下一节点与目标节点的距离作为预估代价，这二者之和构成了A算法的估价函数。以这一函数代替蚁群算法的启发式函数，同时引入平衡因子，得到改进启发式函数如下：

其中:为当前节点到下一节点的距离，为下一节点到目标节点的距离。通过这种改进方式，增强了蚁群算法的搜索效率，提高了全局寻优能力，有效避免陷入局部最优。

改进算法流程如图6所示。

图6 改进蚁群算法流程框图Fig.6 Improved ant colony algorithm flow chart

4 实验数据分析

为了验证算法的性能，以及相关参数对算法性能的影响，在二维栅格地图模型上进行仿真验证。因此，将整体实验分为2个部分，实验1通过固定地图规模，调整参数的方式，进行对照实验来验证相关参数对算法性能的影响；实验2通过改变地图大小，分别采用不同的障碍物覆盖率以及不同的障碍物形状模拟实际飞行中可能存在的威胁来构建地图环境。利用Matlab软件进行仿真实验的操作，通过实验对比，分析路径的优劣，以此来判断算法的性能。

实验1：不同实验参数对算法性能影响。

将本文改进的算法在20×20的栅格地图模型中进行实验，通过调整、和的取值来验证不同参数对算法性能的影响，实验结果如图7所示。

图7 不同参数对改进算法性能的影响曲线Fig.7 The influence of different parameters on the performance of the improved algorithm

由实验1结果可知：改变算法的、和的取值对实验的结果有较大影响，因此在考虑算法收敛速度和仿生学实际情况的基础上，对算法参数的取值进行选择，通过实验结果选择=1、=7、=04(虽然=08使得在该次实验中算法的收敛速度以及精度都较高，但是从参数的实际意义考虑，取值过大，不利于算法在复杂环境下累积信息素，强化最优路径上信息素的迭代速率。

实验2：不同地图规模对算法性能影响对比。

将本文改进的算法与ACO算法分别在20×20，30×30，40×40的栅格地图上进行对比实验，并对实验数据进行分析，检验算法性能。首先对算法的参数进行初始化设置，如表1所示。

表1 算法参数设置Table 1 Algorithm parameter settings

1)算法在20×20的栅格地图上进行的实验结果如图8所示。

图8 路径规划结果示意图Fig.8 Comparison of path planning results on a 20×20 map

由此可见，ACO算法在进行路径规划的过程中，出现无法收敛到全局最优解的情况。因为在面临有复杂障碍出现时，ACO算法中的蚂蚁会在复杂障碍中反复前进后退，而本文改进的蚁群算法，利用了视场机制、逃出机制。有效减少了算法的迭代次数，提高了收敛精度。实验数据结果如表2所示。

表2 算法在 的栅格地图上的运行结果Table 2 Comparison of the running results of the two algorithms on a 20×20 grid map

2)算法在30×30的栅格地图上进行的实验结果如图9所示。

图9 基本蚁群算法路径规划结果示意图Fig.9 ACO algorithm path planning results

由实验2可知：ACO算法在对进行路径规划的时，随着环境规模的增大，复杂障碍的出现，会出现在规定的迭代次数完成后无法获得稳定的规划路径，仍然会存在陷入障碍中无法寻得路径的情况；并且，在这种情况下，基本蚁群算法必须通过增大迭代的次数，使得算法收敛，从而找到最优路径。因此对基本蚁群算法做出改进，得实验结果如图10和表3所示。

图10 在30×30地图上的路径规划结果示意图Fig.10 Comparison of path planning results on a 30×30 map

表3 算法在30×30的栅格地图上的运行结果Table 3 Comparison of the running results of the two algorithms on a 30×30 grid map

3)算法在40×40的栅格地图上进行的实验结果如图11所示。由于地图规模的扩大，搜索路径的难度增大，为了更好地进行路径规划，获得更加准确的结果，对迭代次数和蚂蚁数量进行调整，参数调整如表4所示。

表4 算法在40×40的栅格地图上的算法参数设置Table 4 Algorithm parameter settings on 40×40 grid map

图11 在40×40地图上的路径规划结果对比Fig.11 Comparison of path planning results on a 40×40 map

由实验3可知，随着实验地图规模的扩大，ACO算法在规定的迭代次数内无法搜索到最优规划路径，暴露出ACO算法迭代收敛速度慢，在复杂环境下寻优能力弱的现象；而本文由于引入了视场机制、逃逸策略、并且优化了信息素的更新方式，搜索到全局最优解，优化了ACO算法的搜索能力。实验数据结果如表5所示。

表5 算法在40×40的栅格地图上的运行结果Table 5 Comparison of the running results of the two algorithms on a 40×40 grid map

5 结论

算法利用Toeplitz规律，使初始信息素沿着初始点与目标点的连线上呈现正态分布，有效的降低了蚂蚁盲目搜索的概率；利用Logistic混沌模型优化全局信息素更新方式；再引入视场机制和逃出策略，并改变启发式函数，解决了蚂蚁在搜索路径过程中陷入局部最优、甚至死解的情况，并通过Matlab进行仿真验证。结果表明：相比于ACO的航路规划，采用本文的改进算法能够有效的提高收敛速度和精度，并且能够解决在复杂地形环境中陷入局部最优的情况，对无人机自主航迹规划具有应用价值。

如何对算法进行进一步优化，缩短算法的运行时间以及如何将其应用到动态障碍规避中，是下一步需要研究的内容。