多无人机协同任务分配的改进遗传模拟退火算法研究

Research on improved genetic simulated annealing algorithm for multi-UAV cooperative task allocation
2022年发布于Journal of Physics: Conference Series
原文地址：https://iopscience.iop.org/article/10.1088/1742-6596/2246/1/012081

文献名

摘要： 针对大规模区域内多无人机协同搜索问题，提出了一种结合模拟退火(SA)的遗传算法(GA)，在将大区域划分为多个小区域的前提下，解决多无人机之间的任务区域分配问题。首先，描述了待解决的问题，并将多无人机任务区域分配问题视为多旅行商问题(multiple traveling salesman problem, MTSP)。目标函数是在平衡每个无人机需要搜索的任务区域数量的前提下建立的。然后，我们对遗传算法进行了改进，利用遗传算法能够跳出局部最优解的优点对遗传算法生成的后代新种群进行优化。最后，利用TSPLIB数据库验证了该算法的有效性，解决了设置的MTSP问题。通过一系列的对比实验，验证了GAISA算法的有效性和求解MTSP问题的优越性。

---

---

一、介绍

在大区域内执行搜索任务时，可以将大区域划分为几个小区域，以提高搜索效率。进一步将多无人机协同搜索问题转化为区域划分、子区域分配和子区域全覆盖路径规划三个子问题。首先，采用一定的方法[1]将大面积区域划分为若干个子区域;然后，根据平均划分的思想将子区域分配给无人机。最后，无人机依次遍历各自的子任务区域。然后将多无人机协同搜索问题转化为多无人机任务分配问题。
提出了一种集成模拟退火的遗传算法(GAISA)。利用遗传算法对更新后的种群进行优化调整，有效地避免了遗传算法陷入局部最优问题，同时结合遗传算法本身的快速收敛性，解决了多无人机任务分配的MTSP 问题。

---

二、问题描述与建模

2.1 问题描述

假设一个大的区域按照某种方法被划分为N个子区域。这些子区域需要分配给M个uav作为一个任务。假设无人机在搜索过程中以一定的高度飞行。如图1所示，在每个子任务区域中选择一个点S，需要无人机到达子区域的这个点后才能开始任务区域的遍历。这些点组成一个任务集，此时多无人机任务分配问题可以转化为MTSP问题求解。

2.2 建模

在TSP问题中，一个旅行推销员访问了所有的城市，每个城市只访问一次，然后在访问完所有的城市后返回起点。在实际应用中，无人机执行搜索任务时，往往在任务区域外起飞，然后依次访问任务区域，每个任务区域只访问一次。遍历所有任务区域后返回起点。因此，模型是:

在距离成本中考虑了起点的影响

• C ：距离成本
• D_SN，S0 ：无人机从最后一个任务点S_N返回到起始点S₀的距离
• 后面的：从第一个城市1s到最后一个城市S的总距离
• 
  在MTSP问题中，UAV_i的任务序列可以表示，nⁱ为无人机需要执行的任务数。无人机在完成最后一个任务后需要返回到起始点。每架无人机的路径成本可以表示为
  
  以最小化所有无人机的总路径代价为目标，建立目标函数为
  

---

三、GAISA设计和改进

3.1 初始化

当已知任务数为N时，初始化染色体的长度为N。然后对染色体进行十进编码，染色体的N个基因对应N个不同的值，即:在1到N之间的数字随机排列，表示N个不同的任务点。初始化后的染色体按照无人机数量M进行分段。每架无人机对应一条染色体段，染色体段上对应的基因数量即为无人机需要访问任务点的数量，基因排列的顺序即为被访问任务点的顺序。如图2所示为15个任务点的染色体编码示意图。

初始化第1条染色体为全局最优解R~min global~ ，初始化第1条染色体的路径代价为全局最优代价C~min global~。然后初始化当前迭代号k=1 ，并开始循环迭代。

3.2 选择

在三架无人机的情况下，如图2所示，初始化后的染色体被分成三个片段。然后将起始位置S₀加到相应的染色体片段上。染色体段1表示第一个UAV需要访问的任务点和访问的顺序。然后分别计算每个染色体片段的成本，然后求和，记为总成本C

首先，根据适应度函数计算所有个体的适应度值。然后，利用二元竞赛方法选择具有高度适应性的个体作为下一代，使种群始终朝着有利的方向进化。最后，通过设置遗传比例差距P，选择个体数为N_sel的儿童群体进行后续操作

3.3 杂交

如图3所示，首先在染色体长度范围内随机生成两个数字，两个数字之间的染色体段移动到另一个染色体的最前端。然后，染色体上的每个基因依次被遍历，随后的重复基因被删除。这一操作不断重复，直到该染色体上没有重复的基因。也就是说，获得了一条新的染色体。

对交叉后的种群中的染色体以P_m的概率进行突变操作。染色体上的任意两个基因被选中，选中的第二个基因被插入到第一个基因之后。如果第一个基因位于第二个基因的后面，其他位置的基因就会依次向后移动。否则，依次前进。也就是说，产生了一个突变的染色体。例如，染色体上的基因序列为(3,7,1,4,2,6,8,5)，随机选择的第一个基因为2，随机选择的第二个基因为7。进行突变操作后，新染色体上的基因序列为(3,1,4,2,7,6,8,5)。遵循这个方法，直到所有的个体都被遍历。

3.4 SA优化后代染色体

SA模拟了固体物理退火的过程。连续降低初始温度T₀，并在每个温度下进行一定次数的循环。每个循环扰动当前的解，产生一个新的解。当新的解决方案比当前的解决方案更好时，新的解决方案被积极地接受。当新解较差时，根据概率接受新解。此过程不断迭代，直到温度达到设定的阈值或达到设定的迭代次数。
充分利用SA爬坡、易跳出局部最优的优点，进一步优化和调整生成的后代人口的新人口。具体流程如下:

• 初始化：初始化当前子种群：

• 循环： 当 j < N_sel 时，选择 j 个个体进行模拟退火处理，然后让 j = j + 1 。否则，执行步骤3。
  

• 输出优化后的新种群，Selch。

• 

3.5 迭代

将亲本的部分个体加入到优化种群中，新种群数量达到G_m。计算新种群中每个个体的成本。新种群中的最优个体被选择为局部最优解R_minlocal ，个体的代价被视为局部最优代价C_minlocal 。然后和C_minglobal比较。
if

---

总结

谁懂啊家人们，看完才发现这篇有中文版的。啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊小丑小丑TAT
中文版：基于改进遗传算法的多无人机任务分配