1、無人機航跡算法綜述為促進航跡規劃技術的發展，對航跡規劃常用算法進行綜述。首先對航跡規劃的 規劃思想和構成進行分析；其次將航跡規劃算法分為傳統經典算法和現代智能算法 兩大類，對其中幾種常用算法進行分析總結；最后闡述現代智能算法在航跡規劃應用 中的改進、多重算法的融合改進以及多無人機四維航跡規劃算法研究3個研究熱點 及未來發展趨勢。隨著航空技術日益發展,越來越多的無人機被用于替代飛行員執行一些高危險、 高強度或大范圍巡檢、搜救任務，因此完善的任務規劃系統是無人機順利完成任務的 重要保障。任務規劃系統一般由航跡規劃、導航、數據通信3大子系統組成，而航跡 規劃則是任務規劃系統的核心部分。無人機航跡規劃

2、就是在綜合考慮無人機到達時間、油耗、威脅以及飛行區域等 因素的前提下，為無人機規劃出最優或滿意的飛行航跡，以保證圓滿地完成飛行任務 1。無論是在軍事還是民用領域，好的航跡規劃系統都是提高無人機安全性能，保證 無人機出色完成任務的重要手段。筆者將在對航跡規劃問題進行分析的基礎上，對當 前幾種常用航跡規劃算法進行分類總結，最后指出目前研究熱點及未來發展趨勢。1航跡規劃問題分析在不考慮時間因素的情況下，無人機航跡規劃應該是在三維空間中進行的，但在 一些任務中，無人機保持在固定高度飛行，不需要考慮高度變化問題。因此在進行航 跡規劃時可以將三維空間中的物體投影到二維平面，從而將三維航跡規劃問題降至二 維

3、，簡化問題的復雜度。但在軍事突防、電力巡線、山地救援等應用中，二維航跡規 劃實用價值有限。筆者將從規劃思想和構成兩方面對航跡規劃問題進行分析。1.1規劃思想航跡規劃問題是一個包含多個優化目標和多個約束的非線性規劃問題2,其核 心就是建立目標函數的數學模型和有效地處理各項約束。由于涉及約束條件較多，目 標函數復雜,數學模型建立困難,為降低問題復雜性，目前大多數學者都采用分層規劃 的思想，將航跡規劃分為兩步進行。首先根據已知的環境信息、任務要求等在無人機 起飛前為其規劃出一條滿足約束條件的全局最優參考航跡。無人機在按照此航跡飛 行的過程中，當出現未知或動態威脅信息時，再進行局部航跡動態優化。由于全

4、局參 考航跡規劃需要考慮整體的優化，因此要在避免陷入局部最優的情況下盡量減少計算 量。而局部航跡動態優化用于應對突發威脅，因此要盡量縮短規劃時間以確保實時 性。1.2規劃構成無人機航跡規劃一般由以下幾個部分組成：描述規劃空間，選擇航跡的表示形 式，分析約束條件,確定代價函數，選取航跡搜索算法和航跡平滑。1）描述規劃空間。其目的是建立一個便于計算機進行航跡規劃所使用的環境模 型，即將實際的物理空間抽象成算法能處理的抽象空間，實現相互間的映射。規劃空 間的表示是否合理直接影響規劃的效率和結果的優劣性。一種好的規劃空間表示法 應能滿足如下要求：規劃空間能合理且盡量完善地反映飛行環境中的各種信息（地形

5、、威脅、障礙 等），以利于航跡搜索；當飛行環境中的某些信息發生變化時能實時地進行更新，以滿足實時應用的要 求；能滿足無人機自身性能約束條件，包括最大拐彎角、最大爬升/俯沖角、最大 航跡距離、最小航跡段長度和最低飛行高度等。常用的規劃空間表示方法有柵格法和圖形法。柵格法將規劃空間分解成為一些 簡單的單元，并為每個單元分配一個代價值,對應于無人機經過空間相應區域的代價, 并判斷這些單元之間是否存在可行路徑，找到包含起始點和目標點的單元，從起始單 元開始，依次向柵格中代價最小的鄰域移動，最后到達目標單元3。航跡搜索算法中 的A*算法、動態規劃法等就是利用柵格描述規劃空間。由于數字地圖采用柵格的形 式

6、存儲，所以多數的航跡規劃研究都是使用柵格法表示規劃空間。圖形法首先根據一 定規則將規劃空間表示成一個由一維線段構成的網絡圖，然后采用某一搜索算法在該 網絡圖上進行搜索。使用圖形法必須表示出所有可能的路徑，否則就可能丟失最優 解。圖形法相比柵格法數據處理量少，但是更新較困難。常用的圖形法有Voronoi圖 法4、可視圖法(VisibilityGraph)5、隨機路標圖法(PRM： ProbabilisticRoadMap)6 等。航跡表示。其形式有兩種：一種是基于無人機運動學、動力學描述的連續平 滑航跡，采用此種表示方法可以省去最后的航跡平滑環節；另一種是用航跡點表示， 相鄰航跡點之間用直線段連

7、接幾何折線航跡。第2種表示方法有如下優點：可以通過調整航跡節點的數目達到所需要的精度；將復雜的航跡規劃問題分解為一組統一形式的小規模子問題，對于每個子問 題，只需關心一個點的坐標，從而將考察航跡是否可行變為僅考察一個點或一條直線 段是否滿足要求；便于實現并行、分布式計算。分析約束條件。航跡規劃問題需要考慮的約束條件包括環境約束、任務約束 和無人機自身性能約束。環境約束有威脅約束(如被敵方雷達發現概率、敵方導彈高 炮擊落概率、撞地概率等)、禁飛區約束、復雜氣象區約束等；任務約束有任務完成 時間、起始點、目標點、固定航向角、低空/超低空突防等；無人機自身性能約束有 最大/最小平飛速度、最大航程、最

8、高/最低飛行高度、水平最小轉彎半徑、最大爬 升角/俯沖角、最大縱向曲率、最大法向過載等7。若是進行二維航跡規劃,則不需 要考慮無人機的爬升/俯沖角約束和飛行高度約束。確定代價函數。代價函數將算法與實際物理問題緊密聯系在一起。對于無人 機航跡規劃，代價函數是評價航跡優劣的標準，代價值越小則表明航跡越優，反之表明 航跡越差。確定代價函數需要綜合考慮影響航跡性能的各項因素，對各個指標進行量 化和計算。三維航跡規劃的代價函數通常包含航跡長度代價、威脅代價和高度代價, 表示為J=3 1L+3 2T+3 3H(1)3 1+3 2+3 3 = 1(2)其中J為航跡總代價,L為航跡長度代價，一些文獻也稱其為燃

9、油代價,T為威脅 代價川為高度代價；3 1、32、33為相應的權系數，根據任務需要設置其值。二維 航跡規劃則不需要考慮高度代價。選取搜索算法。根據任務需求選取合適的算法規劃出滿足約束條件、規避障 礙、使代價函數獲得最優值的航跡是航跡規劃問題的核心部分。航跡平滑。通過相應算法搜索出的航跡對于無人機實際飛行而言并不一定可 行，例如規劃出的航跡拐彎點較多,而無人機在實際飛行中由于自身機動限制不能頻 繁轉彎，因此需要對規劃出的航跡進行平滑處理，消除不必要的拐彎點以利于無人機 實際飛行。常用航跡平滑方法有三次樣條插值法8、貝塞爾曲線 (BezierCurve)9、k-trajectory 算法10等。2

10、常用航跡規劃算法無人機航跡規劃的本質是路徑規劃，即尋找適當的策略構成連接起點到終點位置 的由序列點或曲線組成的路徑，因此用于航跡規劃的算法實際上也就是路徑規劃算 法。路徑規劃算法有很多，每種算法都有其自身的優缺點和適用范圍,按照規劃決策 可以將算法分為傳統經典算法和現代智能算法11兩類。2.1傳統經典算法近年來常用于航跡規劃的傳統經典算法有Dijkstra算法、人工勢場法(APF： Artificial PotentialField)和模擬退火算法(SAA:SimulatedAnnealingAlgorithm) o Dijkstra算法是圖論中求解最短路徑的經典算法,適用于每條邊的權數 為非

11、負的情況，能得到從指定頂點到其他任意頂點的最短路徑。使用Dijkstra算法 進行航跡規劃，構建的賦權圖的頂點代表航跡點，賦權圖的邊代表所有可行航 跡,Dijkstra算法的作用就是在這些可行航跡里找到最優航跡。Dijkstra算法實現 簡單，但其運算時間和所用內存與搜索空間中節點個數平方成正比，在大范圍高維空 間中搜索時間長，對內存要求也很高，因此多用于二維靜態航跡規劃12,13。由于航 跡規劃空間范圍大，對于Dijkstra算法在航跡規劃中的應用，如何選取有效航跡點， 減少航跡點數量,縮短規劃時間是問題的關鍵。文獻12在Voronoi圖的基礎上使用 Dijkstra算法尋找最優航跡，將威脅

12、看作一個點，選取各威脅點之間連線的中垂線的 交點為航跡點。這種方法能保證航跡最大化避開各個威脅，安全性高,但航跡較長。 并且沒有考慮無人機最大轉彎角約束，航跡不一定可飛。文獻13在可視圖的基礎上 使用Dijkstra算法尋找最短航跡，將多邊形障礙的各個頂點看作航跡點，并建立轉彎 角約束機制。這種方法得到的航跡短,滿足無人機最大轉彎角約束，但由于航跡貼近 障礙物，安全性較低。此外，可視圖不能表達物體運動的方向性約束的缺陷導致 Dijkstra算法在搜索時可能找不到路徑。雖然Dijkstra算法多用于二維航跡規劃， 但也有學者將其應用于三維航跡規劃。文獻14 將飛行空間映射到由若十個四面體 組成的

13、三維Delaunay三角網中，四面體的頂點對應威脅的位置，四面體內切球的中心 作為航跡點，所有相鄰四面體內切球中心點的連線構成一個三維網絡,這個三維網絡 就是所有可行航跡。然后用Dijkstra算法在這個三維網絡上尋找最短航跡。最后用 人工勢場法對初始航跡進行優化，獲得平滑可飛的航跡。該方法與Voronoi圖法類 似，規劃出的航跡能最大化避開威脅，安全性高，但航跡相對較長。目前使用Dijkstra 算法進行航跡規劃多是利用Voronoi圖、概率地圖或可視圖描述規劃環境，然后在此 基礎上利用Dijkstra算法尋找最短航跡，但得到的航跡若安全性高則航跡長,若航跡 短則安全性低，沒有在航跡長度與安

14、全性之間尋找到一個好的平衡。人工勢場法是一種模擬電勢場分布的規劃方法，任務區域內的目標點產生引力 場，威脅源產生斥力場，無人機在引力和斥力的共同作用下向目標點運動。傳統人工 勢場法定義如下。航跡點X的引力勢函數和斥力勢函數分別為 U而(X)=!k”0(X,Xg) - (4)其中Katt和Krep分別為引力和斥力增益系數，且均為正常數；p(X，XG)為航跡 點X與目標點XG之間的距離；p(X，XO)為航跡點X與威脅源XO之間的距離；PO為 威脅源最大影響距離。無人機在X處受到的引力和斥力分別是相應勢函數的負梯度Fatt=- Uatt(X)=-KattP(X，XG)(5)D上e = . f昧M -

15、 g E 心 l y即Frep=_，- - -(6)總勢場力為目標點產生的引力和各個威脅源產生的斥力的矢量和Ftotal=Fatt+EFrep(7)人工勢場法的優點是算法簡明、實時性好、規劃速度快，在局部規劃和實時規劃 領域應用廣泛。缺點是當無人機離目標點比較遠,Fatt Frep時，合力方向更趨近目 標點方向，無人機可能會進入威脅區；當目標點附近有威脅源時，斥力將會非常大，而 引力相對較小，無人機將很難到達目標點；在復雜環境中，容易產生局部極小值，使算 法停滯或震動；在障礙物附近有抖動現象，在狹窄通道間頻繁擺動；在動態環境下規 劃效果減弱；計算勢場負梯度的方法因為沒有優化變量，將航跡規劃問題

16、轉換成了非 優化問題，因此缺乏評價指標衡量航跡的優劣,勢場的建立直接決定了航跡的質量，相 同的環境下，不同的勢場形式也可能得到不同的航跡。針對該問題，學者們結合無人 機航跡規劃的特點提出了多種改進方法。文獻15 在斥力勢函數中加入無人機與目 標點的距離，減小斥力，改善障礙物在目標附近時，目標不可達的問題。設置引導點為 無人機提供方向隨機的勢場力,解決局部極小值和震蕩問題。文獻16 在人工勢場法 搜索陷入威脅區時，構造懲罰勢函數替代斥力勢函數，并使用模擬退火算法取代虛擬 力引導的方法搜索逃離位置，有效避免了局部極小值和抖動現象，得到的航跡能成功 避開威脅，但增大了計算量，降低了人工勢場法的實時性

17、。文獻17通過引入相對速 度斥力勢場和斥力增益模糊控制器實現人工勢場法的動態避障，避免局部極小值。文 獻18 通過增加高度調節引力勢函數以增強人工勢場法在三維航跡規劃中對高度的 控制，同時引入飛行器的動力學約束條件，使航跡更具可飛性，并改善了人工勢場法的 局部極小值、障礙物附近抖動、狹窄通道間頻繁擺動等缺點。然而文獻15-18 中均 未衡量航跡優劣的評價指標，對此文獻19引入附加控制力作為優化變量，通過優化 出適當的附加控制力，使無人機在滿足各種物理約束的條件下，規劃出的航跡可使代 價指標最優，降低了勢場建立的任意性對航跡結果的影響。但文獻19 在考慮無人機 動力學模型時將無人機看作質點，與實

18、際動力學模型有一定差異。總之，對于極小值 等問題，前人提出的各種改進方法都在一定程度上彌補甚至消除了這些缺陷，但對于 障礙物附近抖動、狹窄通道間頻繁擺動這一缺陷的改善效果還有待提高。模擬退火算法是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索算法。它模擬 固體物質的退火過程，在某一初始溫度下，伴隨溫度控制參數按照降溫函數不斷下降, 結合概率的突跳特性在解空間中隨機尋找目標函數的全局最優解，即能概率性地跳出 局部最優解并最終趨于全局最優解。退火過程由冷卻進度表(CoolingSchedule )控 制，包括溫度控制參數的初值t及其衰減因子At、每個t值時的迭代次數和終止條 件。模擬退火算法的優點是算

19、法求得的解與初始解狀態無關，具有漸近收斂性，是一 種以概率1收斂于全局最優解的全局優化算法。缺點是解的質量依賴于當前解產生 新解的變換方法和冷卻進度表的設計。在航跡規劃中，模擬退火算法的一個解代表一 條航跡，目標函數則是代價函數，常用于求解二維航跡規劃中的TSP問題20，但該算 法多數沒有考慮無人機的機動性能約束，得到的航跡可飛性不高。模擬退火算法也可 與易陷入局部最優解的算法相結合幫助其跳出局部最優找到全局最優解，如遺傳模擬 退火算法21,在交叉和變異過程中使用Metropolis準則判斷是否接受新解，當然， 這會增大原算法的計算量。2.2現代智能算法相較于傳統經典算法，現代智能算法的應用更

20、為廣泛。在航跡規劃中常用的現代 智能算法有A*算法、遺傳算法(GA： Genetic Algorithm)、蟻群優化(ACO： AntColony Optimization)算法和粒子群優化(PSO： Particle Swarm Optimization) 算法。A*算法是一種智能啟發式搜索算法,它將搜索空間表示為網格的形式，以網格的 中心點或頂點作為航跡點，通過搜索鄰域內代價函數值最小的航跡點,從起始點逐步 搜索到目標點，最后逆向回溯當前節點的父節點生成最優航跡，其中待擴展航跡節點 存放在OPEN表中，已擴展節點存放在CLOSE表中。代價函數的表達式如下所示f(x)=g(x)+h(x)(8

21、)其中g(x)表示從起始點到當前節點的實際代價,h(x)稱為啟發函數，表示從當前 節點到目標點的估算代價，常用的啟發函數可選用歐氏距離、曼哈頓距離、對角線距 離等。啟發函數是A*算法的核心，它能在搜索效率和最優解之間權衡。若h(x)小于 從當前節點到目標點的實際代價,則搜索得到最優路徑，但這時搜索節點增多,搜索效 率降低；若h(x) 一直等于從當前節點到目標點的實際代價，此時A*嚴格按照最優路 徑搜索，搜索效率最高；若h(x)大于從當前節點到目標點的實際代價,則搜索結果可 能不是最優路徑，但搜索效率會提高。此外,OPEN表的維護方式也會影響A*算法的搜 索效率，當路徑很長時，這種影響會更明顯。

22、總之，啟發函數的選擇決定了 A*算法是否 能找到最優解,OPEN表的維護方式和搜索節點數量決定了 A*算法的運行速度。隨著 搜索空間增大,A*算法的計算量會呈指數增長，導致規劃時間過長，一般用于靜態航跡 規劃。在航跡規劃中，如何提高A*算法的運行速度并得到最優航跡是學者們重點考慮 的問題。文獻7 采用結構體式最小二叉堆和三層嵌套的二叉堆技術分別維護管理 OPEN表和CLOSE表，相比較于傳統的數組式最小二叉堆維護OPEN表和單向鏈表管理 CLOSE表的方式，提高了最優節點的提取速度，克服了數組二叉堆的容量可能導致 OPEN表溢出的問題，有效解決了動態二叉樹易出現的極度不平衡問題，保證了節點查

23、找的高效率，較大幅度提高了 A*算法的規劃效率。文獻22提出使用2.5維網格模型 描述三維規劃空間,每個網格點包含經度、緯度和高程信息，此方法計算效率要遠大 于三維網格劃分方式。文獻23 將三維航跡規劃分解為二維規劃和高度規劃,使用動 態時間規整(DTW:Dynamic Time Warping)距離作為A*算法的啟發函數進行二維規劃, 再由二維航跡結合高程數字地圖，利用粒子沉降法賦予每個航跡點高度信息,生成三 維航跡。這種方法有效地將三維空間的搜索節點刪減至二維，大大減少了搜索節點數 量，縮短了規劃時間。使用DTW距離作為啟發函數得到的航跡也要優于常用的歐氏距 離、曼哈頓距離和對角線距離，但

24、仍不是最優航跡。由于航跡規劃問題的復雜性，雖 然學者們通過各種改進方法提高了 A*算法的搜索效率，但仍沒有找到值恒等于從當前 節點到目標點真實代價的啟發函數，實現A*算法的高效最優搜索。遺傳算法的基本思想是模擬生物遺傳進化過程，根據“適者生存”、“優勝劣 汰”的原則，借助選擇、交叉、變異等操作，使所要解決的問題從初始解一步步逼近 最優解。在航跡規劃中,遺傳算法每條染色體(個體)代表無人機的一條航跡,基因的 編碼方式也就是航跡節點的編碼方式，適應度函數由代價函數變化而來。遺傳算法的 優點是不要求優化函數具備連續、可導和單峰等條件，具有較強的魯棒性，是一種高 效、并行、全局的搜索方法，適用于三維全

25、局航跡規劃。缺點是種群失去多樣性而導 致早熟收斂，尋優時間長，局部搜索能力差等。針對該問題，學者們提出了不同的改進 方法，如引入量子、自適應等因子,但這些改進方法仍然存在較多不足。文獻24 針 對量子遺傳算法初始種群的單一性，引入關于概率劃分的小生境協同進化策略，并對 各種群采用動態量子旋轉角；采用精英選擇機制，保留每一代中的最優個體，并借鑒 狼群分配原則對種群進行更新。該方法提高了量子遺傳算法的穩定性和尋優精度，但 在收斂速度上沒有改善，且沒有考慮無人機自身性能約束。文獻25使用并行遺傳算 法結合概率地圖實現多無人機協同航跡規劃，并行遺傳算法很好地克服了遺傳算法早 熟的缺陷，但文獻同樣沒有考

26、慮無人機自身性能約束。文獻26 通過在遺傳算法主種 群上附加一個病毒種群的方法，保證可行引導段的有效積累并維持種群多樣性。采用 定長實值和變長實值兩種編碼方式分別為染色體和病毒個體編碼，通過采用反轉錄和 轉導這兩種病毒感染操作實現兩個種群間模塊的信息交換，使進化信息在種群內迅 速、定向地傳播，消除了尋優過程的盲目性。該方法改善了遺傳算法早熟和局部收斂 慢的問題，提高了收斂速度，但對于搜索精度幾乎沒有提高。文獻27 提出多頻振動 遺傳算法，在遺傳操作中使用兩次變異操作，分別作用于整個種群和精英個體，為種群 提供全局多樣性和局部多樣性，從而有效避免早熟，提高搜索精度，達到快速收斂的目 的。蟻群優化

27、算法模擬螞蟻在尋找食物過程中發現路徑的行為特性，利用信息素濃度 進行后繼行為。T時刻螞蟻n從節點a轉移到節點b的概率為|0.其他(9)其中Tab為節點b上的信息素濃度；nab為節點a與節點b之間的能見度，也 叫啟發函數，它可以是距離開銷，也可以是距離開銷與其它開銷的組合,如高度、安全 度等；a、B為Tab與nab的相對重要性的權值；為節點a的所有相鄰節點 的集合。信息素具有揮發性，隨著時間的增加其濃度會降低。信息素的更新分為局部更新 和全局更新，局部信息素更新是用在螞蟻完成一個航跡點的選擇時，相應的減少該點 的信息素，降低此點對后來螞蟻的吸引程度，從而增加螞蟻的探尋范圍，減小算法陷入 停滯的概

28、率。其更新公式為Tab(t+1)=；Tab(t)(10)其中E為信息素減少因子,用于控制信息素減少的大小。全局信息素更新是經 過m時刻，當螞蟻完成尋路任務后對其經過的所有航跡點上的信息素進行更新，通過 這種方式增加這條航路上的信息素，其表達式為Tab(t+m) = (1-p)Tab(t) + pATab(11) Tab二Q/J(12)其中P為信息素揮發因子；J為這條航跡的性能指標；Q為性能指標對于信息 素的更新的比例系數。蟻群優化算法的優點是具有良好的并行性、協作性和魯棒性，后期收斂速度快。 缺點是前期搜索時間長,參數多并且解的質量受參數影響大，容易陷入局部最優解，適 用于三維全局航跡規劃。由

29、于信息素的分布情況、揮發方式和螞蟻選擇前進方向的 盲目性影響著解的質量和獲得解的時間，學者們也通常從這幾個方面,結合航跡規劃 的特性對蟻群算法進行改進。文獻28 將螞蟻按數量均勻分組,并在信息素濃度更新 過程中使用差分進化算法的交叉、變異、選擇操作，合理分配各路徑上螞蟻留下的信 息素，避免某條路徑上信息素累積過多而導致陷入局部最優解,從而引導螞蟻找到最 優路徑。該混合算法在保證基本蟻群算法優點的同時提高了全局收斂的速度，但得到 的航跡過長。文獻29 提出一種文化蟻群算法，設計了由蟻群算法演化的群體空間和 由群體空間最優解構成的信仰空間，兩個空間同時演化，彼此促進。在群體空間中加 入懲獎機制，對

30、到達終點的螞蟻走過的路徑，提高其信息素濃度，反之，則降低,從而提 高了螞蟻找到可行路徑的概率。信仰空間利用選擇、交叉、變異這3種遺傳操作進 行更新。此外，文獻在啟發式函數中加入了航路點的方差，計算待選節點和其前面n 個點的方差,使選出的節點與前面節點的波動相對較小，從而獲得更平滑的航跡。該 方法的雙層進化模型加快了航跡的搜索速度，但懲獎機制的評判標準單一，到達終點 的螞蟻走過的路徑并不一定就好,此機制可能會降低解的質量。文獻30首先限制信 息素揮發因子的范圍，防止其過大或過小影響算法的全局搜索能力，并在信息素調整 規則中引入航跡評價指標，提高解的質量。然后將起始點和目標點之間的連線這一最 短航

31、跡信息反饋到系統中作為搜索的指導信號，將能見度改進為當前節點與待擴展節 點的距離和待擴展節點到最短航線的垂直距離加權和的倒數，降低算法尋找航跡的盲 目性，加快了搜索效率。最后在該能見度的基礎上，將轉移概率與一個01之間的隨 機數相乘，選擇鄰域中轉移概率最大的節點擴展。該方法在保證基本蟻群算法優點的 同時提高了解的質量，大大縮短了搜索時間。粒子群優化算法模擬鳥群飛行捕食行為，把每個粒子看作優化問題的一個可行 解,并將其延伸到N維空間，每個粒子主要通過跟蹤兩個位置決定自己下一步的飛行， 一個是粒子本身所找到的最優解Pbest,即個體最好位置；另一個是種群中所有粒子 當前找到的最優解Gbest,即全

32、局最好位置，最終群體成員逐漸移入問題空間的更好區 域。所有的粒子都有一個由被優化的函數決定的適應值,每個粒子還有一個決定其飛 行方向和距離的速度。粒子群算法的速度和位置更新方式分別為vij(k+1) = 3vij(k)+c1r1(pij(k) -xij(k)+c2r2(gij(k)-xij(k)(13) xij(k+1)=xij(k)+vij(k)(14)其中下標i、j、k分別表示第i個粒子，第j維空間，第k代粒子；3為慣性權 重，描述了粒子對之前速度的“繼承”；c1、c2為常數,稱為學習因子，體現了粒子向 全局最優粒子學習的特性；r1、r2為(0,1)之間的隨機數。與其他進化算法相比，粒子群

33、算法具有兩個顯著的不同特點。一是沒有“優勝劣 汰”的機制，所有的粒子在迭代過程中始終作為種群的成員保留；二是沒有交叉、變 異等進化算子，每個粒子通過追隨當前搜索到的最優值尋找全局最優。粒子群算法的 優點是具有較強的魯棒性，對種群大小敏感性不高,參數少，前期收斂速度快,缺點是 后期收斂速度慢，容易早熟陷入局部最優解，可用于三維全局航跡規劃。在航跡規劃 中學者們對粒子群算法的改進也多是通過提高種群的多樣性避免局部最優。文獻31在量子粒子群優化算法(QPSO： Quantum-behavedParticleSwarmOptimization) 的基礎上引入繁殖機制，整個種群中粒子位置更新后不直接進入

34、下一代，而是以一定 概率將粒子放入繁殖池，種群中最優個體不參與繁殖操作，以便保護其不被破壞。該 方法與QPSO算法和PSO算法相比，能找到更優的航跡，但由于增加了繁殖機制，每次 迭代時間要比QPSO算法多。文獻32在基本PSO算法中引入病毒種群，以增強主群 體粒子的多樣性，提高局部搜索能力，解決基本PSO算法容易陷入局部最優、收斂速 度慢的問題。文獻33在？5。算法中引入潛在網格構造算子，在整個種群中粒子位置 更新后，為每個粒子運用相應的算子，以克服PSO算法易陷入局部最優和后期收斂速 度慢的問題，該方法能得到質量更好的航跡。3目前研究熱點及發展趨勢3.1現代智能算法的改進航跡規劃是一個NP-hard問題,要得到最優航跡需要極大