复杂环境下航迹快速规划是智能飞行器控制的一个重要课题。本文分析智能飞行器系 统自身结构局限性以及飞行环境导致飞行任务失败等多种原因，建立了多目标规划模型， 利用禁忌搜索算法和遗传算法求解出最优的智能飞行器航行轨迹方案。
针对问题一，在确保智能飞行器能够成功到达目的地的条件下，本文考虑了多种约束 条件，建立了多约束条件下航迹长度最小化和误差校正点数最小化的双目标优化模型。模 型求解时， 首先引入规范函数进行无量纲化处理并通过线性加权法将该模型转化为单目标 优化模型， 以降低模型复杂度；然后通过约束条件将符合条件的误差校正点根据航迹长度 最短原则，使用贪心算法初始化解， 再使用禁忌搜索算法，优化初始解， 在 120 次迭代后 得到较优解， 运行时间为 70.64s， 改善情况为 6.55%。对数据集 1 求解出的最佳航行轨迹 方案为： A→503→69→237→115→338→457→555→436→B， 经过误差校正点数 8 个， 航 迹长度为 104898m， 比 AB 直线距离增加了 4.41%；对数据集 2 求解出的最佳航行轨迹方 案为： A→163→114→8→309→305→123→45→160→92→93 →61→292→B， 经过误差校 正点数 12 个， 航迹长度为 109342m， 比 AB 直线距离增加了 6.11%。该算法时间复杂度为 O n ( ) 2 。本文通过深度优先搜索策略进行遍历， 验证两组数据最优解的校正点数为 8 和 12， 该算法针对两组数据最优解的点数均为最优；同时，两组数据航迹长度比仅比 AB 直线距 离增加 4.41%和 6.11%， 验证了算法的有效性。
针对问题二，在确保智能飞行器能够成功到达目的地的条件下，需要考虑飞行器转向 轨迹。为此本文参考 Dubins 曲线，分析了飞行器在三维空间中从 A 点到 B 点的转向过程， 设计了飞行器转向约束，根据优先级尽可能短的航迹长度>尽可能少的误差校正点，在此 基础上改进问题一的双目标优化模型，建立了带多约束条件的航迹长度最小化和误差校正 点数最小化的双目标优化模型。模型求解时， 先引入规范函数进行无量纲化处理并通过线 性加权法将该模型转化为单目标优化模型， 再使用贪心算法求解初始化解，然后引入了集 中和分散机制，提出并使用改进禁忌搜索算法优化初始解，一定程度上解决了禁忌搜索算 法在求解优化问题时存在着的停滞现象，进一步提高了禁忌搜索算法的搜索质量和收敛速 度， 在 120 次迭代后得到较优解，运行时间为 74.41s，改善情况为 6.79%。 对数据集 1 求 解出的最佳航行轨迹方案为： A→503→69→237→233→598→561→448→485→B，经过误2 差校正点数 8 个，航迹长度为 104960m，比 AB 直线距离增加了 4.47%，比问题一最优方 案距离增加了 0.02%；对数据集 2 求解出的最佳航行轨迹方案为： A→163→114→8→309 →305→123→45→160→92→93→61→292→B，经过误差校正点数 12 个，航迹长度为 109411m，比 AB 直线距离增加了 6.18%，比问题一最优方案距离增加了 0.06%。该算法 时间复杂度低于O n ( ) 2 。本文通过深度优先搜索策略进行遍历， 验证两组数据最优解的校 正点数为 8 和 12， 该算法针对两组数据最优解的点数均为最优；同时，两组数据航迹长度 比仅比 AB 直线距离增加 4.47%和 6.18%，仅比第一问最优方案增加了 0.02%和 0.06%， 验证了算法的有效性。
针对问题三，由于无法确保智能飞行器能够成功抵达目的地，因此需尽量降低失败概 率，同时使航迹长度尽可能小，经过的校正点个数尽可能少。为此本文考虑了飞行器成功 到达目的地的多种约束条件，建立了带多约束条件的失败概率最小化、航迹长度最小化和 误差校正点数最小化的多目标优化模型。通过模型求解时， 先引入规范函数进行无量纲化 处理并通过线性加权法将该模型转化为单目标模型，再使用贪心算法求解初始化解，然后 将禁忌搜索算法与遗传算法结合，提出并使用遗传禁忌混合搜索算法优化初始解， 在 120 次迭代后得到较优解，运行时间为 87.86s，改善情况为 6.13%。 对数据集 1 求解出的最佳 航行轨迹方案为： A→578→417→80→237→607→33→194→450→448→485→302→612 →B， 经过误差校正点数 12 个， 航迹长度为 108439m， 比 AB 直线距离增加了 7.93%， 成 功抵达终点概率 100%；对数据集 2 求解出的最佳航行轨迹方案为： A→169→322→100→ 137→194→190→296→250 →243→73→82→44 →211→321→279→301→38→287→99→326 →B， 经过误差校正点数 19 个， 航迹长度为 147271m， 比 AB 直线距离增加了 42.91%， 成 功抵达终点概率 65.01%。该算法时间复杂度T n O n ( ) ( / ) = 4 （ 为种群数量）。本文通过 深度优先搜索策略进行遍历， 验证两组数据最优解的校正点数为 12 和 19， 该算法针对两 组数据最优解的点数均为最优；同时，两组数据航迹长度比比 AB 直线距离增加 7.93%和 42.91%， 验证了算法的有效性。
关键词： 多目标规划； 贪心算法； 禁忌搜索算法； 时间复杂度
F19103360018链接：https://pan.baidu.com/s/14mh0f6BAASBmTndzM0NTRQ
提取码：ly2o
代码下载地址：下载地址