歐陽(yáng)城添， 朱東林， 王豐奇， 邱亞嫻

(江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000)

0 引言

無(wú)人機(jī)技術(shù)的飛速發(fā)展，使其在多個(gè)領(lǐng)域具有重要作用。無(wú)人機(jī)的路徑規(guī)劃是一個(gè)典型的復(fù)雜多目標(biāo)優(yōu)化問(wèn)題，在綜合考慮各種環(huán)境條件下，找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的可行或最優(yōu)的飛行軌跡。進(jìn)化算法因較好的魯棒性被廣泛用于解決路徑規(guī)劃這類問(wèn)題。

為了更好地實(shí)現(xiàn)進(jìn)化算法對(duì)無(wú)人機(jī)的路徑規(guī)劃，學(xué)者們提出了各種應(yīng)對(duì)方案。文獻(xiàn)[1]在灰狼優(yōu)化算法中引入了遺傳算法的交叉和變異算子，使無(wú)人機(jī)在復(fù)雜環(huán)境中的路徑選擇具有較好的判斷能力；文獻(xiàn)[2]提出了基于相位角編碼和突變自適應(yīng)機(jī)制的果蠅優(yōu)化算法，在不同的測(cè)試環(huán)境下，證明了改進(jìn)算法的有效性；文獻(xiàn)[3]在麻雀搜索算法(SSA)中引入了混沌策略增強(qiáng)種群的多樣性，并使用自適應(yīng)慣性權(quán)重及柯西-高斯突變策略來(lái)增強(qiáng)算法的尋優(yōu)能力，使得改進(jìn)的麻雀搜索算法具有較強(qiáng)的搜索能力，規(guī)劃的路線較為安全；文獻(xiàn)[4]將天牛須算法融合粒子群算法，使得改進(jìn)的粒子群算法在路徑規(guī)劃中的代價(jià)更小；文獻(xiàn)[5]提出一種混沌麻雀搜索算法，采用立方映射初始化種群，并引入精英反向?qū)W習(xí)及正余弦算法，增強(qiáng)局部與全局能力,最后采用非線性遞減及高斯游走策略防止算法出現(xiàn)早熟,在無(wú)人機(jī)路徑規(guī)劃中取得較好的效果。以上文獻(xiàn)雖取得不錯(cuò)的成效，但在尋優(yōu)過(guò)程中缺乏判斷能力且沒(méi)有從根本上改善原算法的尋優(yōu)機(jī)制，例如：變異策略在實(shí)際環(huán)境中僅對(duì)原位置做出局部變化，沒(méi)有從根本上平衡算法的全局與局部能力；混沌理論本身具有不確定性，因此在高維復(fù)雜環(huán)境中仍然存在陷入局部最優(yōu)的概率，導(dǎo)致穩(wěn)定性不足。

針對(duì)以上問(wèn)題，本文提出一種折射麻雀搜索算法(Refracted Sparrow Search Algorithm,RSSA)來(lái)改善路徑規(guī)劃中的安全與穩(wěn)定等問(wèn)題，麻雀搜索算法(SSA)是2020年提出的新型進(jìn)化算法[6]，在函數(shù)優(yōu)化上具有較強(qiáng)的尋優(yōu)能力，但局部搜索能力不足，因此，本文采用折射反向?qū)W習(xí)(ROBL)增大算法的搜索范圍，開(kāi)拓未知區(qū)域的搜索，再引入瘋狂算子提高算法的局部開(kāi)發(fā)能力，最后利用模擬退火(SA)算法提升算法跳出局部最優(yōu)的能力,來(lái)綜合提升麻雀搜索算法的尋優(yōu)能力，使其在路徑規(guī)劃中具有較好的尋優(yōu)手段。

1 麻雀搜索算法

麻雀搜索算法在尋優(yōu)過(guò)程中分為發(fā)現(xiàn)者、追隨者和偵察者3個(gè)行為階段。發(fā)現(xiàn)者為種群內(nèi)的其他個(gè)體提供覓食的方向，具有較好的全局搜索能力。發(fā)現(xiàn)者的位置更新算式為

(1)

式中：i為當(dāng)前迭代次數(shù)；M為最大迭代次數(shù)；Xi,j為第i只麻雀在第j維中的位置信息；α′為隨機(jī)數(shù)，α′∈(0,1]；R2和ST分別表示預(yù)警值和安全值，R2∈[0,1]，ST∈[0.5,1]；Q為隨機(jī)數(shù)且服從正態(tài)分布；L′表示元素為1的1×d矩陣。當(dāng)R2

追隨者在發(fā)現(xiàn)者的帶領(lǐng)下進(jìn)行局部搜索，適應(yīng)度較好的個(gè)體會(huì)優(yōu)先獲得食物。追隨者的位置更新算式為

(2)

式中：XP為當(dāng)前的發(fā)現(xiàn)者所占據(jù)的最優(yōu)位置；Xworst為當(dāng)前全局最差的位置；A是1×d矩陣且隨機(jī)賦值為1或-1，A+=AT(AAT)-1。i>n/2，表示沒(méi)有獲取食物或沒(méi)有足夠食物，需要飛往他處進(jìn)行覓食。

現(xiàn)實(shí)中麻雀也存在被天敵捕捉的危險(xiǎn)，因此麻雀種群中存在偵察的個(gè)體，發(fā)現(xiàn)危險(xiǎn)時(shí)會(huì)發(fā)出信號(hào)，使得發(fā)現(xiàn)者帶領(lǐng)其他個(gè)體飛向安全的地方。其具體行為算式為

(3)

式中：Xbest表示目前全局最佳的位置；β′為步長(zhǎng)控制參數(shù)，是服從均值為0且方差為1的正態(tài)分布的隨機(jī)數(shù)；K∈[-1,1]，是一個(gè)隨機(jī)數(shù)，表示麻雀移動(dòng)的方向同時(shí)也是步長(zhǎng)控制參數(shù)；fi為當(dāng)前麻雀?jìng)€(gè)體的適應(yīng)度值；fg和fw分別為當(dāng)前全局最優(yōu)和最差的適應(yīng)度值；ε為最小的常數(shù)，以避免分母出現(xiàn)零；fi>fg，表示極其容易受到捕食者的攻擊，fi≤fg，表示部分麻雀意識(shí)到了危險(xiǎn)，需要通過(guò)離開(kāi)當(dāng)前位置盡量減少它們被捕食的風(fēng)險(xiǎn)。

2 折射麻雀搜索算法

2.1 折射反向?qū)W習(xí)

反向?qū)W習(xí)(OBL)[7]是改善智能優(yōu)化算法的常用手段，通過(guò)計(jì)算當(dāng)前位置的反向解來(lái)提升算法的搜索范圍，這種方式在前期能夠使得算法的尋優(yōu)性能得到提高，但手段單一且缺乏靈活性，在后期尋優(yōu)中同樣存在陷入局部最優(yōu)的概率。為進(jìn)一步改善這種缺陷，本文采用折射反向?qū)W習(xí)(Refracted Oppposite-Based Learning,ROBL)[8-9]更新發(fā)現(xiàn)者位置，其原理是在反向?qū)W習(xí)的基礎(chǔ)之上引入光的折射定律，利用折射定律來(lái)開(kāi)發(fā)更深度的解。具體原理如圖1所示。

圖1 折射反向?qū)W習(xí)原理圖

圖1中，X軸上解的搜索區(qū)間為[lb,ub],Y軸表示法線，l與l′分別為入射光線與折射光線的長(zhǎng)度，α和β分別為入射角和折射角,O為[lb,ub]的中點(diǎn)，由圖中的幾何關(guān)系及折射率的定義可知

(4)

令h=l/l′,代入式(4)可得

(5)

將算式變形，得到折射反向解為

(6)

顯然，h=n=1時(shí)，ROBL可轉(zhuǎn)換為一般的OBL，由此可看出，一般的OBL得到的解較固定，手段單一，而ROBL則可以通過(guò)調(diào)整參數(shù)動(dòng)態(tài)獲取新解，降低算法陷入局部最優(yōu)的概率。當(dāng)優(yōu)化的問(wèn)題維度上升，ROBL算式為

(7)

式中：x′i,j為折射反向解；lbj與ubj分別為第j維空間的最小值和最大值。

2.2 瘋狂算子

在麻雀搜索算法中，追隨者的位置受發(fā)現(xiàn)者的牽制，僅在其附近進(jìn)行隨機(jī)搜索，若遇到局部極值點(diǎn)，追隨者無(wú)力跳出局部狀態(tài)，因此采用“瘋狂”的思想來(lái)降低個(gè)體出現(xiàn)早熟的現(xiàn)象。本文在追隨者位置更新算式中引入瘋狂算子[10-11]，使得追隨者的尋優(yōu)手段較為豐富，維持個(gè)體的多樣性。新的追隨者的更新算式為

(8)

式中：xcraziness通常取較小的常數(shù)，一般為0.000 1；P′與Q′分別定義為

(9)

(10)

其中：c4是服從[0,1]的均勻分布隨機(jī)數(shù)；Pcr是設(shè)定的瘋狂概率，若太小，P值為0的概率增加，因此在多次實(shí)驗(yàn)下，取0.5較為適宜。

2.3 模擬退火算法

模擬退火(Simulated Annealing,SA)算法[12]來(lái)源于固體退火原理，是一種基于概率的經(jīng)典算法。SA算法與進(jìn)化算法相結(jié)合，用于提煉進(jìn)化算法每次找到的解，利用模擬退火的退溫操作擺脫局部最優(yōu)的干擾，使得每次獲得解的質(zhì)量提高，趨向全局性[13-14]。

2.4 算法實(shí)現(xiàn)步驟

麻雀搜索算法雖有較快的收斂速度，但易出現(xiàn)早熟現(xiàn)象，為此，本文提出了一種折射麻雀搜索算法(RSSA)，引入ROBL提升算法全局視野，再使用瘋狂算子使算法的搜索變得更加細(xì)致，最后通過(guò)模擬退火算法提煉每次得到的解，使得最優(yōu)解的質(zhì)量提高。具體實(shí)現(xiàn)步驟如下。

1)初始化種群位置、數(shù)量以及迭代次數(shù)等相應(yīng)參數(shù)。

2)計(jì)算各種群的適應(yīng)度函數(shù)，得到相應(yīng)的最大值和最小值，確定最好及最差位置。

3)計(jì)算預(yù)警值，根據(jù)預(yù)警值更新發(fā)現(xiàn)者的位置。

4)根據(jù)式(7)與式(1)更新發(fā)現(xiàn)者的位置。

5)根據(jù)式(8)與式(2)更新追隨者的位置。

6)根據(jù)式(3)更新意識(shí)到危險(xiǎn)的麻雀位置。

7)執(zhí)行模擬退火操作，即

Tk+1=λTk

(11)

式中：T為溫度系數(shù)；λ為退火過(guò)程中的衰減參數(shù)。

8)增加了當(dāng)前溫度下麻雀?jìng)€(gè)體pi被選擇為全局最優(yōu)的概率算式，即

(12)

式中：Tfit表示新的適應(yīng)度值；N為麻雀?jìng)€(gè)體總數(shù)。

9)從當(dāng)前麻雀?jìng)€(gè)體pi中確定新的全局最優(yōu)值fg。

10)若未達(dá)到迭代次數(shù)，則回到2)；若達(dá)到，則進(jìn)行下一步。

11)輸出最佳位置和最小代價(jià)。

3 算法性能測(cè)試

為測(cè)試改進(jìn)算法的尋優(yōu)能力，本文選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)來(lái)驗(yàn)證，前2個(gè)為單峰函數(shù)，中間3個(gè)為復(fù)雜多峰函數(shù)，最后1個(gè)為固定維度函數(shù)，具體測(cè)試函數(shù)信息如表1所示。同時(shí)，將SSA算法、粒子群優(yōu)化(PSO)算法和灰狼優(yōu)化(GWO)算法進(jìn)行對(duì)比，為驗(yàn)證算法的可行性與新穎性，將文獻(xiàn)[15]中的混沌麻雀搜索算法(CSSA)與文獻(xiàn)[16]中的改進(jìn)麻雀搜索算法(ISSA)進(jìn)行對(duì)比。所有算法的種群數(shù)量為100，迭代次數(shù)為500，PSO算法中學(xué)習(xí)因子c1=c2=2，權(quán)重w=0.728，實(shí)驗(yàn)環(huán)境為Matlab 2018b，Windows10操作系統(tǒng)，運(yùn)行內(nèi)存為8 GiB。分別統(tǒng)計(jì)各算法的最優(yōu)值(Best)、平均值(Ave)及方差(Std)3項(xiàng)指標(biāo)，用來(lái)綜合衡量算法的尋優(yōu)能力。

表1 測(cè)試函數(shù)表

各算法尋優(yōu)結(jié)果見(jiàn)表2。由表2可看出，RSSA算法在各函數(shù)中均展現(xiàn)出較好的尋優(yōu)能力，尤其在F3～F6函數(shù)中，RSSA算法的尋優(yōu)效果與其他算法差異較大，從F1函數(shù)中可看出，RSSA算法并沒(méi)有削弱SSA算法本身的尋優(yōu)能力，由此證明了該算法的合理性。

表2 各算法尋優(yōu)結(jié)果

僅憑3項(xiàng)指標(biāo)確定改進(jìn)算法的性能具有片面性，為體現(xiàn)其合理性及公平性，通過(guò)統(tǒng)計(jì)檢驗(yàn)對(duì)改進(jìn)算法相比于其他算法的優(yōu)越性進(jìn)行評(píng)估。本文采用Wilcoxon秩檢驗(yàn)顯示每種算法是否存在顯著性差異，在5%的顯著水平下進(jìn)行實(shí)驗(yàn)，當(dāng)P<0.05時(shí)，可認(rèn)為拒絕零假設(shè)，即存在顯著性差異；當(dāng)P>0.05時(shí)，兩種算法之間的差異性不明顯，則用N/A表示。具體結(jié)果如表3所示。

表3 Wilcoxon秩和檢驗(yàn)P值

由表3中看出，RSSA算法與各算法均存在顯著性差異，僅個(gè)別算法存在性能相當(dāng)?shù)那闆r，因此進(jìn)一步驗(yàn)證了RSSA算法的有效性。

4 無(wú)人機(jī)路徑規(guī)劃

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

4.1.1 地形威脅區(qū)域

當(dāng)無(wú)人機(jī)執(zhí)行任務(wù)時(shí)，應(yīng)考慮地形起伏變化的特點(diǎn)。本文主要采取復(fù)雜函數(shù)模擬地形起伏變化的建模，具體數(shù)學(xué)模型如下

(13)

式中：x,y是地形投影在水平面上的點(diǎn)坐標(biāo)，z為水平面點(diǎn)坐標(biāo)對(duì)應(yīng)的高程；a，b，c，d，e，f，g為常系數(shù)，對(duì)數(shù)字地圖中的地表特征進(jìn)行控制。

4.1.2 障礙區(qū)域建模

為了使無(wú)人機(jī)在躲避障礙區(qū)域中能夠更直觀地在三維模型中進(jìn)行觀測(cè)，障礙區(qū)域建模主要是建立山峰模型，山峰模型采用的數(shù)學(xué)表達(dá)式為

(14)

式中：i為第i座山；hi為山的高度；z為其高程；(xi,yi)是第i座山的地理中心坐標(biāo)；xsi,ysi為控制山峰的坡度。

4.2 約束條件

無(wú)人機(jī)在實(shí)際運(yùn)行中要考慮多方面的因素，因此其約束條件主要有以下幾個(gè)方面。

4.2.1 最大長(zhǎng)度約束

無(wú)人機(jī)在任務(wù)飛行的過(guò)程中，自身燃油攜帶量是有限的，因此每次飛行總長(zhǎng)度需要受到限制。若一條路徑中有n個(gè)點(diǎn)，且最大航程為L(zhǎng)max，在路徑節(jié)點(diǎn)的第i段長(zhǎng)度可表示為L(zhǎng)i。因此整條路線的總長(zhǎng)度表示為

(15)

4.2.2 最低高度約束

在飛行過(guò)程中，低飛行高度確實(shí)能帶來(lái)許多益處，但機(jī)身不能與地面距離太近，太近也同樣存在著安全隱患，因此需選擇合適的最低高度限制。如果第i段路徑軌跡的離地最低高度為Hi，無(wú)人機(jī)最低飛行高度約束為Hmin，那么無(wú)人機(jī)飛行過(guò)程中將被要求始終滿足

H≥Hmin。

(16)

4.2.3 最大爬升角約束

爬升角度是現(xiàn)實(shí)環(huán)境中無(wú)人機(jī)進(jìn)行路徑規(guī)劃需要考慮的約束之一，因?yàn)?，無(wú)人機(jī)在遇到障礙物時(shí)需要提前做好爬升準(zhǔn)備，但是爬升角度有一個(gè)最大限制，超過(guò)此約束限制會(huì)造成無(wú)人機(jī)失速?gòu)亩l(fā)生危險(xiǎn)。角度γ滿足

(17)

4.2.4 最大轉(zhuǎn)彎角約束

在將算法用于無(wú)人機(jī)路徑規(guī)劃時(shí)，有必要考慮最大轉(zhuǎn)向角約束，轉(zhuǎn)彎角也是影響機(jī)身安全的因素之一。如果特定旋轉(zhuǎn)角度超出了無(wú)人機(jī)應(yīng)有的最大承受性能范圍，則此可選節(jié)點(diǎn)將被直接舍棄。假如旋轉(zhuǎn)角度可以滿足無(wú)人機(jī)的機(jī)動(dòng)性，則判斷其他指標(biāo)因素。最大轉(zhuǎn)彎角約束如圖2所示，其中，θ是無(wú)人機(jī)在水平面上的最大轉(zhuǎn)彎角。假設(shè)飛行路徑段i的水平面投影為Ai=(xi-xi-1,yi-yi-1)，并且其在路徑段i+1上的投影為Ai+1=(xi+1-xi,yi+1-yi)，那么無(wú)人機(jī)的最大轉(zhuǎn)彎角約束可以通過(guò)矢量Ai和Ai+1之間的角度表示。θ的計(jì)算方法如下

圖2 最大轉(zhuǎn)彎角約束示意圖

(18)

式中，‖Ai‖表示向量的模。

4.2.5 威脅區(qū)域約束

無(wú)人機(jī)在飛行過(guò)程中也會(huì)受到諸多因素的威脅，因此本文使用不同大小的圓柱體來(lái)表示威脅區(qū)域，如圖3所示。

圖3 威脅模型示意圖

無(wú)人機(jī)航跡規(guī)劃是在繞過(guò)幾個(gè)威脅區(qū)域的前提下，使無(wú)人機(jī)在最短的距離內(nèi)到達(dá)目的地。假定無(wú)人機(jī)與威脅中心之間的距離為dT，威脅區(qū)域?qū)o(wú)人機(jī)造成的損壞概率PT(dT)可以表示為

(19)

式中：dTmax表示受威脅區(qū)域影響的最大半徑區(qū)域；dTmin表示無(wú)人機(jī)飛行發(fā)生碰撞墜毀的可能性為1的半徑區(qū)域。

4.3 代價(jià)函數(shù)設(shè)計(jì)

對(duì)路徑規(guī)劃使用各算法時(shí)，代價(jià)函數(shù)被用來(lái)評(píng)價(jià)生成路徑的優(yōu)劣程度，也可作為算法種群迭代進(jìn)化好壞的依據(jù)，算法執(zhí)行的效率與質(zhì)量取決于代價(jià)函數(shù)的優(yōu)劣程度，同時(shí)也是評(píng)判路徑規(guī)劃水平的性能指標(biāo)。為了更好地對(duì)路徑質(zhì)量進(jìn)行考核，本文綜合考慮路徑的高度代價(jià)、長(zhǎng)度代價(jià)以及偏轉(zhuǎn)角大小這3個(gè)方面來(lái)構(gòu)造適應(yīng)度函數(shù)，即

Jcost=ω1Jlength+ω2Jheight+ω3Jsmooth

(20)

式中：Jcost表示路徑的總代價(jià)；Jlength，Jheight，Jsmooth分別為路徑的總長(zhǎng)度代價(jià)、總高度代價(jià)以及平滑度代價(jià)；w1，w2，w3分別為對(duì)應(yīng)權(quán)值。

4.3.1 路徑長(zhǎng)度代價(jià)

路徑長(zhǎng)度是評(píng)價(jià)路徑優(yōu)劣最重要的指標(biāo)之一，路徑越短，無(wú)人機(jī)飛行時(shí)耗能和耗時(shí)就越少。本文引入路徑長(zhǎng)度代價(jià)如下

(21)

4.3.2 高度代價(jià)

無(wú)人機(jī)的穩(wěn)定飛行高度同樣是無(wú)人機(jī)航跡規(guī)劃過(guò)程中的重要環(huán)節(jié)。相對(duì)于大多數(shù)飛行器來(lái)說(shuō)，飛行高度不應(yīng)該有大幅度的波動(dòng)。穩(wěn)定飛行高度有助于減輕控制系統(tǒng)的負(fù)擔(dān)，節(jié)省更多的燃料。故引入航跡高程代價(jià)函數(shù)如下

(22)

4.3.3 光滑度代價(jià)

無(wú)人機(jī)在轉(zhuǎn)彎時(shí)受到空氣阻力的影響，需要消耗一部分能量，同時(shí)也對(duì)機(jī)體產(chǎn)生一定的壓力，轉(zhuǎn)角越小，產(chǎn)生的壓力越大且耗能越多，同時(shí)飛行效率低，因此飛行的平滑度也是飛行代價(jià)的關(guān)鍵因素。算式為

(23)

φj=(xj+1-xj,yj+1-yj,zj+1-zj)。

(24)

4.4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證融合算法優(yōu)化無(wú)人機(jī)效果的可行性與實(shí)用性，將其與模擬退火粒子群算法(SAPSO),PSO,SSA優(yōu)化效果進(jìn)行對(duì)比，各算法參數(shù)設(shè)置如下：種群數(shù)量統(tǒng)一為100，迭代次數(shù)統(tǒng)一為400，初始溫度T為25，λ=0.99，θ=45°，β=30°，Hmin=0.3 km,實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置見(jiàn)表4。

表4 模型仿真參數(shù)

為增強(qiáng)實(shí)驗(yàn)說(shuō)服力及減小偶然事件的干擾，每種算法獨(dú)立運(yùn)行10次，統(tǒng)計(jì)各算法每次規(guī)劃路線的最小值、平均值、最差值這3項(xiàng)指標(biāo)，各算法最優(yōu)路線見(jiàn)圖4，各算法的性能指標(biāo)見(jiàn)表5，平均代價(jià)函數(shù)收斂圖見(jiàn)圖5。

圖4 各算法最短路徑規(guī)劃圖

圖5 各算法平均代價(jià)收斂圖

由圖4及表5可看出，RSSA與SAPSO算法優(yōu)化無(wú)人機(jī)的路徑最為簡(jiǎn)單且清晰，從各算法性能指標(biāo)表來(lái)看，RSSA算法比SAPSO算法具有更好的收斂精度與穩(wěn)定性，其他算法的穩(wěn)定性較差，最差代價(jià)值超過(guò)61；從圖5中可看出，RSSA算法具有較好的收斂精度，在50次迭代之前找到了一條代價(jià)最小的路徑，SSA算法找到的路線較差，復(fù)雜且代價(jià)最大。同時(shí)也驗(yàn)證了改進(jìn)算法的有效性與實(shí)用性。綜合來(lái)看，RSSA算法雖增加了內(nèi)部循環(huán)的計(jì)算代價(jià)，但沒(méi)有根本改變算法的總體結(jié)構(gòu)，且極大地改善了算法尋優(yōu)能力，因此增加的代價(jià)是值得的。

表5 各算法的性能指標(biāo)

5 結(jié)束語(yǔ)

本文針對(duì)麻雀搜索算法在尋優(yōu)過(guò)程中存在陷入局部最優(yōu)且依賴于初始化種群的缺陷，引入了基于折射原理的反向?qū)W習(xí)策略與瘋狂算子，使得搜索方式更加靈活、仔細(xì)，再融合模擬退火算法，提煉每次得到的最優(yōu)解，通過(guò)標(biāo)準(zhǔn)測(cè)試函數(shù)及無(wú)人機(jī)路徑規(guī)劃實(shí)驗(yàn)驗(yàn)證了RSSA算法的有效性及實(shí)用性，下一步需要考慮更多的約束條件，實(shí)現(xiàn)精準(zhǔn)的路線規(guī)劃。