[0075] 以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
[0076] 本发明的目的是针对现有技术的缺陷，提供了一种基于遗传算法的飞行器航迹快速规划优化方法。
[0077] 实施例一
[0078] 本实施例提供一种基于遗传算法的飞行器航迹快速规划优化方法，如图1所示，包括步骤：
[0079] S11.建立多目标飞行器路线规划的目标函数和约束条件；
[0080] S12.根据所述目标函数和约束条件建立多目标飞行器路线规划的第一模型；
[0081] S13.基于非支配排序遗传算法NSGA‑II对建立的第一模型进行求解，得到航迹规划的最优解。
[0082] 本实施例要求为智能飞行器拟制最佳的校准飞行路线，保证其在飞行过程中位置误差能够得到及时校正并按照规定航迹继续飞行，同时，拟定的路线还需要满足问题相应的约束条件，使得飞行器的航迹长度尽可能小，且经过校正区域进行校正的次数尽可能少。
[0083] 如图2所示，智能飞行器从起始点A点出发，其垂直和水平误差均为0。
[0084] 飞行器经过垂直误差校正点时，需要满足垂直误差不大于α1个单位，水平误差不大于α2个单位，才能进行即时垂直误差校正，即垂直误差清零。
[0085] 飞行器经过水平误差校正点时，需要满足垂直误差不大于β1个单位，水平误差不大于β2个单位，才能进行即时水平误差校正，即水平误差清零。
[0086] 因此，可将上述问题转换为带约束条件的多目标车辆路线规划问题(Multi‑objective Vehicle Routing Problem,MVRP)，进而转述为：不考虑转弯半径，探寻出一种误差校正点规划方案，使得在经过校正点数量最少的情况下，车辆(飞行器)经过的路径长度最短。
[0087] 在步骤S11中，建立多目标飞行器路线规划的目标函数和约束条件。
[0088] 根据上述内容的分析，本模型存在两个优化目标，分别为飞行器航迹最短和飞行器经过的误差调整点数量最少，故将目标函数设定如下：
[0089]
[0090] 其中，Tab表示飞行器从A点出发抵达B点时飞行航迹的总长度；N表示飞行器在飞行过程中所经过的误差校正点的数量；k表示经过的校正点的集合，{k1,k2,…,kn}； 表示A点到第一个误差校正点的航迹长度； 表示第i个校准点到第i+1校准点的航迹长度；表示最后一个校准点到终点B点的航迹长度；
[0091] 建立多目标飞行器路线规划的约束条件，约束条件包括第一约束条件、第二约束条件、第三约束条件；
[0092] 第一约束条件为当飞行器的垂直误差不大于α1个单位，水平误差不大于α2个单位时才能进行垂直误差校正，表示为：
[0093]
[0094]
[0095] 其中， 表示飞行器到达垂直校正点时的垂直误差， 表示飞行器到达垂直校正点时的水平误差；α1表示飞行器垂直误差在垂直误差校正点能被校正时，垂直最大容差；α2表示飞行器垂直误差在垂直误差校正点能被校正时，水平最大容差；
[0096] 第二约束条件为当飞行器的垂直误差不大于β1个单位，水平误差不大于β2个单位时才能进行水平误差校正，表示为：
[0097]
[0098]
[0099] 其中， 为飞行器到达垂直校正点时的垂直误差， 为飞行器到达垂直校正点时的水平误差；β1表示飞行器水平误差在垂直误差校正点能被校正时，垂直最大容差；β2表示飞行器水平误差在垂直误差校正点能被校正时，水平最大容差。
[0100] 第三约束条件为当垂直误差和水平误差均小于θ个单位时，飞行器仍能够按照规划路径飞行，表示为：
[0101]
[0102]
[0103] 其中，i＝0时，ki即为A点； 分别表示离开当前误差校正点时飞行器的垂直误差和水平误差；δ表示飞行器每行进1m产生的误差专用单位； 表示当前误差校正点到规划方案中下一个误差校正点的距离。
[0104] 在步骤S12中，根据目标函数和约束条件建立多目标飞行器路线规划的第一模型。
[0105] 不考虑飞行器在飞行过程中转弯受到结构和控制系统的限制，即不考虑最小转弯半径，设定的数学模型如下：
[0106]
[0107]
[0108] 在步骤S13中，基于非支配排序遗传算法NSGA‑II对建立的第一模型进行求解，得到航迹规划的最优解。
[0109] 在以往针对单目标优化问题，能够使用诸如遗传算法、蚁群算法、粒子群算法等智能优化算法对问题进行求解，而且在小规模问题中往往能够得到最优解。然而在多目标优化问题中如问题一，各个目标之间相互制约，较多情况在改善一个目标性能效果时，损失了其他目标的性能效果，难以求得一个使所有目标性能效果都达到最优的解，因此，本发明采用NSGA‑II算法，该算法在众多解决多目标优化问题的遗传算法中影响最大且应用范围最广，具有简单有效、特征对比明显的优点。
[0110] 如图3所示，步骤S13具体包括：
[0111] S131.根据约束条件，产生规模为N的可行解集作为初始父代种群Pt，并通过遗传算子产生子代种群Qt，并将产生的父代种群和子代种群合并形成种群Rt；
[0112] S132.对种群Rt进行快速非支配排序，并计算每个非支配层中的个体拥挤度，根据非支配排序结果和个体拥挤度结果，利用精英选择策略选取数量为N的个体组成新的父代种群Pt+1；
[0113] S133.对选取的新的父代种群进行选择、交叉、变异操作，得到数量为N的新的子代种群Qt+1，将新的父代种群Pt+1和新的子代种群Qt+1进行合并，形成新的种群Rt+1；
[0114] S134.重复步骤S132‑S133，直到达到设定的最大迭代次数。
[0115] 本实施例以数据集1、数据集2为例具体说明：
[0116] 建立多目标飞行器路线规划的第一模型，利用NSGA‑II算法进行求解，求解结果显示：
[0117] 数据集1中存在2个较好方案：方案1——飞行器在经过8个误差校正点后，最短航迹距离为106050.2342米，航迹规划方案为：0(A)—>303—>64—>607—>170—>278—>369—>214—>397—>612(B)，程序运行时间为17.18s；方案2——飞行器在经过9个误差校正点后，最短航迹距离为105236.7332米，航迹规划方案为：0(A)—>503—>69—>237—>
233—>33—>315—>403—>594—>397—>612(B)，程序运行时间为15.562s。
[0118] 数据集2中的最好方案：飞行器在经过12个误差校正点后，最短航迹距离为118026.3673米，航迹规划方案为：0(A)—>163—>114—>5—>222—>8—>309—>305—>
123—>45—>160—>92—>93—>61—>292—>326(B)，程序运行时间为10.01s。上述各方案求解得出的最短航迹距离均接近于AB两点直线距离，因此可证明算法的有效性，NSGA‑II算
2
法复杂度为O(mN),其中m为目标函数数量，N为种群规模。
[0119] 本实施例通过对第一模型进行求解，得到两个优解，如下表1：
[0120] 最短航迹距离(米) 经过的最少校正点数量(个)方案1 105236.7332 9
方案2 106050.2342 8
[0121] 表1
[0122] 如图4所示为方案一中飞行器最短飞行航迹以及误差校正点的最小数量示意图；如图5所示为方案一中飞行器的航迹图。
[0123] 如图6所示为方案二中飞行器最短飞行航迹以及误差校正点的最小数量示意图；如图7所示为方案二中飞行器的航迹图。
[0124] 由表1可以得出，在方案一中飞行器需多经历1个校准点，但航迹距离仅减少813.501米，因此，选择方案二作为第一模型中的最优解，如下表2为方案二中数据集1的结果：
[0125] 校正点编号 校正前垂直误差 校正前水平误差 校正点类型0 0 0 出发点A
303 17.674222 17.674222 0
64 22.805206 5.130984 1
607 18.455596 23.58658 0
170 22.048516 3.592919 1
278 10.457033 14.049953 0
369 21.893167 11.436134 1
214 13.313572 24.749705 0
397 22.330655 9.017083 1
612 16.972691 25.989774 终点B
[0126] 表2
[0127] 依据数据集1，得出飞行器最短航迹为106050.2342米，经过误差校正点的最少数量为8个，且经过顺序为：0(A)—>303—>64—>607—>170—>278—>369—>214—>397—>612(B)。
[0128] 如下表3为方案二中数据集2的结果：
[0129]
[0130]
[0131] 表3
[0132] 依据数据集2，得出飞行器最短航迹为118026.3673米，经过误差校正点的最少数量为12个，且经过顺序为：0(A)—>163—>114—>5—>222—>8—>309—>305—>123—>45—>160—>92—>93—>61—>292—>326(B)。
[0133] 如图8所示为飞行器最短飞行航迹以及误差校正点的最小数量示意图；如图9所示为数据集2中飞行器的航迹图。
[0134] NSGA‑II是对初代NSGA算法的改进，被广大研究者运用在复杂约束条件下的多目标优化问题，而其优化体现在以下三个方面：
[0135] 1.算法复杂度。NSGA‑II在初代算法的基础上，使用了快速非支配排序算法，使得3 2
算法的时间复杂度由第一代O(mN)降至O(mN)，其中m为目标函数的个数，N为种群的大小。
[0136] 2.精英选择策略。采用精英选择策略，并将父代种群和自带种群和并扩大采样规模，保证父代中的优良个体得以保留，不会被抛弃，从而提高由算法得出结果的准确性。
[0137] 3.拥挤度比较准则。弥补了初代算法需要主动设定共享参数的缺陷，使用拥挤度比较准则作为种群个体间的比较标准，保证种群的多样性。
[0138] 综上，本实施例采用NSGA‑II算法求解该问题，得出的最短航迹距离均接近于AB两点直线距离，因此可证明算法是有效的。
[0139] 本实施例对三维空间的飞行器航迹规划问题，转化为多目标车辆路径规划问题，将复杂的飞行器空间航迹规划转为多约束下求解给定点的最短路径，简化了计算复杂度，提高了模型的通用性。
[0140] 实施例二
[0141] 本实施例提供的一种基于遗传算法的飞行器航迹快速规划优化方法与实施例一的不同之处在于：
[0142] 本实施例在第一模型的基础上考虑了转弯半径的飞行器航迹规划，得到第二模型，具体步骤为：
[0143] S11.建立多目标飞行器路线规划的目标函数和约束条件；
[0144] S12.根据所述目标函数和约束条件建立多目标飞行器路线规划的第一模型；
[0145] S13.将飞行器自身最小转弯半径的约束条件加入第一模型中，得到多目标飞行器路线规划的第二模型；
[0146] S14.基于非支配排序遗传算法NSGA‑II对建立的第二模型进行求解，得到航迹规划的最优解。
[0147] 本实施例的步骤S11、步骤S12、步骤S14均与实施例一类似，在此不多做赘述。
[0148] 在步骤S13中，将飞行器自身最小转弯半径的约束条件加入第一模型中，得到多目标飞行器路线规划的第二模型。
[0149] 飞行器在转弯时受到结构和控制系统的限制，无法完成即时转弯(飞行器前进方向无法突然改变)，假设飞行器的最小转弯半径为200m，因此飞行器自身最小转弯半径的约束条件，表示为：
[0150]
[0151] 其中， 表示经过第i‑1个、第i个、第i+1个校准点确定的圆的半径，i≥2。
[0152] 在第一模型的基础上，目标函数不变，加入上述新增约束条件，第二模型表示为：
[0153]
[0154]
[0155] 本实施例以数据集1、数据集2为例具体说明：
[0156] 基于第一模型，加入最小转弯半径的约束条件。本实施例证明了飞行器在最小转弯半径下航线距离最短的结论。求解飞行器转弯圆弧距离时，将航迹规划方案中连续经过的3个误差校正点转化为二维平面对圆弧进行求解。结合实施例一中提出的第一模型，得到最佳航迹规划方案：
[0157] 数据集1：飞行器在经过8个误差校正点后，最短航迹距离为109029.2049米，航迹规划方案为：0(A)—>346—>69—>237—>155—>338—>457—>555—>277—>612(B)，运行时间为14.95s；
[0158] 数据集2：飞行器在经过12个误差校正点后，最短航迹距离为113426.3511米，航迹规划方案为：0(A)—>163—>114—>8—>309—>305—>123—>45—>160—>92—>93—>61—>292—>326(B)，运行时间为11.96s。
[0159] 通过对第二模型进行求解，得到两个优解，如下表4：
[0160] 最短航迹距离(米) 经过的最少校正点数量(个)方案1 106351.0792 9
方案2 109029.2049 8
[0161] 表4
[0162] 如下表5所示为数据集1的结果：
[0163]
[0164]
[0165] 表5
[0166] 依据数据集1，在再加入飞行器最小转弯半径的约束下，得出飞行器最短航迹为109029.2049米，经过误差校正点的最少数量为8个，且经过顺序为：0(A)—>346—>69—>
237—>155—>338—>457—>555—>277—>612(B)。
[0167] 如图10所示为飞行器最短飞行航迹以及误差校正点的最小数量示意图；如图11所示为数据集1中飞行器的航迹图。
[0168] 如下表6所示为数据集2的结果：
[0169]
[0170]
[0171] 表6
[0172] 依据数据集2，在再加入飞行器最小转弯半径的约束下，得出飞行器最短航迹为113426.3511米，经过误差校正点的最少数量为12个，且经过顺序为：0(A)—>163—>114—>
8—>309—>305—>123—>45—>160—>92—>93—>61—>292—>326(B)。
[0173] 如图12所示为方案二中飞行器最短飞行航迹以及误差校正点的最小数量示意图；如图13所示为数据集2中飞行器的航迹图。
[0174] 本实施例依旧使用带精英策略的非支配排序遗传算法(NSGA‑II)，只在问题一的2
基础上加入了飞行器的最小转弯半径的约束，因此算法的有效性和复杂度(O(mN))均未发生明显改变。
[0175] 本实施例将航迹规划方案中连续经过的3个误差校正点转化为二维平面对曲线航迹进行求解，降低了计算的复杂度，提高了求解效率。
[0176] 实施例三
[0177] 本实施例提供的一种基于遗传算法的飞行器航迹快速规划优化方法与实施例一的不同之处在于：
[0178] 本实施例考虑随时间会发生动态变化的飞行环，即使校正点在飞行器飞行前已经确定，但飞行器在部分校正点(简称为异常点)进行误差校正时存在无法达到理想校正的情况，即将某个误差精确校正为0。异常点能够成功将某个状态的误差校正为0的概率是80％，如果校正失败，则校正后的剩余误差为min(error校正前,5)个单位。在考虑异常点存在校正失败的情况下，以成功到达终点的概率尽可能大为目标，建立三目标优化模型(航迹尽可能短、经过的误差校正点数量尽可能少、成功到达终点的概率尽可能大)，求解出最佳飞行航迹规划方案。
[0179] 具体包括步骤：
[0180] S11.建立多目标飞行器路线规划的目标函数和约束条件；
[0181] S12.根据所述目标函数和约束条件建立多目标飞行器路线规划的第一模型；
[0182] S13.将误差校正失败概率的约束条件加入第一模型中，得到多目标飞行器路线规划的第三模型；
[0183] S14.基于非支配排序遗传算法NSGA‑II对建立的第三模型进行求解，得到航迹规划的最优解。
[0184] 在步骤S13中，若飞行当前所在校正点是异常点(存在校准失败的概率)，那么下一个校准点必须为正常点，即异常点不能连续出现，误差校正失败概率的约束条件表示为：
[0185] fi×fi+1＝0
[0186] 其中，fi表示第i个误差校正点是否为异常点。
[0187] 根据申述内容，存在三个优化目标，分别为飞行器航迹最短、飞行器经过的误差调整点数量最少以及飞行器成功抵达终点的概率最大，故将目标函数设定如下：
[0188]
[0189] 其中， 表示经过异常点，没有被成功校正但能继续按规定航迹飞行的概率；Pf＝0表示经过正常点的概率
[0190] 在第一模型建立的模型基础上，目标函数不变，加入上述新增约束条件，得到多目标飞行器路线规划的第三模型，表示为：
[0191]
[0192]
[0193] 本实施例以数据集1、数据集2为例具体说明：
[0194] 基于第一模型，考虑飞行器在动态环境下到达部分误差校正点会出现校正失败的情况，通过控制异常点出现的频率及其连续性，从而保证飞行器成功抵达终点的概率尽可能大，为此建立了多目标优化模型，利用NSGA‑II算法对问题进行求解，给出航迹规划的最优策略。
[0195] 数据集1：飞行器在经过9个误差校正点后，最短航迹距离为111311.1米，航迹规划方案为：0(A)—>503—>69—>91—>233—>89—>315—>450—>594—>397—>612(B)。
[0196] 数据集2：飞行器在经过16个误差校正点后，最短航迹距离为129859.4米，航迹规划方案为：0(A)—>140—>163—>114—>188—>5—>222—>227—>309—>54—>123—>115—>160—>92—>93—>61—>292—>326(B)。
[0197] 通过对第三模型进行求解，得到三个优解，如下表7：
[0198]
[0199] 表7
[0200] 对比三个方案后，选择成功概率最大的方案3作为最优解展示。
[0201] 如下表8所示为方案3中数据集1的结果：
[0202]校正点编号 校正前垂直误差 校正前水平误差 校正点类型
0 0 0 出发点A
503 13.387920 13.387920 1
69 8.807342 22.195262 0
91 17.708705 8.901363 1
233 14.649724 23.551087 0
89 22.432534 7.782811 1
315 14.378320 22.161131 0
450 19.697496 5.319176 1
594 18.052585 23.371761 0
397 21.111709 3.059124 1
612 16.972691 20.031816 终点B
[0203] 表8
[0204] 如图14所示为数据集1中飞行器的航迹图。
[0205] 如下表9所示为通过对第三模型的求解，得到两个优解：
[0206]
[0207] 表9
[0208] 如下表10为表9中方案2的数据集2：
[0209]
[0210]
[0211] 表10
[0212] 如图15所示为方案2中数据集2中飞行器的航迹图。
[0213] 本实施例依旧使用带精英策略的非支配排序遗传算法(NSGA‑II)，只在问题一的2
基础上加入了飞行器的最小转弯半径的约束，因此算法的有效性和复杂度(O(mN))均未发生明显改变。
[0214] 本实施例通过分类讨论，分析了飞行器在动态环境下误差校正的多种情况，对飞行成功概率分析模型进行了优化，提高了可行解的搜索广度。
[0215] 注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例，而本发明的范围由所附的权利要求范围决定。
