基于改进蚁群算法的无人机集群任务规划∗

宋霏羽 夏学知

（武汉数字工程研究所 武汉 430205）

1 引言

多无人机协同任务规划是指多架无人机对多个目标进行侦察，以最小化出动无人机架次，任务执行时间最短和油耗成本最小为目标函数构建数学模型进行求解［1］。分配问题是UAV异构多模式，且约束条件复杂的最优化NP问题［2］。目前研究中大都将多UAV协同侦察任务规划系统模型转化为经典问题，如多旅行商问题（MTSP），车辆路径问题（VRP）［3］。

在以往对于任务分配问题求解算法的研究中，绝大多数文献都是采用人工智能算法进行求解，这类算法虽然操作简单，易于实现，但是很难保证收敛到全局最优解［4～8］。基于数学规划的启发式算法克服了这些缺点，常见的启发式算法有遗传算法，禁忌算法，蚁群算法等，目前这些算法都取得了很大的进展。由于路径规划是一个多约束的组合优化问题，各个约束之间存在交叉重叠，目前常用的算法在路径规划中各有所长，但也有一些弱点。比如新兴算法计算速度块，准确率相对较高，但在迭代过程中易停滞陷入局部最优。所以，实际应用中一般会根据具体的问题改进算法［9～11］。

蚁群算法作为一种元启发式算法，可以非常高效地解决路径规划问题。但蚁群算法也存在一些缺陷，如容易陷入局部最优解，初期收敛速度慢，运行时间长等。本文将针对以上缺点，对蚁群算法进行改进，使最后的算法性能更好，具有普适性和可推广性。

2 基于交叉避免的蚁群算法设计

为了使无人机集群并行执行任务所需要的时间最短，也就是要找出单个无人机最长执行任务的路径距离，并使这个路径距离最小化。因此，可以把问题抽象为优化局部路径，那么可以优化整个路径。如果路径中存在交叉，则这条路径一定不是一个最优路径。这个结论启发我们找到存在交叉的路径并将该交叉解开，就可以减少整条路径的长度。利用蚁群算法来寻找最优航线，但在进行最优航线规划时，易陷入局部最优［12］。

2.1 交叉检测

假设存在交叉的路径中这两条路径的四个点分别是A(xa，ya)，B(xb，yb)，C(xc，yc)，D(xd，yd) ，并 且它们的交点是O(xo，yo)。因此有下面的线性方程组：

2.2 交叉消除

消除交叉的过程实际上可以简化成将有交叉的那个部分的路径的起点和终点中间的所有点进行颠倒。这次的改变可以增加一次迭代优化能力，增加了解的多样性，这在遗传算法领域相当于是基因变异，在一定程度上能跳出局部最优解。因为蚁群算法一定程度上是正反馈的算法，在算法后期由于解空间路径的信息素浓度远大于非解空间路径的信息素浓度，而很容易陷入局部最优，通过以上的改进，可以在减少运行时间的同时增强跳出局部最优解的能力。

2.3 蚁群算法流程

1）初 始 化α，β，ρ，trailmatrix，antnum，cyclenum，L，H。

2）从开始的任务点出发，选择下一个要访问的任务点。

（1）找出已经访问过，后续禁止再访问的任务点；

（2）综合考虑信息素和启发式函数计算每个任务点的出行概率；

（3）使用轮盘赌选择要去的任务点。

3）找出当前代最好的解决方案

（1）计算每只蚂蚁的路线长度；

（2）找出最小的路径长度；

（3）对最优解交叉检测，并重新计算长度，更新全局最优路径。

4）更新信息素浓度矩阵。

5）输出全局最优解。

3 实验结果

为了比较蚁群算法的准确性，我们把改进的蚁群算法的运行结果和Lingo 17的运行结果进行比较。以下结论都是基于改进蚁群算法运算了8次取其中最好的结果，而且所有问题也被Lingo 17使用精确算法求解相关的优化模型计算了一次。蚁群算法的参数设置：蚂蚁数量为7，初始信息素浓度为1，挥发率ρ为0.2，迭代次数为100，α系数为1，β系数为5。蚁群算法使用Python在Pycharm上进行实现，而Lingo 17解决优化模型的计算平台是阿里云的云计算平台。从表1看到，由于蚁群算法是一种启发式算法，而Lingo是精确算法，因此在运行时间上蚁群算法的运行时间远小于Lingo的运行时间，而由于对蚁群算法引入了交叉检测机制，使其能有效克服前期寻优效果差和后期易局部收敛的缺点，因此改进蚁群算法能获得与Lingo相近的目标结果。这个结果显示出我们算法精度的优良和运行效率的良好。

表1 蚁群算法结果和Lingo优化模型结果比较

4 结语

在本文中，我们运用改进的蚁群算法求解多UAV并行任务分配问题，重点对蚁群参数，适应度函数和交叉的路径检测消除进行详细设计。以任务执行时间最小为优化目标，解决目标函数为最小化最长路径的UAV群体并行任务分配的问题。首先讨论了该蚁群算法的设计和交叉避免的算法流程。其次用eil51这个基准数据集产生了四个不同规模的测试问题，并利用python进行仿真。最后，解决了所有问题并且把得到的结果和Lingo产生的最优解进行比较。可以看出，大多数情况下，和最优解结果比起来，蚁群算法提供的解的精度丢失不大，但蚁群算法所需要的运行时间却非常小。最后的测试结果显示改进后的算法虽然精度平均丢失4.07%，但运算速度提高了96.4%。表明该算法能够对UAV群体并行任务分配的问题成功求解，从而极大提高任务的执行效率。