基于改進麻雀搜索算法的無人機航路規劃研究

王玲玲，孫 磊，丁光平，王加剛，段 譽

(1 鹽城工學院機械工程學院，江蘇 鹽城 224001；2 重慶望江工業有限公司，重慶 400020；3 清華大學精密儀器系，北京 100084)

0 引言

隨著航天技術和軍事需求的不斷增長，航路規劃在無人機作戰任務過程中發揮著越來越重要的作用。無人機作戰時需要根據多個特定的約束條件，搜索出一條從起點到指定終點最安全有效的軌跡[1-3]。

算法設計是解決無人機復雜航路規劃的核心環節。近年來，仿生群體智能優化算法層出不窮，研究人員對其開展了深入研究。文獻[4]結合了三次樣條插值函數和改進的蟻群算法，對無人機飛行路徑進行優化，得出了最優的航路。文獻[5]以傳統粒子群優化算法為基礎，引入細菌覓食算法及遺傳算法思想，提高算法計算速度與能力。文獻[6]提出了一種基于改進的哈里斯鷹群優化的無人機航跡規劃算法，引入柯西變異策略和自適應權重以提高其性能。文獻[7]提出了一種利用局部信息和相對距離的三維路徑規劃深度強化學習方法，無人機可在實際場景中獲取附近有效的環境信息。但是上述算法仍不能達到理想的效果且存在易陷入局部極值的情況。

為此，文中選用麻雀搜索算法進行無人機的航路規劃設計。麻雀搜索(sparrow search algorithm, SSA) 算法[8]是由Xue等2020年提出的一種新智能優化方法，是根據麻雀覓食和隱蔽天敵的行為來創建優化模型，該算法具有較好的魯棒性，可快速有效地規劃出無人機航行路徑。但該算法和其他群智能算法一樣，存在初始化種群的隨機性分布不能達到絕對均勻，局部搜索的性能較差，容易忽略最優解的問題。為了改善在三維航路規劃中的安全與效率等問題，文中提出了一種基于改進麻雀搜索算法(circle chaos and firefly strategy based sparrow search algorithm, CFSSA)的三維航路規劃方法。該方法通過采用 Circle混沌映射對原始麻雀種群進行初始化操作，在初始化的過程中利用螢火蟲擾動策略不斷對麻雀位置進行迭代優化，從而減少陷入局部最優值的概率，提高全局搜索的能力。實驗證明，較其他算法，基于 CFSSA的三維航路規劃方法效果更好，能夠取得尋優結果。

1 麻雀搜索算法

SSA受到自然界中麻雀覓食和躲避天敵現象的啟發，麻雀有很好的飛行能力和很強的警覺性。SSA可以被理解為一個發現者-追隨者模型，其中還增加了預警機制。發現者負責發現食物，并把食物位置信息傳遞給整個群體，而追隨者通過發現者的信息獲取食物。此外，還有一些個體擔任預警者的角色負責在覓食過程中躲避捕食者，并警示種群中的其他麻雀，這時所有麻雀需要向附近麻雀靠近并飛向其他安全區域，以減少被捕食的幾率。

麻雀種群中的發現者的位置更新公式為：

(1)

麻雀種群中跟隨者的位置更新迭代公式為：

(2)

麻雀種群中預警者的位置迭代更新公式為：

(3)

2 改進的麻雀搜索算法

2.1 Circle混沌映射優化初始種群

在初始化階段，由于麻雀個體分布不均勻，導致麻雀初始位置過于集中，不利于搜索出全局最優位置。而Circle混沌映射[9]有著隨機性、均勻性和有序性等特點，并且不會重復所有的狀態，可以用來初始化種群，克服種群初始化時的盲目性，使得個體在搜索空間的初始位置分布更加均勻，提高麻雀種群的多樣性，為后期麻雀搜索算法尋優打下基礎。Circle映射可表示為[10]：

xk+1=mod(xk+b-(a/2π)sin(2πxk),1)

(4)

式中：mod為取余函數；a，b為系數，分別取值0.5和0.2。

從圖1可見，利用Circle映射進行初始化種群，相比于隨機初始點，Circle混沌映射值分布更加均勻，麻雀種群在空間中的搜索范圍更廣，有效改善了原來算法極易陷入局部最優的問題。

圖1 Circle混沌映射分布圖

2.2 螢火蟲擾動策略

螢火蟲算法是一種仿生群智能優化算法，仿生群智能優化算法的主要思想是通過研究自然界中模仿生物群體生活的社會行為而構建的一種隨機搜索方法[11]。螢火蟲算法的優化原理為：將空間中的每一個點看作是螢火蟲﹐螢火蟲的種群是隨機分散的，利用發光度大的螢火蟲吸引發光度小的螢火蟲的特點，在發光度弱的螢火蟲向發光度強的螢火蟲移動的過程中，完成位置的更新迭代，從而找到最優位置，該過程也是完成尋找最優解的過程。

群體中每一個螢火蟲都對應問題的一個可能解。假設Xk=(xk1,xk2,…,xkd)是一只螢火蟲，其中：k表示螢火蟲的數量編號;d表示變量的維度。

螢火蟲的相對熒光亮度I可表示為：

(5)

式中：I0是每個個體螢火蟲的目標函數值，即最大熒光亮度，當I0值越大時螢火蟲適應度值越優；γ為光強吸收系數，該系數隨著距離的增加、傳播媒介的吸收而逐漸變小；rmn=|Xm-Xn|為第m只和第n只各螢火蟲間的距離。

螢火蟲的吸引度β可表示為：

(6)

式中：β0表示個體光源處的吸引度，一般為常數。

螢火蟲擾動位置更新公式為：

xi=xi+β·(xj-xi)+α·(rand(n)-1/2)

(7)

式中：xi和xj為麻雀i和j的空間位置；α為步長因子；rand(n)∈[0,1]為隨機因子，可以增加搜索范圍，避免在早期階段進入局部最優。

2.3 改進的麻雀搜索算法流程

綜合考慮，改進的麻雀搜索算法流程為：

1)系數初始化。設置種群數量、最大迭代次數、發現者和預警者比例、預警值等。

2)初始化麻雀種群的位置。利用Circle混沌映射進行初始化，使其在解空間中隨機分布。

3)計算適應度值函數，比較后得到最優和最差的適應度值的麻雀信息。

4)按比例從群體中選擇適應度值高(即路徑長度最短)的麻雀作為發現者，并通過式(1)更新發現者的位置。

5)根據式(2)，更新跟隨者的位置。

6)根據式(3)，更新預警者的位置。

7)引入螢火蟲擾動策略，此時麻雀種群位置等同于螢火蟲位置。根據式(5)、式(6)計算出螢火蟲群體的相對亮度I0和吸引度β，確定螢火蟲的移動方向。

8)并根據式(7)更新螢火蟲的位置，并對處于最優位置的螢火蟲進行隨機擾動，當達到迭代次數或收斂后，移動結束，輸出全局的最佳個體位置。

3 無人機三維航路規劃建模

3.1 任務環境建模

無人機在執行任務的時候，往往需要考慮復雜多變的三維地形環境，主要受到地形威脅和障礙威脅等因素的影響[12]。具體的三維空間模型為：

(8)

式中：x，y，z2分別為地圖模型中點的橫縱坐標和高度；a，b，c，d，e，f，g這7個常數用于改變地貌特征粗糙表面的參數。

(9)

式中：n表示地圖中山峰的個數；(x,y)表示山峰在平面投影所對應的位置坐標；(x0(u),y0(u))為第u座山的峰頂坐標；h(u)為山峰的高度；ax(u),by(u)表示第u座山峰沿x軸和y軸方向的坡度。

采用式(8)建立基準地形模型來建立粗糙的地面，采用式(9)來模擬基準地形上的山體障礙物。

3.2 約束條件設置

基于無人機的機動性，主要考慮到5個約束條件：

1)最大航程約束。假設路徑中有n段，且第q個航路段長度為lq，最大航程為Lmax，約束需滿足：

(10)

2)最小航跡段約束。受無人機姿態調整的延遲等限制，最小航跡段距離為Lmin，則航跡中任意一段航跡的距離滿足：

lq≥Lmin(q=1,2,…,n)

(11)

3)最大轉彎角。無人機的自身性能也受轉彎角代價的限制，轉彎角度只能在預設的最大拐角范圍內完成無人機的姿態調整[13]。轉彎代價函數為：

(12)

其中：α表示最大轉彎角；aq表示其水平方向的投影。

4)最大爬升/俯沖角。與轉彎角相同，無人機爬升和俯沖也存在著最大角度的限制，通常被稱為最大爬升/俯沖角即θ[14]，應滿足：

(13)

5)飛行高度限制。無人機飛行高度需高于最低高度，防止觸地墜落。設最低離地高度為H，則飛行過程中需滿足：

H≥Hmin

(14)

3.3 航跡代價指標

航跡代價函數用來計算航路的代價值以便分析航路性能的好壞[15]。綜合權衡了燃料消耗代價、高度變化代價和威脅指數3個因素，所采用的航路規劃評價函數為：

Jmin=k1L1+k2L2+k3L3

(15)

式中：Jmin表示最小代價航跡；L1，L2和L3分別表示燃料消耗代價、高度變化代價和威脅指數；k1，k2和k3為常數且分別代表各自的權重系數，且滿足k1+k2+k3=1。

4 仿真實驗與分析

4.1 實驗環境與參數設置

為了驗證文中CFSSA改進算法的有效性，將其與SSA算法、PSO算法對比。所有算法的種群數量為50，迭代次數為100，空間維度為30。

4.2 測試與分析

4.2.1 算法性能測試

為了測試改進算法的有效性，選取 6個標準測試函數來驗證改進算法與SSA算法、粒子群優化(particle swarm optimization,PSO)算法，前4個為單峰函數， 后 2個為多峰函數。標準測試函數信息如表1所示。算法優化對比實驗結果見表2。

表1 標準函數測試表

從表2可以看出，針對6種測試函數，CFSSA在各函數測試中都能得到不錯的收斂精度且更快地趨向于0，整體要優于SSA和PSO，特別是針對前4個單峰函數。由此看出，改進策略的引入是有效的，不僅CFSSA的求解效果和魯棒性比其他算法好，而且更加穩定，具有較強的尋優能力。

表2 各算法優化對比計算結果

4.2.2 仿真結果及分析

在規格為100 m×100 m×450 m的柵格地圖中進行航跡規劃仿真實驗，設置任務的起點為(15 m,52 m,160 m)，終點為(76 m,89 m,250 m)。

根據給定參數，對CFSSA，SSA和PSO算法分別進行航跡規劃測試，獨立仿真100次，統計3種算法各自的航跡長度、航跡代價、航跡節點個數和搜索時間如表3所示。各算法的適應度值曲線見圖2，各算法的航跡規劃圖見圖3。

圖2 平均適應度值曲線

圖3 各算法最短路徑規劃對比仿真圖

表3 各算法路線統計表

從表3中可以看出，CFSSA得到的航跡長度最短且搜索時間最快，付出的航跡代價也最小，能夠快速穩定地進行航路規劃，符合設定的約束并且效果最好。從圖2中可看出，SSA算法找到的路線較為復雜且代價最大，PSO算法雖然前期的收斂速度最快，但后期CFSSA 收斂速度最快，也具有較好的收斂精度，在50次迭代之前就已經找到了一條代價最小且時間最短的路徑，對比這3種算法CFSSA的尋優值最小且效果最好。

由圖3可以看出，CFSSA 與其他群智能算法相比，無人機的航路最為平滑且清晰，且所規劃的航跡長度最短。綜合來看，CFSSA多種策略的引入使得算法的搜索效果更好、耗時短且穩定，由此證明了算法的合理性。

5 結語

針對麻雀搜索算法在尋優過程中存在陷入局部最優且初始化種群分布不均勻等缺陷，引入了Circle混沌映射來擴大種群初始化，再采用螢火蟲擾動策略對麻雀種群的最優位置進行強化更新。為了驗證該算法的有效性，利用無人機航路規劃進行了仿真。結果表明，提出的算法明顯增強了收斂性，能夠獲得更高質量的導航軌跡和收斂精度，從而更好地避開威脅路徑。