無人機航跡算法綜述

為促進航跡規(guī)劃技術(shù)的發(fā)展,對航跡規(guī)劃常用算法進行綜述。首先對航跡規(guī)劃的規(guī)劃思想和構(gòu)成進行分析；其次將航跡規(guī)劃算法分為傳統(tǒng)經(jīng)典算法和現(xiàn)代兩大類,對其中幾種常用算法進行分析總結(jié)；最后闡述現(xiàn)代智能算法在航跡規(guī)劃應(yīng)用隨著航空技術(shù)日益發(fā)展,越來越多的無人機被用于替代飛行員執(zhí)行一些高危險、高強度或大范圍巡檢、搜救任務(wù),因此完善的任務(wù)規(guī)劃系統(tǒng)是無人機順利完成任務(wù)的重要保障。任務(wù)規(guī)劃系統(tǒng)一般由航跡規(guī)劃、導(dǎo)航、數(shù)據(jù)通信3大子系統(tǒng)組成,而航跡無人機航跡規(guī)劃就是在綜合考慮無人機到達時間、油耗、威脅因素的前提下,為無人機規(guī)劃出最優(yōu)或滿意的飛行航跡,以保證圓滿地完成飛行任務(wù)[1]。無論是在軍事還是民用領(lǐng)域,好的航跡規(guī)劃系統(tǒng)都是提高無人機安全性能,保證無人機出色完成任務(wù)的重要手段。筆者將在對航跡規(guī)劃問題進行分析的基礎(chǔ)上,對當(dāng)前幾種常用航跡規(guī)劃算法進行分類總結(jié),最后指出目前研究熱點及未來發(fā)展趨勢。在不考慮時間因素的情況下,無人機航跡規(guī)劃應(yīng)該是在三維空間中進行的,但在一些任務(wù)中,無人機保持在固定高度飛行,不需要考慮高度變化問題。因此在進行航跡規(guī)劃時可以將三維空間中的物體投影到二維平面,從而將三維航跡規(guī)劃問題降至二維,簡化問題的復(fù)雜度。但在軍事突防、電力巡線、山地救援等應(yīng)用中,二維航跡規(guī)航跡規(guī)劃問題是一個包含多個優(yōu)化目標(biāo)和多個約束的非線性規(guī)劃問題[2],其核心就是建立目標(biāo)函數(shù)的數(shù)學(xué)模型和有效地處理各項約束。由于涉及約束條件較多,目標(biāo)函數(shù)復(fù)雜,數(shù)學(xué)模型建立困難,為降低問題復(fù)雜性,目前大多數(shù)學(xué)者都采用分層規(guī)劃的思想,將航跡規(guī)劃分為兩步進行。首先根據(jù)已知的環(huán)境信息、任務(wù)要求等在無人機起飛前為其規(guī)劃出一條滿足約束條件的全局最優(yōu)參考航跡。無人機在行的過程中,當(dāng)出現(xiàn)未知或動態(tài)威脅信息時,再進行局部航跡動態(tài)優(yōu)化。由于全局參考航跡規(guī)劃需要考慮整體的優(yōu)化,因此要在避免陷入局部最優(yōu)的情況下盡量減少計算量。而局部航跡動態(tài)優(yōu)化用于應(yīng)對突發(fā)威脅,因此要盡量縮短規(guī)劃時間以確保實時無人機航跡規(guī)劃一般由以下幾個部分組成：描述規(guī)劃空間,選擇航跡的表示形式,分析約束條件,確定代價函數(shù),選取航跡搜索算法和航跡平滑。1)描述規(guī)劃空間。其目的是建立一個便于計算機進行航跡規(guī)劃所使用型,即將實際的物理空間抽象成算法能處理的抽象空間,實現(xiàn)相互間的映射。規(guī)劃空間的表示是否合理直接影響規(guī)劃的效率和結(jié)果的優(yōu)劣性。一種好的規(guī)劃應(yīng)能滿足如下要求:①規(guī)劃空間能合理且盡量完善地反映飛行環(huán)境中的各種信息(地形、威脅、障礙等),以利于航跡搜索；②當(dāng)飛行環(huán)境中的某些信息發(fā)生變化時能實時地進行更新,以滿足實時應(yīng)用的要③能滿足無人機自身性能約束條件,包括最大拐彎角、最大爬升/俯沖角、最大常用的規(guī)劃空間表示方法有柵格法和圖形法。柵格法簡單的單元,并為每個單元分配一個代價值,對應(yīng)于無人機經(jīng)過空間相應(yīng)區(qū)域的代價,并判斷這些單元之間是否存在可行路徑,找到包含起始點和目標(biāo)點的單元,從起始單元開始,依次向柵格中代價最小的鄰域移動,最后到達目標(biāo)單元[3]。航跡搜索算法中式存儲,所以多數(shù)的航跡規(guī)劃研究都是使用柵格法表示規(guī)劃空間。圖形法首先根據(jù)一定規(guī)則將規(guī)劃空間表示成一個由一維線段構(gòu)成的網(wǎng)絡(luò)圖,然后采用某一搜索算法在該網(wǎng)絡(luò)圖上進行搜索。使用圖形法必須表示出所有可能的路徑,否則就可能丟失最優(yōu)法[4]、可視圖法(VisibilityGraph)[5]、隨機路標(biāo)圖法(PRM：2)航跡表示。其形式有兩種：一種是基于無人機滑航跡,采用此種表示方法可以省去最后的航跡平滑環(huán)節(jié)；另一種是用航跡點表示,②將復(fù)雜的航跡規(guī)劃問題分解為一組統(tǒng)一形式的小規(guī)模子問題,對于每個子問題,只需關(guān)心一個點的坐標(biāo),從而將考察航跡是否可行變?yōu)閮H考察一個點或一條直線3)分析約束條件。航跡規(guī)劃問題需要考慮的約束條件包括環(huán)境約束、任務(wù)約束和無人機自身性能約束。環(huán)境約束有威脅約束(如被敵方雷達發(fā)現(xiàn)概率、敵方導(dǎo)彈高炮擊落概率、撞地概率等)、禁飛區(qū)約束、復(fù)雜氣象區(qū)約束等；任務(wù)約束有任務(wù)完成時間、起始點、目標(biāo)點、固定航向角、低空/超低空突防等；無人機自身性能約束有最大/最小平飛速度、最大航程、最高/最低飛行高度、水平最小轉(zhuǎn)彎半徑、最大爬升角/俯沖角、最大縱向曲率、最大法向過載等[7]。若是進行二維航跡規(guī)劃,則不需4)確定代價函數(shù)。代價函數(shù)將算法與實際物理問題緊密聯(lián)系在一起。對于無人機航跡規(guī)劃,代價函數(shù)是評價航跡優(yōu)劣的標(biāo)準(zhǔn),代價值越小則表明航跡越優(yōu),反之表明航跡越差。確定代價函數(shù)需要綜合考慮影響航跡性能的各項因素,對各個指標(biāo)進行量化和計算。三維航跡規(guī)劃的代價函數(shù)通常包含航跡長度代價、威脅代價和高度代價,其中J為航跡總代價,L為航跡長度代價,一些文獻也稱其為燃油代價,T為威脅代價,H為高度代價；ω1、ω2、ω3為相應(yīng)的權(quán)系數(shù),根據(jù)任務(wù)需要設(shè)置其值。二維5)選取搜索算法。根據(jù)任務(wù)需求選取合適的算法規(guī)劃出滿足約束條件、規(guī)避障6)航跡平滑。通過相應(yīng)算法搜索出的航跡對于無人機實際飛行而言并不一定可行,例如規(guī)劃出的航跡拐彎點較多,而無人機在實際飛行中由于自身機動限制不能頻繁轉(zhuǎn)彎,因此需要對規(guī)劃出的航跡進行平滑處理,消除不必要的拐彎點以利于無人機實際飛行。常用航跡平滑方法有三次樣條插值法[8]、貝塞爾曲線(BezierCurve)[9]、k-trajectory算法[10]等。無人機航跡規(guī)劃的本質(zhì)是路徑規(guī)劃,即尋找適當(dāng)?shù)牟呗詷?gòu)成連接起點到終點位置的由序列點或曲線組成的路徑,因此用于航跡規(guī)劃的算法實際上也就是路徑規(guī)劃算法。路徑規(guī)劃算法有很多,每種算法都有其自身的優(yōu)缺點和適用范圍,按照規(guī)劃決策可以將算法分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法[11]兩類。2.1傳統(tǒng)經(jīng)典算法近年來常用于航跡規(guī)劃的傳統(tǒng)經(jīng)典算法有Dijkstra算法、人工勢場法(APF：ArtificialPotentialField)和模擬退火算法(SAA:SimulatedAnnealingAlgorithm)。Dijkstra算法是圖論中求解最短路徑的經(jīng)典算法,適用于每條邊的權(quán)數(shù)為非負的情況,能得到從指定頂點到其他任意頂點的最短路徑。使用Dijkstra算法進行航跡規(guī)劃,構(gòu)建的賦權(quán)圖的頂點代表航跡點,賦權(quán)圖的邊代表所有可行航跡,Dijkstra算法的作用就是在這些可行航跡里找到最優(yōu)航跡。Dijkstra算法實現(xiàn)簡單,但其運算時間和所用內(nèi)存與搜索空間中節(jié)點個數(shù)平方成正比,在大范圍高維空間中搜索時間長,對內(nèi)存要求也很高,因此多用于二維靜態(tài)航跡規(guī)劃[12,13]。由于航跡規(guī)劃空間范圍大,對于Dijkstra算法在航跡規(guī)劃中的應(yīng)用,如何選取有效航跡點,減少航跡點數(shù)量,縮短規(guī)劃時間是問題的關(guān)鍵。文獻[12]在Voronoi圖的基礎(chǔ)上使用Dijkstra算法尋找最優(yōu)航跡,將威脅看作一個點,選取各威脅點之間連線的中垂線的交點為航跡點。這種方法能保證航跡最大化避開各個威脅,安全性高,但航跡較長。并且沒有考慮無人機最大轉(zhuǎn)彎角約束,航跡不一定可飛。文獻[13]在可視圖的基礎(chǔ)上使用Dijkstra算法尋找最短航跡,將多邊形障礙的各個頂點看作航跡點,并建立轉(zhuǎn)彎角約束機制。這種方法得到的航跡短,滿足無人機最大轉(zhuǎn)彎角約束,但由于航跡貼近障礙物,安全性較低。此外,可視圖不能表達物體運動的方向性約束的缺陷導(dǎo)致Dijkstra算法在搜索時可能找不到路徑。雖然Dijkstra算法多用于二維航跡規(guī)劃,但也有學(xué)者將其應(yīng)用于三維航跡規(guī)劃。文獻[14]將飛行空間映射到由若干個四面體作為航跡點,所有相鄰四面體內(nèi)切球中心點的連線構(gòu)成一個三維網(wǎng)絡(luò),這個三維網(wǎng)絡(luò)就是所有可行航跡。然后用Dijkstra算法在這個三維網(wǎng)絡(luò)上尋找最短航跡。最后用似,規(guī)劃出的航跡能最大化避開威脅,安全性高,但航跡相對較長。目前使用Dijkstra基礎(chǔ)上利用Dijkstra算法尋找最短航跡,但得到的航跡若安全性高則航跡長,若航跡短則安全性低,沒有在航跡長度與安全性之間尋找到一個好的平衡。人工勢場法是一種模擬電勢場分布的規(guī)劃方法,任務(wù)區(qū)域內(nèi)的目標(biāo)點產(chǎn)生引力場,威脅源產(chǎn)生斥力場,無人機在引力和斥力的共同作用下向目標(biāo)點運動。傳統(tǒng)人工(3)(4)其中Katt和Krep分別為引力和斥力增益系數(shù),且均為正常數(shù)；ρ(X,XG)為航跡Fatt=-Uatt(X)=-Kattρ(X,XG)(5)總勢場力為目標(biāo)點產(chǎn)生的引力和各個威脅源Ftotal=Fatt+∑Frep(7)人工勢場法的優(yōu)點是算法簡明、實時性好、規(guī)劃速度快,在局部規(guī)劃和實時規(guī)劃領(lǐng)域應(yīng)用廣泛。缺點是當(dāng)無人機離目標(biāo)點比較遠,Fatt?Frep時,合力方向更趨近目標(biāo)點方向,無人機可能會進入威脅區(qū)；當(dāng)目標(biāo)點附近有威脅源時,斥力將會非常大,而引力相對較小,無人機將很難到達目標(biāo)點；在復(fù)雜環(huán)境中,容易產(chǎn)生局部極小值,使算法停滯或震動；在障礙物附近有抖動現(xiàn)象,在狹窄通道間頻繁擺動；在動態(tài)環(huán)境下規(guī)劃效果減弱；計算勢場負梯度的方法因為沒有優(yōu)化變量,將航跡規(guī)劃問題轉(zhuǎn)換成了非優(yōu)化問題,因此缺乏評價指標(biāo)衡量航跡的優(yōu)劣,勢場的建立直接決定了航跡的質(zhì)量,相同的環(huán)境下,不同的勢場形式也可能得到不同的航跡。針對該問題,學(xué)者們結(jié)合無人機航跡規(guī)劃的特點提出了多種改進方法。文獻[15]在斥力勢函數(shù)中加入無人機與目標(biāo)點的距離,減小斥力,改善障礙物在目標(biāo)附近時,目標(biāo)不可達的問題。設(shè)置引導(dǎo)點為無人機提供方向隨機的勢場力,解決局部極小值和震蕩問題。文獻[16]在人工勢場法搜索陷入威脅區(qū)時,構(gòu)造懲罰勢函數(shù)替代斥力勢函數(shù),并使用模擬退火算法取代虛擬力引導(dǎo)的方法搜索逃離位置,有效避免了局部極小值和抖動現(xiàn)象,得到的航跡能成功避開威脅,但增大了計算量,降低了人工勢場法的實時性。文獻[17]通過引入相對速度斥力勢場和斥力增益模糊控制器實現(xiàn)人工勢場法的動態(tài)避障,避免局部極小值。文獻[18]通過增加高度調(diào)節(jié)引力勢函數(shù)以增強人工勢場法在三維航跡規(guī)劃中對高度的控制,同時引入飛行器的動力學(xué)約束條件,使航跡更具可飛性,并改善了人工勢場法的局部極小值、障礙物附近抖動、狹窄通道間頻繁擺動等缺點。然而文獻[15-18]中均未衡量航跡優(yōu)劣的評價指標(biāo),對此文獻[19]引入附加控制力作為優(yōu)化變量,通過優(yōu)化出適當(dāng)?shù)母郊涌刂屏?使無人機在滿足各種物理約束的條件下,規(guī)劃出的航跡可使代價指標(biāo)最優(yōu),降低了勢場建立的任意性對航跡結(jié)果的影響。但文獻[19]在考慮無人機動力學(xué)模型時將無人機看作質(zhì)點,與實際動力學(xué)模型有一定差異。總之,對于極小值等問題,前人提出的各種改進方法都在一定程度上彌補甚至消除了這些缺陷,但對于模擬退火算法是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索算法固體物質(zhì)的退火過程,在某一初始溫度下,伴隨溫度控制參數(shù)按照降溫函數(shù)不斷下降,結(jié)合概率的突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解,即能概率性地跳出制,包括溫度控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)和終止條件。模擬退火算法的優(yōu)點是算法求得的解與初始解狀態(tài)無關(guān),具有漸近收斂性,是一新解的變換方法和冷卻進度表的設(shè)計。在航跡規(guī)劃中,模擬退火算法的一個解代表一條航跡,目標(biāo)函數(shù)則是代價函數(shù),常用于求解二維航跡規(guī)劃中的TSP問題[20],但該算法多數(shù)沒有考慮無人機的機動性能約束,得到的航跡可飛性不高。模擬退火算法也可與易陷入局部最優(yōu)解的算法相結(jié)合幫助其跳出局部最優(yōu)找到全局最優(yōu)解,如遺傳模擬退火算法[21],在交叉和變異過程中使用Metropolis準(zhǔn)則判斷是否接受新解,當(dāng)然,2.2現(xiàn)代智能算法相較于傳統(tǒng)經(jīng)典算法,現(xiàn)代智能算法的應(yīng)用更為廣泛。在航跡規(guī)劃中常用的現(xiàn)代A*算法是一種智能啟發(fā)式搜索算法,它將搜索空間表示為網(wǎng)格的形式,以網(wǎng)格的中心點或頂點作為航跡點,通過搜索鄰域內(nèi)代價函數(shù)值最小的航跡點,從起始點逐步搜索到目標(biāo)點,最后逆向回溯當(dāng)前節(jié)點的父節(jié)點生成最優(yōu)航跡,其中待擴展航跡節(jié)點f(x)=g(x)+h(x)(8)其中g(shù)(x)表示從起始點到當(dāng)前節(jié)點的實際代價,h(x)稱為啟發(fā)函數(shù),表示從當(dāng)前節(jié)點到目標(biāo)點的估算代價,常用的啟發(fā)函數(shù)可選用歐氏距離、曼哈頓距離、對角線距離等。啟發(fā)函數(shù)是A*算法的核心,它能在搜索效率和最優(yōu)解之間權(quán)衡。若h(x)小于從當(dāng)前節(jié)點到目標(biāo)點的實際代價,則搜索得到最優(yōu)路徑,但這時搜索節(jié)點增多,搜索效率降低；若h(x)一直等于從當(dāng)前節(jié)點到目標(biāo)點的實際代價,此時A*嚴格按照最優(yōu)路徑搜索,搜索效率最高；若h(x)大于從當(dāng)前節(jié)點到目標(biāo)點的實際代價,則搜索結(jié)果可索效率,當(dāng)路徑很長時,這種影響會更明顯。總之,啟發(fā)函數(shù)的選擇決定了A*算法是否搜索空間增大,A*算法的計算量會呈指數(shù)增長,導(dǎo)致規(guī)劃時間過長,一般用于靜態(tài)航跡規(guī)劃。在航跡規(guī)劃中,如何提高A*算法的運行速度并得到最優(yōu)航跡是學(xué)者們重點考慮的問題。文獻[7]采用結(jié)構(gòu)體式最小二叉堆和三層嵌套的二叉堆技術(shù)分別維護管理找的高效率,較大幅度提高了A*算法的規(guī)劃效率。文獻[22]提出使用2.5維網(wǎng)格模型描述三維規(guī)劃空間,每個網(wǎng)格點包含經(jīng)度、緯度和高程信息,此方法計算效率要遠大于三維網(wǎng)格劃分方式。文獻[23]將三維航跡規(guī)劃分解為二維規(guī)劃和高度規(guī)劃,使用動再由二維航跡結(jié)合高程數(shù)字地圖,利用粒子沉降法賦予每個航跡點高度信息,生成三維航跡。這種方法有效地將三維空間的搜索節(jié)點刪減至二維,大大減少了搜索節(jié)點數(shù)離、曼哈頓距離和對角線距離,但仍不是最優(yōu)航跡。由于航跡規(guī)劃問題的復(fù)雜性,雖然學(xué)者們通過各種改進方法提高了A*算法的搜索效率,但仍沒有找到值恒等于從當(dāng)前遺傳算法的基本思想是模擬生物遺傳進化過程,根據(jù)“適者生存”、“優(yōu)勝劣汰”的原則,借助選擇、交叉、變異等操作,使所要解決的問題從初始解一步步逼近最優(yōu)解。在航跡規(guī)劃中,遺傳算法每條染色體(個體)代表無人機的一條航跡,基因的編碼方式也就是航跡節(jié)點的編碼方式,適應(yīng)度函數(shù)由代價函數(shù)變化而來。遺傳算法的優(yōu)點是不要求優(yōu)化函數(shù)具備連續(xù)、可導(dǎo)和單峰等條件,具有較強的魯棒性,是一種高效、并行、全局的搜索方法,適用于三維全局航跡規(guī)劃。缺點是種群失去多樣性而導(dǎo)致早熟收斂,尋優(yōu)時間長,局部搜索能力差等。針對該問題,學(xué)者們提出了不同的改進方法,如引入量子、自適應(yīng)等因子,但這些改進方法仍然存在較多不足。文獻[24]針對量子遺傳算法初始種群的單一性,引入關(guān)于概率劃分的小生境協(xié)同進化策略,并對各種群采用動態(tài)量子旋轉(zhuǎn)角；采用精英選擇機制,保留每一代中的最優(yōu)個體,并借鑒狼群分配原則對種群進行更新。該方法提高了量子遺傳算法的穩(wěn)定性和尋優(yōu)精度,但在收斂速度上沒有改善,且沒有考慮無人機自身性能約束。文獻[25]使用并行遺傳算法結(jié)合概率地圖實現(xiàn)多無人機協(xié)同航跡規(guī)劃,并行遺傳算法很好地克服了遺傳算法早熟的缺陷,但文獻同樣沒有考慮無人機自身性能約束。文獻[26]通過在遺傳算法主種群上附加一個病毒種群的方法,保證可行引導(dǎo)段的有效積累并維持種群多樣性。采用定長實值和變長實值兩種編碼方式分別為染色體和病毒個體編碼,通過采用反轉(zhuǎn)錄和轉(zhuǎn)導(dǎo)這兩種病毒感染操作實現(xiàn)兩個種群間模塊的信息交換,使進化信息在種群內(nèi)迅速、定向地傳播,消除了尋優(yōu)過程的盲目性。該方法改善了遺傳算法早熟和局部收斂慢的問題,提高了收斂速度,但對于搜索精度幾乎沒有提高。文獻[27]提出多頻振動遺傳算法,在遺傳操作中使用兩次變異操作,分別作用于整個種群和精英個體,為種群提供全局多樣性和局部多樣性,從而有效避免早熟,提高搜索精度,達到快速收斂的目蟻群優(yōu)化算法模擬螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為特性,利用信息素濃度(9)叫啟發(fā)函數(shù),它可以是距離開銷,也可以是距離開銷與其它開銷的組合,如高度、安全度等；α、β為τab與ηab的相對重要性的權(quán)值；為節(jié)點a的所有相鄰節(jié)點信息素具有揮發(fā)性,隨著時間的增加其濃度會降低。信息素的更新分為局部更新和全局更新,局部信息素更新是用在螞蟻完成一個航跡點的選擇時,相應(yīng)的減少該點的信息素,降低此點對后來螞蟻的吸引程度,從而增加螞蟻的探尋范圍,減小算法陷入τab(t+1)=ξτab(t)(10)其中ξ為信息素減少因子,用于控制信息素減少的大小。全局信息素更新是經(jīng)過m時刻,當(dāng)螞蟻完成尋路任務(wù)后對其經(jīng)過的所有航跡點上的信息素這種方式增加這條航路上的信息素,其表達式為τab(t+m)=(1-ρ)τab(t)+ρΔτab(11)Δτab=Q/J(12)蟻群優(yōu)化算法的優(yōu)點是具有良好的并行性、協(xié)作性和魯棒性,后期收斂速度快。缺點是前期搜索時間長,參數(shù)多并且解的質(zhì)量受參數(shù)影響大,容易陷入局部最優(yōu)解,適用于三維全局航跡規(guī)劃。由于信息素的分布情況、揮發(fā)方式和螞蟻選擇前盲目性影響著解的質(zhì)量和獲得解的時間,學(xué)者們也通常從這幾個方面,結(jié)合航跡規(guī)劃的特性對蟻群算法進行改進。文獻[28]將螞蟻按數(shù)量均勻分組,并在信息素濃度更新過程中使用差分進化算法的交叉、變異、選擇操作,合理分配各路徑上螞蟻留下的信息素,避免某條路徑上信息素累積過多而導(dǎo)致陷入局部最優(yōu)解,從而引導(dǎo)螞蟻找到最優(yōu)路徑。該混合算法在保證基本蟻群算法優(yōu)點的同時提高了全局收斂的速度,但得到的航跡過長。文獻[29]提出一種文化蟻群算法,設(shè)計了由蟻群算法演化的群體空間和由群體空間最優(yōu)解構(gòu)成的信仰空間,兩個空間同時演化,彼此促進。在群體空間中加入懲獎機制,對到達終點的螞蟻走過的路徑,提高其信息素濃度,反之,則降低,從而提行更新。此外,文獻在啟發(fā)式函數(shù)中加入了航路點的方差,計算待選節(jié)點和其前面n個點的方差,使選出的節(jié)點與前面節(jié)點的波動相對較小,從而獲得更平滑的航跡。該方法的雙層進化模型加快了航跡的搜索速度,但懲獎機制的評判標(biāo)準(zhǔn)單一,到達終點的螞蟻走過的路徑并不一定就好,此機制可能會降低解的質(zhì)量。文獻[30]首先限制信息素揮發(fā)因子的范圍,防止其過大或過小影響算法的全局搜索能力,并在信息素調(diào)整規(guī)則中引入航跡評價指標(biāo),提高解的質(zhì)量。然后將起始點和目標(biāo)點之間的連線這一最短航跡信息反饋到系統(tǒng)中作為搜索的指導(dǎo)信號,將能見度改進為當(dāng)前節(jié)點與待擴展節(jié)點的距離和待擴展節(jié)點到最短航線的垂直距離加權(quán)和的倒數(shù),降低算法尋找航跡的盲目性,加快了搜索效率。最后在該能見度的基礎(chǔ)上,將轉(zhuǎn)移概率與一個0～1之間的隨機數(shù)相乘,選擇鄰域中轉(zhuǎn)移概率最大的節(jié)點擴展。該方法在保證基本蟻群算法優(yōu)點的同時提高了解的質(zhì)量,大大縮短了搜索時間。粒子群優(yōu)化算法模擬鳥群飛行捕食行為,把每個粒子看作優(yōu)化問題的一個可行解,并將其延伸到N維空間,每個粒子主要通過跟蹤兩個位置決定自己下一步的飛行,一個是粒子本身所找到的最優(yōu)解Pbest,即個體最好位置；另一個是種群中所有粒子當(dāng)前找到的最優(yōu)解Gbest,即全局最好位置,最終群體成員逐漸移入問題空間的更好區(qū)域。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值,每個粒子還有一個決定其飛行方向和距離的速度。粒子群算法的速度和位置vij(k+1)=ωvij(k)+c1r1(pij(k)-xij(k))+c2r2(gij(k)-xij(k))(13)xij(k+1)=xij(k)+vij(k)(14)其中下標(biāo)i、j、k分別表示第i個粒子,第j維空間,第k代粒子；ω為慣性權(quán)重,描述了粒子對之前速度的“繼承”；c1、c2為常數(shù),稱為學(xué)習(xí)因子,體現(xiàn)了粒子向全局最優(yōu)粒子學(xué)習(xí)的特性；r1、r2為(0,1)之間的隨機數(shù)。與其他進化算法相比,粒子群算法具有兩個顯著的不同特點。一是沒有“優(yōu)勝劣汰”的機制,所有的粒子在迭代過程中始終作為種群的成員保留；二是沒有交叉、變異等進化算子,每個粒子通過追隨當(dāng)前搜索到的最優(yōu)值尋找全局最優(yōu)。粒子群算法的優(yōu)點是具有較強的魯棒性,對種群大小敏感性不高,參數(shù)少,前期收斂速度快,缺點是后期收斂速度慢,容易早熟陷入局部最優(yōu)解,可用于三維全局航跡規(guī)劃。在航跡規(guī)劃中學(xué)者們對粒子群算法的改進也多是通過提高種群的多樣性避免局部最的基礎(chǔ)上引入繁殖機制,整個種群中粒子位置更新后不直接進入下一代,而是以一定概率將粒子放入繁殖池,種群中最優(yōu)個體不參與繁殖操作,以便保護其不被破壞。該度慢的問題,該方法能得到質(zhì)量更好的航跡。3.1現(xiàn)代智能算法的改進這將要消耗大量的時間,而實際應(yīng)用往往要求航跡規(guī)劃系統(tǒng)能快速響應(yīng),遠遠超出規(guī)定時間得到的航跡即便再優(yōu)也不具有任何意義。因此,保證在規(guī)定時間內(nèi)規(guī)劃出可行且盡量接近理論最優(yōu)航跡的規(guī)劃方法更具有現(xiàn)實意義。而實現(xiàn)這一