本发明涉及一种无人机航迹规划方法。
背景技术：
无人机已经在军事和民用领域展现其优势与潜力。为了实现无人机自主导航，必须考虑建模，航迹规划，以及控制系统设计等方面。其中，航迹规划是一类已被广泛研究的重要问题。无人机(unmannedaerialvehicle，uav)航迹规划问题是一类具有多个目标和约束条件的优化问题。无人机航迹规划是在满足多个约束条件(包括无人机属性和地形限制)的情况下找到从起点到终点的最优或次优航迹。航迹的优劣通过飞行长度，飞行高度，被摧毁概率等指标衡量。因此，航迹规划问题可以被描述为一个约束多目标优化问题。具体而言，基于时间域，无人机航迹规划问题可以分为在线优化与离线优化；基于空间域，无人机航迹规划问题分为2维环境与3维环境下的优化问题。因为在线航迹规划问题可以看做是离线航迹规划问题的扩展，所以研究最广泛的是离线航迹规划问题。
针对无人机航迹规划问题中存在的多个相互冲突的优化目标，常见方法是加权聚合多个目标，然后利用单目标演化算法求解无人机多目标航迹规划问题。学者们已经提出了多种航迹规划方法，例如，a*算法，d*lite算法，双层规划算法，基于网格的算法和智能计算方法等。
尽管人们提出了大量的求解无人机航迹规划问题的方法，但是人们通常将航迹规划问题表示为单目标优化问题，并提出单目标优化算法。然而航迹规划问题通常具有多个相互矛盾的目标，例如希望获得最小被摧毁概率但是同时希望航迹最短。现有的处理多个相互矛盾的目标的方法是将每个目标乘以一个系数，然后将这些加权后的目标值相加。事实上，这些相互矛盾的目标的属性是不同的，不能简单地将这些目标加权求和。而且如何确定合适的加权系数是一个关键的但又不易解决的问题。此外，基于一组固定的加权系数运行一次单目标优化算法仅能获得一个最佳的飞行航迹，一旦决策者的偏好有所改变，就需要再运行一次算法以获得新的最优航迹。考虑到多目标演化算法有强大的全局搜索能力和鲁棒性，以及仅运行一次即可为决策者提供多样化的折衷航迹，利用多目标演化算法求解无人机航迹规划问题较为实用。
也有一些研究提出了一些求解无人机航迹规划问题的多目标演化算法。mittal和deb利用结合了局部搜索方法的nsga-ii解决了两种航迹规划问题，一种航迹规划问题除了无人机和地形约束外不考虑其他约束条件，另一种规划问题定义了一个无人机必须经过的特殊点。在规划无人机的安全飞行路线时，为了同时获得研究人员感兴趣的目标的双基地sar成像，sun等使用《three-dimensionalo_inepathplanningforuavsusingmultiobjectiveevolutionaryalgorithms》中的算法，以找到无人机导航和双基sar成像之间的折衷解。此外，为了求解这一优化问题，sun等还提出了一种约束自适应多目标差分进化算法，根据熵自适应调整差分进化算子控制参数。《three-dimensionalpathplanningforunmannedaerialvehiclesbasedonmulti-objectivegeneticalgorithm》中，以nsga-ii为框架，设计了几种变异算子，并自适应调整算子的使用概率，然后用改进的算法优化飞行长度，飞行高度以及总威胁指数。此外，受a*算法启发，还提出了一种重构算子使解逃离受限区域。为了更好地演化航迹中的优质路径点，yang等提出将原始航迹规划约束条件和目标函数分解成一系列新的子函数，然后单独演化评估每个路径点。其中，路径点的优化算法是结合了基于优先级的多准则处理方法的jade算法。为了规划多个无人机的航迹，besada-portas等提出了基于无人机属性，地形和不同优先级的优化准则，并提出了每个无人机使用一种演化算法并在演化时分享最优解的多智能体协同进化算法。考虑到航迹规划中变化的环境和受限的信息，peng等提出了一种动态多目标演化算法，该算法挑选历史pareto解集构建时间序列，并利用一种预测方法推测新的pareto解集。
总体来看，目前不将目标加权求和，而是直接求解无人机多目标航迹规划问题的方法较少，需要学者们进一步研究。
技术实现要素：
本发明是为了解决目前没有一种可以不将目标加权求和而直接求解无人机多目标航迹规划问题的无人机航迹规划方法，以及现有的规划方案效果不好的问题。
一种针对路径点聚类机器学习的无人机航迹规划方法，包括以下步骤：
首先，利用航迹的路径点坐标组成染色体，随机地生成初始种群p＝{x1,…,xn}并计算p目标值，同时建立外部文档a用于储存环境选择中表现优良的解；
然后，针对所有航迹，计算每个路径点的交配限制概率矩阵b和可行性矩阵i；
交配限制概率矩阵
随后将n条航迹演化t代；每一代的航迹演化过程包括以下步骤：
首先利用聚类算法将所有航迹聚类，找到每条航迹的邻居航迹矩阵s；
然后对每条航迹进行重组操作和环境选择操作；其中，针对路径点进行重组的过程中，重组算子演化更新w-2个路径点，生成新航迹np；
然后计算新航迹的目标值以及新航迹中路径点的交配限制概率β*和可行性i*；
随后，将新航迹和外部文档混合进行环境选择，如新航迹质量较优，则保存至外部文档，并利用β*和i*更新b和i；
在每一代演化的最后，利用a更新p；
所述计算新航迹中路径点的交配限制概率β*和可行性i*的过程包括以下步骤：
计算第j个路径点的约束违反值，航迹长度指标值dscorej和高度指标值hscorej；
如果第五约束g5＞0，设置交配限制概率
对于违反第一约束至第四约束条件的路径点，
如果路径点没有违反约束，则路径点是可行的
最终得到路径点的交配限制概率
第一约束为转弯角约束，第二约束为坡度角的约束，第三约束为航迹段中间点高度约束，第四约束为最小航迹段长度约束，第五约束为航迹的总长度约束；
其中，xj,yj,zj是第j个路径点的坐标值；pzj,m为航迹段上的第m个中间点的z轴坐标，m＝1,…,nm。
进一步地，第一约束至第五约束具体如下：
θmax是无人机的最大转弯角；θj是矢量(xj-xj-1,yj-yj-1)和(xj 1-xj,yj 1-yj)之间的夹角；第一个约束函数表示为：
其中，
αmax是最大爬升/俯冲角限制，航迹段的斜率αj表示航迹的爬升/俯冲角；第二个约束函数为：
其中，
hmin为无人机到地面的最低垂直高度；第三个约束函数表示为：
其中，
dj为两个相邻路径点之间的距离，lmin为最小航迹段长度；第四个约束函数表示如下：
其中，
规划航迹时还规定航迹的总长度小于一个预定义的长度值lmax；第五个约束函数为：
进一步地，所述pzj,m＝zj-1 m/nm×(zj-zj-1)。
进一步地，计算新航迹的目标值中所述的目标值如下：
x＝(x1,y1,z1,…,xw,yw,zw)t
s.t.xj∈[xa,xb],yj∈[ya,yb],zj∈[za,zb]
其中，f1(x)为总航迹长度，f2(x)为总飞行高度，gk为约束函数，k为聚类数；x1,y1,z1为第1个路径点的坐标值，xw,yw,zw为第w个路径点的坐标值，w为航迹中路径个数；[xa,xb],[ya,yb]和[za,zb]分别表示x，y和z坐标的下边界和上边界。
进一步地，所述针对路径点进行重组，产生新航迹np的具体过程包括以下步骤：
首先选择可行航迹中最差的路径点；如果一条航迹中所有路径点为可行的，则该条航迹为可行航迹；此时具有最大交配限制概率的路径点为最差路径点；
然后对每个路径点进行重组操作，具体包括以下步骤：
对于第i条航迹中的第j个路径点，找到其邻居航迹sk,k∈{1,…,k}；
根据交配限制概率
然后利用差分进化算子产生尝试解
将超过搜索空间的基因值设为边界值；
针对
最后，如果第ww个路径点比之前的飞行高度更高，优化路径点的飞行高度。
进一步地，所述的配对池
其中，rand1是[0,1]范围内的随机数。
进一步地，利用差分进化算子产生的尝试解
其中rand2、rand3、rand4是[0,1]范围内的随机数；f是差分系数，cr是交叉概率。
进一步地，如果第ww个路径点比之前的飞行高度更高，优化路径点的飞行高度为
其中，
进一步地，所述聚类算法采用k-means算法。
有益效果：
基于现有无人机航迹规划方法存在的问题，本发明提出了一种基于评估函数和k-means聚类算法的交配限制策略，进而提出了一种多目标演化算法(moeawiththematingrestrictionstrategybasedonmetricfunctionsandk-meansclusteringalgorithm，mfkc)求解无人机航迹规划问题。mfkc利用k-means算法找到邻居航迹。根据每个路径点的交配限制概率，控制配对池由当前路径点所处航迹的邻居航迹或者全部航迹构成，以分别加强开采和勘探。每个路径点的交配限制概率由评估函数测得的路径点质量决定。此外，mfkc还利用了一个局部搜索算子进一步优化飞行高度。
本发明的主要贡献如下：
1、提出了两种场景下的无人机航迹规划问题模型。
2、提出了一系列评估函数衡量可行路径点和不可行路径点的质量，根据路径点质量自适应地调整路径点的交配限制概率。
3、基于每个路径点的交配限制概率，控制配对池组成，进而控制路径点的搜索范围。
4、为了进一步加强对飞行高度的最小化，提出了一种局部搜索算子。
附图说明
图1为航迹段上的中间点示意图；
图2航迹长度指标计算原理示意图；
图3(a)和图3(b)为场景1下的n条航迹中航迹长度最短的航迹效果图；图3(c)至图3(d)为场景1下的n条航迹中飞行高度最低的航迹效果图；
图4(a)和图4(b)为场景2下的n条航迹中航迹长度最短的航迹效果图；图4(c)至图4(d)为场景2下的n条航迹中飞行高度最低的航迹效果图。
具体实施方式
本发明的航迹规划问题是指3维环境下无人机离线航迹规划问题。
具体实施方式一：
本实施方式为一种针对路径点聚类机器学习的无人机航迹规划方法，过程如下：
航迹表示：
基于曲线表示无人机航迹的方法可以使航迹光滑，但是需要很大的计算开销，因此本发明建立一系列路径点并用线段连接路径点形成航迹。
一些航迹规划方法将航迹坐标进行了变换，以提高搜索速度。本发明中演化算法的染色体由固定个数的路径点在笛卡尔坐标系中的坐标值组成。一条航迹中有w路径点，因此染色体可以表示为(x1,y1,z1,…,xj,yj,zj,…,xw,yw,zw)t，其中，xj,yj,zj是第j个路径点的坐标值，j是路径点在航迹中的序号。染色体中第一个点和最后一个点的坐标分别为起点和终点的坐标。
目标函数：
为了减少燃料消耗和任务完成时间，无人机应该有尽量短的航迹长度。为了利用地形掩护，提高生存概率，无人机的飞行高度应该尽量低。因此，建立优化目标为最小化总航迹长度f1和总飞行高度f2。
本实施方式中用实际航迹长度除以理想航迹长度表示总航迹长度f1，理想航迹是一条直接连接起点和终点的线段；用w-1条航迹段高度的平均值表示总飞行高度f2。现有衡量飞行高度的方法是将所有路径点的高度相加，但是忽略了路径点之间的飞行高度，因此本发明采用航迹段高度衡量飞行高度。利用均匀分布的中间点将相邻航迹点之间的线段分成nm个线段，每条航迹段的高度是nm个中间点和一个路径点相对地面的高度的平均值。第j条航迹段上的第m个中间点的坐标值为(pxj,m,pyj,m,pzj,m)，如图1所示。其中，pzj,m可以通过公式pzj,m＝zj-1 m/nm×(zj-zj-1)计算获得，m＝1,…,nm。将上述航迹规划问题的目标函数表示如下：
其中，hj,m是平面坐标为(pxj,m,pyj,m)的地形高度。
约束条件：
第j个路径点对应的转弯角、坡度角、航迹段为第j个转弯角、第j个坡度角、第j条航迹段。
考虑到无人机的可操作性，航迹的转弯角θj应该小于无人机的最大转弯角θmax；否则，设置该约束的违反函数值大于0。θj是矢量(xj-xj-1,yj-yj-1)和(xj 1-xj,yj 1-yj)之间的夹角。
第一个约束函数表示为：
其中，
相似的，受无人机可操作性限制，存在最大爬升/俯冲角αmax限制。用航迹段的斜率αj表示航迹的爬升/俯冲角，该斜率应该小于αmax，第二个约束函数为：
其中，
尽管较低的飞行高度可以使无人机受地面掩护不被袭击，但为了确保飞行安全，无人机在飞行时必须离地面有一定的高度。设置无人机到地面的最低垂直高度为hmin。可以将第三个约束函数表示为：
其中，
因为无人机需要一定的时间调整姿态，所以两个相邻路径点之间的距离dj应该大于最小航迹段长度lmin。第四个约束函数表示如下：
其中，
除了航迹段约束，规划航迹时还规定航迹的总长度小于一个预定义的长度值lmax。因此第五个约束函数为：
在规划航迹之前，还需要限定搜索空间的边界。[xa,xb]，[ya,yb]和[za,zb]分别表示x，y和z坐标的下边界和上边界。在搜索空间以外的路径点用演化算法的修复算子处理，在此不设立约束函数。
综上，可以将无人机航迹规划问题表示为：
minf(x)＝(f1(x),f2(x))t
x＝(x1,y1,z1,…,xw,yw,zw)t
s.t.xj∈[xa,xb],yj∈[ya,yb],zj∈[za,zb],j＝1,…,w
gk＝0,k＝1,…,5(14)
进一步将约束违反值乘以106后加入到目标值中，表示成公式(15)的形式。这种处理方式使不可行解具有非常大的目标值，而且，约束违反值越大，目标值越大，在环境选择中越先被剔除。此时，上述约束多目标优化问题转化为一个仅带有盒约束的多目标优化问题，可以用一般的、无需在环境选择中考虑多个约束条件的多目标演化算法求解。
x＝(x1,y1,z1,…,xw,yw,zw)t
s.t.xj∈[xa,xb],yj∈[ya,yb],zj∈[za,zb],j＝1,…,w(15)
场景描述：
规定搜索空间范围是[xa,xb]＝[0,300]km,[ya,yb]＝[0,300]km,[za,zb]＝[0,1.5]km，且所有位置坐标单位均为km。本发明提出了两种场景下的无人机航迹规划问题。无人机航迹规划的场景包括地形以及威胁。地形由初始地形和山峰地形组成。
初始地形由公式(16)模拟生成：
h1(x,y)＝sin(y/180 1.5×π) 0.1×sin(x/16) 0.9×cos(0.3×median) 0.01×sin(0.01×median) 0.3×cos(y/36)(16)
其中，h1是点(x,y)的初始地形高度，
山峰地形由公式(17)模拟生成：
其中，h2是点(x,y)的山峰高度。k表示山峰个数。h(k)是第k座山峰的最高高度。(o1(k),o2(k))是第k座山峰中心的水平坐标。l1(k)和l2(k)控制第k座山峰的轮廓。设置环境中存在6座山峰，相应的参数值为h＝{0.7,1.77,1.8,2.34,2.5,3.2}；o1＝{50,160,70,130,100,100}；o2＝{60,100,30,20,160,100}；l1＝{140,170,170,160,280,150}；l2＝{20,230,150,190,220,280}。
考虑雷达和导弹两种防空单元做为航迹规划问题的威胁。一旦无人机进入防空单元的最大风险范围，就有被发现或者被攻击的可能。因为设定的z轴上的最大搜索范围比防空单元的最大风险范围小很多，因此将防空单元的威胁范围简化为一个圆柱体。圆柱体中心点水平坐标与威胁一致，半径是威胁的最大风险距离，高度是z轴上的最大搜索范围。
第一种场景中，考虑了两个雷达威胁和两个导弹威胁，其中心点水平坐标分别为{[100，225]，[240，150]}和{[100，100]，[225，250]}，最大风险距离分别为{50，50}和{25，25}。第二种场景中存在四个雷达威胁和四个导弹威胁，航迹的可行域相比于第一种场景更小。威胁的中心点水平坐标为{[120，240]，[175，75]，[50，175]，[240，150]}和{[75，60]，[225，250]，[170，170]，[100，125]}，最大风险距离为{50，50，35，35}和{25，25，25，25}。
此外，设置nm为10，因此在计算飞行高度和高度约束违反值等物理量时，每个航迹段被划分为10个区域。最大转弯角θmax和最大爬升/俯冲角αmax分别为60°和30°。离地面的最低飞行高度为hmin＝0.05km，最短航迹段长度lmin为2km，最大航迹长度为
本发明所述的一种针对路径点聚类机器学习的无人机航迹规划方法，简记为mfkc；每个路径点都有实际物理含义，根据其物理含义判断路径点的质量，辅助算法的交配限制，可以进一步提高算法的搜索能力。因此，本发明提出了一系列评估函数测度路径点质量，进而提出了一种基于评估函数和k-means聚类算法的交配限制策略，利用聚类算法建立每条航迹的邻域关系，根据路径点的质量决定配对池为邻居航迹还是全部航迹，并以此提出了一种多目标演化算法求解无人机航迹规划问题。本发明的具体执行过程包括以下步骤：
首先，利用航迹的路径点坐标组成染色体，随机地生成初始种群p＝{x1,…,xn}并计算p目标值，同时建立外部文档a用于储存环境选择中表现优良的解(算法伪代码第1行)；x1为第1条航迹，xn为第n条航迹；
然后，针对所有航迹，基于评估函数计算每个路径点的交配限制概率矩阵b和可行性矩阵i(算法伪代码第2行)；
交配限制概率矩阵
随后将n条航迹演化t代(算法伪代码第3-11行)；每一代的航迹演化过程包括以下步骤：
首先利用聚类算法(k-means算法)将所有航迹聚类，找到每条航迹的邻居航迹矩阵s(算法伪代码第4行)；
然后对每条航迹进行重组操作和环境选择操作(算法伪代码第5-9行)；其中，针对路径点进行重组的过程中，重组算子演化更新w-2个路径点(不包括起始点和终点)，生成新航迹np(算法伪代码第6行)；
然后计算新航迹的目标值(公式15)以及新航迹中路径点的交配限制概率β*和可行性i*(算法伪代码第7行)；
随后，将新航迹和外部文档混合(求并集)进行环境选择，如新航迹质量较优，则保存至外部文档，并利用β*和i*更新b和i(算法伪代码第8行)；
在每一代演化的最后，利用a更新p(算法伪代码第10行)。
mfkc的伪代码如算法1所示。需要说明的是在算法中被聚类和演化的路径点不包括起始点和终点。
算法1中，n是航迹条数。a是用于环境选择的外部文档。邻居航迹矩阵s＝[s1,…,sk]是一个邻域矩阵，其中k是最大聚类数，sk记录被分到第k类的航迹，k＝1,…,k。差分进化算子控制参数{f,cr}中，f为缩放因子，cr为交叉因子。
考虑到k-means算法的低计算复杂度和高聚类准确度，mfkc采用k-means算法对航迹进行聚类，将种群p划分为k个类{s1,…,sk}。聚类以后需要检查聚类结果：如果聚类后仅存在1类，则将前
交配限制概率及可行性更新过程如下：
在mfkc中，分别以1-β和β的概率将全部航迹和邻居航迹作为配对池。换言之，基于不同的父代来源，β可以控制算法是加强局部搜索还是全局搜索。此外，不同的路径点具有不同的质量，需要不同的搜索范围，因此每个路径点的β都根据路径点的质量而调整。
初始种群是在搜索范围的约束下随机生成的，此时没有考虑其它约束条件，因而航迹中会存在一些不可行路径点。在演化过程中，对航迹的可行点与不可行点进行演化，将带有不可行路径点的航迹赋予一个非常大的目标值，使其被删除的可能性变大，进而促使算法对可行航迹的搜索。在演化过程中，如果路径点违反了约束条件中的前四种约束条件，则利用公式(3)，(6)，(9)和(11)作为评估函数评估路径点质量，计算β。路径点的约束违反值在[0,1]范围内变化，并且随着路径点质量变差而逐渐变大。对于可行的路径点，提出了如下两种指标：
dscorej的计算原理如图2所示。第j 1个路径点离前后两个路径点连成的直线距离较近，说明当前航迹段(a b)接近于理想航迹段(c)。航迹点离理想航迹段越近，dscorej 1的值越大。与之相反，第j个路径点离理想航迹段c′较远，所以质量较差，对应的dscorej值也较小。hscorej由航迹段中间点高度pzj,m和地形高度hj,m决定。较低的飞行高度产生一个较大的hscorej。
根据评估函数的计算值，用算法2更新路径点的交配限制概率。在算法1的第2行和第7行中，除了参与计算的路径个数不同，交配限制概率的计算和可行性的判断过程是相同的。在此以算法1中第7行为例，阐述了交配限制概率及可行性更新过程。算法1的第2行中，计算种群里路径点交配限制概率和判断路径点可行性的过程相当于运行n次算法2。
计算新航迹中路径点的交配限制概率β*和可行性i*的过程包括以下步骤：
计算第j个路径点的约束违反值，航迹长度指标值dscorej和高度指标值hscorej(算法伪代码第2行)；
如果g5＞0，说明航迹总长度f1大于预定义的最大值，路径点需要非常大的搜索范围形成合理的路径点序列，此时所有的路径点都以最大的概率进行勘探，因而设置交配限制概率
对于算法2，还需要解释以下几点：
第一，因为航迹的终点固定，所以在计算第w-1个路径点的
第二，如算法2所示，公式(18)-(19)是可行路径点的指标评估函数，基于这两个指标评估函数，具有较好质量的可行航迹点的β较大。不同于其他文献中建立约束条件函数时，简单地将不可行解的约束违反值设置为1或者为约束变量的值，本发明提出了新的约束函数：公式(3)，(6)，(9)和(11)。基于此，不可行点的转弯角越大，爬升/俯冲角越大，飞行高度越低于地面高度，航迹段长度越小，则不可行路径点的质量越差，交配限制概率越低。
第三，基于公式(3)，(6)，(9)和(11)和公式(18)-(19)表示的评估函数，路径点的质量将决定交配限制概率值。具体而言，具有较小目标值的可行点或者较小约束违反值的不可行点的交配限制概率较高，可以加强局部搜索。反之，具有较大目标值的可行解和较大约束违反的不可行解具有较小的交配限制概率，进而加强全局搜索。
第四，不同于将多个约束或者目标加权求和，进而将多目标航迹优化问题转化为单目标优化问题的过程，在算法2第6行和第8行中，利用多个评估函数值的均值计算交配限制概率时，先将约束违反值和目标值转化为路径点质量，然后根据路径点质量调整交配限制概率。以这种方式，转化后的变量具有相同的属性，因此可以将评估指标值的均值作为交配限制概率。
新解生成过程如下：
在重组过程中，当前航迹的邻居航迹以β的概率被选为配对池，而所有航迹以1-β的概率被选为父代来源。mfkc利用差分进化算子和多项式变异算子，基于随机选择的父代个体产生新路径点。此外，利用局部搜索算子进一步降低可行航迹中质量最差的路径点的飞行高度，具体细节如算法3，即所述针对路径点进行重组，产生新航迹np的具体过程包括以下步骤：
首先选择可行航迹中最差的路径点(算法伪代码第2-4行)；
然后对每个路径点进行重组操作(算法伪代码第5-15行)，具体包括以下步骤：
对于第i条航迹中的第j个路径点，找到其邻居航迹sk,k∈{1,…,k}(算法伪代码第6行)；
根据交配限制概率
然后利用差分进化算子产生尝试解
为了使路径点可行，将超过搜索空间的基因值设为边界值(算法伪代码第10行，第10行修复在搜索空间以外的基因的含义是：新解如果超过搜索空间的基因值，则设为边界值。如果没有超出则不变。)；
mfkc还采用了带有基因修复机制的多项式变异算子演化尝试解，即针对
最后，如果第ww个路径点比之前的飞行高度更高，进一步优化路径点的飞行高度
关于算法3，给出如下几点说明：
第一，在重组过程中，首先选择了可行航迹中质量最差的点。如果一条航迹中所有路径点为可行的，则该条航迹为可行航迹。此时，具有最大交配限制概率的路径点为最差路径点。
第二，航迹的邻居航迹分布相似，因此设置邻居航迹的路径点为交配父代可以提高开采能力。另一方面，全部航迹通常在搜索空间内较广泛地分布，从这类航迹中选择父代有利于勘探。
第三，利用差分进化算子和多项式变异算子演化更新路径点以后，如果最差的路径点的新飞行高度
环境选择过程如下：
mfkc通过环境选择[25]保证优质解进入下一代演化。最劣前沿上被最多的个体支配的解收敛性最差。当所有解互不支配时，具有最小超体积贡献度的解多样性最差。基于pareto支配和超体积贡献度，算法4中的环境选择可以保证解的收敛性和多样性。根据环境选择，将更优的航迹保存在外部文档a中的过程包括以下步骤：
为了保证解的收敛性，需要删除最劣前沿上被最多的个体支配的解(算法伪代码第1-2行，支配指的是演化算法中的pareto支配)，即如果a∪np中存在被其他个体支配的解，删除最劣前沿上被最多的个体支配的解xp∈a∪np；否则(即所有解具有相同的pareto等级)，删除超体积贡献度最小的解(算法伪代码第3-5行)；
如果新航迹np至少比外部文档a中的一个解优秀，则被删除的解xp是位于a中的。此时，分别用新航迹np，新航迹的交配限制概率β*以及新航迹的可行性i*更新外部文档a，交配限制概率矩阵b和可行性矩阵i(算法伪代码第6-9行)。
本发明考虑到航迹规划问题中，不同的路径点具有不同的质量，需要不同的搜索策略。因此，提出了一种基于评估函数和k-means聚类算法的自适应交配限制策略和一种基于此策略的多目标演化算法(mfkc)。mfkc首先利用k-means算法找到每条航迹的邻居个体，然后基于每个路径点的交配限制概率决定其父代来源，从而加强勘探或者开采。随后利用包含局部搜索算子的重组算子产生新航迹。最后利用评估函数计算新航迹的交配限制概率，并执行环境选择。
实施例
mfkc是一种多目标演化算法，而多目标演化算法根据环境选择机制可以分为基于支配，基于指标以及基于分解的多目标演化算法。关于重组算子，主要存在基于遗传算子和基于模型的多目标演化算法。因此，为了验证mfkc的性能，选择每一类中的代表性算法(基于支配的nsga-ii，基于指标的sms-emoa，基于分解的moea/d-de和基于模型的rm-meda)为对比算法。为了对比的公平性，将nsga-ii和sms-emoa中的sbx算子替换为de算子。此外，基于原始文献和前期实验，对每个算法的参数进行了优化。具体参数值如表5所示。
表5针对两种场景下无人机航迹规划问题的nsga-ii，sms-emoa，moea/d-de，rm-meda和mfkc算法的参数值
选用超体积指标(hv)评估算法性能。计算hv值时的参考点为z＝[1.5,1.5]t。每个算法在每种场景下独立运行31次获得hv的统计结果列于表2中。每种算法搜索失败的次数列于括号中。
表6nsga-ii，sms-emoa，rm-meda，moea/d-de以及mfkc算法在两种场景下的无人机航迹优化问题上获得的统计结果
mfkc在两种场景下均获得了最佳的hv平均值，而moea/d-de获得了次优hv均值。在场景1中，moea/d-de有2次未能成功找到n条可行航迹。与之相反，mfkc在31次运行中均找到了可行航迹。在场景2中，因为防空单元数目增多，可行空间变小，所以moea/d-de和mfkc搜索失败的次数都变多了。然而，相比于moea/d-de，mfkc仍然具有更多的成功次数并获得了更大的hv平均值。综上可知，mfkc性能更优。
选择mfkc在31次运行中获得最大hv值时，场景1下的n条航迹中航迹长度最短的航迹如图3(a)和图3(b)所示，图3(a)和图3(b)是相同的飞行航迹，只是绘制角度不同。场景1下的n条航迹中飞行高度最低的航迹如图3(c)至图3(d)所示，图3(c)和图3(d)是相同的飞行航迹，只是绘制角度不同。
场景2下的n条航迹中航迹长度最短的航迹如图4(a)和图4(b)所示。图4(a)和图4(b)是相同的飞行航迹，只是绘制角度不同。场景2下的n条航迹中飞行高度最低的航迹如图4(c)至图4(d)所示，图,4(c)和图4(d)是相同的飞行航迹，只是绘制角度不同。
可以从图3(a)至图3(d)和图4(a)至图4(d)中发现，mfkc搜索到的飞行航迹是可行的。对比上图和下图的飞行航迹发现，具有最短飞行长度的航迹飞行高度较高，而具有最低飞行高度的航迹飞行长度较长。这一现象再次说明无人机航迹规划问题的目标是相互冲突的，一个目标值的提升导致另一个目标值的下降。然而，mfkc可以权衡飞行航迹总长度与飞行高度两个目标，找到一系列多样化的可行航迹供决策者选择。
需要注意的是，具体实施方式仅仅是对本发明技术方案的解释和说明，不能以此限定权利保护范围。凡根据本发明权利要求书和说明书所做的仅仅是局部改变的，仍应落入本发明的保护范围内。
1.一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，包括以下步骤：
首先，利用航迹的路径点坐标组成染色体，随机地生成初始种群p＝{x1,…,xn}并计算p目标值，同时建立外部文档a用于储存环境选择中表现优良的解；x1为第1条航迹，xn为第n条航迹；
然后，针对所有航迹，计算每个路径点的交配限制概率矩阵b和可行性矩阵i；
交配限制概率矩阵
随后将n条航迹演化t代；每一代的航迹演化过程包括以下步骤：
首先利用聚类算法将所有航迹聚类，找到每条航迹的邻居航迹矩阵s；
然后对每条航迹进行重组操作和环境选择操作；其中，针对路径点进行重组的过程中，重组算子演化更新w-2个路径点，生成新航迹np；
然后计算新航迹的目标值以及新航迹中路径点的交配限制概率β*和可行性i*；
随后，将新航迹和外部文档混合进行环境选择，如新航迹质量较优，则保存至外部文档，并利用β*和i*更新b和i；
在每一代演化的最后，利用a更新p；
所述计算新航迹中路径点的交配限制概率β*和可行性i*的过程包括以下步骤：
计算第j个路径点的约束违反值，航迹长度指标值dscorej和高度指标值hscorej；
如果第五约束g5＞0，设置交配限制概率
对于违反第一约束至第四约束条件的路径点，
如果路径点没有违反约束，则路径点是可行的
最终得到路径点的交配限制概率
第一约束为转弯角约束，第二约束为坡度角的约束，第三约束为航迹段中间点高度约束，第四约束为最小航迹段长度约束，第五约束为航迹的总长度约束；
其中，xj,yj,zj是第j个路径点的坐标值；pzj,m为航迹段上的第m个中间点的z轴坐标，m＝1,…,nm。
2.根据权利要求1所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，第一约束至第五约束具体如下：
θmax是无人机的最大转弯角；θj是矢量(xj-xj-1,yj-yj-1)和(xj 1-xj,yj 1-yj)之间的夹角；第一个约束函数表示为：
其中，
αmax是最大爬升/俯冲角限制，航迹段的斜率αj表示航迹的爬升/俯冲角；第二个约束函数为：
其中，
hmin为无人机到地面的最低垂直高度；第三个约束函数表示为：
其中，
dj为两个相邻路径点之间的距离，lmin为最小航迹段长度；第四个约束函数表示如下：
其中，
规划航迹时还规定航迹的总长度小于一个预定义的长度值lmax；第五个约束函数为：
3.根据权利要求2所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，所述pzj,m＝zj-1 m/nm×(zj-zj-1)。
4.根据权利要求2所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，计算新航迹的目标值中所述的目标值如下：
x＝(x1,y1,z1,…,xw,yw,zw)t
s.t.xj∈[xa,xb],yj∈[ya,yb],zj∈[za,zb]
其中，f1(x)为总航迹长度，f2(x)为总飞行高度，gk为约束函数，k为聚类数；x1,y1,z1为第1个路径点的坐标值，xw,yw,zw为第w个路径点的坐标值，w为航迹中路径个数；[xa,xb],[ya,yb]和[za,zb]分别表示x，y和z坐标的下边界和上边界。
5.根据权利要求4所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，所述针对路径点进行重组，产生新航迹np的具体过程包括以下步骤：
首先选择可行航迹中最差的路径点；如果一条航迹中所有路径点为可行的，则该条航迹为可行航迹；此时具有最大交配限制概率的路径点为最差路径点；
然后对每个路径点进行重组操作，具体包括以下步骤：
对于第i条航迹中的第j个路径点，找到其邻居航迹sk,k∈{1,…,k}；
根据交配限制概率
然后利用差分进化算子产生尝试解
将超过搜索空间的基因值设为边界值；
针对
最后，如果第ww个路径点比之前的飞行高度更高，优化路径点的飞行高度。
6.根据权利要求5所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，所述的配对池
其中，rand1是[0,1]范围内的随机数。
7.根据权利要求6所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，利用差分进化算子产生的尝试解
其中rand2、rand3、rand4是[0,1]范围内的随机数；f是差分系数，cr是交叉概率。
8.根据权利要求7所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，如果第ww个路径点比之前的飞行高度更高，优化路径点的飞行高度为
其中，
9.根据权利要求1至8之一所述的一种针对路径点聚类机器学习的无人机航迹规划方法，其特征在于，所述聚类算法采用k-means算法。
技术总结