关 键 词：

无人机 自主 飞行 航迹 规划 算法 研究

资源描述：

无人机自主飞行航迹规划算法研究,无人机,自主,飞行,航迹,规划,算法,研究

内容简介：

本科毕业设计论文本科毕业设计论文题题 目目无人机自主飞行航迹规划算法研究无人机自主飞行航迹规划算法研究系 别 自动化系 专 业 自动化 班 级 191002 学生姓名 张 川 学 号 103613 指导教师 聂 聪 毕业 任务书一、题目无人机自主飞行航迹规划算法研究2、指导思想和目的要求(1) 了解和熟悉现代飞行控制技术的基本概念、内容与作用；(2) 熟悉已有的航迹规划算法，选择并设计合适的航迹规划算法；(3) 综合运用已学的有关飞行控制与飞行仿真方面的知识，并参阅国内外有关参考文献，设计某型无人机的航迹自主飞行控制系统，达到理论与实践相结合的目的；(4) 基本掌握飞行控制系统的计算机仿真方法与仿真实践。三、主要技术指标(1) 完成航迹规划算法，满足某型飞机的任务要求。(2) 完成飞机的航迹控制，侧向航迹误差在 5 米内；四、进度和要求毕业设计论文时间从 2014 年 2 月 25 日6 月 1 日，应在 15 周内完成。2014 年 6 月 1 日6 月 20 日为论文评阅、答辩时间。进度要求：1)第 1 周第 3 周，开始英文资料翻译；收集论文资料，熟悉研究内容，确定设计方案。2)第 4 周第 12 周，按照指标要求开展论文的研究工作。3)第 13 周，论文初稿审查和修改。4)第 14 周，论文定稿和装订。5)第 15 周，论文评阅。6)第 16 周，论文答辩。设计论文西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文i其他要求：(1) 毕业设计论文格式严格按照教务处统一格式编写，模版从教务处网页下载。文内公式应编号、参考文献引用要标注，格式要统一。(2) 论文装订格式：正式封面、内封面（可无） 、任务书、中文摘要、英文摘要、目录、正文（包括论文总结和展望） 、参考文献、致谢等。(3) 英文资料翻译应在论文评阅前与英文原文单独装订成册并与论文一并上交，装订顺序为：封面、中文翻译稿、英文原文。5、主要参考书及参考资料(1) 飞行控制系统张明廉主编航空工业出版社(2) 飞行控制 肖顺达国防工业出版社(3) 现代飞行控制系统文传源北京航空航天大学(4) 控制系统计算机辅助设计MATLAB 语言及应用 薛定宇 著 清华大学出版社学生 张 川 指导教师 聂 聪 系主任 史仪凯 西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文摘 要无人机航迹规划是无人机任务规划系统的关键技术之一，也是无人机实现自主飞行和自主攻击的基础。论文比较了七种常用的航迹规划算法，提出了一种模拟退火遗传方法。最后通过设计侧向偏离控制律，对应用模拟退火遗传算法所规划的飞行最优路径进行了系统仿真验证，仿真结果取得了较好的效果。主要工作内容如下：（1）论述了空中主要威胁，并建立了雷达方程；综合考虑雷达威胁和航程等因素，确定了航迹代价函数；把无人机的航迹规划问题转化为图论中求最短路径的问题。（2）以正确度和复杂度作为仿真结果的评价标准，比较了Floyd算法，算法，双向算法，遗传算法，模拟退火算法，蚁群算法和粒子群算法，得*A*A出了如下的结论：传统的航迹规划算法的复杂度随着节点数的增加迅速上升，这就导致它在现代航迹规划算法中发展受到了限制；在随机算法中模拟退火算法正确性较高，而遗传算法复杂度较低。（3）针对无人机的具体特点并综合模拟退火算法和遗传算法提出了一种模拟退火遗传算法。仿真结果表明该方法继承了模拟退火算法正确性较高和遗传算法复杂度较低的优点。（4）建立了无人机的运动方程，使用模拟退火遗传算法规划出了最优飞行路径，最后使用侧向偏离控制律跟踪得出的最优路径。 关键词：无人机航迹规划，模拟退火遗传算法，侧向偏离，飞行控制西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文IABSTRACTUAV path planning is one of the key technologh of the UAV task planning system, meanwhile it is the foundation of automatic flight and automatic attack. This paper compares seven typical path planning method, brings up a kind of simulated annealing genetic algorithm. Finally, the laterad departure control law is designed, and the best route gained by simulated annealing genetic algorithm is tested by system simulation, and the results have a sound response. The main task of this paper can be outlined as follows:(1) The main air threaten is discussed, and the radar equation is established; after comprehensively considered radar threaten, distance and other factors, the path cost function is determined; the UAV path planning problem is transformed to the issue of finding the shortest route in the graph theory.(2) Setting the simulation accuracy and complexity as evaluated standards, this paper compares Floyd algorithm, algorithm, simulated annealing algorithm, *Agenetic algorithm, ant algorithm and particle swarm optimization algorithm and reaches this conclusion: the complexity of the traditional route planning algorithms incleases with the number of nodes which lead to the restriction of the their development in the modern route planning algorithm; the accuracy of the simulated annealing algorithm is high and the complexity of the genetic algorithm is low among the random algorithms.(3) Aiming at the concrete characteristic of UAV, a kind of simulated annealing genetic algorithm is brought up after weighing simulated annealing genetic and the genetic algorithm comprehensively. Through simulation, it inheriting the merits of high accuracy of the simulated annealing and the low complexity of the genetic algorithm is demonstrated.(4)The UAV locomotion equation is established and optimization path is gained 西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文IIfrom path planning method and finally the optimization route is tracked by using the laterad departure control law and the tracking results satisfy the requirements of GB2191-94.KEY WORDS UAV path planning, simulated annealing, genetic algorithm, laterad departure，flight simulation西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文III目 录摘摘 要要 .IABSTRACT.II第第 1 章章 概概 论论.11.1引言.11.2无人机航迹规划方法回顾.21.2.1 决策型搜索方法.31.2.2 随机型搜索方法.41.3 本文的主要工作.5第第 2 章章 无人机航迹规划基础无人机航迹规划基础.72.1 雷达威胁模型.72.2 航迹规划问题的数学描述.82.2.1 路线优化问题的模型.82.2.2 航迹代价函数.92.3 本章小节.10第第 3 章章 无人机航迹规划方法无人机航迹规划方法.113.1 传统航迹规划算法.113.1.1 Floyd 算法 .113.1.2 算法.12*A3.1.3 双向算法.15*A3.2 现代航迹规划算法.153.2.1 遗传算法.163.2.2 模拟退火算法.213.2.3 蚁群算法.24西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文IV3.2.4 粒子群算法.263.3 航迹规划算法的仿真分析.283.3.1 算法正确率分析.283.3.2 算法复杂度分析.383.4 航迹规划算法的比较.433.5 本章小结.45第第 4 章章 模拟退火遗传算法模拟退火遗传算法.474.1 模拟退火遗传算法的基本原理.474.2 模拟退火遗传算法编程的实现.474.3 模拟退火遗传算法仿真分析.534.4 本章小结.56第第 5 章章 基于模拟退火遗传算法的无人机航迹仿真基于模拟退火遗传算法的无人机航迹仿真.575.1 无人机运动方程.575.1.1 无人机运动的六自由度方程.575.1.2 无人机运动方程的解耦.595.2 无人机控制律.605.2.1 倾斜保持的自动控制.615.2.2 增稳系统.625.2.3 预选航向的自动控制.645.2.4 侧向偏离的自动控制.645.3 基于模拟退火遗传算法的无人机航迹仿真.685.4 本章小结.71第六章第六章 全文总结全文总结.72参考文献参考文献.73致致 谢谢.76毕业设计小结毕业设计小结.77西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文0第 1 章 概 论1.1 引言随着第一架无人机于20世纪初在英国诞生，在最近的一个世纪中无人机(UVA)得到了飞速的发展。它从最初简单的靶机，发展到现在广泛应用到侦查、监视、攻击以及电子战等多种任务的战斗平台1。随着现代科学技术的不断进步，无人机吸收了现代科技的优秀成果并朝着隐身化、数字化、小型化、智慧化、通用化以及攻防兼备等方向发展2。总的来说，现代无人机在战争中主要使用形式有1：（1）作侦察机使用，和军事卫星、有人驾驶侦察飞机相配合，为作战部队提供战区实时情报 。（2）作战术诱饵机使用，模拟飞机或导弹的雷达或红外特性，吸引对方火力，减少作战飞机的损失。（3）通信中继、炮火校正、作战效果评估等。由于无人机没有飞行员驾驶，所以它相对于有人驾驶飞机而言具有体积小、重量轻、机动性好、隐蔽性高、适应性强而且成本低等特点。这就使得它在军用和民用领域得到了广泛的关注3-4。正是因为无人机没有飞行员，为了使无人机能够实现全自主方式的飞行，操作人员必须提前对无人机的航线进行规划，包括航线中各个关键航点的经纬度位置信息、高度信息以及对任务设备的操作等。对操作人员而言，这是一项非常繁重的任务。随着计算机技术的进步和GPS系统的广泛应用，无人机地面控制站中逐渐发展出了一个崭新的独立模块一航迹系统。利用航迹系统，操作人员可以直接在数字地图上进行航迹的规划，能够实时、便捷地得到数字地图中任意一点的多种信息。这一功能将航迹规划所需的时间从原来的数个小时甚至更长时间缩短到了数十分钟甚至只需数分钟。同时，航迹系统还能够实时地跟踪无人机航迹5。目前美国研制的任务规划系统己经发展到第三代，正朝着提高效率和降低西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文1系统成本等方面继续发展。英国已研制成功Pathfinder2000任务规划系统。法国目前装备有M工PSY，CINNA和CIRCE2000等系列任务规划系统。90年代以来，NASA和美国军方联合开展一项名为ANOE的研究计划，旨在辅助直升机驾驶员实施贴地飞行。在50年代到70年代，飞行器航迹优化的理论有了一定的发展，主要的工作在于求近似解析解。随着最优控制理论、最优化数值计算方法和计算机技术的飞速发展，最优航迹的数值计算在80年代得到长足发展并趋于成熟。我国在八十年代初开始了地形跟踪与回避技术的研究，到了九十年代，这项技术的研究得到了蓬勃地发展，西工大、北航、南航等单位在飞行器低空突防策略和控制、航迹规划技术等领域做了一定的研究。目前，我国航迹规划技术研究正进一步向智能化、实时性、可实现性方向发展，但基本上还处于跟踪国外的水平，性能完善的航迹规划系统特别是无人机航迹规划系统还有待进一步研究开发2。1.2 无人机航迹规划方法回顾航迹规划方法的主要目的是在给定的规划区域内寻找一条最优的或满意的飞行航迹，因此从根本上讲属于一个路径或航迹搜索的问题。航迹规划方法一般可归纳为两大类搜索方法:决策型搜索方法和随机型搜索方法6。航迹规划方法的具体示意图如下所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文2 航迹规划方法 决策型搜索方法 随机型搜索方法 动态规划算法 启发式动态优先算法 盲目搜索方法 神经网络算法 蚁群算法 遗传算法 势场法 贝叶斯优算法 模拟退火算法 粒子群算法 Monte-Carlo算法 深度优先搜索技术 其它盲目搜索方法 宽度优先搜索技术 其它随机型搜索方法 图1-1 无人机航迹规划方法示意图1.2.1 决策型搜索方法（1）盲目搜索算法（非启发式搜索算法）盲目搜索方法是一种最简单的决策型算法。在无人机航迹规划中，这种算法无法利用目标信息指导其搜索过程，规划效率不高，目标信息仅仅被当作规划结束的判决条件6，所以它只适于求解比较简单的问题。无人机航迹规划常用的算法如宽度优先、深度优先搜索技术7等均属于盲目搜索，它们只提供了一种机械的搜索策略，而不能不断变化的外部威胁调整它们的搜索行为。这往往导致它们搜索效率低，而易触发组合爆炸。（2）启发式最佳优先算法在无人机航迹规划中，启发式最佳优先算法使用极为普遍。最佳优先算法在规划中利用到了启发式因子指导规划过程8，启发式信息在路径规划中主要是目标位置，它在规划中转换为了一种数据结构或函数，算法根据每个节点的启发信息来选择最佳的扩展节点，启发式算法的性能直接与这些启发式函数人f(n)的选择有关。由于启发式搜索引入了问题求解的目标信息，可以根据不同的求解目标而调整其规划行为，避免了盲H搜索，极大的提高了搜索的效率6。当西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文3把无人机运行区域网格化了之后，使用启发式函数f(n)=g(n)+h(n)，把无人机航迹规划问题转化为用树状结构表示，则就成了最佳优先算法即为著名的算法。*A其中g(n)为起始点到当前节点n的路径代价，h(n)为当前节点n到目标点的预测代价5。由于当算法的启发式因子满足单调性条件时，其搜索性能被证明是最*A佳的，因此在无人机航迹规划中成为最常用的算法之一9-10。*A（3）动态规划算法动态规划实际上是一种宽度优先算法的递归形式，它最早应用于最优控制问题。它将规划问题视为一个多级决策问题，然后将之转换为一系列简单的、易于求解的多个单级决策问题来处理5-6。它应用的一个前提条件即所谓的过程无后效性，也就是说，对于当前状态，前一个状态与决策的选择仅仅表现为它们将状态转移到了当前状态，并随之确定了可供选择的决策集合，至于当前状态到下一个状态的决策选择，以及后续过程将如何进行，与它们无关11。由于无人机航迹规划的特殊性，后一个状态一般前一个状态均有关联，这就大大的限制了动态规划算法在无人机航迹规划中的应用。1.2.2 随机型搜索方法（1）势场法基于势场法的路径搜索算法借鉴了电磁场理论的电磁势概念，为规划区域的不同物体建立起了势场，异性物体相吸，同性相斥。目标点被赋以很高的正势，而起始点被赋予比目标点还低的势位。而运动点被赋以与起始点相同的势位，同时障碍(禁飞区)则被赋以比起始点更低的势位。因而运动点被起始点与障碍所排斥，而被吸引向目标点6。在无人机航迹规划中，这种方法的主要缺点是运动点可能陷入局部极小值，即计算出来的航迹不一定最优的。（2）遗传算法在无人机航迹规划中，遗传算法是一种很有前途的随机型搜索算法12，它应用遗传学与进化论来分析问题求解问题。在其中，路径被编码成类似基因的结构。以代价函数为依据，通过对大量的路径基因串的再生产、基因互换、个体变异等运算，可以进化出具有最优基因的路径5。遗传算法的优点是它可以进行并行计算。然而，即使最优解的确存在，这种算法并不一定能找到最优解。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文4它常常收敛到一个性能平平的解，而在这个解的附近却有更好的解6,10。（3）模拟退火算法模拟退火算法摹仿了热力学中的退火过程。在无人机航迹规划问题中。退火算法将“加热”在起始点附近一定范围内的所有点。然后不断进行迭代运算，使所有的点的温度都逐渐冷却13。冷却的速度根据一个随机产生的冷却时间表决定。禁飞区域被赋以更高的能量状态，因而，冷却过程将回避这些区域，在迭代一定时间后，通过寻找规划区域的最低温度，可以得到最优航迹6。（4）蚁群算法粒子群算法是一种新兴的无人机航迹规划算法。蚁群算法 (Ant Algorithm)也是一种概率搜索算法，它利用生物信息激素(Pheromone/5tigmergy)作为蚂蚁选择后续行为的依据。每只蚂蚁会对一定范围内其它蚂蚁散布的生物信息激素做出反应，依据生物信息激素的强度在侮一个道日对多条路径选择做出概率上的判断并执行该选择，由此察觉并影响到它们以后的行为5。当一些路径上通过的蚂蚁越来越多时，其留下的生物信息激素轨迹(Trail)也越来越多，以致生物信息激素强度增大(当然，由于生物信息激素的蒸发作用，其强度会随时间的推移逐渐减弱)，后来蚂蚁做选择时该路径的被选概率也越高，从而更增加了该路径上的生物信息激素强度。这样，经过一个众多蚂蚁协同搜寻的过程后，几乎所有蚂蚁都会走最短的那一条路径，最短路径也由此被搜索找到14-15。（5）粒子群算法粒子群优化算法源于对鸟群觅食行为的研究。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，其行为不可预测，但其整体总保持一致性且个体与个体间也保持着最适宜的距离2。通过对类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制，它为群体的进化提供了一种优势这也是PSO算法形成的基础。由于粒子群算法的解是连续的，而无人机的航迹应该是离散的，这就大大限制了粒子群算法在无人机航迹规范中的应用。（6）贝叶斯优算法(BOA)把无人机路径编码为离散时间上的速度和航向变化序列，每一步的速度和航向变化量都限制在无人机相应最大变化量之内，所以这种编码方法对应的物理轨迹是无人机可飞的。利用每代种群中的优良解集构造贝叶斯网络，用贝叶西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文5斯网络的结构体现染色体基因位之间的联系，用贝叶斯网络参数体现染色体基因位之间的联系程度。用贝叶斯网络产生新的染色体以体现种群的进化，这取代了传统遗传算法的交叉和变异过程。如果不满足终止条件，则用新一代种群的优良解集构造贝叶斯网络，直到满足终止条件16。（7）Dijkstra 算法Dijkstra 算法是由EW狄克斯拉在1959年首先提出来的，是解决图论中最短路径的经典方法。与Floyd算法相似，该算法不仅能求出从起点到终点的最短路，而且还能求出起点到其它各中间点的最短路。其算法思想是按路径长度递增次序产生从某源点到图中各顶点的最短路径17。算法总的时间复杂度为O()2n18。由于无人机的航迹规划时节点数很多，Dijkstra 算法所需要的内存空间很难满足，这就意味着Dijkstra 算法在无人机规划中使用不多。1.3 本文的主要工作本文对7种典型的路径规划算法-Floyd算法，算法，双向算法，遗传*A*A算法，模拟退火算法，蚁群算法，粒子群算法-进行了分析，针对无人机任务的特殊性，综合考虑前七种方法的优缺点，提出了模拟退火遗传算法，并使用MATLAB软件进行了飞行仿真。本文的工作可以分为如下的几个方面：(1)第一章介绍了无人机的主要作战形式和无人机航迹规划算法的发展；简要的介绍了无人机航迹规划的两类方法-决策性搜索方法（传统搜索方法）和随机型搜索方法，并着重的介绍了盲目搜索算法（非启发式搜索算法） ，启发式最佳优先算法，动态规划算法，势场法，遗传算法，模拟退火算法，蚁群算法，粒子群优化算法（PSO） ，贝叶斯优算法(BOA)，Dijkstra 算法。(2)第二章分析了空中主要威胁，建立了雷达方程；综合考虑雷达威胁和航程等因素，确定了航迹代价函数；把无人机的航迹规划问题转化为图论问题。(3)第三章分析和比较了Floyd算法，算法，双向算法，遗传算法，模*A*A拟退火算法，蚁群算法和粒子群算法，并得出了重要的性质。(4)第四章综合模拟退火算法和遗传算法的特点并针对无人机的特殊要求提出了一种模拟退火遗传算法；通过仿真分析证明了它继承了模拟退火算法和遗传算法的优点。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文6(5)第五章建立了无人机的运动方程，通过小扰动原理实现了运动方程的横纵向解耦；使用模拟退火遗传算法得出了最优路径，然后使用侧向偏离控制律跟踪得到的最优路径；仿真结果满足了国军标GB2191-94要求。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文7第 2 章 无人机航迹规划基础2.1 雷达威胁模型在无人机完成指定任务的过程中，将受到多种威胁的综合作用，如地形因素威胁、电磁干扰威胁、防空火炮威胁、地空导弹威胁、雷达探测威胁以及大气条件威胁2。因为雷达是防空火力的“眼睛”，本文将着重考虑雷达的威胁。目前，雷达是远距离发现目标最重要的设备。依靠自身发射的电磁波，雷达通过对余波的分析来得到有关目标的信息。典型的雷达是由天线、发射机、接收机、信号处理器和终端显示设备组成。雷达发射机产生探测所需辐射强度的电磁波，强功率信号馈送到天线，由天线辐射到特定空间，为满足雷达的测向精度和分辨力，天线一般具有很强的方向性。接收机将微弱的目标回波信号经检波、放大等处理后，判断目标是否存在，并由显示设备方便显示2。雷达方程是描述雷达系统特性的最基本的数学方程。在雷达方程的完整形式中，考虑了雷达系统参量、目标参量、背景杂波和干扰影响、传播影响、传播介质等各种因素对雷达作用距离的影响，雷达方程对目标探测问题的分析十分必要19-21。常见的雷达方程如(2-1)式所示。 (2-1)222322(4 )TTRTRRTRBTRP G GF FPR R C L L 其中，各符号的含义见表2-1。如果在式(2-1)中考虑了方向图传播因子和损耗因子，未考虑大气衰减因子。对于收发合置的单基地雷达，由于= =R, = =G， = =L, TRRPTGRGRLTL=F,所以，式(2.1)可以简化为RFTF (2-2)22234(4 )TRBP GFPR C L 因此可以根据方程计算无人机在每一点被发现的概率从而优化无人机的轨迹。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文8 表 2-1 雷达航程各符号的含义符号含义符号含义RP雷达接收机收到的回波信号功率TP为雷达发射机输出功率TG发射天线增益RG接收天线增益雷达的工作波长目标的雷达散射截面积TF发射方向图传播因子RF接收方向图传播因子TR发射机到目标的距离RR接收机到目标的距离TL发射损耗因子RL接收损耗因子。BC滤波器与信号波形匹配程度系数，在匹配情况下，=1，不匹配情况下， BCBC12.2 航迹规划问题的数学描述把无人机进入威胁区域定位开始点，把攻击目标所处的方位作为目标点，我们可以把无人机的航迹规划问题转化为图论中的最优路径问题。这种方法是一种确定性状态空间搜索方法，可以减小规划空间的规模，降低了航路规划的难度22。因此我们可以分两步走：（1）我们先考虑一些约束条件（如无人机的航程） ，同时忽略掉一些约束条件（如无人机的性能约束） ，以航程最短以及威胁最小为目标，得出最优的航迹。（2）然后在此基础上利用没有考虑的剩余约束，对求得的航迹进行修正和光顺处理，以得到无人机可用的理性轨迹。把问题分解后我们可以看出，航迹规划问题的第一步实际上就是一个路线优化问题。2.2.1 路线优化问题的模型路线优化问题是依据某些优化准则，如花费代价最小或行走路线最短等，在其规划空间(网络图中)找出一条经过若干节点的，能够从起始点到达目标点，并且能够避开各种阻碍的最优运动路径，实现花费代价最小或行走路线最短等目标。它应可以根据起始点和目标点的方位和路网(空域)状况，选择最优路径西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文9及对多目标点存在的情况下进行优化选择以取得某种效益。它是包括机器人和导航等问题在内许多领域的研究内容22-23。对于无人机具体而言，可以对无人机的规划空间进行二维/三维网格划分以后会得到若干节点，构成个一个网络图。这样就把无人机复杂的路径规划问题简化为求取网络图中最短路径的优化问题，即从网络图的所有节点中选取一些节点，使得无人机在沿这些节点所形成的路径上飞行时路径的某种代价最小5。如果假设网络图的各个节点所组成的集合为S: S= , , 1s2sms网络图中所有可能的从起始点到目标点的路径集合为E:E= , , 1e2eme若 和 (,S)为其中某一条路径 (E )上的两个相邻节点，连iSjSiSjSkeke接两节点的边用V(,)表示，并用表示该条边的代价，则无人机的航路规iSjSijd划问题可描述为5: (2-3)ij1k(s ,s ) ekf(e )=min=s.t. e,ijijdE sS sS2.2.2 航迹代价函数为了得出无人机的最佳飞行航迹，应该综合考虑飞机的所面对的敌方威胁，飞机的机动性能的限制，地形的约束，航迹长度等因素。所以为了得到最优的路径，就需要对于综合考虑上节说提出的每条边的代价，它可以通过这些因ijd素加权平均来实现24。在第一步中，我们主要考虑敌方威胁和航迹长度，则每条边的代价可以如下表示：ijd (2-4)0(1)fLtfWk WkW dt式中，W为广义代价函数。为航路的威胁代价，为航路的油耗代价。系tWfW数k表示在制订航路过程中根据任务安排航路制订人员所做出的倾向性选择。如西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文10果认为无人机在飞行过程中速度保持恒定5，则上式可以改写如下:min (2-5)0(1)LtfWk WkW ds其中，L为航路的长度。那么，在节点搜索过程中第i条边的权值为 (2-6),(1)it if iwk wkw如果简单地认为敌方防御区域内的各个雷达均相同且无相互联系，并对雷达威胁模型进行了简化处理，认为雷达信号正比于1/ (d是无人机到敌方雷达、4d导弹威胁阵地的距离)，则当无人机沿网络图的第i条边飞行时，两节点间的威胁代价可近似地认为正比于1/沿这条边的积分5。4d当无人机以某一规定速度飞行时，可以简单地认为油耗代价与航程成正比，有如下关系: (2-7),f iiWL这样式(2-3)中的无人机的航路规划问题可以表示成求下式航路代价函数的最小值。 ij1k(s ,s ) ek,f(e )=min=s.t. e,(1)ijijijt iidE sS sSdk wkL2.3 本章小节本章对无人机航迹规划方法做了基础性的分析：把对复杂状态空间的搜索转变为了简单的图论问题；同时，讨论了雷达威胁和油耗因素的影响，并最终建立了以雷达威胁最小和油耗因素最少为目标的航路代价函数模型。(2-8)西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文11第 3 章 无人机航迹规划方法在敌方防守区域里去完成攻击、监视等任务时，无人机应该根据具体情况选择一条敌方威胁较小同时无人机性能指标能够满足要求的航路22-25。无人机航迹规划是指飞行器能够完成飞行任务并且满足约束条件的飞行轨迹。航迹规划是无人机任务规划系统的关键组成部分，其目标是在适当的时间内计算出最优或次最优的飞行轨迹，能使无人机（UAV）回避敌方威胁环境，安全的完成预定任务26。如第一章所述，目前路径规划的方法主要分为决策型搜索方法和随机型搜索方法，在本章中将对具有代表意义的几种算法-Floyd算法，算法，*A双向算法，遗传算法，模拟退火算法，蚁群算法，粒子群算法-进行比较和分*A析。3.1 传统航迹规划算法这里将对几种传传统算法-Floyd 算法，算法和双向算法进行分析。*A*A3.1.1 Floyd 算法Floyd算法是目前解决路径规划问题最常用、最简单的算法。Floyd算法又称为弗洛伊德算法或插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd 算法的基本思路是：从图的带权邻接矩阵A=开始，递归地 ( , )n na i j进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 递推公式为： D(0)=A； 西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文12D(1)= ，其中=min (0), (0)+ (0)； (1)ijn nd(1)ijdijd1 id1jdD(2)= ，其中=min (1), (1)+ (1)(2)ijn nd(2)ijdijd1 id1jd D(n)= ，其中= min (n-1), (n-1)+ (n-1)； ( )ijn ndn( )ijdnijd1 id1jd 计算结束后根据D矩阵就可以求出最短路径了。具体实验伪代码如下：初始化：Du,v=Au,vFor k:=1 to n For i:=1 to nFor j:=1 to nIf Di,jDi,k+Dk,j ThenDI,j:=DI,k+Dk,j; end if end for end for end for 算法结束：D即为所有点对的最短路径矩阵。对于Floyd算法边权可正可负。此算法简单有效，由于三重循环结构紧凑，效率较高。它的优点可以总结为：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；同时缺点也较明显：时间复杂度比较高，不适合计算大量数据。3.1.2 算法*A算法采用链式结构存储，相对于Floyd算法使用的Floyd矩阵所占的内存*A空间要小的多，在目前无人机的航迹规划中使用十分广泛。算法就是对启发函数最小的节点依次扩展实现优化的。因为启发函数是*A由起始节点到当前节点的最小目标函数值与从当前节点到目标节点的估计目标函数值计算得到的，它依赖于启发信息-估计目标函数值，所以被称为启发函数。因此，算法也被称为启发式算法。算法通过从起始节点出发，不断地找寻*A*A有希望以最小代价通向目标点的节点并优先扩展这些能够使目标函数值较小的西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文13节点，从而形成一个节点集，则集合内这些节点的有序连接即为所求优化路径，这一过程实际上是被选节点不断增加、扩展的过程。它存在种潜能，可以采用最少的估价源找到优化路径。这种算法是一种有效的计算最短路径的方法5。本文采用的平行扩展算法可以同时对节点进行扩展，计算出网络图中各*A节点到目标节点的最优代价。其思路是这样的: 当给定一个赋权网络图后，由任意节点经若干条边和若干个节点最终到达目标节点的最优路线是存在且唯一的，所以由任意节点到日标节点的最优路线的代价可以表示为该节点的函数，可简单地认为是该节点的代价。由于这一路线必定是经由该节点的某一相邻节点的路线，因此如果令由节点s到目标节点的最优路线代价为fs,即节点代价为fs,则fs可以通过计算连接相邻节点的边的代价与相邻节点的代价和得到。如果令do(s,e)表示由节点s出发经过边e到达的节点，cost(s,e)为边e的代价，则fs可定义为: 0 sGMin cost(s,e)+fdo(s,e) sG其中G代表目标节点的集合。这表明当节点s为目标节点时,由节点s到目标节点的最优路线代价为0，否则就选取相邻节点和连接相邻节点的边总和代价最小值作为该节点的代价。这样，网络图中每一节点的代价均可由式(3-1)计算得到，而由该节点通往日标节点的最优路线就可通过回溯过程依次选取若干节点的选择策略来确定，即依次确定当前节点的后续途经节点。这一选择策略可由式(3-2)计算得到，表明由该节点通过特定边到达某一相邻节点的通路是最优路线的组成部分5。 (3-2) argmincos ( , )( , )Policy st s ef do s e这种反向定义fs的方法是很有效的，可以从日标点开始计算并把所有节点的代价反向传递到该节点，就像波的传播过程。为了避免把每一节点的计算单独从这一传递过程中独立出来，可采用以下方法:视每一个计算节点为单独的单元，它的节点代价可按式(3-1)定义的得到，通过以下三步实现平行扩展:（1）初始化所有的节点代价为无穷，除目标节点为0;（2）通过搜索与每一节点相连的边及通过这些边可以到达的节点do(s,e)的代价 fdo(s ,e) 按式(3-1)的定义迭代计算每一节点的代价fs,同时该节点的选择策略由式(3-2)得到。fs=(3-1)西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文14（3）重复第二步直至迭代过程结束。因为由每一节点到达目标点的最优航路代价都是候选航路中代价最小的，故每一节点代价都存在一个最小值，而在这一迭代过程中每一节点的代价也将不断地被更新直至收敛到这一最小值为止。当所有节点的代价收敛到它们的最小值时此算法将退出，各节点的代价及选择策略将在这一计算过程中一并得到。随后由起始点开始不断采用各节点的选择策略进行节点扩展，一条连接起始点和目标点的最优路线就被搜索得到。下面，本文给出了迭代计算过程的伪代码:1. 初始化所有节点的f、v: f、v 2. 目标节点：f、v 03. Do 在每一个节点s:4. FixPoint? TRUE5. for 每一条边 do , ,eN S W E NW NE SW SE6. Let vmin( ,( )._cos ( )v do e varct e7.if(vf) then8. fv9.FixPoint? FALSE10. end if11. end for12. until(FixPoint?)13. Do 在每一个节点s:14. Policy=015.For 每一条边 do , ,eN S W E NW NE SW SE16.if f=do(e).v+arc_cost(e) then17.把e插入到Policy18.end if19.end for20. until(节点全部循环完？) 其中，当各节点在迭代过程中不再发生变化时，布尔类型变量FixPoint?为真，否则为假。do(e).v为相邻节点的f值。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文153.1.3 双向算法*A普通的算法是从单向搜索的（即从目的地*A出发地，或者从出发地目的地） ，如果从两个方向同时搜索，则相交出现比单向早。双向的搜索算法与单项的搜索算法基本上是一致的，不同的是采用双向搜索更新的方法。当从目标点和起始点同时出发后，同时按照代价函数的大小从小到大依次扩展节点。当他们有相交时，记录下这一条路径。同时如果其它从目标点出发的搜索路径的最前端的节点代价函数值均大于这条路径从目标点到交点的函数值，同时从起始点出发的也一样，则这条路径为最短路径。具体的程序流程图如图3-1所示。 图 3-1 双向算法的流程图*A3.2 现代航迹规划算法这里将对几种现代算法-遗传算法，模拟退火算法，蚁群算法和粒子群算法进行了分析。开始结束同时从起始点和目标点开始搜索找代价函数最小的前端节点并扩展判读是否有交点判断是否结束NNYY西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文163.2.1 遗传算法遗传算法（Genetic Algorithm, GA）最先是由美国Michgan大学的John Holland于1975年提出的28。遗传算法是具有“生成+检测”的迭代过程的搜索算法29-30。它是一种种群型操作算法，该操作以群体中的所有个体为对象，如图3-2所示。选择（selection） 、交叉（crossover）和变异（mutation）是遗传算法的三个主要操作算子。遗传算法包含如下的6个基本要素31：（1）参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型结构数据。所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是都是通过随机方程产生的。 （2）适应度评价检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度（fitness）值来评价个体或解的优劣，并作为以后遗传操作的依据。（3）选择（selection）:选择或复制操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。本文采用与适应度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和，再计算每个个体的适应度所占的比例，并以此作为相应的选择概率。 图3-2 遗传算法流程图（4）交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉可以分两步进行：先对种群中的个体进行随机配对;然后在配对个体中随机选取一个交叉段，彼此交换相应的部分信息。开始结束编码和种群生成种群适应度评价选择交叉变异种群是否收敛YN西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文17（5）变异操作：变异操作是按照位进行的，即 把某一位的内容进行替换。变异操作同样是随机进行的。一般而言，变异的概率较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。针对无人机路径规划的特殊性，我采用如下的编码来实现无人机的遗传算法航迹规划：（1）染色体编码和适应度函数编码是应用遗传算法时首先要解决的问题。编码方法除了决定个体基因染色体排列形式外，它还决定了个体从搜索空间基因型变换到解空间表现型时的解码方法，编码方式也会影响到交叉算子、变异算子等遗传算子的运算方式。编码方式在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。常用的遗传算法编码方式有三大类: 二进制编码，浮点数编码和符号编码5。根据无人机的特点本文使用了符号编码的方式。这个基因染色体表示无人机从出发点出发后依次经过若干中间点后最终到达目标点，因而航路对应的基因编码可采用因而航路对应的基因编码可采用最自然、最简单的表示方法路径表示法。例如无人机的飞行航路为：由出发点1，路经中间点2，中间点3，中间点4，中间点5，路经中间点6，最后到达目标点7，此时航路可以表示为2，3，4，5，6。由于点1，7分别是相应的起点和终点，在任何的基因染色体中都是一样的，所以在航路中不再列出。由于本文要讨论的是从起始点到目标点的最短路径问题，基因染色体采用如下的编码方式：1V2ViVnV图3-2 基因染色体编码如上图所示，基因染色体所表示的航路为， 。根1V2ViVnV据2.2.1节对无人机的活动区间网格化处理了之后，假设产生了N个节点。则无人机的最短路径最多由（N-2）个节点组成（除开起始点和目标点） ，所以染色西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文18体中的基因的个数最多为（N-2）个，即染色体的维数为（N-2）维。但是在实际运算中最短路径很难达到（N-2）维，即最短路径仅经过较少的几个节点就到达了目标点。这样我们就有必要定义基因染色体的有效长度。在本文中，基因染色体的有效长度指无人机从起始点开始，依次按照基因染色体从左到右顺序经过数个中间节点（注意不是染色体中的所有节点） ，最终到达目标点的最短路径中的中间节点的个数，如下图所示。起始点 1中 间节点2中 间节点5中 间节点4中 间节点3中 间节点6中 间节点7中 间节点8目标点 118765432基因染色体图3-3 基因染色体的有效长度示意图在图3-3中，包括起始点和目标点在内共有9个点，所以染色体的维数定为9-2=7维。如图所示，这个染色体表示了八条路径编号分别为1到8，这八条路径分别为：1 起始点1，目标点9；2 起始点1，中间点2，目标点9；3 起始点1，中间点2，中间点3，目标点9；4 起始点1，中间点2，中间点3，中间点4，目标点9；5 起始点1，中间点2，中间点3，中间点4，中间点5，目标点9；6 起始点1，中间点2，中间点3，中间点4，中间点5，中间点6，目标点9；7 起始点1，中间点2，中间点3，中间点4，中间点5，中间点6，中间点7，目标点9；8 起始点1，中间点2，中间点3，中间点4，中间点5，中间点6，中间点7，中间点8，目标点9；然后，分别计算这八条路径的代价和（） ，选出代价和最小的-即最短id西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文19的路径。假设最短的路径编号为6，这个染色体的有效长度为5（即仅中间点2，中间点3，中间点4，中间点5，中间点6为有效节点，中间节点7为无效节点） ，这个染色体的适应度函数值为编号为6的代价和。（2）遗传算法的初始化由于采用了符号编码，初始种群的生成就受到了限制。首先，生成1到N共N个数（假设节点数为N）,然后从中间除去起始点和目标点，剩下N-2个数。把这N-2个数打乱顺序后随机的放入（N-2）维的基因中间去。这样就生成了一个初始基因种群。以此类推，随机生成与种群规模相当的基因数目。（3）交叉为了保证基因的完整性，本文使用特殊的交叉方式。随机配对后，对于每个对子分别指定父代parent1和parent2。选取父代parent1为主交叉染色体，随机的产生两个数（1到N-2之间的整数，如果两个数相等则不用交叉） ，这两个数之间的基因片段将预备进行交叉。首先为了保证交叉有意义，交叉基因片段的两个交叉点至少应该保证有一个在基因染色体的有效长度之内。 5V6V1V2V3V8V7V4V6V1V2V3V8V7V4V5V5V5V6V6V4V要交叉的基因片要交叉的基因片主交叉辅交叉4V图3-4 主交叉染色体示意图（阴影表示有效基因）如上图所示，产生的两个随机数为4和6，其中4在基因染色体的有效长度5之内。则要交叉的基因片段为 。456,V V V选取父代parent2为辅交叉染色体，根据parent1产生的要交叉的基因片段，寻找到父代parent2中间的相应部分，并保留原先的顺序 ，如下图所645,V V V示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文205V6V1V2V3V8V7V4V6V1V2V3V8V7V4V5V5V5V6V6V4V要交叉的基因片要交叉的基因片主交叉辅交叉4V图3-5 辅交叉染色体示意图（阴影表示有效基因）互换要交叉的基因片段，保留基因的原来顺序，互换后新的基因分别插入原先抽取的基因的位置，交叉之后的两基因如图3-6所示。最后要重新计算染色体基因的有效长度和适应度函数值。（4）变异为了保证基因的完整性，本文使用特殊的变异方式。对于任意染色体，产生一个0到1的随机数，如果大于变异的概率则进行变异，否则不进行变异。6V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V1V3V5V5V4V6V7V8V1V6V3V4V5V7V7V8V主交叉辅交叉变异之前的染色体变异之后的染色体图3-6 交叉之后染色体示意图（此时阴影已经失去了意义）如果进行变异，对于父代parent随机产生两个数（在1到N-2之间的整数，如果两个数相等则不用交叉）分别作为变异点1，2。同样要保证变异点1，2至少有一个在基因染色体的有效长度之内。取抽取点为变异点1，变异点2之中的较小值；取插入点为变异点1，变异点2之中的较大值。然后，抽出抽取点处的基因，插入到插入点之后，中间的基因依次前移，具体操作如下图所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文216V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V1V3V5V5V4V6V7V8V1V6V3V4V5V7V7V8V主交叉辅交叉变异之前的染色体变异之后的染色体图3-7 染色体变异示意图（此时阴影已经失去了意义）如上图所示，产生的两个随机数为2和6。则第2个基因移到第6个基因处，原先的第2，3，4，5个基因依次前移。最后要重新计算染色体基因的有效长度和适应度函数值。（5）选择选择将决定哪一个基因可以进入下一代。本文采用了赌轮盘选择法选择，进入下一代的可能性与适应度函数值成正比。得到如下遗传算法伪代码。1. 生成初始种群2. Do 3.种群配对4. 染色体交叉5.染色体变异6. 选择进入下一代7. until (种群收敛？)3.2.2 模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(k*T)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文22化问题的模拟退火算法。模拟退火算法与传统的算法相比，它与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想: (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数。 (5) 若t0，然后转第2步。模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若t0则接受S作为新的当前解S，否则以概率exp(-t/T)接受S作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文23应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。由于无人机航迹规划的特殊性，本文采用与上节-遗传算法-相同的符号编码方式：对无人机的活动区间网格化处理了之后，假设产生了 N 个节点。则无人机的最短路径最多由（N-2）个节点组成（除开起始点和目标点） ，所以解中的基因的个数最多为（N-2）个，即解的维数最多为（N-2）维。但是在实际运算中最短路径很难达到（N-2）维，同样我们有必要定义解的有效长度。解的有效长度的定义与基因染色体的有效长度的定义相同。同时目标函数的定义于遗传算法中适应度函数的定义相同。6V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V2V1V1V6V3V4V5V7V7V8V转逆之前的解转逆之后的解变异之前的染色体变异之后的染色体6V5V4V3V7V8V图 3-8 转逆中间示意图（阴影此时失去了意义）6V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V2V1V1V6V3V4V5V7V7V8V转逆之前的解转逆之后的解变异之前的染色体变异之后的染色体6V5V4V3V7V8V图 3-9 转逆两端示意图（阴影此时失去了意义）然后，以如下的方法产生新解：（1）随机产生1和N-2之间的两相异数k和m。（2）如果km，则逆转k,m中间的数，如图3-8所示（假设k,m分别为3,6） 。（3）否则逆转k,m两端的数，如图3-9所示（假设k,m分别为6,3） 。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文24转化完之后要重新计算计算解的有效长度和目标函数值。代价函数差可以定义为新解和原解的目标函数值之差。具体的算法流程图如图3-10所示。选择初始路径X0确定初始温度T0结束当前路径Xi=X0当前温度Ti=T0产生随机数k,m并产生新的路径Xn判断是否接受新解？判断内循环次数是否到了？判断外循环次数是否到了？YNXn=XiNYNY降低温度Ti开始图 3-10 模拟退火算法流程图3.2.3 蚁群算法蚁群算法来源于对自然界蚂蚁寻找从蚁巢到食物源的最短路径行为的研究，它是一种并行算法，所有蚂蚁(智能体)独立行动，没有监督机构，从而使其避西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文25开局部最优。它是一种鲁棒算法，因为只要对算法作小小的修改，就可以运用于别的组合优化问题5。为说明该算法，引入如下的标记：m表示蚁群中蚂蚁的数量， ijd(i，j=1,，n-1)表示节点i和节点j之间的距离，表示t时刻位于节点i的蚂蚁( )ib t数，显然应满足m =，表示t时刻在ij连线上的信息量(即真实蚁群中10( )niib t( )ijt的外激素量)。在算法的初始时刻，将m只蚂蚁全部放在起始点，此时各路径上的信息量相等，设=C(C为常数)。每只蚂蚁根据路径上保留的信息量独立(0)ij地选择下一个节点。在时刻t，蚂蚁k从节点i转移到节点j的概率如下表示35：kijp (3-4)( )( ),( )( )0kijijkisiss allowedttjallowedtt如果，否则其中， = 0，1，2 ，n-1，另外用列表表示蚂蚁k下一步kallowedktravelled允许选择的所有节点，列表纪录了当前蚂蚁k所走过的节点，当目标ktravelled点进入到列表中之后，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径便是问题的一个解。是一个启发式因子，表示蚂蚁从节点i转移到节点j的期望程ij度，在蚂蚁算法中，通常取节点ij之间距离的倒数。分别表示路径上信ij, 息量和启发示因子的重要程度。当所有蚂蚁均到达目标点之后，各路径上的信息量要根据下式调整： ()(1)*( )( )ijijijijtntt(0,1)1mkijijk其中表示路径上信息的蒸发系数，1-表示信息的保留系数；表示本次ij循环路径ij上信息的增量。表示第k只蚂蚁在本次循环中留在路径ij上的信息kij量，如果蚂蚁k没有经过路径ij，则的值为零，因此表示为下式：kijkij ，如果蚂蚁k在本次循环中经过路径ij kQL=kijp(3-5)(3-6)=kijkij西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文26 0 , 如果蚂蚁k在本次循环中不经过路径ij其中，Q为常数，表示第k只蚂蚁在本次循环中所走过的路径的长度。kL从模型不难看出，蚂蚁系统实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的外激素(蚂蚁之间通过交换信息而留下的产物)，而且也用到了节点之间距离的倒数作为启发式因子。由上述的模型可以得出无人机蚁群算法的伪代码如下：1. 初始化ij2. Do 3. 把m只蚂蚁置于起点4. Do 对于每只蚂蚁5. 依照相应概率选取下一节点6.Until(到达目标点？)7. 更新ij8. Until（路径收敛？）3.2.4 粒子群算法粒子群优化(Particle Swarm Optimization，PSO)算法的运行机理不是依靠个体的自然进化规律，而是对生物群体的社会行为进行模拟33。PSO算法中每个粒子即解空间中的一个解，它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历过的最好位置，就是粒子本身找到的 图3-11 粒子群算法流程图最优解。整个群体所经历过的最好位置，就是整个群体目前找到的最优解。前者叫做个体极值（pBest） ，后者叫做全局极值(gBest)34。每个粒子都通过上述两个极值不断更新自己，从而产生新一代群体。实际操作中通过由优化问题所决定的适应度函数值 (fitness value)来评价粒子的“好坏”程度。显然在PSO算法初始化粒子种群开始计算每个粒子的适应度根据适应度更新个体极值与全局极值根据公式更新粒子种群的速度和位置达到最大迭代次数或最小错误标准？结束YN西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文27中，每个粒子可看作解空间中的一个点，若粒子的群体规模为N，则第i(i=1N)个粒子的位置可表示为，它所经历过的“最好”位置记为，其速度用表iX( )bestpiiV示，群体中“最好”粒子的位置的索引号用g表示。粒子i将根据下式公式35： (3-7)2*()*( )*()*( )iiiBestiBestiVVcRandpiXcRandpgX (3-8)(1)( )*(1)iiiX kXkK V k来更新自己的速度和位置，其中，为常数，称为学习因子;Rand()和rand()12,C C是0，1上的随机数，为惯性权重，K是压缩因子，用于对粒子的飞行进行约束。并且粒子在不断根据速度调整自己的位置同时，还要受到最大速度限maxV制。当超过时，将被限定为。iVmaxVmaxV该公式由三部分组成:第一部分是粒子先前的速度，说明了粒子目前的状态;第二部分是认知部分(cognition Modal)，表示粒子本身的思考;第三部分为社会部分(Social Modal)。三个部分共同决定了粒子的空间搜索能力。第一部分起到了平衡全局和局部搜索的能力;第二部分使粒子有了足够强的全局搜索能力，避免局部极小:第三部分体现了粒子间的信息共享。在这三部的共同作用下粒子才能有效的到达最好位置2。基本PSO 的流程可以描述为36-37:Step 1 初始化。初始搜索点的位置及其速度通常是在允许的范围内0iX0iV随机产生的, 每个粒子的pBest 坐标设置为其当前位置, 且计算出其相应的个体极值(即个体极值点的适应度值) , 而全局极值(即全局极值点的适应度值) 就是个体极值中最好的, 记录该最好值的粒子序号, 并将gBest设置为该最好粒子的当前位置。Step 2 评价每一个粒子。计算粒子的适应度值, 如果好于该粒子当前的个体极值, 则将pBest设置为该粒子的位置, 且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值, 则将gBest 设置为该粒子的位置, 记录该粒子的序号, 且更新全局极值。Step 3 粒子的更新。用式(3-6) 和式(3-7) 对每一个粒子的速度和位置进行更新。Step 4 检验是否符合结束条件。如果当前的迭代次数达到了预先设定的最大次数(或达到最小错误要求) , 则停止迭代, 输出最优解, 否则转到Step 2 。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文28具体流程图见图3-11所示。针对无人机航迹规划的特殊性，对于粒子群采用如下的编码方式：粒子群由（N-2）个粒子组成， （N-2）维粒子的具体含义与前节中（N-2）维染色体的定义相同。粒子群中的每个粒子均表示一个节点。无人机将按照从左到右的顺序依次经过这些节点。粒子群的有效长度与基因染色体的有效长度定义一样；粒子群的适应度函数值与染色体的适应度函数值定义一样。同时由于粒子群中的每个粒子均为有理数，所以每次计算都需要对结果取整。3.3 航迹规划算法的仿真分析3.3.1 算法正确率分析首先，我们假设有四个节点的情况，中心有一个雷达。四个节点的坐标和各个节点之间的边的代价标准化后分别如表3-1-1和表3-1-2所示：表 3-1-1 节点坐标节点序号1234坐标0,010000,00,1000010000,10000表 3-1-2 节点之间的代价矩阵代价 节点节点 节点 1节点 2节点 3节点 4节点 1011inf节点 210inf1节点 31inf01节点 4inf110西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文2901000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000011infinf111234radary(传 传 传 传 )x(传 传 传 传 )PointBest Route图 3-12 4 节点仿真图选取起始节点为1，终止节点为4，应用MATLAB程序仿真计算，七种算法得到的路径保持一致，均为：124或者134仿真路线如图3-12所示。从图3-12中可以轻松看出从节点1到节点4的最短路径正是：124或者134现在我们来讨论55=25个节点的情况。对敌方威胁和航迹长度归一化后加权平均，得到25个节点的坐标和各个节点之间的边的代价以及雷达的位置分别如表3-2和图3-13所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文30表 3-2 25 节点坐标节点序号12345坐标0,00,25000,50000,75000,10000节点序号678910坐标2500,02500,25002500,50002500,75002500,10000节点序号1112131415坐标5000,05000,25005000,50005000,75005000,10000节点序号1617181920坐标7500,07500,25007500,50007500,75007500,10000节点序号122232425坐标10000,010000,250010000,500010000,750010000,1000002000400060008000100000200040006000800010000123456789101112131415161718192021222324250.353510.353510.353553510.353510.353553510.353553553510.353510.353510.353553510.353510.353553510.353553553510.353510.353510.353510.35351radarradarradarradary(传 传 传 传 )x(传 传 传 传 )图 3-13 25 节点之间的代价矩阵图（单位:米） （节点之间未标者代价为无穷）分别选取起始节点为1，对应终止节点为25，应用MATLAB程序仿真计算3次，得到的最优路线分别如下：（1）Floyd算法选取起始节点为1，终止节点为25，使用Floyd算法得到的最优路线如下：1612182425或者128142025从常理判断，这都应该是最短路径，如图3-14所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文3101000 20003000400050006000700080009000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-14 Floyd 算法 25 节点仿真图10203040506070809010000.511.5传 传传 传 传 传 传图 3-15 Floyd 算法正确率由于Floyd算法是决策性搜索算法，搜索结果不存在随机性而且是逐个节点比较，所以算法的正确率一直保持在1，不随节点数的变化而变化，如图3-15所示。（2）算法*A选取起始节点为1，终止节点为25，使用Floyd算法得到的最优路线如下：1612182425或者128142025西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文32从常理判断，这应该是最短路径，而这也与Floyd算法的计算结果一致，如图3-16所示。01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-16 算法 25 节点仿真图*A10203040506070809010000.511.5传 传传 传 传 传 传图 3-17 算法正确率*A由于算法也是决策性搜索算法，搜索结果不存在随机性而且是逐个节点*A比较，所以算法的正确率一直保持在1，不随节点数的变化而变化，如图3-17所示。（3）双向算法*A选取与Floyd算法一样的起始节点和终止节点，得到的仿真曲线如图3-18。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文3301000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-18 双向算法 25 节点仿真图*A由于双向算法也是决策性搜索算法，搜索结果不存在随机性，所以算法*A的正确率一直保持在1，不随节点数的变化而变化，如下图所示。10203040506070809010000.511.5传 传传 传 传 传 传图 3-19 双向算法正确率*A（4）遗传算法选取起始节点为1，对应的终止节点为25，选取种群大小为100，繁殖代数为100代，交叉概率为0.8，变异概率为0.08，应用MATLAB程序仿真计算，得到的最优路线如下图所示：西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文3401000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-20 遗传算法 25 节点仿真图10203040506070809010000.81传 传传 传 传 传 传图 3-21 遗传算法正确率示意图由于遗传算法是一种随机搜索算法，搜索结果的正确率随节点数的增加而降低，考虑到跳出最大循环次数后算法正确率将陡然下降的情况，采用二次分段插值，仿真100次得到正确率随节点变化的示意曲线如图3-21所示。（5）模拟退火算法选取起始节点为1，终止节点为25，选取初始温度为100，应用MATLAB程西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文35序仿真计算，得到的最优路径如下图所示：01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-22 模拟退火算法 25 节点仿真图10203040506070809010000.81传 传传 传 传 传 传图 3-23 模拟退火算法正确率示意图由于模拟退火算法是一种全局随机搜索算法，搜索结果的正确率随节点数的增加而降低，考虑到跳出最大循环次数后算法正确率将陡然下降的情况，采用二次分段插值，仿真100次得到正确率随节点变化的示意曲线如图3-23所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文36从图3-23中可以看出，如果在最大循环次数的范围收敛，模拟退火算法的正确率要比遗传算法高得多。 （6）蚁群算法选取起始节点为1，对应的终止节点为25，选取最大迭代次数为200次，m(蚂蚁个数)为31，Alpha（表征信息素重要程度的参数）为1，Beta（表征启发式因子重要程度的参数）为5，Rho（信息素蒸发系数）为0.1，Q（信息素增加强度系数）为100，用MATLAB程序仿真计算，得到最优路线如图3-24所示。01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-24 蚁群算法 25 节点仿真图由于蚁群算法是一种随机搜索算法，搜索结果的正确率随节点数的增加而降低，考虑到跳出最大循环次数后算法正确率将陡然下降的情况，采用二次分段插值，仿真100次得到正确率随节点变化的示意路线如图3-25所示。从图中可以看出，在起始阶段蚁群算法正确率随节点数上升而下降这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，正确率将陡然下降。（7）粒子群算法分别选取起始节点为1，终止节点为25，选取，循环次数为122,2cc1000，种群大小为600，用MATLAB程序仿真计算，得到的最优路线如图3-26所西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文37示：10203040506070809010000.81传 传传 传 传 传 传图 3-25 蚁群算法正确率示意图01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 3-26 粒子群算法 25 节点仿真图由于粒子群算法是一种随机搜索算法，搜索结果的正确率随节点数的增加而降低，考虑到跳出最大循环次数后算法正确率将陡然下降的情况，采用二次分段插值，仿真100次得到正确率随节点变化的如图3-27所示。从图3-27中可以看出，在起始阶段粒子群算法正确率随节点数上升而下降西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文38这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，正确率将陡然下降；同时和蚁群算法，遗传算法以及模拟退火算法相比，由于粒子群算法要不断对连续的值取整，所以正确率偏低。10203040506070809010000.81传 传传 传 传 传 传图 3-27 粒子群算法正确率示意图3.3.2 算法复杂度分析（1）Floyd算法复杂度分析由3.1.1节可以知道Floyd算法的复杂度与节点数的立方成正比。它的复杂度随节点数变化的曲线如图3-28所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文39102030405060708090100020406080100120140160180200传 传传 传 传 传 传图 3-28 Floyd 算法复杂度从图中可以看出，在起始阶段Floyd算法复杂度很低，但是随着节点数的增加算法的复杂度陡然增加，这就大大的增加了计算负担。（2）算法复杂度分析*A算法的复杂度主要与节点数的立方成正比。它的复杂度随节点数变化如*A图3-29所示。102030405060708090100020406080100120140160180200传 传传 传 传 传 传图 3-29算法复杂度*A从图3-29中可以看出，在起始阶段算法复杂度较低，但是随着节点数的*A增加算法的复杂度增加较小，没有Floyd算法的增加得剧烈，此时相比Floyd算西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文40法有优势。102030405060708090100020406080100120140160180200传 传传 传 传 传 传图 3-30 双向算法复杂度*A（3）双向算法复杂度分析*A双向算法的复杂度主要与节点数相关，理论上复杂度是算法的一半。*A*A它的复杂度随节点数变化的如图3-30所示。从图3-30可以看出，在起始阶段双向算法复杂度较低，但是随着节点数*A的增加算法的复杂度增加较小，没有Floyd算法的增加得剧烈，此时相比Floyd算法有优势；同时相比算法由于适用双向搜索，理论上发现目标所消耗的时*A间减少了一倍。（4）遗传算法复杂度分析1020304050607080901000102030405060708090100传 传传传传传传图 3-31 遗传算法复杂度示意图在最大种群繁殖代数的范围内收敛情况下，由于节点的个数将直接决定基西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文41因大小，所以它的复杂度与节点数成正比；但在最大种群繁殖代数的范围内未收敛的情况下，它将立即跳出循环，同时复杂度不再变化。因为要分析的四种随机算法在在最大循环次数内收敛情况下，它的复杂度均与节点数成正比，而当它跳出循环时，复杂度均不再变化，为了方便比较本文采用记录运行时间的方法表征他们的复杂度。对运行时间记录采用二次分段插值，仿真100次得到复杂度随节点变化如图3-31所示。从图中可以看出，在起始阶段遗传算法复杂度随节点数上升这与前面的算法是相同的；但是随着节点数的增加在最大种群繁殖代数的范围将变得不可收敛，此时算法的将跳出循环，复杂度不再上升，和前面的决策性搜索算法相比有优势。（5）模拟退火算法复杂度分析在最大循环次数的范围内收敛情况下，与遗传算法一样，它的复杂度与节点数成正比；但在最大循环次数的范围内未收敛情况下，它将立即跳出循环，同时复杂度不再变化，对运行时间记录采用二次分段插值，仿真100次得到复杂度随节点变化的示意图如下。1020304050607080901000102030405060708090100传 传传 传 传 传 传图 3-32 模拟退火算法复杂度示意图从图中可以看出，在起始阶段模拟退火算法复杂度随节点数上升这与前面的算法是相同的，它的复杂度与节点数成正比；但是随着节点数的增加在最大循环次数的范围将变得不可收敛，此时算法的将跳出循环，复杂度不再上升，西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文42和前面的决策性搜索算法相比有优势。同时与遗传算法相比复杂度大为上升。（6）蚁群算法复杂度分析在最大循环次数的范围内收敛情况下，与遗传算法一样，它的复杂度与节点数成正比；但在最大循环次数的范围内未收敛的情况下，它将立即跳出循环，同时复杂度不再变化，对运行时间记录采用分段插值，仿真100次得到复杂度随节点变化的如图3-33所示。从图3-33可以看出，在起始阶段蚁群算法复杂度随节点数上升这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，复杂度不再上升。（7）粒子群算法复杂度分析在最大循环次数的范围内收敛情况下，与遗传算法一样，它的复杂度与节点数成正比；但在最大循环次数的范围内未收敛的情况下，它将立即跳出循环，同时复杂度不再变化，对运行时间记录采用分段插值，仿真100次得到复杂度随节点变化如图3-34。1020304050607080901000102030405060708090100110传 传传 传 传 传 传图 3-33 蚁群算法复杂度示意图西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文43102030405060708090100020406080100120140160180200传 传传 传 传 传 传图 3-34 粒子群算法复杂度示意图从图中可以看出，在起始阶段粒子群算法复杂度随节点数上升这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，复杂度不再上升；同时和蚁群算法，遗传算法以及模拟退火算法相比，由于粒子群算法要不断对连续的值取整，所以很难收敛，复杂度更高。3.4 航迹规划算法的比较分别比较以上七种算法的正确率和复杂度得到如图3-35和3-36所示：西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文4410203040506070809010000.81传 传传 传 传 传 传Floyd传 传AStar传 传传 传 AStar传 传传 传 传 传传 传 传 传 传 传传 传 传 传传 传 传 传 传图 3-35 七种算法正确率比较示意图102030405060708090100020406080100120140160180200传 传传 传 传 传 传Floyd传 传AStar传 传传 传 AStar传 传传 传 传 传传 传 传 传 传 传传 传 传 传传 传 传 传 传图 3-36 七种算法复杂度比较示意图根据两图的特点，可以分两个部分来讨论：当节点数较少时，传统航迹规划算法无论是在正确率或者复杂度上都占有绝对的优势。当节点数较多时，传统航迹规划算法虽然在正确率上依然领先但是算法复西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文45杂度急剧上升，所以在现代航迹规划中使用受到了限制；现代航迹规划算法则在复杂度上的优势开始变为明显。在现代航迹规划算法中，模拟退火算法具有较高的正确率但是复杂度也偏高；遗传算法具有较低的复杂度，但是正确率也较低。如果能把两种算法结合并取长补短，则能同时达到减小复杂度和提高正确率的要求。各个算法的优缺点如表3-3所示：表 3-3 七种常用无人机航迹规划方法特点分析航迹规划方法名称优点缺点Floyd 算法流程简单，正确率高。节点数较少时计算速度很快。节点数较多时，算法的复杂度急剧上升。算法*A采用链式存储，节约计算机内存。正确率高。节点数较多时，计算速度相对较快。编程复杂。节点较少时，计算速度的优势体现不出来。双向算法*A采用双向搜索的算法，理论上比算法还要快一倍。*A编程复杂。节点较少时，计算速度的优势体现不出来。遗传算法模拟生命进化过程。节点较多时，计算速度较快。编程复杂。可能限于局部最优解。算法正确率随节点数的增加而下降，尤其是在超出了最大遗传代数的情况下。模拟退火算法准确率在随机算法中较高。计算时间要求长。准确率在超出了最大循环次数的情况下变低。蚁群算法模拟蚂蚁寻找食物的过程。节点较多时，计算速度较快。计算时间和准确率仍然不算太理想。仍然不能避免在超出了最大循环次数的情况下准确率的降低。粒子群算法模拟鸟类寻找食物的过程。节点较多时，计算速度较快。由于要对连续变量取整输出，所以无论是准确率还是计算时间都不是很理想。3.5 本章小结本章针对单目标的路径规划问题和无人机的特殊要求，适当修改了遗传算西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文46法，模拟退火算法，蚁群算法和粒子群算法。对这四种算法和传统的三种典型算法Floyd算法，算法，双向算法，对正确率和复杂度进行了分析比*A*A较。得出在节点数较少时，传统算法无论是正确率还是复杂度均占优；在节点数较多时，现代航迹规划算法在复杂度上的优势开始变为明显，与此相反传统航迹规划算法复杂度极度上升，这就限制了它的使用；在现代航迹规划算法中，模拟退火算法具有较高的正确率，遗传算法具有较低的复杂度，它们两种算法的取长补短的结合将会取得较好的效果。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文47第 4 章 模拟退火遗传算法随着节点数的增多，传统航迹规划算法复杂度极度上升，这就限制了它的使用，在现代随机规划算法中，遗传算法和模拟退火算法各有特点。遗传算法容易出现“早熟”的现象-过早的收敛于局部最优点而且不容易跳出，从而算法的正确率不高；模拟退火算法由于初始温度设定的问题收敛过程很慢，从而算法的复杂度较高。但是由于遗传算法的“早熟”,收敛速度较快；模拟退火算法由于全局搜索能力强，反而收敛速度很慢。本文将尝试结合模拟退火和遗传算法并用于无人机的路径规划中，利用模拟退火算法在全局范围内的搜索能力加上遗传算法的收敛能力来解决两种算法各自的缺陷。4.1 模拟退火遗传算法的基本原理遗传算法的收敛性主要是由种群的交叉，变异和选择所决定的；模拟退火算法的全局搜索能力是由初始温度以及里外两层循环所决定。从上面的分析可以看出这两者并不矛盾可以有机结合起来。本文使用了遗传算法的染色体组代替了模拟退火的解。基本的流程与模拟退火的过程很相似，仅仅是用随机数k,m来转逆中间或者两端来产生新解变为了使用遗传算法的种群交叉，变异和选择部分。代价函数差定义为新染色体平均适应度函数值和原染色体平均适应度函数值之差。4.2 模拟退火遗传算法编程的实现综合模拟退火和遗传算法的特点，可以得到如下的伪代码：1. 生成初始种群P02. Pi=P0, Ti=T03. Do 4. Do西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文485. 种群配对6. 染色体交叉7. 染色体变异选择初始种群P0确定初始温度T0开始当前种群Pi=P0当前温度Ti=T0种群交叉判断是否接受新种群？判断内循环次数是否到了？判断外循环次数是否到了？NPn=Pi降低温度Ti种群变异种群选择产生新的种群结束YNNYY图 4-1 模拟退火遗传算法流程图 8. 选择并生成新的种群Pn9. if 接受新的种群10. Pi=Pn11.end if12. until （不接受新种群的循环次数已到？）13. 降低温度Ti西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文4914. until (种群收敛？)下面分别该出各个模块MATLAB代码:(1)染色体交叉模块交叉时选取两个父代为Parent1,Parent2，产生的两个个体为Child1,Child2，Cross_Possible为交叉概率。function Child1,Child2=Crossover(Parent1,Parent2,Cross_Possible) Gene_Size=length(Parent1)-2; Cross_Valid=min(Parent1(Gene_Size+1),Parent2(Gene_Size+1); Child1=Parent1; Child2=Parent2; Cross_Point_K=round(rand(1)*Gene_Size+0.5); Cross_Point_M=round(rand(1)*Gene_Size+0.5); if(rand(1)Cross_Possible) Cross_Point_Max=max(Cross_Point_K,Cross_Point_M); Cross_Point_Min=min(Cross_Point_K,Cross_Point_M); Cross_Tempt=Child1( Cross_Point_Min:Cross_Point_Max); Cross_Index=0; Index=false; for Loop=1:Cross_Point_Max-Cross_Point_Min+1 for j=1: Gene_Size if all ( Cross_Tempt - Child2(j) ) if Index=false Index=true; Cross_Index=j; else Cross_Index=Cross_Index,j; end end end end for Loop=1:Cross_Point_Max-Cross_Point_Min+1 Child1( Cross_Point_Min-1+Loop) = Child2( Cross_Index(Loop) ); Child2( Cross_Index(Loop) )=Cross_Tempt(Loop) ; 西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文50 end end(2)染色体变异模块变异操作为一个父代Parent产生单个子代Children，Variance_Possible为变异概率。function Children= Genetic_Variance(Parent,Variance_Possible) Gene_Size=length(Parent)-2;Variance_Valid=Parent(Gene_Size+1); Variance_Point1=round( rand(1)*Gene_Size +0.5); Variance_Point2=round( rand(1)*Gene_Size +0.5); Variance_Max=max(Variance_Point1,Variance_Point2);Variance_Min=min(Variance_Point1,Variance_Point2);Children=Parent;if (rand(1)Variance_Possible) Children=Parent(1:Variance_Min-1),Parent(Variance_Min+1:Variance_Max),Parent(Variance_Min),Parent(Variance_Max+1:Gene_Size+2) ; end (3)选择并生成新的种群模块采用赌轮盘操作决定那些个体可以进入下一代。function Pop_Matrix=Genetic_Selection(Pop_Old_Matrix) Gene_Size=size(Pop_Old_Matrix,2)-2;Pop_Size=size(Pop_Old_Matrix,1); Total_Fitness=sum(Pop_Old_Matrix(:,Gene_Size+2); Selection_Prob=Pop_Old_Matrix(:,Gene_Size+2)/Total_Fitness;Selection_Prob=cumsum(Selection_Prob); Selection_Rns=sort(rand(Pop_Size,1);Select_Fitin=1;Select_Newin=1; while Select_Newin=Pop_Size if (Selection_Rns(Select_Newin)Selection_Prob(Select_Fitin) Pop_Matrix(Select_Newin,:)=Pop_Old_Matrix(Select_Fitin,:) ; Select_Newin=Select_Newin+1; else西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文51 Select_Fitin=Select_Fitin+1; end end(4)主程序模块依次实现种群配对，染色体交叉，染色体变异，选择并生成新的种群Pn，判断是否接受新的种群，判断当不接受时新种群的循环次数是否已到以及 降低温度Ti等功能。function Output_None=SA_Genetic_Algorithms(Cost_Matrix,Start_Point,End_Point) global Best_Route%SA initial inputSA_Temperature=100;Loop_Count_Limit=1000;Admit_Nonnew_Limit=5;%Genetic intialPop_Size=100;Cross_Possible=0.8;Variance_Possible=0.08;SA_Length=size(Cost_Matrix,1);%Pop_Matrix=Genetic_Initial(Cost_Matrix,Pop_Size); SA_Repeat=true;Admit_Nonnew=0; Pop_Matrix=Genetic_Fitness(Pop_Matrix);Loop_Count=0;while SA_Repeat=true Pop_Matrix_New=Pop_Matrix; %crossover Pop_Matrix_New= Genetic_Orderless(Pop_Matrix_New); Cross_Loop=1; while Cross_LoopPop_Size Parent1=Pop_Matrix_New(Cross_Loop,:); Parent2=Pop_Matrix_New(Cross_Loop+1,:);西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文52 Child1,Child2= Genetic_Crossover(Parent1,Parent2,Cross_Possible); Pop_Matrix_New(Cross_Loop,:)=Child1; Pop_Matrix_New(Cross_Loop+1,:)=Child2; Cross_Loop=Cross_Loop+2; end %variation for Variation_Loop=1:Pop_Size Parent=Pop_Matrix_New(Variation_Loop,:); Children= Genetic_Variance(Parent,Variance_Possible); Pop_Matrix_New(Variation_Loop,:)=Children; end Pop_Matrix_New=Genetic_Fitness(Pop_Matrix_New); Pop_Matrix_New(:,SA_Length+2)=1/Pop_Matrix_New(:,SA_Length+2); Pop_Matrix=Genetic_Fitness(Pop_Matrix); Pop_Matrix(:,SA_Length+2)=1/Pop_Matrix(:,SA_Length+2); Delta_Value=findmin(Pop_Matrix_New(:,SA_Length+2)-findmin(Pop_Matrix （:,SA_Length+2); If（Delta_Valuerand(1) Pop_Matrix_=Pop_Matrix_New; Admit_Nonnew=0; else Admit_Nonnew=Admit_Nonnew+1; if Admit_Nonnew=Admit_Nonnew_Limit SA_Repeat=false; else SA_Repeat=true; end end Loop_Count=Loop_Count+1; if Loop_CountLoop_Count_Limit break西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文53 end end4.3 模拟退火遗传算法仿真分析(1)模拟退火遗传算法正确率分析首先，我们假设有四个节点的情况。四个节点的坐标和各个节点之间的边的代价（权）分别与3.3.1节的一致。01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000011infinf111234radary(传 传 传 传 )x(传 传 传 传 )PointBest Route图 4-2 模拟退火遗传算法 4 节点仿真图选取起始节点为1，终止节点为4，选取种群大小为100，繁殖代数为100代，交叉概率为0.8，变异概率为0.08，初始温度为100，应用MATLAB程序仿真计算，得到的最优路线如下：124仿真路线如图4-2所示，这个结果与前面算法的计算结果是一致的。现在我们来讨论55=25个节点的情况。25个节点的坐标和各个节点之间的边的代价（权）与3.3.1节一致。选取起始节点为1，终止节点为25，应用MATLAB程序仿真3次，得到的最优路线如下：1612182425或者128142025西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文54仿真路线图如下图所示：01000 2000 3000 4000 5000 6000 7000 8000 9000 1000001000200030004000500060007000800090001000012345678910111213141516171819202122232425radarradarradarradary(传 传 传 传 )x(传 传 传 传 )PointBest Route of the 1st simulinkBest Route of the 2nd simulinkBest Route of the 3rd simulink图 4-3 模拟退火遗传算法 25 节点仿真图10203040506070809010000.81传 传传 传 传 传 传传 传 传 传传 传 传 传 传 传传 传 传 传 传 传 传 传图 4-4 模拟退火遗传算法与模拟退火算法以及遗传算法正确率比较图从常理判断，这应该是最短路径，而这也与前面算法的计算结果一致。从以上的仿真可以看出，模拟退火遗传算法继承了模拟退火算法的优点，相比遗传算法正确率大为增加。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文55下面给出模拟退火遗传算法与模拟退火算法以及遗传算法正确率的比较曲线如图4-4所示。从图4-4中可以看出，在起始阶段遗传算法正确率随节点数上升而下降这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，正确率将陡然下降。模拟退火遗传算法正确率和模拟退火算法相比有所降低；同时相比遗传算法则较高。可见，在正确率上模拟退火遗传算法综合了遗传算法和模拟退火算法的特点。（2）模拟退火遗传算法复杂度分析在最大循环次数的范围内收敛情况下，模拟退火遗传算法的复杂度主要与节点数相关；但在最大循环次数的范围内未收敛的情况下，它将立即跳出循环，同时复杂度不再变化，其与模拟退火算法以及遗传算法复杂的比较图如下：102030405060708090100020406080100120140160180200传 传传 传 传 传 传传 传 传 传传 传 传 传 传 传传 传 传 传 传 传 传 传图 4-5 模拟退火遗传算法复杂度示意图从图中可以看出，在起始阶段遗传算法复杂度随节点数上升这与前面的算法是相同的；但是随着节点数的增加在最大循环次数代数的范围将变得不可收敛，此时算法的将跳出循环，复杂度不再上升。模拟退火遗传算法复杂度和模拟退火算法相比有所降低；同时相比遗传算法这有点偏高。可见，模拟退火遗传算法综合了遗传算法和模拟退火算法的特点。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文564.4 本章小结本章针对模拟退火算法以及遗传算法各自的特点，取长补短提出了模拟退火遗传算法，它综合了遗传算法和模拟退火算法的特点既拥有遗传算法的快收敛性，同时兼顾了模拟退火算法的全局搜索能力。通过MATLAB软件仿真，取得了较好的效果。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文57第 5 章 基于模拟退火遗传算法的无人机航迹仿真模拟退火遗传算法取长补短的综合了模拟退火算法和遗传算法的特点，同时兼顾了遗传算法的快收敛性，和模拟退火算法的全局搜索能力。本章将使用MATLAB软件对通过模拟退火遗传算法得到的最优航迹进行飞行仿真。5.1 无人机运动方程无人的运动方程是建立在如下的基础上：（1）认为飞机不仅是刚体，而且质量不变。（2）假定地球固定于空间，即略去地球自转、公转的影响。（3）假定飞机有一个对称面xoz（机体坐标系）,且飞行器不仅几何外形对称，而且内部质量分布亦对称，惯性积。0xyzyII（4）忽略地面曲率，视地面为平面。5.1.1 无人机运动的六自由度方程飞机在空间的运动有六个自由度，即质心沿地面坐标系的三个移动自由度和绕机体坐标轴系的三个转动自由度，如下。飞机六自由度运动包括飞机绕三轴的转动（飞机姿态变化） ，及飞机三个线位置的变化，在建立六自由度方程时，选机体坐标系。取机体坐标系作为动坐标系，得到如下的动力学方程38：力矩的平衡方程式：:qLHprY一个角运动俯仰纵向航程两个线运动:高度滚转两个角运动:侧向偏航一个线运动侧偏西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文58 (5-1) 22()()()()xxzzrxzrxzxzzxzrxxzLpIrIqr IIpqIMqIpr IIprINrIpIpq IIprI其中L,M,N 分别指沿机体坐标轴x, y, z的力矩，p, q, r分别指沿机体坐标轴x, y, z的角速度，分别表示绕机体坐标轴x, y, z的转动惯量，分别表,xrzIII,yzxzxyIII示绕机体坐标轴x, y, z的惯性积。力平衡方程式： (5-2) ()()()xyzFXuwqvr mdvFmFYvurwp mdtFZwvpup m其中，分别指飞机沿机体坐标轴 x, y, z 所受到的力，m 为飞机的质量，xFyFzFu，v，w 分别指飞机沿机体坐标轴 x, y, z 的速度。根据上式，建立飞机的六自由度方程39：角位置运动学方程式 (5-3)cossin( cossin )1( cossin )cosqrprqtgrq其中，分别为俯仰角，偏航角，滚转角。线位置运动学方程式 (5-4)coscos(cossinsinsincos )(cos sincossinsin )sincos(sinsinsincoscos )( sincoscos sinsin )sincossincoscosggdxuvdtwdyuvdtwdHuvwdt其中，指飞机沿地面坐标轴x, y的位移，H为飞机离地面的高度。这样飞gxgy机的运动方程组就变成关于状态变量控制ggVpqrxyh西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文59输入之间的非线性函数关系了。Tear5.1.2 无人机运动方程的解耦（1）线性化六自由度方程是严重非线性的复杂方程，为便于分析和控制器的设计，借助于小扰动方法进行线性化处理。目前，小扰动条件下线性化的飞机方程是进行飞机稳定性和操纵性理论分析的重要工具。描述飞机的运动参量，可看成是平衡点时的量值加上扰动小量，即： (5-5)00000000000uuuvvvwwwpppqqqrrw各运动量增量均为小量，所以与运动参数有关的外力和外力矩, uv就可以按这些参数的增量展开成泰勒级数形成，然后只留一次项，略去高阶项，使外力和外力矩取决于运动参数及它们对时间的一次导数。得到线性化状态方程如下： (5-6)111eeeeeeXXXnXU UXXXXnU UUXXUnU UEXAXBUfEffAffBf （2）无人机运动方程的分组纵向运动飞机在其对称平面内的运动，包括绕横轴的转动和沿纵轴及西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文60沿立轴的线运动。对称面内运动参数：。, ,V q侧向运动沿机体横轴的线运动，及绕、的转动。不对称运动oy ox oz 参数：。, ,p r得到的侧向线性化小扰动运动方程组如下： (5-7)ar*U=00000010000100001coscossin00coscos00TwwarararepreeeeprprEXAXBUXprYYVEBLLNNYgYYVALLLNNN 和，得到纵向线性化小扰动运动方程组如下： (5-8)TeU=1000cos000sin001000001coscos0sinsin00010TTeeTeeTeVTVeeVTVeeqVTVqEXAXBUXVqXXVZXZEBMMMXXXgZXZgVZAMMMM 和，5.2 无人机控制律典型飞行控制系统结构如下：西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文61重心位置测量元件放大计算装置放大器舵机舵面飞机运动学环节反馈元件敏感元件舵回路稳定回路控制回路图 5-1 典型飞行控制系统结构图由上图可以看出典型的飞行控制系统一般由三个反馈回路组成，即舵回路，稳定回路和控制回路。本文考虑的轨迹跟踪问题主要是进行侧向偏离的修正，在纵向飞机将以v=50m/s的速度飞行。5.2.1 倾斜保持的自动控制采用如下的倾斜保持模态的控制形式： (5-9)arIIkk经调参得到为0.1, 为1.5, 为0.1，为0.1。IIkk当给定一个的干扰后，的变化情况如下：05, , ,p r西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文62050100-4-2024传 传 传 传 传 传 传 传beta传 传 传 传 传 传050100-10-505传 传 传 传 传 传 传 传p传 传 传 传 传 传 传 传050100-4-2024传 传 传 传 传 传 传 传r传 传 传 传 传 传 传 传050100-20246传 传 传 传 传 传 传 传fai传 传 传 传 传 传图 5-2 当给定干扰的变化曲线图05, , ,p r从上图中可以看出，虽然全部都收敛了，但是调节时间较长需要, , ,p r设计增稳系统来进行改进。5.2.2 增稳系统现在的无人机所执行任务的要求越来越高，使得飞行包线不断扩大，飞机的性能也急剧变坏。为改善飞机的角运动性能，仅依靠气动布局和结构设计已经不能实现大包线飞行的要求，这样就有必要设计增稳系统来改进稳定回路。侧向采用如下的增稳形式： (5-10)araakkkI 其中为3，为1，为1.5，为0。kakkI使用附2-1中的飞机状态方程的侧向状态矩阵仿真，当给定一个的05干扰后，的变化情况如下图5-3所示：, , ,p r西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文63050100-1-0.500.5传 传 传 传 传 传 传 传beta传 传 传 传 传 传050100-10-505传 传 传 传 传 传 传 传p传 传 传 传 传 传 传 传050100-0.500.51传 传 传 传 传 传 传 传r传 传 传 传 传 传 传 传050100-20246传 传 传 传 传 传 传 传fai传 传 传 传 传 传图 5-3 增稳后当给定干扰的变化曲线图05, , ,p r由上图可以看出，的变化范围均在要求的范围内，即，, , ,p r05，。同时，曲线不再来回震荡，调节时间大为减025 /ps025 /rs025少。当给定一个的干扰后，的变化情况如图5-4所示：05, , ,p r由上图可以看出，的变化范围均在要求的范围内，即，, , ,p r05，。可见增稳系统很好的保持飞机稳定性。025 /ps025 /rs025西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文64050100-20246传 传 传 传 传 传 传 传beta传 传 传 传 传 传050100-1-0.500.5传 传 传 传 传 传 传 传p传 传 传 传 传 传 传 传050100-10123传 传 传 传 传 传 传 传r传 传 传 传 传 传 传 传050100-0.4-传 传 传 传 传 传 传 传fai传 传 传 传 传 传图 5-4 增稳后当给定干扰的变化曲线图05, , ,p r5.2.3 预选航向的自动控制采用如下的倾斜保持模态控制： (5-11)()()1agrgIIIkkkTs经调参得到为0.1, 为1.5, 为0.1，为0.1，为0.4，k为0.1，T为IIkkI10。当给定，初始状态为。飞机跟踪时的变化如图5-5所示。045g000此时的变化情况如图5-6所示。, , ,p r由图5-6可以看出，的变化范围均在要求的范围内，即，, , ,p r05，。可见系统很好的跟踪了信号。025 /ps025 /rs025045g西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文655.2.4 侧向偏离的自动控制侧向偏离控制的几种方案如下：（1）通过副翼控制滚转转弯以修正侧向偏离y，方向舵只起阻尼与辅助协调作用。此方案用的较广。（2）通过副翼与方向舵两通道协调转弯控制y。0102030405060708090100-505101520253035404550传 传 传 传 传 传 传 传fai传 传 传 传 传 传图 5-5 跟踪给定时的变化曲线图045g西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文6605010001234传 传 传 传 传 传 传 传beta传 传 传 传 传 传050100-1001020传 传 传 传 传 传 传 传p传 传 传 传 传 传 传 传050100-2024传 传 传 传 传 传 传 传r传 传 传 传 传 传 传 传050100051015传 传 传 传 传 传 传 传fai传 传 传 传 传 传图 5-6 跟踪给定时的变化曲线图045g, , ,p r（3）利用副翼与方向舵控制转弯来修正y，副翼通道起辅助协调作用。（4）利用方向舵使飞机保持航向，靠滚转产生侧滑来修正y。（5）通过飞机不倾斜的平面转弯修正y，此时副翼保持机翼水平，方向舵控制飞机平面转弯来修正y。本文采用第1种方案。飞机横侧运动线性化方程如下：侧力方程组： (5-12)()rrSYrYY 滚转力矩方程组： (5-13)()p(i)arprrarLSLSL rLL 偏航力矩方程组： (5-14)pp(i)()arrarNSNSN rNN 由于方向舵是起阻尼和协调作用，可略去偏航力矩方程。仅靠控0a制飞机滚转转弯，且滚转比偏航快的多，认为过程是瞬间完成的，即：西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文67 (5-15)0p由滚转力矩方程得： (5-16)ararL rLL 考虑协调转弯满足公式： (5-17)0gggtguuV考虑侧偏线位移方程： (5-18)cos sinsin sinsincos coscos sinsinsincosdyuvdtw在小扰动条件下，认为均为小值，则有： , , (5-19)00cos,uVV (5-20)00sinvVV (5-21)00cossinwVV 得出： (5-22)00()57.357.3VVy 联合各式得到如下的简化方程组 (5-23)0057.3aragVLLVy 采用如下形式的侧向偏离的控制规律 (5-24)()()()1agygrgIIIIyykkkTs其中为 0.1,为 1.5, 为 0.1，为 0.1，为 0.4，k 为 0.1，T 为 10，IIkkI为 0.00046。yI由简化方程组结合飞机方程看出：当于，相当于，相当于。同y y y 西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文68时是主信号，其余各信号均在动态过程起作用。 ()ygIyy图 5-7 侧向偏离控制系统结构图5.3 基于模拟退火遗传算法的无人机航迹仿真采用3.3.1节25节点的情况进行仿真，得到仿真曲线如图5-8所示：在终点处放大曲线图，可以看到终点处误差为107m，如图5-9所示。01000 2000 3000 4000 5000 6000 7000 8000 9000 1000011000010002000300040005000600070008000900010000y(传 传 传 传 )x(传 传 传 传 )传 传 传 传传 传 传 传图 5-8 25 节点轨迹航迹仿真曲线图 1 sWs1sVg0sV3 .5700yIIIIaWaLIZ1干LyIIgyg+-+西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文6911.0051.011.0151.02x 10498509900995010000y(传 传 传 传 )x(传 传 传 传 )传 传 传 传传 传 传 传图 5-9 25 节点轨迹航迹仿真曲线终点放大图 1这样有必要对控制律进行改进，以尽可能消除误差。给控制律加上积分环节尽快消除y方向上的误差，如下： (5-25)()()()()1agygDygrgIIIIyyIyydykkkTs其中为0.1, 为1.5, 为0.1，为0.1，为0.4，k为0.1，T为10，为IIkkIyI0.00046，为0.000063，得到仿真曲线如图5-10所示：DyI在终点处放大曲线图，可以看到终点处误差为4.8m达到了设计要求，如图5-11所示。西北工业大学明德学院本科毕业设计论文西北工业大学明德学院本科毕业设计论文7001000 2000 3000 4000 5000 6000 7000 8000 9000 1000011000010002000300040005000600070008000900010000y(传 传 传 传 )x(传 传 传 传 )传 传 传 传传 传 传 传图 5-10 25 节点轨迹航迹仿真曲线图 20.9994 0.9996 0.999811.0002 1.0004 1.0006 1.0008 1.001x 104998499869988999