基于改进遗传算法的多无人机协同任务规划

赵民全

(解放军92785部队，辽宁 葫芦岛 125208)

0 引 言

多无人机协同任务规划是针对2架及2架以上的无人机在复杂战场环境中协同执行任务时，处理无人机之间的配合和以代价最小、算法最优、路径最短为目标来进行任务规划的技术。相较于单一无人机作战，多无人机协同作战有着更好的任务处理灵活性，并且通过相互配合，可以增加攻击和防御能力，提高打击效率和侦察成功率。

该技术的研究重点多集中于网络化情况下联合无人空战系统协同作战[1]。如自治编队混合主动控制项目(MICA)[2]包括了无人机协同任务规划、协同跟踪、编队控制等研究方向；异构无人机群实时协同与控制项目[3]是研究异构无人机协同控制及任务分配的技术，其理念就是将侦察区域划分为多个分区,一架无人机完成一个分区的任务,分别建立单个的旅行商问题模型，再采用模拟退火算法进行进一步的优化；文献[4]则是将无人机看作多个智能体，利用它们之间的交互对任务进行最优规划。

采用多旅行商问题建立多无人机协同规划模型，基于改进遗传算法对多无人机任务进行规划，采用模拟退火算法与基本遗传算法相结合的方式对遗传算法进行改进设计，并进行仿真验证分析。

1 多旅行商问题建模

多旅行商问题(MTSP)[5-6]是旅行商问题(TSP)的进一步发展，是一种典型的组合优化问题，是解决在多名旅行商要拜访多个地点时，如何能快速找到逐次抵达各地点一次后再回到起点的最短路径问题。模型设计以点0作为起始点，表示旅行商的始发地，点1到点L分别表示不同的城市，m个旅行商从城市0出发分别去逐个拜访,每一个城市都仅有一个旅行商到达,最后全部回到出发城市0。

建立多旅行商问题模型：

(1)

式(1)为目标函数式，为m个旅行商的总路程最小值，其中：

(2)

式(2)表示旅行商各自的路程，其中Cij表示旅行商经过对应弧段(i,j)用去的时间。

限定条件为：

(3)

式(3)表示从指定城市0出发，所有城市有且只有一个旅行商进行一次访问。

2 基于遗传算法的多无人机任务规划

遗传算法[7]是一种能有效求解最优化问题的算法，是遵循自然界“优胜劣汰”法则的方法。首先形成一组初始解群，然后通过选择、交叉和变异等遗传操作产生新一组满足设定目标的候选解，循环开展适应度评价、选择、交叉和变异遗传等操作，逐步迭代优化，直至得到最优目标解。

在使用遗传算法建模上，我们对适应度函数复制、交叉和变异等指标操作进行如下选择和设定。

适应度函数一般要求非负,这里通过变换将多重旅行商问题的目标函数变为适应度函数。复制选择上采用轮盘赌策略法，交叉在遗传操作中起核心作用，可增强遗传算法搜索能力。这里采用基本遗传算法部分匹配交叉算子，其中变异在遗传操作中是用来维持群体的多样性的，对于多旅行商问题而言，染色体变异可以通过交换2个随机位置上的基因来实现。

侦察无人机数量N为8时，假设需要侦察300 m×450 m的区域，进行仿真后可获得基本遗传算法规划效果如图1所示[8]。

图1 N=8时遗传算法四次求解仿真曲线

实验结果数据如表1所示。

表1 N=8时遗传算法仿真数据

可见当无人机数量为8架时，基本遗传算法能够基本完成对多无人机任务规划问题的求解，给无人机分配目标位置使得每架无人机走过的路程开始不太均匀，几次实验中优化出的最短飞行距离和迭代次数的结果很接近，但求出最短距离和迭代次数数值都较高，优化效果有待提高。

3 基于改进遗传算法的多无人机任务规划

从遗传算法实例仿真结果可以看出，其存在算法收敛性能差、找最优解时间长等不足之处。为使遗传算法得到更好的应用，需要在改善算法搜索能力和提高算法收敛速度等方面加以改进。

现将模拟退火算法的Metorpolis准则[9-10]引入遗传算法中,该算法是基于对温度控制过程的模拟，用冷却进度表来控制算法的进程，通过控制遗传算法子代染色体的选择来实现。随着进化过程的进行,算法在控制参数T逐步趋向于零时最终获取相对于全局的最优解。该方法使解的收敛从局部最优中跳出,最终达到全局收敛，同时实现了算法收敛速度的提升。

3.1 混合算法

模拟退火部分采用Metorpolis准则，采取内外双层循环模式，内循环终止准则选用连续若干次搜索得到新解的变化较小；外循环终止准则选用最优解在算法运行过程中在较长迭代次数内保持不变，得到交叉退火之后的新种群：

(4)

(5)

式中：Pi为接受第i个新个体的概率；Pj为接受第j个新个体的概率；si,sj为第i,j个原始个体序号；ci,cj为第i,j个新个体序号；fit(*)为适应度函数；T为控制参数。

通过遗传变异算子进行子代路径变异操作获得新个体，最后得到变异退火之后的新种群：

(6)

式中：i为变异前状态；i′为变异后状态。

根据温度终止条件判断是否需要重复以上步骤，通过逐步迭代获得最优解。

3.2 实例仿真结果

无人机数量N为8时，假设需要侦察300 m×450 m的区域，混合模拟退火遗传算法规划效果如图2所示。

图2 N=8时改进遗传算法四次求解仿真结果

实验结果数据如表2所示。

表2 N=8时改进遗传算法仿真数据

可见当无人机数量为8架时，改进遗传算法能够完成对多无人机任务规划问题的求解，优化出的最短飞行距离和迭代次数的结果很接近，求出的最短距离较小，以总飞行路程值来看，优化效果比较良好。对比2次仿真结果可知：在约束条件不变的情况下，混合模拟退火遗传算法求得的最优值即最短飞行距离比基本遗传算法都有明显的优化，迭代次数上更少，即优化时间更短。由此得出，混合模拟退火遗传算法确实使基本遗传算法在寻得最优解的能力上得到优化。

4 结束语

本文以飞行时间最短作为优化目标，建立了组合优化模型，采用遗传算法进行求解，并用多旅行商问题对模型进行修正，进而采用混合模拟算法和遗传算法相结合的策略对传统遗传算法进行改进，将模拟退火算法与遗传算法过程整合成一个双循环，由模拟退火算法判定是否保留该解。最后，改进后的遗传算法仿真实验表明：基于模拟退火算法对遗传算法的改进是可行的，具有一定的工程应用价值。