基于適應度值優劣粒子群算法的無人機路徑規劃

王小璐，黃辰，于遠航，陳福豪，胡蝶，陸琪，崔曦予

（沈陽航空航天大學民用航空學院，遼寧沈陽，110136）

0 引言

近年來，隨著傳感器技術和智能控制技術的發展，無人機已被廣泛應用于軍事和民用領域，如偵察[1]、監視[2]、目標檢控[3]、無線通信[4]、油田檢測[5]等。與載人飛機相比，無人機因為體積小、成本低、對使用環境要求低和具有較強的生存能力等優點而得到了廣泛的應用，并正在逐漸取代傳統的載人飛行器，無人機(Unmanned Aerial Vehicle, UAV)的研究對一個國家的經濟與民生起著重要的作用。路徑規劃作為[6]無人機系統自主導航的基礎技術，是保證飛行任務順利完成的重要組成部分，因而受到越來越多的關注。無人機路徑規劃的主要目標是在規定的約束條件下，在任務空間中尋找從起始位置到目的位置的最優或接近最優的飛行路徑。近年來，常用于解決路徑規劃問題的主要方法有啟發式算法（例如，A*算法[7]、D*算法[8]）、進化算法（例如，蟻群算法[9]、粒子群算法[10]、人工蜂群算法[11]、遺傳算法[12]）、人工勢場法[13]等。

與傳統方法相比，進化計算算法在路徑上獲得高質量解的能力很強。航跡規劃問題通常被認為是一個非線性NPhard優化問題，通過進化算法進行求解。眾所周知，進化算法已經取得了很大的進展，并得到了深入而廣泛的研究。進化算法的靈感來自“自然生物進化”，通過將自然界各種事物的演化規律與解題過程相結合，從而得到實際問題的高精度近似解，并在生產實踐中得到了廣泛應用。進化算法已被成功應用于尋找全局或近似全局最優路徑。Yang等[14]發現了在歷史搜索中的高質量路徑點難以得到進一步利用的缺點，提出了一種將路徑點分別評估和演化的方法用于二維無人機路徑規劃。Huang等[15]提出了一種基于全局最優解競爭的改進PSO算法，并將路徑規劃器應用于三維無人機。Zhang[16]提出了一種改進的基于相位角編碼并結合突變適應機制的果蠅優化算法，以解決無人機(UAV)路徑規劃問題。

粒子群優化算法(Particle Swarm Optimization, PSO)[17]基于一個簡單的機制，通過模仿鳥類等群居動物的群體覓食行為。粒子群中包含有一群粒子，每個粒子表示優化問題的一個候選解，并且每個粒子都有一個在D維搜索空間中飛行的位置和速度。為了找到全局最優值，每個個體根據某些特定的適應值進行自我評估，在搜索過程中記住自己搜索到的最佳位置pbest以及全體的最佳位置gbest。利用這兩個極值來調整飛行，最終找到食物的位置。與其他受生物種群行為特征啟發的算法一樣，優化問題從隨機初始解開始，通過計算適應度值來評估解的質量，通過迭代進化的方式逐步找到最優解，反復迭代多次。

1 無人機路徑規劃問題描述

在搜索空間中，定義起始點為PS(x S,yT)，目標點為PT(xT,yT)，如圖1所示。圖1 描述無人機的飛行環境。飛行任務是根據目標函數下，在S和T之間生成最優路徑。一條優化路徑可以用一個集合C= {PS,P1,P2···,PD,PT}其中路徑點PD= (x d,yd)來表示。然后通過連接各個路徑點得到一條無人機的飛行路線。威脅的區域采用圓形來定義，如圖1所示。

圖1 環境描述

在進行路徑規劃之前，首先需要對運動空間進行離散化，使其成為對路徑規劃有意義的表示。這種表示與搜索算法密切相關，規劃算法只有在與環境表示相配合的情況下才會有好的表現。令(x,y)表示任務空間中任意一點的坐標，任務空間可以被表示為：

其中，xmin，xmax，ymin，ymax分別定義為,x y的邊界值。

當無人機執行飛行任務時，可能會面臨敵方導彈攻擊、雷達探測等高風險威脅。因為雷達和導彈的防御范圍是全方位的，因此用圓來描述威脅源的數學模型。第i個雷達或導彈的數學模型可以被寫成：

其中，(xk,yk)為第k個威脅源的中心坐標，rk是第k個威脅源的半徑。

2 建立目標函數

無人機航跡的目標函數主要包括障礙危險成本和長度成本，所以目標函數是障礙威脅和長度的加權總和，可表示為：

其中，J1為長度成本，J2為障礙危險成本，w1、w2分別為障礙危險成本和長度成本的權重。

長度成本可通過下式來計算：

其中，i=D+1時，Pi表示目標點。i-1=0時代表起點。

規劃路徑的安全代價可計算為：

其中，Oj為第j個障礙物的圓心，rj為第j個障礙物的圓心。

3 改進粒子群算法

3.1 粒子群算法

粒子群優化算法通過將求解的問題看作是空間中的粒子，算法通過模仿昆蟲，鳥類的覓食行為來解決各種工程最優化問題。鳥群中個體的飛行過程類比為單個粒子的運動過程，將其群體覓食行為的過程類比為尋找最優解的迭代過程。在該過程中基本無需外部信息，只通過群體內部的交流。在粒子群算法中，假設每個粒子都能記住歷史上的最佳位置，也就是整個種群所發現的最佳位置，被稱為全局最優解，以及每個粒子目前所發現的最佳位置，即個體最佳位置。每個粒子向個人最佳位置和全局最佳位置學習。該算法操作簡單、實現容易、精度高、且具有優秀的收斂性。

設在D維空間搜索域中，群體中有N個粒子，N為種群規模，種群規模不宜過小，以保證種群多樣性，提高算法性能；且不宜過大，致使收斂速度過于緩慢。

每個粒子i的位置表示為搜索域中的一個向量Xi=(xi1,xi2,···,xiD)，速度為Vi= (vi1,vi2,···,viD),i= 1,2,···,N。粒子個體的最優位置和粒子群體整體最優位置分別用pbest和gbest來表示，第k次迭代中粒子的位置及速度按照以下方程進行更新：

其中，ω為慣性權重，c1為個體加速系數，c2為群體加速系數，r1，r2為[0,1]上均勻分布的隨機數。

個體加速系數c1表示粒子下一步運動受自己經驗驅使所占的權重。即將粒子推向個體最優位置pbest的加速權重；群體加速系數c2表示粒子下一步運動受其它粒子經驗影響所占的權重。即將粒子推向群體最優位置gbest的加速權重。c1的值過小會造成群體多樣性降低，導致搜索局限。c2過小自會導致自我認知型粒子群算法，即社會共享信息少，致使收斂速度緩慢。

3.2 改進粒子群算法

慣性權重ω指粒子保持原有運動狀態的能力，使其有能力在搜索域中對新控件進行探索。進而使得PSO在全局搜索和局部開發之間取得平衡。ω作為粒子群優化算法的關鍵參數之一，它的取值很大程度上決定了算法性能：在算法前期，ω值大有利于粒子搜索更大的范圍，在算法后期，ω值較小則可以加快收斂速度。

當慣性權值ω較小時，算法的局部搜索能力較好。ω較大時，算法的全局搜索能力得到了提高，在接近最優位置時瞬間又飛越了最優位置，這樣算法就很難收斂。一般選取慣性權重ω的值在[0.4, 0.9]范圍內，慣性權重ω的值很嚴重影響算法的優化性能。根據種群中各粒子的適應度值，種群中的粒子將劃分為“開發型”與“探索型”兩種。“開發型”粒子主要任務是對已找到的優質解進行優化，而“探索型”粒子用于找到優質解的區域。針對不同的搜索類型，建立了分段非線性慣性權重函數, “開發型”慣性權重采用隨機方法獲得，粒子群算法中的慣性權值ω采用隨機機制，隨機機制有利于保持學習多樣性和種群多樣性可以避免過早收斂性和落入局部最優。而 “探索型”慣性權重收斂速度最慢，因此，通過分組的方式來調整慣性權重的大小可以有效提高算法的搜索效率。改進后的慣性權重ω描述為：

4 仿真實驗與分析

為了研究算法對無人機路徑規劃的可行性和有效性，在MATLAB2016a仿真環境下進行實驗，并與PSO算法進行了進一步的實驗比較。環境1中設置起始點的坐標(0, 0)，目標點的坐標為(400, 600)。環境1中設置3個障礙物，其中心坐標分別為(150, 450)、(400, 300)和(120, 150)。 環境2中設置起點坐標為(200, 100)，目標點的坐標為(800, 800)。環境2中設置6個障礙物，其坐標為(300, 200)、(500, 400)、(600, 200)、(300, 500)、(700, 550)和(600, 750)。粒子個數N=100，最大迭代次數Tmax=100。

每個算法獨立運行25次，采用兩種算法進行路徑規劃，兩種算法的適應度值的結果如表1所示。PSO和改進的PSO算法得到的規劃路徑在兩種環境中的規劃路徑曲線分別如圖2和4所示，適應度值變化曲線如圖3和5所示。

表1 兩種算法的適應度值結果

圖2 環境1的規劃路徑

圖3 環境1中適應度值變化曲線

比較表1中的兩種算法的適應度值可以看出，在環境1和2中，FPSO算法的最優適應度值小于原PSO算法，FPSO算法的平均適應度值比PSO算法要小，平均適應度值表示算法在多次運行時的穩定性。對比實驗結果在PSO和FPSO之間，可以得出PSO的參數更新策略具有更強大的尋優能力。這兩種環境下的實驗結果證明了FPSO算法的優越性，可以用于求解無人機航路規劃問題。

圖4 環境2的規劃路徑

圖5 環境2中適應度值變化曲線

5 結論

在PSO算法用于處理無人機的路徑規劃問題中，由于傳統PSO算法存在易陷入局部最優的缺陷，本文從整個種群粒子的適應度值出發，將種群劃分為探索和開發兩個子部分，在兩個子部分中分別采用不同的慣性權重ω選擇策略，以此來提高了算法的多樣性和搜索尋優能力。通過對傳統PSO算法和改進后的PSO算法進行路徑規劃仿真并對結果進行對比分析。與傳統PSO算法相比，FPSO可以得到一條更平滑和路線較短的無人機飛行路線。