無(wú)人機(jī)自主飛行航跡規(guī)劃算法研究

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