無人機自主飛行航跡規(guī)劃算法研究,無人機,自主,飛行,航跡,規(guī)劃,算法,研究 本科畢業(yè)設(shè)計論文本科畢業(yè)設(shè)計論文題題 目目無人機自主飛行航跡規(guī)劃算法研究無人機自主飛行航跡規(guī)劃算法研究系 別 自動化系 專 業(yè) 自動化 班 級 191002 學生姓名 張 川 學 號 103613 指導教師 聶 聰 畢業(yè) 任務(wù)書一、題目無人機自主飛行航跡規(guī)劃算法研究2、指導思想和目的要求(1) 了解和熟悉現(xiàn)代飛行控制技術(shù)的基本概念、內(nèi)容與作用；(2) 熟悉已有的航跡規(guī)劃算法，選擇并設(shè)計合適的航跡規(guī)劃算法；(3) 綜合運用已學的有關(guān)飛行控制與飛行仿真方面的知識，并參閱國內(nèi)外有關(guān)參考文獻，設(shè)計某型無人機的航跡自主飛行控制系統(tǒng)，達到理論與實踐相結(jié)合的目的；(4) 基本掌握飛行控制系統(tǒng)的計算機仿真方法與仿真實踐。三、主要技術(shù)指標(1) 完成航跡規(guī)劃算法，滿足某型飛機的任務(wù)要求。(2) 完成飛機的航跡控制，側(cè)向航跡誤差在 5 米內(nèi)；四、進度和要求畢業(yè)設(shè)計論文時間從 2014 年 2 月 25 日6 月 1 日，應(yīng)在 15 周內(nèi)完成。2014 年 6 月 1 日6 月 20 日為論文評閱、答辯時間。進度要求：1)第 1 周第 3 周，開始英文資料翻譯；收集論文資料，熟悉研究內(nèi)容，確定設(shè)計方案。2)第 4 周第 12 周，按照指標要求開展論文的研究工作。3)第 13 周，論文初稿審查和修改。4)第 14 周，論文定稿和裝訂。5)第 15 周，論文評閱。6)第 16 周，論文答辯。設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文i其他要求：(1) 畢業(yè)設(shè)計論文格式嚴格按照教務(wù)處統(tǒng)一格式編寫，模版從教務(wù)處網(wǎng)頁下載。文內(nèi)公式應(yīng)編號、參考文獻引用要標注，格式要統(tǒng)一。(2) 論文裝訂格式：正式封面、內(nèi)封面（可無） 、任務(wù)書、中文摘要、英文摘要、目錄、正文（包括論文總結(jié)和展望） 、參考文獻、致謝等。(3) 英文資料翻譯應(yīng)在論文評閱前與英文原文單獨裝訂成冊并與論文一并上交，裝訂順序為：封面、中文翻譯稿、英文原文。5、主要參考書及參考資料(1) 飛行控制系統(tǒng)張明廉主編航空工業(yè)出版社(2) 飛行控制 肖順達國防工業(yè)出版社(3) 現(xiàn)代飛行控制系統(tǒng)文傳源北京航空航天大學(4) 控制系統(tǒng)計算機輔助設(shè)計MATLAB 語言及應(yīng)用 薛定宇 著 清華大學出版社學生 張 川 指導教師 聶 聰 系主任 史儀凱 西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文摘 要無人機航跡規(guī)劃是無人機任務(wù)規(guī)劃系統(tǒng)的關(guān)鍵技術(shù)之一，也是無人機實現(xiàn)自主飛行和自主攻擊的基礎(chǔ)。論文比較了七種常用的航跡規(guī)劃算法，提出了一種模擬退火遺傳方法。最后通過設(shè)計側(cè)向偏離控制律，對應(yīng)用模擬退火遺傳算法所規(guī)劃的飛行最優(yōu)路徑進行了系統(tǒng)仿真驗證，仿真結(jié)果取得了較好的效果。主要工作內(nèi)容如下：（1）論述了空中主要威脅，并建立了雷達方程；綜合考慮雷達威脅和航程等因素，確定了航跡代價函數(shù)；把無人機的航跡規(guī)劃問題轉(zhuǎn)化為圖論中求最短路徑的問題。（2）以正確度和復雜度作為仿真結(jié)果的評價標準，比較了Floyd算法，算法，雙向算法，遺傳算法，模擬退火算法，蟻群算法和粒子群算法，得*A*A出了如下的結(jié)論：傳統(tǒng)的航跡規(guī)劃算法的復雜度隨著節(jié)點數(shù)的增加迅速上升，這就導致它在現(xiàn)代航跡規(guī)劃算法中發(fā)展受到了限制；在隨機算法中模擬退火算法正確性較高，而遺傳算法復雜度較低。（3）針對無人機的具體特點并綜合模擬退火算法和遺傳算法提出了一種模擬退火遺傳算法。仿真結(jié)果表明該方法繼承了模擬退火算法正確性較高和遺傳算法復雜度較低的優(yōu)點。（4）建立了無人機的運動方程，使用模擬退火遺傳算法規(guī)劃出了最優(yōu)飛行路徑，最后使用側(cè)向偏離控制律跟蹤得出的最優(yōu)路徑。 關(guān)鍵詞：無人機航跡規(guī)劃，模擬退火遺傳算法，側(cè)向偏離，飛行控制西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文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 西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文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西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文III目 錄摘摘 要要 .IABSTRACT.II第第 1 章章 概概 論論.11.1引言.11.2無人機航跡規(guī)劃方法回顧.21.2.1 決策型搜索方法.31.2.2 隨機型搜索方法.41.3 本文的主要工作.5第第 2 章章 無人機航跡規(guī)劃基礎(chǔ)無人機航跡規(guī)劃基礎(chǔ).72.1 雷達威脅模型.72.2 航跡規(guī)劃問題的數(shù)學描述.82.2.1 路線優(yōu)化問題的模型.82.2.2 航跡代價函數(shù).92.3 本章小節(jié).10第第 3 章章 無人機航跡規(guī)劃方法無人機航跡規(guī)劃方法.113.1 傳統(tǒng)航跡規(guī)劃算法.113.1.1 Floyd 算法 .113.1.2 算法.12*A3.1.3 雙向算法.15*A3.2 現(xiàn)代航跡規(guī)劃算法.153.2.1 遺傳算法.163.2.2 模擬退火算法.213.2.3 蟻群算法.24西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文IV3.2.4 粒子群算法.263.3 航跡規(guī)劃算法的仿真分析.283.3.1 算法正確率分析.283.3.2 算法復雜度分析.383.4 航跡規(guī)劃算法的比較.433.5 本章小結(jié).45第第 4 章章 模擬退火遺傳算法模擬退火遺傳算法.474.1 模擬退火遺傳算法的基本原理.474.2 模擬退火遺傳算法編程的實現(xiàn).474.3 模擬退火遺傳算法仿真分析.534.4 本章小結(jié).56第第 5 章章 基于模擬退火遺傳算法的無人機航跡仿真基于模擬退火遺傳算法的無人機航跡仿真.575.1 無人機運動方程.575.1.1 無人機運動的六自由度方程.575.1.2 無人機運動方程的解耦.595.2 無人機控制律.605.2.1 傾斜保持的自動控制.615.2.2 增穩(wěn)系統(tǒng).625.2.3 預選航向的自動控制.645.2.4 側(cè)向偏離的自動控制.645.3 基于模擬退火遺傳算法的無人機航跡仿真.685.4 本章小結(jié).71第六章第六章 全文總結(jié)全文總結(jié).72參考文獻參考文獻.73致致 謝謝.76畢業(yè)設(shè)計小結(jié)畢業(yè)設(shè)計小結(jié).77西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文0第 1 章 概 論1.1 引言隨著第一架無人機于20世紀初在英國誕生，在最近的一個世紀中無人機(UVA)得到了飛速的發(fā)展。它從最初簡單的靶機，發(fā)展到現(xiàn)在廣泛應(yīng)用到偵查、監(jiān)視、攻擊以及電子戰(zhàn)等多種任務(wù)的戰(zhàn)斗平臺1。隨著現(xiàn)代科學技術(shù)的不斷進步，無人機吸收了現(xiàn)代科技的優(yōu)秀成果并朝著隱身化、數(shù)字化、小型化、智慧化、通用化以及攻防兼?zhèn)涞确较虬l(fā)展2。總的來說，現(xiàn)代無人機在戰(zhàn)爭中主要使用形式有1：（1）作偵察機使用，和軍事衛(wèi)星、有人駕駛偵察飛機相配合，為作戰(zhàn)部隊提供戰(zhàn)區(qū)實時情報 。（2）作戰(zhàn)術(shù)誘餌機使用，模擬飛機或?qū)椀睦走_或紅外特性，吸引對方火力，減少作戰(zhàn)飛機的損失。（3）通信中繼、炮火校正、作戰(zhàn)效果評估等。由于無人機沒有飛行員駕駛，所以它相對于有人駕駛飛機而言具有體積小、重量輕、機動性好、隱蔽性高、適應(yīng)性強而且成本低等特點。這就使得它在軍用和民用領(lǐng)域得到了廣泛的關(guān)注3-4。正是因為無人機沒有飛行員，為了使無人機能夠?qū)崿F(xiàn)全自主方式的飛行，操作人員必須提前對無人機的航線進行規(guī)劃，包括航線中各個關(guān)鍵航點的經(jīng)緯度位置信息、高度信息以及對任務(wù)設(shè)備的操作等。對操作人員而言，這是一項非常繁重的任務(wù)。隨著計算機技術(shù)的進步和GPS系統(tǒng)的廣泛應(yīng)用，無人機地面控制站中逐漸發(fā)展出了一個嶄新的獨立模塊一航跡系統(tǒng)。利用航跡系統(tǒng)，操作人員可以直接在數(shù)字地圖上進行航跡的規(guī)劃，能夠?qū)崟r、便捷地得到數(shù)字地圖中任意一點的多種信息。這一功能將航跡規(guī)劃所需的時間從原來的數(shù)個小時甚至更長時間縮短到了數(shù)十分鐘甚至只需數(shù)分鐘。同時，航跡系統(tǒng)還能夠?qū)崟r地跟蹤無人機航跡5。目前美國研制的任務(wù)規(guī)劃系統(tǒng)己經(jīng)發(fā)展到第三代，正朝著提高效率和降低西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文1系統(tǒng)成本等方面繼續(xù)發(fā)展。英國已研制成功Pathfinder2000任務(wù)規(guī)劃系統(tǒng)。法國目前裝備有M工PSY，CINNA和CIRCE2000等系列任務(wù)規(guī)劃系統(tǒng)。90年代以來，NASA和美國軍方聯(lián)合開展一項名為ANOE的研究計劃，旨在輔助直升機駕駛員實施貼地飛行。在50年代到70年代，飛行器航跡優(yōu)化的理論有了一定的發(fā)展，主要的工作在于求近似解析解。隨著最優(yōu)控制理論、最優(yōu)化數(shù)值計算方法和計算機技術(shù)的飛速發(fā)展，最優(yōu)航跡的數(shù)值計算在80年代得到長足發(fā)展并趨于成熟。我國在八十年代初開始了地形跟蹤與回避技術(shù)的研究，到了九十年代，這項技術(shù)的研究得到了蓬勃地發(fā)展，西工大、北航、南航等單位在飛行器低空突防策略和控制、航跡規(guī)劃技術(shù)等領(lǐng)域做了一定的研究。目前，我國航跡規(guī)劃技術(shù)研究正進一步向智能化、實時性、可實現(xiàn)性方向發(fā)展，但基本上還處于跟蹤國外的水平，性能完善的航跡規(guī)劃系統(tǒng)特別是無人機航跡規(guī)劃系統(tǒng)還有待進一步研究開發(fā)2。1.2 無人機航跡規(guī)劃方法回顧航跡規(guī)劃方法的主要目的是在給定的規(guī)劃區(qū)域內(nèi)尋找一條最優(yōu)的或滿意的飛行航跡，因此從根本上講屬于一個路徑或航跡搜索的問題。航跡規(guī)劃方法一般可歸納為兩大類搜索方法:決策型搜索方法和隨機型搜索方法6。航跡規(guī)劃方法的具體示意圖如下所示。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文2 航跡規(guī)劃方法 決策型搜索方法 隨機型搜索方法 動態(tài)規(guī)劃算法 啟發(fā)式動態(tài)優(yōu)先算法 盲目搜索方法 神經(jīng)網(wǎng)絡(luò)算法 蟻群算法 遺傳算法 勢場法 貝葉斯優(yōu)算法 模擬退火算法 粒子群算法 Monte-Carlo算法 深度優(yōu)先搜索技術(shù) 其它盲目搜索方法 寬度優(yōu)先搜索技術(shù) 其它隨機型搜索方法 圖1-1 無人機航跡規(guī)劃方法示意圖1.2.1 決策型搜索方法（1）盲目搜索算法（非啟發(fā)式搜索算法）盲目搜索方法是一種最簡單的決策型算法。在無人機航跡規(guī)劃中，這種算法無法利用目標信息指導其搜索過程，規(guī)劃效率不高，目標信息僅僅被當作規(guī)劃結(jié)束的判決條件6，所以它只適于求解比較簡單的問題。無人機航跡規(guī)劃常用的算法如寬度優(yōu)先、深度優(yōu)先搜索技術(shù)7等均屬于盲目搜索，它們只提供了一種機械的搜索策略，而不能不斷變化的外部威脅調(diào)整它們的搜索行為。這往往導致它們搜索效率低，而易觸發(fā)組合爆炸。（2）啟發(fā)式最佳優(yōu)先算法在無人機航跡規(guī)劃中，啟發(fā)式最佳優(yōu)先算法使用極為普遍。最佳優(yōu)先算法在規(guī)劃中利用到了啟發(fā)式因子指導規(guī)劃過程8，啟發(fā)式信息在路徑規(guī)劃中主要是目標位置，它在規(guī)劃中轉(zhuǎn)換為了一種數(shù)據(jù)結(jié)構(gòu)或函數(shù)，算法根據(jù)每個節(jié)點的啟發(fā)信息來選擇最佳的擴展節(jié)點，啟發(fā)式算法的性能直接與這些啟發(fā)式函數(shù)人f(n)的選擇有關(guān)。由于啟發(fā)式搜索引入了問題求解的目標信息，可以根據(jù)不同的求解目標而調(diào)整其規(guī)劃行為，避免了盲H搜索，極大的提高了搜索的效率6。當西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文3把無人機運行區(qū)域網(wǎng)格化了之后，使用啟發(fā)式函數(shù)f(n)=g(n)+h(n)，把無人機航跡規(guī)劃問題轉(zhuǎn)化為用樹狀結(jié)構(gòu)表示，則就成了最佳優(yōu)先算法即為著名的算法。*A其中g(shù)(n)為起始點到當前節(jié)點n的路徑代價，h(n)為當前節(jié)點n到目標點的預測代價5。由于當算法的啟發(fā)式因子滿足單調(diào)性條件時，其搜索性能被證明是最*A佳的，因此在無人機航跡規(guī)劃中成為最常用的算法之一9-10。*A（3）動態(tài)規(guī)劃算法動態(tài)規(guī)劃實際上是一種寬度優(yōu)先算法的遞歸形式，它最早應(yīng)用于最優(yōu)控制問題。它將規(guī)劃問題視為一個多級決策問題，然后將之轉(zhuǎn)換為一系列簡單的、易于求解的多個單級決策問題來處理5-6。它應(yīng)用的一個前提條件即所謂的過程無后效性，也就是說，對于當前狀態(tài)，前一個狀態(tài)與決策的選擇僅僅表現(xiàn)為它們將狀態(tài)轉(zhuǎn)移到了當前狀態(tài)，并隨之確定了可供選擇的決策集合，至于當前狀態(tài)到下一個狀態(tài)的決策選擇，以及后續(xù)過程將如何進行，與它們無關(guān)11。由于無人機航跡規(guī)劃的特殊性，后一個狀態(tài)一般前一個狀態(tài)均有關(guān)聯(lián)，這就大大的限制了動態(tài)規(guī)劃算法在無人機航跡規(guī)劃中的應(yīng)用。1.2.2 隨機型搜索方法（1）勢場法基于勢場法的路徑搜索算法借鑒了電磁場理論的電磁勢概念，為規(guī)劃區(qū)域的不同物體建立起了勢場，異性物體相吸，同性相斥。目標點被賦以很高的正勢，而起始點被賦予比目標點還低的勢位。而運動點被賦以與起始點相同的勢位，同時障礙(禁飛區(qū))則被賦以比起始點更低的勢位。因而運動點被起始點與障礙所排斥，而被吸引向目標點6。在無人機航跡規(guī)劃中，這種方法的主要缺點是運動點可能陷入局部極小值，即計算出來的航跡不一定最優(yōu)的。（2）遺傳算法在無人機航跡規(guī)劃中，遺傳算法是一種很有前途的隨機型搜索算法12，它應(yīng)用遺傳學與進化論來分析問題求解問題。在其中，路徑被編碼成類似基因的結(jié)構(gòu)。以代價函數(shù)為依據(jù)，通過對大量的路徑基因串的再生產(chǎn)、基因互換、個體變異等運算，可以進化出具有最優(yōu)基因的路徑5。遺傳算法的優(yōu)點是它可以進行并行計算。然而，即使最優(yōu)解的確存在，這種算法并不一定能找到最優(yōu)解。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文4它常常收斂到一個性能平平的解，而在這個解的附近卻有更好的解6,10。（3）模擬退火算法模擬退火算法摹仿了熱力學中的退火過程。在無人機航跡規(guī)劃問題中。退火算法將“加熱”在起始點附近一定范圍內(nèi)的所有點。然后不斷進行迭代運算，使所有的點的溫度都逐漸冷卻13。冷卻的速度根據(jù)一個隨機產(chǎn)生的冷卻時間表決定。禁飛區(qū)域被賦以更高的能量狀態(tài)，因而，冷卻過程將回避這些區(qū)域，在迭代一定時間后，通過尋找規(guī)劃區(qū)域的最低溫度，可以得到最優(yōu)航跡6。（4）蟻群算法粒子群算法是一種新興的無人機航跡規(guī)劃算法。蟻群算法 (Ant Algorithm)也是一種概率搜索算法，它利用生物信息激素(Pheromone/5tigmergy)作為螞蟻選擇后續(xù)行為的依據(jù)。每只螞蟻會對一定范圍內(nèi)其它螞蟻散布的生物信息激素做出反應(yīng)，依據(jù)生物信息激素的強度在侮一個道日對多條路徑選擇做出概率上的判斷并執(zhí)行該選擇，由此察覺并影響到它們以后的行為5。當一些路徑上通過的螞蟻越來越多時，其留下的生物信息激素軌跡(Trail)也越來越多，以致生物信息激素強度增大(當然，由于生物信息激素的蒸發(fā)作用，其強度會隨時間的推移逐漸減弱)，后來螞蟻做選擇時該路徑的被選概率也越高，從而更增加了該路徑上的生物信息激素強度。這樣，經(jīng)過一個眾多螞蟻協(xié)同搜尋的過程后，幾乎所有螞蟻都會走最短的那一條路徑，最短路徑也由此被搜索找到14-15。（5）粒子群算法粒子群優(yōu)化算法源于對鳥群覓食行為的研究。研究者發(fā)現(xiàn)鳥群在飛行過程中經(jīng)常會突然改變方向、散開、聚集，其行為不可預測，但其整體總保持一致性且個體與個體間也保持著最適宜的距離2。通過對類似生物群體的行為的研究，發(fā)現(xiàn)生物群體中存在著一種社會信息共享機制，它為群體的進化提供了一種優(yōu)勢這也是PSO算法形成的基礎(chǔ)。由于粒子群算法的解是連續(xù)的，而無人機的航跡應(yīng)該是離散的，這就大大限制了粒子群算法在無人機航跡規(guī)范中的應(yīng)用。（6）貝葉斯優(yōu)算法(BOA)把無人機路徑編碼為離散時間上的速度和航向變化序列，每一步的速度和航向變化量都限制在無人機相應(yīng)最大變化量之內(nèi)，所以這種編碼方法對應(yīng)的物理軌跡是無人機可飛的。利用每代種群中的優(yōu)良解集構(gòu)造貝葉斯網(wǎng)絡(luò)，用貝葉西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文5斯網(wǎng)絡(luò)的結(jié)構(gòu)體現(xiàn)染色體基因位之間的聯(lián)系，用貝葉斯網(wǎng)絡(luò)參數(shù)體現(xiàn)染色體基因位之間的聯(lián)系程度。用貝葉斯網(wǎng)絡(luò)產(chǎn)生新的染色體以體現(xiàn)種群的進化，這取代了傳統(tǒng)遺傳算法的交叉和變異過程。如果不滿足終止條件，則用新一代種群的優(yōu)良解集構(gòu)造貝葉斯網(wǎng)絡(luò)，直到滿足終止條件16。（7）Dijkstra 算法Dijkstra 算法是由EW狄克斯拉在1959年首先提出來的，是解決圖論中最短路徑的經(jīng)典方法。與Floyd算法相似，該算法不僅能求出從起點到終點的最短路，而且還能求出起點到其它各中間點的最短路。其算法思想是按路徑長度遞增次序產(chǎn)生從某源點到圖中各頂點的最短路徑17。算法總的時間復雜度為O()2n18。由于無人機的航跡規(guī)劃時節(jié)點數(shù)很多，Dijkstra 算法所需要的內(nèi)存空間很難滿足，這就意味著Dijkstra 算法在無人機規(guī)劃中使用不多。1.3 本文的主要工作本文對7種典型的路徑規(guī)劃算法-Floyd算法，算法，雙向算法，遺傳*A*A算法，模擬退火算法，蟻群算法，粒子群算法-進行了分析，針對無人機任務(wù)的特殊性，綜合考慮前七種方法的優(yōu)缺點，提出了模擬退火遺傳算法，并使用MATLAB軟件進行了飛行仿真。本文的工作可以分為如下的幾個方面：(1)第一章介紹了無人機的主要作戰(zhàn)形式和無人機航跡規(guī)劃算法的發(fā)展；簡要的介紹了無人機航跡規(guī)劃的兩類方法-決策性搜索方法（傳統(tǒng)搜索方法）和隨機型搜索方法，并著重的介紹了盲目搜索算法（非啟發(fā)式搜索算法） ，啟發(fā)式最佳優(yōu)先算法，動態(tài)規(guī)劃算法，勢場法，遺傳算法，模擬退火算法，蟻群算法，粒子群優(yōu)化算法（PSO） ，貝葉斯優(yōu)算法(BOA)，Dijkstra 算法。(2)第二章分析了空中主要威脅，建立了雷達方程；綜合考慮雷達威脅和航程等因素，確定了航跡代價函數(shù)；把無人機的航跡規(guī)劃問題轉(zhuǎn)化為圖論問題。(3)第三章分析和比較了Floyd算法，算法，雙向算法，遺傳算法，模*A*A擬退火算法，蟻群算法和粒子群算法，并得出了重要的性質(zhì)。(4)第四章綜合模擬退火算法和遺傳算法的特點并針對無人機的特殊要求提出了一種模擬退火遺傳算法；通過仿真分析證明了它繼承了模擬退火算法和遺傳算法的優(yōu)點。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文6(5)第五章建立了無人機的運動方程，通過小擾動原理實現(xiàn)了運動方程的橫縱向解耦；使用模擬退火遺傳算法得出了最優(yōu)路徑，然后使用側(cè)向偏離控制律跟蹤得到的最優(yōu)路徑；仿真結(jié)果滿足了國軍標GB2191-94要求。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文7第 2 章 無人機航跡規(guī)劃基礎(chǔ)2.1 雷達威脅模型在無人機完成指定任務(wù)的過程中，將受到多種威脅的綜合作用，如地形因素威脅、電磁干擾威脅、防空火炮威脅、地空導彈威脅、雷達探測威脅以及大氣條件威脅2。因為雷達是防空火力的“眼睛”，本文將著重考慮雷達的威脅。目前，雷達是遠距離發(fā)現(xiàn)目標最重要的設(shè)備。依靠自身發(fā)射的電磁波，雷達通過對余波的分析來得到有關(guān)目標的信息。典型的雷達是由天線、發(fā)射機、接收機、信號處理器和終端顯示設(shè)備組成。雷達發(fā)射機產(chǎn)生探測所需輻射強度的電磁波，強功率信號饋送到天線，由天線輻射到特定空間，為滿足雷達的測向精度和分辨力，天線一般具有很強的方向性。接收機將微弱的目標回波信號經(jīng)檢波、放大等處理后，判斷目標是否存在，并由顯示設(shè)備方便顯示2。雷達方程是描述雷達系統(tǒng)特性的最基本的數(shù)學方程。在雷達方程的完整形式中，考慮了雷達系統(tǒng)參量、目標參量、背景雜波和干擾影響、傳播影響、傳播介質(zhì)等各種因素對雷達作用距離的影響，雷達方程對目標探測問題的分析十分必要19-21。常見的雷達方程如(2-1)式所示。 (2-1)222322(4 )TTRTRRTRBTRP G GF FPR R C L L 其中，各符號的含義見表2-1。如果在式(2-1)中考慮了方向圖傳播因子和損耗因子，未考慮大氣衰減因子。對于收發(fā)合置的單基地雷達，由于= =R, = =G， = =L, TRRPTGRGRLTL=F,所以，式(2.1)可以簡化為RFTF (2-2)22234(4 )TRBP GFPR C L 因此可以根據(jù)方程計算無人機在每一點被發(fā)現(xiàn)的概率從而優(yōu)化無人機的軌跡。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文8 表 2-1 雷達航程各符號的含義符號含義符號含義RP雷達接收機收到的回波信號功率TP為雷達發(fā)射機輸出功率TG發(fā)射天線增益RG接收天線增益雷達的工作波長目標的雷達散射截面積TF發(fā)射方向圖傳播因子RF接收方向圖傳播因子TR發(fā)射機到目標的距離RR接收機到目標的距離TL發(fā)射損耗因子RL接收損耗因子。BC濾波器與信號波形匹配程度系數(shù)，在匹配情況下，=1，不匹配情況下， BCBC12.2 航跡規(guī)劃問題的數(shù)學描述把無人機進入威脅區(qū)域定位開始點，把攻擊目標所處的方位作為目標點，我們可以把無人機的航跡規(guī)劃問題轉(zhuǎn)化為圖論中的最優(yōu)路徑問題。這種方法是一種確定性狀態(tài)空間搜索方法，可以減小規(guī)劃空間的規(guī)模，降低了航路規(guī)劃的難度22。因此我們可以分兩步走：（1）我們先考慮一些約束條件（如無人機的航程） ，同時忽略掉一些約束條件（如無人機的性能約束） ，以航程最短以及威脅最小為目標，得出最優(yōu)的航跡。（2）然后在此基礎(chǔ)上利用沒有考慮的剩余約束，對求得的航跡進行修正和光順處理，以得到無人機可用的理性軌跡。把問題分解后我們可以看出，航跡規(guī)劃問題的第一步實際上就是一個路線優(yōu)化問題。2.2.1 路線優(yōu)化問題的模型路線優(yōu)化問題是依據(jù)某些優(yōu)化準則，如花費代價最小或行走路線最短等，在其規(guī)劃空間(網(wǎng)絡(luò)圖中)找出一條經(jīng)過若干節(jié)點的，能夠從起始點到達目標點，并且能夠避開各種阻礙的最優(yōu)運動路徑，實現(xiàn)花費代價最小或行走路線最短等目標。它應(yīng)可以根據(jù)起始點和目標點的方位和路網(wǎng)(空域)狀況，選擇最優(yōu)路徑西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文9及對多目標點存在的情況下進行優(yōu)化選擇以取得某種效益。它是包括機器人和導航等問題在內(nèi)許多領(lǐng)域的研究內(nèi)容22-23。對于無人機具體而言，可以對無人機的規(guī)劃空間進行二維/三維網(wǎng)格劃分以后會得到若干節(jié)點，構(gòu)成個一個網(wǎng)絡(luò)圖。這樣就把無人機復雜的路徑規(guī)劃問題簡化為求取網(wǎng)絡(luò)圖中最短路徑的優(yōu)化問題，即從網(wǎng)絡(luò)圖的所有節(jié)點中選取一些節(jié)點，使得無人機在沿這些節(jié)點所形成的路徑上飛行時路徑的某種代價最小5。如果假設(shè)網(wǎng)絡(luò)圖的各個節(jié)點所組成的集合為S: S= , , 1s2sms網(wǎng)絡(luò)圖中所有可能的從起始點到目標點的路徑集合為E:E= , , 1e2eme若 和 (,S)為其中某一條路徑 (E )上的兩個相鄰節(jié)點，連iSjSiSjSkeke接兩節(jié)點的邊用V(,)表示，并用表示該條邊的代價，則無人機的航路規(guī)iSjSijd劃問題可描述為5: (2-3)ij1k(s ,s ) ekf(e )=min=s.t. e,ijijdE sS sS2.2.2 航跡代價函數(shù)為了得出無人機的最佳飛行航跡，應(yīng)該綜合考慮飛機的所面對的敵方威脅，飛機的機動性能的限制，地形的約束，航跡長度等因素。所以為了得到最優(yōu)的路徑，就需要對于綜合考慮上節(jié)說提出的每條邊的代價，它可以通過這些因ijd素加權(quán)平均來實現(xiàn)24。在第一步中，我們主要考慮敵方威脅和航跡長度，則每條邊的代價可以如下表示：ijd (2-4)0(1)fLtfWk WkW dt式中，W為廣義代價函數(shù)。為航路的威脅代價，為航路的油耗代價。系tWfW數(shù)k表示在制訂航路過程中根據(jù)任務(wù)安排航路制訂人員所做出的傾向性選擇。如西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文10果認為無人機在飛行過程中速度保持恒定5，則上式可以改寫如下:min (2-5)0(1)LtfWk WkW ds其中，L為航路的長度。那么，在節(jié)點搜索過程中第i條邊的權(quán)值為 (2-6),(1)it if iwk wkw如果簡單地認為敵方防御區(qū)域內(nèi)的各個雷達均相同且無相互聯(lián)系，并對雷達威脅模型進行了簡化處理，認為雷達信號正比于1/ (d是無人機到敵方雷達、4d導彈威脅陣地的距離)，則當無人機沿網(wǎng)絡(luò)圖的第i條邊飛行時，兩節(jié)點間的威脅代價可近似地認為正比于1/沿這條邊的積分5。4d當無人機以某一規(guī)定速度飛行時，可以簡單地認為油耗代價與航程成正比，有如下關(guān)系: (2-7),f iiWL這樣式(2-3)中的無人機的航路規(guī)劃問題可以表示成求下式航路代價函數(shù)的最小值。 ij1k(s ,s ) ek,f(e )=min=s.t. e,(1)ijijijt iidE sS sSdk wkL2.3 本章小節(jié)本章對無人機航跡規(guī)劃方法做了基礎(chǔ)性的分析：把對復雜狀態(tài)空間的搜索轉(zhuǎn)變?yōu)榱撕唵蔚膱D論問題；同時，討論了雷達威脅和油耗因素的影響，并最終建立了以雷達威脅最小和油耗因素最少為目標的航路代價函數(shù)模型。(2-8)西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文11第 3 章 無人機航跡規(guī)劃方法在敵方防守區(qū)域里去完成攻擊、監(jiān)視等任務(wù)時，無人機應(yīng)該根據(jù)具體情況選擇一條敵方威脅較小同時無人機性能指標能夠滿足要求的航路22-25。無人機航跡規(guī)劃是指飛行器能夠完成飛行任務(wù)并且滿足約束條件的飛行軌跡。航跡規(guī)劃是無人機任務(wù)規(guī)劃系統(tǒng)的關(guān)鍵組成部分，其目標是在適當?shù)臅r間內(nèi)計算出最優(yōu)或次最優(yōu)的飛行軌跡，能使無人機（UAV）回避敵方威脅環(huán)境，安全的完成預定任務(wù)26。如第一章所述，目前路徑規(guī)劃的方法主要分為決策型搜索方法和隨機型搜索方法，在本章中將對具有代表意義的幾種算法-Floyd算法，算法，*A雙向算法，遺傳算法，模擬退火算法，蟻群算法，粒子群算法-進行比較和分*A析。3.1 傳統(tǒng)航跡規(guī)劃算法這里將對幾種傳傳統(tǒng)算法-Floyd 算法，算法和雙向算法進行分析。*A*A3.1.1 Floyd 算法Floyd算法是目前解決路徑規(guī)劃問題最常用、最簡單的算法。Floyd算法又稱為弗洛伊德算法或插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。Floyd 算法的基本思路是：從圖的帶權(quán)鄰接矩陣A=開始，遞歸地 ( , )n na i j進行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。 遞推公式為： D(0)=A； 西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文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 計算結(jié)束后根據(jù)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 算法結(jié)束：D即為所有點對的最短路徑矩陣。對于Floyd算法邊權(quán)可正可負。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，效率較高。它的優(yōu)點可以總結(jié)為：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單；同時缺點也較明顯：時間復雜度比較高，不適合計算大量數(shù)據(jù)。3.1.2 算法*A算法采用鏈式結(jié)構(gòu)存儲，相對于Floyd算法使用的Floyd矩陣所占的內(nèi)存*A空間要小的多，在目前無人機的航跡規(guī)劃中使用十分廣泛。算法就是對啟發(fā)函數(shù)最小的節(jié)點依次擴展實現(xiàn)優(yōu)化的。因為啟發(fā)函數(shù)是*A由起始節(jié)點到當前節(jié)點的最小目標函數(shù)值與從當前節(jié)點到目標節(jié)點的估計目標函數(shù)值計算得到的，它依賴于啟發(fā)信息-估計目標函數(shù)值，所以被稱為啟發(fā)函數(shù)。因此，算法也被稱為啟發(fā)式算法。算法通過從起始節(jié)點出發(fā)，不斷地找尋*A*A有希望以最小代價通向目標點的節(jié)點并優(yōu)先擴展這些能夠使目標函數(shù)值較小的西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文13節(jié)點，從而形成一個節(jié)點集，則集合內(nèi)這些節(jié)點的有序連接即為所求優(yōu)化路徑，這一過程實際上是被選節(jié)點不斷增加、擴展的過程。它存在種潛能，可以采用最少的估價源找到優(yōu)化路徑。這種算法是一種有效的計算最短路徑的方法5。本文采用的平行擴展算法可以同時對節(jié)點進行擴展，計算出網(wǎng)絡(luò)圖中各*A節(jié)點到目標節(jié)點的最優(yōu)代價。其思路是這樣的: 當給定一個賦權(quán)網(wǎng)絡(luò)圖后，由任意節(jié)點經(jīng)若干條邊和若干個節(jié)點最終到達目標節(jié)點的最優(yōu)路線是存在且唯一的，所以由任意節(jié)點到日標節(jié)點的最優(yōu)路線的代價可以表示為該節(jié)點的函數(shù)，可簡單地認為是該節(jié)點的代價。由于這一路線必定是經(jīng)由該節(jié)點的某一相鄰節(jié)點的路線，因此如果令由節(jié)點s到目標節(jié)點的最優(yōu)路線代價為fs,即節(jié)點代價為fs,則fs可以通過計算連接相鄰節(jié)點的邊的代價與相鄰節(jié)點的代價和得到。如果令do(s,e)表示由節(jié)點s出發(fā)經(jīng)過邊e到達的節(jié)點，cost(s,e)為邊e的代價，則fs可定義為: 0 sGMin cost(s,e)+fdo(s,e) sG其中G代表目標節(jié)點的集合。這表明當節(jié)點s為目標節(jié)點時,由節(jié)點s到目標節(jié)點的最優(yōu)路線代價為0，否則就選取相鄰節(jié)點和連接相鄰節(jié)點的邊總和代價最小值作為該節(jié)點的代價。這樣，網(wǎng)絡(luò)圖中每一節(jié)點的代價均可由式(3-1)計算得到，而由該節(jié)點通往日標節(jié)點的最優(yōu)路線就可通過回溯過程依次選取若干節(jié)點的選擇策略來確定，即依次確定當前節(jié)點的后續(xù)途經(jīng)節(jié)點。這一選擇策略可由式(3-2)計算得到，表明由該節(jié)點通過特定邊到達某一相鄰節(jié)點的通路是最優(yōu)路線的組成部分5。 (3-2) argmincos ( , )( , )Policy st s ef do s e這種反向定義fs的方法是很有效的，可以從日標點開始計算并把所有節(jié)點的代價反向傳遞到該節(jié)點，就像波的傳播過程。為了避免把每一節(jié)點的計算單獨從這一傳遞過程中獨立出來，可采用以下方法:視每一個計算節(jié)點為單獨的單元，它的節(jié)點代價可按式(3-1)定義的得到，通過以下三步實現(xiàn)平行擴展:（1）初始化所有的節(jié)點代價為無窮，除目標節(jié)點為0;（2）通過搜索與每一節(jié)點相連的邊及通過這些邊可以到達的節(jié)點do(s,e)的代價 fdo(s ,e) 按式(3-1)的定義迭代計算每一節(jié)點的代價fs,同時該節(jié)點的選擇策略由式(3-2)得到。fs=(3-1)西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文14（3）重復第二步直至迭代過程結(jié)束。因為由每一節(jié)點到達目標點的最優(yōu)航路代價都是候選航路中代價最小的，故每一節(jié)點代價都存在一個最小值，而在這一迭代過程中每一節(jié)點的代價也將不斷地被更新直至收斂到這一最小值為止。當所有節(jié)點的代價收斂到它們的最小值時此算法將退出，各節(jié)點的代價及選擇策略將在這一計算過程中一并得到。隨后由起始點開始不斷采用各節(jié)點的選擇策略進行節(jié)點擴展，一條連接起始點和目標點的最優(yōu)路線就被搜索得到。下面，本文給出了迭代計算過程的偽代碼:1. 初始化所有節(jié)點的f、v: f、v 2. 目標節(jié)點：f、v 03. Do 在每一個節(jié)點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 在每一個節(jié)點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(節(jié)點全部循環(huán)完？) 其中，當各節(jié)點在迭代過程中不再發(fā)生變化時，布爾類型變量FixPoint?為真，否則為假。do(e).v為相鄰節(jié)點的f值。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文153.1.3 雙向算法*A普通的算法是從單向搜索的（即從目的地*A出發(fā)地，或者從出發(fā)地目的地） ，如果從兩個方向同時搜索，則相交出現(xiàn)比單向早。雙向的搜索算法與單項的搜索算法基本上是一致的，不同的是采用雙向搜索更新的方法。當從目標點和起始點同時出發(fā)后，同時按照代價函數(shù)的大小從小到大依次擴展節(jié)點。當他們有相交時，記錄下這一條路徑。同時如果其它從目標點出發(fā)的搜索路徑的最前端的節(jié)點代價函數(shù)值均大于這條路徑從目標點到交點的函數(shù)值，同時從起始點出發(fā)的也一樣，則這條路徑為最短路徑。具體的程序流程圖如圖3-1所示。 圖 3-1 雙向算法的流程圖*A3.2 現(xiàn)代航跡規(guī)劃算法這里將對幾種現(xiàn)代算法-遺傳算法，模擬退火算法，蟻群算法和粒子群算法進行了分析。開始結(jié)束同時從起始點和目標點開始搜索找代價函數(shù)最小的前端節(jié)點并擴展判讀是否有交點判斷是否結(jié)束NNYY西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文163.2.1 遺傳算法遺傳算法（Genetic Algorithm, GA）最先是由美國Michgan大學的John Holland于1975年提出的28。遺傳算法是具有“生成+檢測”的迭代過程的搜索算法29-30。它是一種種群型操作算法，該操作以群體中的所有個體為對象，如圖3-2所示。選擇（selection） 、交叉（crossover）和變異（mutation）是遺傳算法的三個主要操作算子。遺傳算法包含如下的6個基本要素31：（1）參數(shù)編碼：由于遺傳算法不能直接處理解空間的解數(shù)據(jù)，因此必須通過編碼將它們表示成遺傳空間的基因型結(jié)構(gòu)數(shù)據(jù)。所以必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是都是通過隨機方程產(chǎn)生的。 （2）適應(yīng)度評價檢測：遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用適應(yīng)度（fitness）值來評價個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。（3）選擇（selection）:選擇或復制操作是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。個體適應(yīng)度越高，其被選擇的機會就越多。本文采用與適應(yīng)度成比例的概率方法進行選擇。具體地說，就是首先計算群體中所有個體適應(yīng)度的總和，再計算每個個體的適應(yīng)度所占的比例，并以此作為相應(yīng)的選擇概率。 圖3-2 遺傳算法流程圖（4）交叉操作：交叉操作是遺傳算法中最主要的遺傳操作。簡單的交叉可以分兩步進行：先對種群中的個體進行隨機配對;然后在配對個體中隨機選取一個交叉段，彼此交換相應(yīng)的部分信息。開始結(jié)束編碼和種群生成種群適應(yīng)度評價選擇交叉變異種群是否收斂YN西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文17（5）變異操作：變異操作是按照位進行的，即 把某一位的內(nèi)容進行替換。變異操作同樣是隨機進行的。一般而言，變異的概率較小。變異操作是十分微妙的遺傳操作，它需要和交叉操作配合使用，目的是挖掘群體中個體的多樣性，克服有可能限于局部解的弊病。針對無人機路徑規(guī)劃的特殊性，我采用如下的編碼來實現(xiàn)無人機的遺傳算法航跡規(guī)劃：（1）染色體編碼和適應(yīng)度函數(shù)編碼是應(yīng)用遺傳算法時首先要解決的問題。編碼方法除了決定個體基因染色體排列形式外，它還決定了個體從搜索空間基因型變換到解空間表現(xiàn)型時的解碼方法，編碼方式也會影響到交叉算子、變異算子等遺傳算子的運算方式。編碼方式在很大程度上決定了如何進行群體的遺傳進化運算以及遺傳進化運算的效率。常用的遺傳算法編碼方式有三大類: 二進制編碼，浮點數(shù)編碼和符號編碼5。根據(jù)無人機的特點本文使用了符號編碼的方式。這個基因染色體表示無人機從出發(fā)點出發(fā)后依次經(jīng)過若干中間點后最終到達目標點，因而航路對應(yīng)的基因編碼可采用因而航路對應(yīng)的基因編碼可采用最自然、最簡單的表示方法路徑表示法。例如無人機的飛行航路為：由出發(fā)點1，路經(jīng)中間點2，中間點3，中間點4，中間點5，路經(jīng)中間點6，最后到達目標點7，此時航路可以表示為2，3，4，5，6。由于點1，7分別是相應(yīng)的起點和終點，在任何的基因染色體中都是一樣的，所以在航路中不再列出。由于本文要討論的是從起始點到目標點的最短路徑問題，基因染色體采用如下的編碼方式：1V2ViVnV圖3-2 基因染色體編碼如上圖所示，基因染色體所表示的航路為， 。根1V2ViVnV據(jù)2.2.1節(jié)對無人機的活動區(qū)間網(wǎng)格化處理了之后，假設(shè)產(chǎn)生了N個節(jié)點。則無人機的最短路徑最多由（N-2）個節(jié)點組成（除開起始點和目標點） ，所以染色西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文18體中的基因的個數(shù)最多為（N-2）個，即染色體的維數(shù)為（N-2）維。但是在實際運算中最短路徑很難達到（N-2）維，即最短路徑僅經(jīng)過較少的幾個節(jié)點就到達了目標點。這樣我們就有必要定義基因染色體的有效長度。在本文中，基因染色體的有效長度指無人機從起始點開始，依次按照基因染色體從左到右順序經(jīng)過數(shù)個中間節(jié)點（注意不是染色體中的所有節(jié)點） ，最終到達目標點的最短路徑中的中間節(jié)點的個數(shù)，如下圖所示。起始點 1中 間節(jié)點2中 間節(jié)點5中 間節(jié)點4中 間節(jié)點3中 間節(jié)點6中 間節(jié)點7中 間節(jié)點8目標點 118765432基因染色體圖3-3 基因染色體的有效長度示意圖在圖3-3中，包括起始點和目標點在內(nèi)共有9個點，所以染色體的維數(shù)定為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西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文19的路徑。假設(shè)最短的路徑編號為6，這個染色體的有效長度為5（即僅中間點2，中間點3，中間點4，中間點5，中間點6為有效節(jié)點，中間節(jié)點7為無效節(jié)點） ，這個染色體的適應(yīng)度函數(shù)值為編號為6的代價和。（2）遺傳算法的初始化由于采用了符號編碼，初始種群的生成就受到了限制。首先，生成1到N共N個數(shù)（假設(shè)節(jié)點數(shù)為N）,然后從中間除去起始點和目標點，剩下N-2個數(shù)。把這N-2個數(shù)打亂順序后隨機的放入（N-2）維的基因中間去。這樣就生成了一個初始基因種群。以此類推，隨機生成與種群規(guī)模相當?shù)幕驍?shù)目。（3）交叉為了保證基因的完整性，本文使用特殊的交叉方式。隨機配對后，對于每個對子分別指定父代parent1和parent2。選取父代parent1為主交叉染色體，隨機的產(chǎn)生兩個數(shù)（1到N-2之間的整數(shù)，如果兩個數(shù)相等則不用交叉） ，這兩個數(shù)之間的基因片段將預備進行交叉。首先為了保證交叉有意義，交叉基因片段的兩個交叉點至少應(yīng)該保證有一個在基因染色體的有效長度之內(nèi)。 5V6V1V2V3V8V7V4V6V1V2V3V8V7V4V5V5V5V6V6V4V要交叉的基因片要交叉的基因片主交叉輔交叉4V圖3-4 主交叉染色體示意圖（陰影表示有效基因）如上圖所示，產(chǎn)生的兩個隨機數(shù)為4和6，其中4在基因染色體的有效長度5之內(nèi)。則要交叉的基因片段為 。456,V V V選取父代parent2為輔交叉染色體，根據(jù)parent1產(chǎn)生的要交叉的基因片段，尋找到父代parent2中間的相應(yīng)部分，并保留原先的順序 ，如下圖所645,V V V示。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文205V6V1V2V3V8V7V4V6V1V2V3V8V7V4V5V5V5V6V6V4V要交叉的基因片要交叉的基因片主交叉輔交叉4V圖3-5 輔交叉染色體示意圖（陰影表示有效基因）互換要交叉的基因片段，保留基因的原來順序，互換后新的基因分別插入原先抽取的基因的位置，交叉之后的兩基因如圖3-6所示。最后要重新計算染色體基因的有效長度和適應(yīng)度函數(shù)值。（4）變異為了保證基因的完整性，本文使用特殊的變異方式。對于任意染色體，產(chǎn)生一個0到1的隨機數(shù)，如果大于變異的概率則進行變異，否則不進行變異。6V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V1V3V5V5V4V6V7V8V1V6V3V4V5V7V7V8V主交叉輔交叉變異之前的染色體變異之后的染色體圖3-6 交叉之后染色體示意圖（此時陰影已經(jīng)失去了意義）如果進行變異，對于父代parent隨機產(chǎn)生兩個數(shù)（在1到N-2之間的整數(shù)，如果兩個數(shù)相等則不用交叉）分別作為變異點1，2。同樣要保證變異點1，2至少有一個在基因染色體的有效長度之內(nèi)。取抽取點為變異點1，變異點2之中的較小值；取插入點為變異點1，變異點2之中的較大值。然后，抽出抽取點處的基因，插入到插入點之后，中間的基因依次前移，具體操作如下圖所示。西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文216V1V2V3V8V7V4V5V6V1V2V3V8V7V4V5V1V3V5V5V4V6V7V8V1V6V3V4V5V7V7V8V主交叉輔交叉變異之前的染色體變異之后的染色體圖3-7 染色體變異示意圖（此時陰影已經(jīng)失去了意義）如上圖所示，產(chǎn)生的兩個隨機數(shù)為2和6。則第2個基因移到第6個基因處，原先的第2，3，4，5個基因依次前移。最后要重新計算染色體基因的有效長度和適應(yīng)度函數(shù)值。（5）選擇選擇將決定哪一個基因可以進入下一代。本文采用了賭輪盤選擇法選擇，進入下一代的可能性與適應(yīng)度函數(shù)值成正比。得到如下遺傳算法偽代碼。1. 生成初始種群2. Do 3.種群配對4. 染色體交叉5.染色體變異6. 選擇進入下一代7. until (種群收斂？)3.2.2 模擬退火算法模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e-E/(k*T)，其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文西北工業(yè)大學明德學院本科畢業(yè)設(shè)計論文22化問題的模擬退火算法。模擬退火算法與傳統(tǒng)的算法相比，它與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L (2) 對k=1，L做第(3)至第6步： (3) 產(chǎn)生新解S (4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數(shù)。 (5) 若t0，然后轉(zhuǎn)第2步。模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： 第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由