1. 项目研究背景
随着人工智能的发展以及现代科技的进步，无人机在战场、救援等领域广泛应用，减少风险和经济损失。无人机集群协同控制至关重要，监视效率低下无人机集群协同执行任务是源于自然界的生物的无意识组织行为，通过相互间通信交流产生整体效应和高度的自主合作，提高任务效率这类似于蜂群的无意识组织行为可提高任务效率。多目标规划项目致力于在复杂环境中优化无人机任务轨迹，考虑飞行、障碍、群体规模、功能需求等因素，实现更精确、高效的规划[1]。
2. 项目研究意义
无人机在作战中扮演着多种角色，伴随其在现代战争中需求度的增加，世界各国对于无人机的作战效率备受重视。一般来说无人机是通过自动驾驶完成任务，地面技术人员设定好飞行路线进行装载，由无人机按照导航设定的航线进行探索，将规划区域按照一定的长度分为若干个区，航路不迂回[2]。对无人机的规划区域内的威胁位置和半径以及航路点的坐标采用直角坐标系表示。定义飞行路径的起点为坐标的原点，终点与起点的连线为直角，为降低搜索空间，增加搜索效率，采取栅格图法将航路段细分为若干个区域，根据不进行路线重复飞行原理，令目的点排成序列依次位于交点，任务点根据无人机的导航方式和飞行控制方法进行合理选择[3]。我们将遗传算法作用于路径规划问题上，在直角坐标系中描述战场环境中的威胁和目的点，从而缩短了基因编码长度，使无人机路径多目标规划问题达到最优解。
3. 研究内容
遗传算法受生物进化论的启发提出，是基于自然遗传学的优化工具。它是基于适者生存的算法，将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体求问题的最优解或满意解[3]。
遗传更新过程分为以下几个过程。
3.1. 种群和个体
遗传算法由进化理论启发，以种群为单位，种群在生物学上指在一定空间范围内同时生活着的同种生物的全部个体。在遗传算法里，个体通常为某个问题的一个解，并且该解在计算机中被编码为一个向量。
3.2. 编码、解码与染色体
遗传算法中的个体也就是一组可能解在计算机程序编写时被编码为一个向量，也是两个取值，两个实数，所以问题就可以转化为如何将实数编码为一个向量表示。将个体编码后的二进制串叫做染色体，是个体的二进制编码表示。最后将编码后的二进制串转换为十进制串，这个过程叫做解码交叉与变异，适应度和选择。
3.3. 交叉、变异，适应度和选择
通过选择当前较好的基因，繁殖后代产生比当前更好的基因，交叉和变异有发生的概率，而变异本质上是让算法跳出局部最优解。根据适者生存规则把优秀的个体保存下来，同时淘汰掉那些不适应环境的个体。在求最大值的问题中可以直接用可能解对应函数的函数值的大小来评估。
4. 项目研究过程
4.1. 数据导入与数据处理
由于无人机全程使用D1、D2、D3短波通信但不同通信手段之间无法通信。因此，构建超短波通信手段覆盖范围的数学模型，绘制任务区域内三种短波通信分别在海拔3 km、6 km、9 km，以达到处理数据的目的。3种通讯方式和三种高度实际上是9个子问题，对每个子问题有：
1. 遍历每一个空中的点；
2. 尝试连接基站x；
3. 查询基站x是否支持通信方式d x，若不支持返回2，尝试下一个；
4. 将该基站点转化为经纬度；
5. 计算距离，若距离超过最远通信距离，返回2；
6. 将该点映射到地面格点，空中点相当于在第a1行第b1列；
7. 求a0，b0到a1，b1直线；
8. 对于直线经过的格点，获取该点高程h0，和该线在空中高度h1；
9. 比较h0，h1，发现h1 < h0，说明被阻，回到2尝试下一个基站。
4.2. 最优化问题求解
4.2.1. 初始化种群
无人机进行路径规划之前首先要创建地图，本文采用栅格法创建无人机的路径空间模型。栅格面积越小，空间中各种环境信息表示越精准，但同时占用的存储空间就会加大，算法所使用的搜索时间就会加大。但若栅格面积越大，空间中各种环境信息不能准确表示出来，容易出现碰撞问题。所以在建立环境模型时，先做以下规定：只考虑障碍物位置问题排除高度因素，无人机飞行空间为二维平面空间；障碍物的大小已知，不存在可移动的障碍物；在规划时把无人机看作质点处理。
种群初始化步骤如下：
初始化种群在二者之间随机生成多条路径，并选取其中不与障碍物产生碰撞的路径作为可行路径。
选择分为以下几个步骤。
第一步产生一条间断路径。无人机每次需要行走一个格子，因此每一行至少有一个栅格在可行路径中。初始化时先按顺序在每一行随机取出一个无障碍栅格，形成一条间断的路径，其中为了减短路径长度，路径的第一个和最后一个栅格分别为机器人的起始位置和目标位置。
第二步是将间断的路径连为连续路径。在这一步中，首先从第一个栅格开始判断相邻的两个栅格是否为连续栅格，栅格是否连续的判断方法为：
为每一行栅格数，int为取整。若D等于1则两个相邻栅格连续，反之不连续。对于不连续的栅格取两个栅格的中点栅格，中点栅格的坐标计算为：
4.2.2. 计算适应度
主要是直接用经过路径的D1网格数，通信盲区网格个数以及总距离的一个加权和作为多目标适应度函数。代码如下：
#函数定义：定义名为calcfit的函数，接受一个种群popu和一个可变参数列表mpf作为输入。mpf可能包含多个参数
Function calcfit (popu,* mpf):
#初始化：cl是一个常数，用于计算适应度中的某个权重。mp0和mp1是从mpf参数列表中提取的，如果mpf中没有第二个元素，则mp1被设置为−1。
cl = 100
mp0 = mpf [0]
mp1 = mpf [1] if length (mpf) > 1 else − 1
#处理种群：popu被转换为一个数组，并计算了路径的长度lenth。如果popu的最后一个元素是0 (表示路径的结束)，则lenth就是popu的长度；否则，路径循环，将lenth设置为popu的长度加1。
popu = Convert_to_array (popu)
lenth = length (popu) if popu [−1] = 0 else length (popu) + 1
d1 = d2 = d5 = 0
#计算适应度相关项：遍历路径中的每个点。检查点是否在mp [mp0]或mp [mp1]地图表示的障碍物上，并相应地增加d1或d2的值。如果下一个点的x坐标不是0，则计算当前点和下一个点之间的距离，并累加到d5中。
for i from 0 to lenth-1:
y_now, x_now = get_coordinates (popu [i], col)
y_next, x_next = get_coordinates (popu [I + 1] if I + 1 < lenth else popu [i], col)
if mp [mp0] [y_now] [x_now] == 1:
d1 + = 1
elifmp1! = −1andmp [mp1] [y_now] [x_now] == 1:
d2 + = 1
if x_next! = 0:
d5 + = calculate_distance (x_now, y_now, x_next, y_now)
#计算适应度：计算非障碍物点的数量d3 (通过从路径长度中减去障碍物点的数量)。定义三个适应度分量fit0、fit1和fit2。其中fit0 是非障碍物点的数量，fit1是路径的总长度，而fit2是一个惩罚项，当路径上有障碍物时，它是一个与障碍物数量成反比的值(如果没有障碍物，则为0)。
d3 = lenth − d2 − d1
fit0 = d3
fit1 = d5
fit2 = cl / d1 if d1! = 0 else 0
#返回适应度值：函数返回了一个线性组合的适应度值，该值由a0、a1和a2 (这些值在函数外部定义)加权。这个值将用于遗传算法中的选择过程，以确定哪些染色体(即路径)在下一代中更有可能被选中。
return a0 * fit0 + a1 * fit1 + a2 * fit2
# 辅助函数：get_coordinates函数用于从给定的索引和列数计算y和x的坐标，而calculate_distance函数用于计算两点之间的直线距离。
function get_coordinates (index, col):
#根据索引和列数计算y和x的坐标
y = index//col
x = index% col
return y, x
function calculate_distance (x1, y1, x2, y2):
#计算两点之间的直线距离
return sqrt ((x2 − x1) * (x2 − x1) + (y2 − y1) * (y2 − y1))
return sqrt ((x2 − x1) * (x2 − x1) + (y2 − y1) * (y2 − y1))
4.2.3. 选择
将值从小到大排序，假设种群中强者的概率是50%，且认为强者都能存活，即都能进入下一代。那么剩下的50%就是弱者，而对于弱者，也有一个弱者存活概率如0.3，采取随机存活方式，产生一个0~1之间的随机小数，若0.3大于这个小数，那么认为可以存活，否则舍弃。存活下来的强者和弱者构成了新的种群，进行下一步操作。
4.2.4. 交叉
首先需要确定一个交叉概率Pc，产生0~1之间的一个随机数，并和交叉概率pc比较，若小于pc则进行交叉。采用的是单点交叉的方式，具体操作是找出两条路径中所有相同的点，然后随机选择其中一个点，将之后的路径进行交叉。
4.2.5. 变异
首先确定一个变异概率Pm，产生0~1之间的一个随机数，并和变异概率Pm比较，若小于Pm则进行变异操作。变异方法是随机选取路径中除起点和终点以外的两个栅格之间的路径，然后以这两个栅格为相邻点，使用初始化路径中的第二步将这两个点连续操作。
5. 项目总结
无人机主要是将自有的控制程序功能与无线电遥控设施加以运用的一种无人承载的飞机[4]。为了减少搜索空间，对规划区域进行简单的处理，将规划区域按照一定的路段长度分为若干个，引入栅格地图的构建和十进制种群的编码方法，减少通信盲区，再利用遗传算法，同时进行多个个体的比较选择交叉变异等运算，增加了其搜索过程的灵活性，达到快速规划最优解的效果。遗传算法的编程实现比较复杂，首先需要对问题进行编码，找到最优解之后还需要对问题进行解码。算子的实现需要很多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质，难以找到最优解。
基金项目
2023年汉江师范学院大学生创新创业训练计划项目(项目编号：S202310518019)。