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

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

0 引言

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

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

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

1 麻雀搜索算法

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

麻雀種群中的發(fā)現(xiàn)者的位置更新公式為：

(1)

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

(2)

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

(3)

2 改進的麻雀搜索算法

2.1 Circle混沌映射優(yōu)化初始種群

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

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

(4)

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

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

圖1 Circle混沌映射分布圖

2.2 螢火蟲擾動策略

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

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

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

(5)

式中：I0是每個個體螢火蟲的目標(biāo)函數(shù)值，即最大熒光亮度，當(dāng)I0值越大時螢火蟲適應(yīng)度值越優(yōu)；γ為光強吸收系數(shù)，該系數(shù)隨著距離的增加、傳播媒介的吸收而逐漸變?。籸mn=|Xm-Xn|為第m只和第n只各螢火蟲間的距離。

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

(6)

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

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

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

(7)

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

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

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

1)系數(shù)初始化。設(shè)置種群數(shù)量、最大迭代次數(shù)、發(fā)現(xiàn)者和預(yù)警者比例、預(yù)警值等。

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

3)計算適應(yīng)度值函數(shù)，比較后得到最優(yōu)和最差的適應(yīng)度值的麻雀信息。

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

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

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

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

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

3 無人機三維航路規(guī)劃建模

3.1 任務(wù)環(huán)境建模

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

(8)

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

(9)

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

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

3.2 約束條件設(shè)置

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

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

(10)

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

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

(11)

3)最大轉(zhuǎn)彎角。無人機的自身性能也受轉(zhuǎn)彎角代價的限制，轉(zhuǎn)彎角度只能在預(yù)設(shè)的最大拐角范圍內(nèi)完成無人機的姿態(tài)調(diào)整[13]。轉(zhuǎn)彎代價函數(shù)為：

(12)

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

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

(13)

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

H≥Hmin

(14)

3.3 航跡代價指標(biāo)

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

Jmin=k1L1+k2L2+k3L3

(15)

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

4 仿真實驗與分析

4.1 實驗環(huán)境與參數(shù)設(shè)置

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

4.2 測試與分析

4.2.1 算法性能測試

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

表1 標(biāo)準(zhǔn)函數(shù)測試表

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

表2 各算法優(yōu)化對比計算結(jié)果

4.2.2 仿真結(jié)果及分析

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

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

圖2 平均適應(yīng)度值曲線

圖3 各算法最短路徑規(guī)劃對比仿真圖

表3 各算法路線統(tǒng)計表

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

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

5 結(jié)語

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