基于混沌麻雀搜索算法的無人機航跡規(guī)劃方法

湯安迪，韓 統(tǒng)，徐登武，謝 磊

（1.空軍工程大學研究生院，西安 710038；2.空軍工程大學航空工程學院，西安 710038；3.94855部隊，浙江衢州 324000）

0 引言

隨著無人機（Unmanned Aerial Vehicle，UAV）技術的不斷發(fā)展，國內外學者對于無人機作戰(zhàn)應用的研究日益增多。無人機航跡規(guī)劃是任務規(guī)劃系統(tǒng)的關鍵部分，是一個典型的非確定性多項式（Nondeterministic Polynomial，NP）問題［1］。隨著規(guī)劃問題復雜度的不斷增加，其難度和計算量迅速增長，很難找到一種有效應對所有復雜環(huán)境的航跡規(guī)劃方法。為解決不同條件下的航跡規(guī)劃問題，學者們不斷對航跡規(guī)劃算法進行研究和改進。文獻［2-8］研究了快速擴展隨機樹（Rapidexploration Random Tree，RRT）算法、A star 算法、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、遺傳算法（Genetic Algorithm，GA）在UAV 航跡規(guī)劃中的運用。Yang 等［2］將環(huán)境勢場引入RRT 算法，但得到的規(guī)劃航跡與實際最短航跡有一定差距；劉華偉等［3］將人的智能決策引入RRT算法，但是該算法依賴人的主觀判斷，容易陷入局部最優(yōu)；趙鋒等［4］將啟發(fā)式權重系數(shù)引入A star 算法，但權重系數(shù)的線性調整策略不能很好地適應復雜的優(yōu)化問題；Zhang 等［5］在PSO 算法中設置異步變化學習因子，但搜索能力依賴于步長的分段設置；程澤新等［6］在GA 中引入差分進化策略，但改進后的算法計算量增大，航跡規(guī)劃實時性較差。

自1975 年美國教授Holland 根據(jù)達爾文進化論以及自然界優(yōu)勝劣汰機制提出了GA 以后，越來越多的學者通過對不同生物種群和物理現(xiàn)象進行分析，從中獲取靈感，提出了多種群智能優(yōu)化算法，包括：灰狼優(yōu)化算法（Grey Wolf Optimizier，GWO）［7］、螢火蟲算法（Firefly Algorithm，F(xiàn)A）［8-9］、天牛須搜索（Beetle Antennae Search，BAS）算法［10］、鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）［11］、天牛群優(yōu)化算法（Beetle Swarm Optimization，BSO）［12］。

麻雀搜索算法（Sparrow Search Algorithm，SSA）［13］通過麻雀個體搜尋食物和反捕食進行迭代尋優(yōu)，具有調整參數(shù)少、收斂速度快、計算簡單等優(yōu)點；但和其他群智能算法一樣，在求解復雜工程優(yōu)化問題時，容易“早熟”，導致收斂精度不高，且易于陷入局部最優(yōu)解。SSA 的更新方式可大致分為兩種：1）向當前最優(yōu)位置靠近；2）向原點靠近。通過仿真實驗可知，在進行航跡模型最優(yōu)航跡求解時，每次收斂是直接跳躍到當前最優(yōu)解附近，容易丟失全局最優(yōu)航跡解，僅可能得到滿足約束的可行解，并且有概率得不到可行解。為了改善全局搜索能力，防止陷入局部最優(yōu)解，借鑒Xu 等［14］引入混沌算子的思路，本文將立方映射混沌算子［15］引入SSA算法，提出了一種混沌麻雀搜索算法（Chaos Sparrow Search Algorithm，CSSA）。CSSA 在對麻雀位置初始化過程中使用混沌序列，同時使用反向學習策略（Opposition-Based Learning，OBL）［16］，有效保證了初始種群的均勻性；使用精英反向學習策略擴大在精英反向解所在區(qū)域內的搜索，增強全局搜索能力，并引入正弦余弦算法（Sine Cosine Algorithm，SCA）［17］，對追隨者位置更新進行優(yōu)化，增強種群多樣性，有利于算法跳出局部最優(yōu)和快速收斂；對警戒者數(shù)量進行線性遞減，平衡算法全局和局部搜索能力；當算法陷入停滯時，采用高斯游走策略幫助算法跳出局部最優(yōu)。最后通過15 個基準測試函數(shù)驗證了CSSA 的優(yōu)越性。同時在威脅環(huán)境下進行航跡規(guī)劃仿真，并與PSO、SSA、WOA、BSO、GWO等對比，仿真結果驗證了所改進算法的有效性。

1 麻雀搜索算法

SSA 主要模擬了麻雀覓食的過程。麻雀覓食過程是發(fā)現(xiàn)者-跟隨者模型的一種，同時還疊加了偵查預警機制。麻雀中容易找到食物的個體作為發(fā)現(xiàn)者，其他個體作為跟隨者，同時種群中選取一定比例的個體進行偵查預警，如果發(fā)現(xiàn)危險則放棄食物，安全第一。由文獻［13］可知，SSA 是一種優(yōu)于GWO、PSO、引力搜索算法（Gravity Search Algorithm，GSA）等算法的一種新的群智能優(yōu)化算法。

SSA 算法中有發(fā)現(xiàn)者、追隨者以及警戒者，分別按照各自規(guī)則進行位置更新，更新規(guī)則如下：

其中：t為當前代數(shù)表示在t+1 代第i只麻雀的適應值；itermax是最大迭代數(shù)；ξ∈(0，1)是一個隨機數(shù)；R2表示警戒值；ST表示安全閾值；q是一個服從正態(tài)分布的隨機數(shù)；L是一個一行多維的全一矩陣。

其中：Xp表示被發(fā)現(xiàn)者占據(jù)的最佳位置；Xworst表示當前最差位置；A是一個各元素為1或-1的一行多維矩陣。

算法實現(xiàn)具體如下：

2 改進的麻雀搜索算法

2.1 立方混沌映射

SSA 和其他智能算法一樣，在求解復雜優(yōu)化問題時，在迭代后期種群多樣性降低，易于陷入局部最優(yōu)，導致收斂精度不高。為了提高算法全局搜索能力，避免迭代后期種群多樣性降低，考慮到混沌算子具有隨機性與規(guī)律性的特點，且能在一定范圍內不重復遍歷所有狀態(tài)，采用混沌算子初始化種群，從圖1 可以得知立方映射比Logistic 映射的均勻性要好，因此采用立方映射混沌算子。立方映射公式如下所示：

圖1 映射對比圖Fig.1 Mapping comparison diagram

初始化麻雀種群由M個d維個體組成，采用立方映射初始化麻雀種群的具體方法為：隨機產生一個每維均為-1 到1的d維向量y1作為第一個個體，之后用式（4）對第一個個體的每一維進行迭代得到剩余(M-1)個個體，最后使用式（5）將立方映射產生的變量值映射到麻雀個體上。

其中：Xlb、Xub為每個個體在各個維度上的上下邊界；Xi為實際個體變量值。

2.2 精英反向學習策略

OBL 是近年來計算智能領域出現(xiàn)的一種新策略，研究表明反向解更接近全局最優(yōu)解的概率比當前解高出50%，使用該策略能夠有效增強種群多樣性，防止算法陷入局部最優(yōu)。

精英反向學習策略（Elite Opposition-Based Learning，EOBL）則是針對OBL不一定比當前搜索空間更易搜索到全局最優(yōu)解這一問題提出的，該策略利用優(yōu)勢個體來構造反向種群，以此增強種群多樣性。

利用動態(tài)邊界來代替搜索空間的固定邊界，能夠積累搜索經驗，使生成的反向解位于逐步縮小的搜索空間，加速算法收斂。當生成的反向解位于邊界之外時，使用隨機生成的方法進行重置。如式（9）所示：

2.3 正弦余弦算法

正弦余弦算法（SCA）是利用正弦函數(shù)與余弦函數(shù)的震蕩特性進行尋優(yōu)，其優(yōu)點是收斂性好，易于實現(xiàn)。

SCA 首先隨機生成N個搜索個體，依據(jù)適應度函數(shù)計算每個個體的適應度，將適應度最好的個體記為最優(yōu)個體X*，尋優(yōu)過程中個體位置更新公式為：

2.4 改進的麻雀搜索算法

針對SSA 存在的不足，首先使用立方映射混沌算子進行種群初始化，并利用反向選擇策略生成初始反向解加入初始種群，從其中選擇最優(yōu)的N個個體作為最終的初始種群。利用精英反向學習策略對麻雀種群中的發(fā)現(xiàn)者進行選擇，以此提高發(fā)現(xiàn)者種群的質量，發(fā)現(xiàn)者作為種群中的優(yōu)勢群體，利用精英反向學習策略，能夠增強其多樣性，為較好的全局搜索奠定基礎，同時可以利用反向解引導算法跳出局部最優(yōu)，并且通過動態(tài)邊界不斷縮小搜索空間，有利于提高算法收斂速度。

另外，在保留SSA追隨者覓食和爭奪機制的基礎上，利用SCA 對其進行改進。在覓食和爭奪機制中，追隨者向最優(yōu)位置的移動是跳躍式的，這種方式雖然有助于算法后期收斂速度的提升，但是也容易導致種群在短時間內迅速聚集，降低了種群多樣性，易于陷入局部最優(yōu)。利用SCA 進行追隨者位置更迭，可以減少搜索盲點。

警戒者的存在能夠增強算法的全局搜索能力，但是其數(shù)量在迭代過程中保持不變，會導致算法后期收斂速度減慢，因此采用線性遞減的方式對警戒者數(shù)量進行控制：在算法初期，數(shù)量多，有利于全局搜索；在算法后期，減少警戒者數(shù)量，有利于算法的收斂。警戒者數(shù)量線性遞減公式如下：

其中：Num為當前警戒者數(shù)量，Numini為初始警戒者數(shù)量；t為當前迭代次數(shù)，tmax為最大迭代次數(shù)。

當算法陷入停滯時，采用高斯隨機游走策略生成新個體，以此幫助算法跳出局部最優(yōu)。位置生成公式如下：

CSSA流程如圖2所示。

圖2 CSSA流程Fig.2 Flowchart of CSSA

3 航跡規(guī)劃問題

3.1 航跡規(guī)劃原理

航跡規(guī)劃的最主要目的就是在已知飛行區(qū)域內產生一條能夠在規(guī)定時間內從起飛點（U）到達目標點（T）、且有效避開敵方威脅區(qū)域的最優(yōu)航跡。通過采用離散航跡點并將航跡點進行連線得到一條滿足約束的最優(yōu)航跡，如圖3，由于是點與點之間的連線段，需要進行航跡平滑處理，后續(xù)仿真實驗采用B樣條曲線［18］進行處理。

圖3 航跡規(guī)劃原理Fig.3 Principle of path planning

3.2 坐標系轉換

傳統(tǒng)二維航跡規(guī)劃考慮兩個方向上的變量，為簡化研究問題維數(shù)，對二維航跡規(guī)劃問題進行降維處理，以UAV起點U為坐標原點，將起點U和目標點T連線作為橫軸，垂直于線段UT作縱軸，建立新的坐標系，如圖4 所示。在圖4 中，將線段UT等分為N+1份，則轉換后的航跡點橫坐標已知，只需求解出航跡點縱坐標，將得到的橫縱坐標轉換到XOY坐標系中，即可得到所規(guī)劃航跡點，最后通過平滑曲線處理即可得到可行航跡。

圖4 坐標系轉換Fig.4 Transformation of coordinate system

3.3 B樣條曲線

B樣條曲線是貝塞爾曲線的一般化形式，公式如下：

其中：m是節(jié)點zi的個數(shù)，zi的取值范圍是{z0，z1，…，zm-1} 并且x0≤x1≤…≤xm-1；Pi是控制節(jié)點，共有m-n-1 個控制節(jié)點；Li，n表示n階的B樣條基數(shù)，公式如式（15）、（16）。

B 樣條曲線的計算成本較低，能夠控制樣條形狀，易于保證路徑連續(xù)性。而Dubins 曲線不具有曲率連續(xù)性，貝塞爾曲線穩(wěn)定性不夠，因此仿真實驗選用B 樣條曲線處理航跡平滑任務。航跡平滑效果如圖5所示。

圖5 B樣條曲線航跡平滑效果Fig.5 Effect of B spline curve path smoothing

3.4 約束函數(shù)和適應度函數(shù)

基于智能優(yōu)化算法隨機生成的種群個體不一定符合搜索空間的要求，需要建立合適的適應度函數(shù)并考慮各種約束，用來淘汰種群中不符合約束的個體，從而獲得較優(yōu)個體。靜態(tài)全局航跡規(guī)劃主要考慮UAV 的油量代價、飛行高度代價以及威脅代價；同時需要考慮到UAV 自身性能，如最大轉彎角、最大俯仰角。本文建立二維航跡規(guī)劃的目標函數(shù)，故不用考慮最大俯仰角約束。

3.4.1 油量代價

UAV 在執(zhí)行任務過程中考慮油量代價，是為了避免UAV在完成任務后沒有足夠燃油返航的問題。假定UAV 在任務中執(zhí)行恒定速率，則油量與航跡長度成正比，表示為如下代價函數(shù)：

其中：ε為油量約束和航跡長度的比值為相鄰航跡點連線段之和，航跡長度采用歐幾里得距離，Li為第i段二維航跡距離；(xi，yi)為第i個航跡點的坐標。

3.4.2 威脅代價和禁飛區(qū)約束

UAV 在執(zhí)行任務時會遇到敵方的防空系統(tǒng)，其中包括探測雷達、防空高炮、地空導彈等威脅，將上述威脅在二維平面上近似看作一個個圓形區(qū)域，探測范圍或打擊范圍作為其半徑，規(guī)定UAV不能通過圓形區(qū)域。

采用如下方法判斷是否穿過威脅區(qū)：

1）分別計算兩相鄰航跡點與威脅源圓心距離D1和D2。

2）情況一：D1、D2有一個或兩者都小于威脅源半徑r，則穿過該威脅區(qū)，如圖6（a）。

3）D1、D2均大于威脅源半徑r，則計算威脅源心和兩航跡點連線距離D3。

4）情況二：若D3≥r，則不穿過該威脅區(qū)，如圖6（b）；若D3＜r，則計算威脅源圓心到相鄰航跡點連線段中點距離D4。

5）情況三：D4≥r，則穿過威脅區(qū)，如圖6（c）。

圖6 威脅區(qū)穿越判斷Fig.6 Judgment of crossing threatened zone

3.4.3 最大轉彎角約束

由于UAV 性能限制，實際飛行的最大轉彎角不能無限制［19］，同時在轉彎過程中，無人機會稍微偏離規(guī)劃的航跡，此時航跡曲率就要被考慮，所以要求生成的相鄰航跡段間的夾角不能超過最大轉彎角，在仿真實驗中規(guī)定最大轉彎角為60°。

3.4.4 最大航程約束

假設UAV 執(zhí)行任務后需要原路安全返回基地，那么UAV攜帶燃油要能夠進行往返飛行，設定最大航程為550 km。

綜上，航跡規(guī)劃目標函數(shù)模型如下：

其中：σ為威脅懲罰系數(shù)，即生成航跡不滿足約束時，代價會劇增，在仿真實驗中設σ為10E+5。

4 仿真與驗證

4.1 算法測試

為了驗證改進算法的先進性，分別采用PSO、BSO、WOA、GWO、SSA 和CSSA 對測試函數(shù)進行求解，測試函數(shù)如表1 所示。上述實驗均在Intel Core i5 CPU，2.50 GHz，16 GB 內存，Windows 10（64 位）的測試環(huán)境中進行，并采用Matlab R2016a軟件編寫。在測試中，將各算法的種群規(guī)模設為100，迭代總數(shù)設為500，各個測試函數(shù)的維度如表1所示。

表1 測試函數(shù)Tab.1 Test functions

分別對各個測試函數(shù)進行30次仿真實驗，統(tǒng)計30次實.得到的平均值、標準差，如表2所示。

表2 算法測試結果比較Tab.2 Comparison of algorithm test results

其中F1～F7為單峰測試函數(shù)，主要用于測試算法的開發(fā)能力，分析這七個單峰函數(shù)求解情況可知，對于F1、F3、F4、F6四個測試函數(shù)，CSSA 尋優(yōu)效果最佳，均能穩(wěn)定得到全局最優(yōu)解；對于F2、F5兩個測試函數(shù)，CSSA 雖不能穩(wěn)定收斂到最優(yōu)解，但收斂效果和收斂精度優(yōu)于對比算法，且F5作為一種極其復雜的病態(tài)測試函數(shù)，其全局最優(yōu)解在一條香蕉型的峽谷上，谷中曲面上的最速下降方向與到達全局最優(yōu)值的方向近似垂直，且山谷內的值變化不大，大部分優(yōu)化算法很難找到全局最優(yōu)解，而CSSA 在求解F5時明顯優(yōu)于其他算法；對于F7測試函數(shù)，CSSA 與其他對比算法差別不大。從整體上看，對于單峰測試函數(shù)，CSSA尋優(yōu)效果優(yōu)于其他算法，且穩(wěn)定性較好。

F8～F15為多峰測試函數(shù)，其中F12～F15是固定維度函數(shù)。該類測試函數(shù)有多個局部最優(yōu)解，智能優(yōu)化算法在求解時易于陷入局部最優(yōu)，因此多峰測試函數(shù)主要用于測試算法的探索能力。在求解F8時，六種算法對于該函數(shù)尋優(yōu)效果均不理想，GWO 最優(yōu)；在求解F9時，CSSA 優(yōu)于三種算法；在求解F10、F11時，優(yōu)于其他對比算法；在求解F12時，六種算法收斂效果相近，但CSSA 穩(wěn)定性更好；在求解F13時，CSSA 和PSO 效果最佳，優(yōu)于其余四種算法；在求解F14時，CSSA 效果僅次于PSO，優(yōu)于其余四種算法；在求解F15時，CSSA、SSA、WOA 和GWO均能收斂到全局最優(yōu)解，但CSSA穩(wěn)定性更好。以上統(tǒng)計數(shù)據(jù)表明，CSSA整體尋優(yōu)能力優(yōu)于PSO、WOA、BSO、GWO和SSA。

為進一步分析六種算法的尋優(yōu)能力，根據(jù)表2 的均值對算法在各個測試函數(shù)中的結果進行比較排序，若相等則比較標準差，結果如表3 所示，表最后一行為各算法的平均排序結果。CSSA 排序第一，六個算法中的尋優(yōu)性能最強，且明顯優(yōu)于SSA。其余算法排序為：SSA、PSO、WOA、GWO和BSO。

表3 算法結果排序Tab.3 Sorting of algorithm results

為驗證CSSA 的穩(wěn)定性與收斂性，列出了F1、F3、F5、F9、F11和F14六個測試函數(shù)的箱式圖和迭代收斂曲線圖。

圖7 為6 種算法獨立運行30 次求解6 個測試函數(shù)得到的箱式圖，由圖知CSSA在求解時，均未出現(xiàn)異常點，并且收斂值的分布相對其余四種算法更加集中，明顯優(yōu)于對比算法，說明CSSA在求解問題時魯棒性更強。

圖7 不同算法在6個基準測試函數(shù)上的收斂箱式圖Fig.7 Convergence box plots of different algorithms for six benchmark test functions

圖8 為各算法收斂曲線圖，實線為CSSA。在求解F1、F3、F5、F13時，CSSA 收斂速度優(yōu)于對比算法；對于F9、F11，CSSA 收斂速度優(yōu)于PSO、WOA、BSO、GWO 四種算法。由于F5的全局最優(yōu)解較難求得，因此迭代后期收斂速度較慢。整體上CSSA收斂速度優(yōu)于其他五種算法，且具有較好的收斂速度與收斂精度。

圖8 各算法收斂曲線Fig.8 Convergence curves of different algorithms

4.2 仿真計算與驗證

航跡規(guī)劃問題實質上是一個非確定性多項式求解問題，運用CSSA求解航跡規(guī)劃問題即用CSSA對目標函數(shù)進行求解尋優(yōu)。麻雀種群代表航跡，每一只麻雀代表一條可能航跡，每只麻雀的維數(shù)代表航跡點的個數(shù)，每只麻雀的各維數(shù)值即為航跡點坐標值，麻雀個體適應度即為目標函數(shù)值，目標函數(shù)由代價函數(shù)和約束函數(shù)構成，麻雀種群中發(fā)現(xiàn)者是當前目標函數(shù)值較優(yōu)個體，跟隨者是當前目標函數(shù)值較差個體，通過對發(fā)現(xiàn)者和跟隨者位置的更新，來得到麻雀種群的最優(yōu)位置，進行若干次迭代尋優(yōu)后，返回最優(yōu)解即為所求最優(yōu)航跡。

仿真實驗環(huán)境為：Intel Core i5 CPU，2.50 GHz，16 GB 內存，Windows 10（64位）。

航跡規(guī)劃模型參數(shù)設置如下：戰(zhàn)場空間為xmax=100 km，ymax=100 km，航跡節(jié)點數(shù)Num=20，最大轉彎角為60°，最大航程550 km，UAV 起點為（1 km，1 km），目標點為（95 km，90 km），威脅源參數(shù)如表4所示。

表4 威脅源參數(shù)Tab.4 Threat parameters

分別使用PSO、SSA、以及CSSA 對靜態(tài)航跡規(guī)劃模型式（19）進行求解，進而得到所需航跡。算法種群規(guī)模設置為100，每一個種群即為一條航跡，最大迭代數(shù)量為100，進行50次仿真實驗。圖9（a）～（c）分別為CSSA 規(guī)劃航跡、SSA 算法規(guī)劃航跡以及PSO 算法規(guī)劃航跡，圖10 為三種算法航跡規(guī)劃迭代收斂曲線。仿真實驗數(shù)據(jù)如表5所示。

表5 威脅環(huán)境下算法效率對比Tab.5 Comparison of algorithm efficiency under threat environment

由圖9（a）～（c）比較可知，CSSA規(guī)劃的航跡優(yōu)于PSO算法和SSA 算法所規(guī)劃航跡，CSSA 規(guī)劃的航跡能夠貼近威脅飛行，減少航跡代價。

圖9 三種算法航跡圖Fig.9 Path charts of three algorithms

由圖10 可知CSSA 在第50 代左右開始收斂，SSA 在第60代左右開始收斂，PSO在15代就開始收斂，說明PSO算法收斂較快，但CSSA 雖然收斂速度前期慢于PSO，但后期能夠穩(wěn)定收斂到最優(yōu)值，且CSSA收斂速度快于SSA。

圖10 三種算法迭代曲線對比Fig.10 Comparison of iterative curves of three algorithms

表5 表明CSSA 得到的平均適應值和最小適應值都低于PSO 算法和SSA 算法，并且能夠穩(wěn)定對航跡規(guī)劃模型進行求解，從而得到一條代價最優(yōu)、滿足約束的安全可行航跡。

5 結語

本文提出利用改進麻雀搜索算法來解決UAV 航跡規(guī)劃問題。麻雀搜索算法通過麻雀的搜尋食物與反捕食及位置更新來搜索最優(yōu)解，將立方映射混沌算子、反向學習策略和正弦余弦算法引入到基本麻雀搜索算法中，采用多樣改進策略，增加種群多樣性，平衡算法的開發(fā)與探索能力，避免麻雀搜索算法陷入局部最優(yōu)，從而找到全局最優(yōu)解。函數(shù)測試表明，改進算法在求解質量上有明顯提高，航跡規(guī)劃仿真結果也表明，基于改進麻雀搜索算法的航跡規(guī)劃能夠有效跳出局部最優(yōu)，并且提高計算速度，穩(wěn)定地規(guī)劃出一條可行高效的UAV 飛行航跡。