基于改進(jìn)麻雀搜索算法的無人機(jī)航路規(guī)劃研究

王玲玲，孫 磊，丁光平，王加剛，段 譽(yù)

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

0 引言

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

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

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

1 麻雀搜索算法

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

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

(1)

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

(2)

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

(3)

2 改進(jìn)的麻雀搜索算法

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

在初始化階段，由于麻雀?jìng)€(gè)體分布不均勻，導(dǎo)致麻雀初始位置過于集中，不利于搜索出全局最優(yōu)位置。而Circle混沌映射[9]有著隨機(jī)性、均勻性和有序性等特點(diǎn)，并且不會(huì)重復(fù)所有的狀態(tài)，可以用來初始化種群，克服種群初始化時(shí)的盲目性，使得個(gè)體在搜索空間的初始位置分布更加均勻，提高麻雀種群的多樣性，為后期麻雀搜索算法尋優(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映射進(jìn)行初始化種群，相比于隨機(jī)初始點(diǎn)，Circle混沌映射值分布更加均勻，麻雀種群在空間中的搜索范圍更廣，有效改善了原來算法極易陷入局部最優(yōu)的問題。

圖1 Circle混沌映射分布圖

2.2 螢火蟲擾動(dòng)策略

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

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

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

(5)

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

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

(6)

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

螢火蟲擾動(dòng)位置更新公式為：

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

(7)

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

2.3 改進(jìn)的麻雀搜索算法流程

綜合考慮，改進(jìn)的麻雀搜索算法流程為：

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

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

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

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

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

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

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

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

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

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

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

(8)

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

(9)

式中：n表示地圖中山峰的個(gè)數(shù)；(x,y)表示山峰在平面投影所對(duì)應(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è)置

基于無人機(jī)的機(jī)動(dòng)性，主要考慮到5個(gè)約束條件：

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

(10)

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

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

(11)

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

(12)

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

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

(13)

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

H≥Hmin

(14)

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

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

Jmin=k1L1+k2L2+k3L3

(15)

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

4 仿真實(shí)驗(yàn)與分析

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

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

4.2 測(cè)試與分析

4.2.1 算法性能測(cè)試

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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