基于果蠅優(yōu)化算法的無人機(jī)航路規(guī)劃方法

張國(guó)印，孟 想，李思照

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱150001)

0 引言

無人機(jī)靜態(tài)航路規(guī)劃是指根據(jù)已知的地圖信息和威脅因素，離線規(guī)劃出一條連接起點(diǎn)和終點(diǎn)的代價(jià)最小的全局路徑。

果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA)是潘文超在2012年提出的一種新型生物啟發(fā)算法[1]，F(xiàn)OA不僅能夠非常有效地解決復(fù)雜的優(yōu)化問題，而且擁有更少的參數(shù)和更小的計(jì)算成本[2]。自推出以來，F(xiàn)OA已被廣泛應(yīng)用于科學(xué)和工程領(lǐng)域，并與其他數(shù)據(jù)挖掘技術(shù)相結(jié)合，如優(yōu)化機(jī)器學(xué)習(xí)算法，提高人臉識(shí)別系統(tǒng)的識(shí)別率、特征選擇、培訓(xùn)風(fēng)險(xiǎn)評(píng)估模型以及預(yù)測(cè)空閑停車位的可用性[3]。

FOA算法操作簡(jiǎn)單、搜索能力強(qiáng)，但也存在后期進(jìn)化過程中過早收斂和收斂速度慢等缺點(diǎn)。為了克服這些缺點(diǎn)以及提高全局搜索能力，研究人員已經(jīng)對(duì)果蠅優(yōu)化算法提出了各種改進(jìn)和變體。IFFO算法[4]引入了一個(gè)新的參數(shù)來控制果蠅群體，使其能夠自適應(yīng)地調(diào)整搜索范圍，并引入了一種新的解生成方法來提高精度和收斂速度。在MFOA[5]中，多個(gè)子群可以同時(shí)在搜索空間中獨(dú)立移動(dòng)，并且利用子群之間的局部行為規(guī)則來探索全局最優(yōu)。所有這些改進(jìn)的FOA變種在一定程度上成功克服了原始FOA的缺點(diǎn)。然而，在收斂速度或避免陷入局部最優(yōu)方面，特別是對(duì)于處理復(fù)雜的實(shí)際問題方面，仍然有很大的改進(jìn)空間。

本文提出了一種基于果蠅優(yōu)化算法的靜態(tài)航路規(guī)劃方案。針對(duì)上述FOA的不足，在基礎(chǔ)FOA的基礎(chǔ)上，從3個(gè)方面提出改進(jìn)：① 采用混沌初始化，減少初始參數(shù)對(duì)解的影響，提高FOA的穩(wěn)定性；② 自適應(yīng)調(diào)節(jié)果蠅步長(zhǎng)，提高算法精度；③ 引入模擬退火策略，使FOA可以有效避免陷入局部最優(yōu)。使用改進(jìn)后的FOA進(jìn)行無人機(jī)靜態(tài)航路規(guī)劃，最后驗(yàn)證算法在無人機(jī)航路規(guī)劃中的合理性和有效性。

1 果蠅優(yōu)化算法介紹

果蠅優(yōu)化算法的靈感來源于果蠅的覓食行為，由于其擁有突出的嗅覺和視覺，在覓食的過程中，果蠅可以利用嗅覺器官感知空氣中漂浮的食物味道，判斷出食物的大致方向，然后向該位置飛近。隨后，其他果蠅會(huì)利用視覺器官感知最優(yōu)果蠅的位置，并向其飛去。果蠅群體的食物搜尋過程如圖1所示，整個(gè)覓食的過程就是一個(gè)不斷迭代求取最優(yōu)值的過程。

圖1 果蠅覓食過程Fig.1 Group iterative food searching process of the fruit fly swarm

根據(jù)果蠅的覓食特點(diǎn)，果蠅優(yōu)化算法大概可以分為以下3個(gè)階段。

(1) 參數(shù)和種群位置初始化

FOA的參數(shù)包含種群大小Mosp和最大迭代次數(shù)Gmax。首先，在決策空間中隨機(jī)初始化果蠅群位置(Xaxis,Yaxis)，如式(1)所示。

(1)

式中，rand()是生成[0,1]之間均勻隨機(jī)數(shù)的函數(shù)。

(2) 基于嗅覺的搜索

在基于嗅覺搜索的過程中，隨機(jī)分配果蠅個(gè)體搜索食物的距離與方向，搜索策略如式(2)所示。

(2)

式中，i=1,2,…,Mosp，random是范圍為[-1,1]之間的隨機(jī)值。

食物的準(zhǔn)確位置未知，因此需要先計(jì)算出果蠅個(gè)體與原點(diǎn)之間的距離Dist，再計(jì)算味道濃度判定值S，此值是Dist的倒數(shù)，如式(3)所示。

(3)

實(shí)際上，味道濃度的判斷對(duì)應(yīng)于決策空間中目標(biāo)函數(shù)的候選解，因此，將S帶入目標(biāo)函數(shù)，可以求出該果蠅個(gè)體此時(shí)所處位置的味道濃度，計(jì)算如式(4)所示。

Smelli=f(Si)。

(4)

(3) 基于視覺的搜索

基于視覺的果蠅群體搜索過程本質(zhì)上就是一個(gè)貪婪選擇的過程，果蠅群通過觀察上述基于嗅覺搜索過程生成的所有位置，找出氣味濃度最佳的位置并記錄該位置的下標(biāo)，如式(5)所示。

index=argmin(Smelli)。

(5)

果蠅群體會(huì)利用視覺向新位置飛去。基于視覺的搜索過程可以描述成式(6)。

(6)

最后，重復(fù)基于嗅覺和視覺的搜索過程，直到達(dá)到最大迭代次數(shù)或找到最優(yōu)解。

2 基于果蠅優(yōu)化算法的無人機(jī)航路規(guī)劃

2.1 基于B樣條曲線的航路表示

無人機(jī)無法直接實(shí)現(xiàn)“急轉(zhuǎn)彎”，直接轉(zhuǎn)換方向進(jìn)入下個(gè)航段，因此需要對(duì)存在夾角的航路進(jìn)行平滑處理，使平滑后的航路能夠滿足無人機(jī)的物理轉(zhuǎn)彎性能，即要大于無人機(jī)的最小轉(zhuǎn)彎半徑。B樣條曲線是目前應(yīng)用比較廣泛的航跡平滑算法。

一般采用二次B樣條曲線進(jìn)行航路平滑，下面詳細(xì)介紹應(yīng)用于平滑航路的B樣條曲線的曲率表達(dá)式推導(dǎo)過程[6]。每一段二次B樣條曲線參數(shù)方程如式(7)和式(8)所示。

(7)

(8)

對(duì)式(7)求導(dǎo)得到式(9)和式(10)：

(9)

(10)

式中，a=x02x1+x2，b=x1-x0，c=y0-2y1+y2，d=y1-y0。由曲線曲率公式可以得到曲率k，如式(11)所示。

(11)

曲線的曲率半徑r為曲率的倒數(shù)。當(dāng)r大于無人機(jī)最小轉(zhuǎn)彎半徑時(shí)，則認(rèn)為無人機(jī)滿足飛行約束條件。

B樣條函數(shù)具有連續(xù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，并且其曲率在轉(zhuǎn)彎點(diǎn)變化均勻，符合無人機(jī)速度和加速度連續(xù)變化的要求，生成的航路曲線更加平滑，也解決了轉(zhuǎn)彎點(diǎn)大角度控制問題。

2.2 無人機(jī)自身性能約束

(1) 最低飛行高度

無人機(jī)在進(jìn)行飛行的過程中需要保持一定海拔高度，飛行高度過低可出現(xiàn)撞擊地面的風(fēng)險(xiǎn)。采用Hmin表示物流無人機(jī)的最低飛行高度，則每一段航路的飛行高度Hi(i=1,2,…,n)，需滿足:

Hi≥Hmin。

(12)

(2) 最小航段長(zhǎng)度

最小航段長(zhǎng)度是指無人機(jī)在調(diào)整飛行姿態(tài)前必須保持的最小直線飛行距離。用Lmin表示物流無人機(jī)的最小航段長(zhǎng)度，Li(i=1,2,…,n)表示物流無人機(jī)第i個(gè)飛行航段的長(zhǎng)度，則該約束可以表示為:

(13)

其中，(xi,yi,zi)為航跡點(diǎn)i的三維空間坐標(biāo)，(xi-1,yi-1,zi-1)為航跡點(diǎn)i-1的三維空間坐標(biāo)。

(3) 最大航程約束

無人機(jī)在執(zhí)行任務(wù)時(shí)，由于物理性能、燃料量以及快件配送時(shí)效性等因素，需要對(duì)無人機(jī)的最大航程加以約束。最大航程總長(zhǎng)為每個(gè)航段長(zhǎng)度之和，用Lmax表示最大航程，則該約束可以表示為:

(14)

(4) 最大偏航角

偏航角限制也是最小轉(zhuǎn)彎半徑限制，轉(zhuǎn)彎角越小無人機(jī)就越能平穩(wěn)飛行。假設(shè)無人機(jī)允許的最大偏航角是θ，最大偏航角示意如圖2所示。

圖2 最大偏航角示意圖Fig.2 Schematic diagram of maximum yaw angle

圖中，Pi-1，Pi，Pi+1分別表示第i-1，i，i+1個(gè)航跡點(diǎn)，坐標(biāo)值分別是(xi-1,yi-1)，(xi,yi)，(xi+1,yi+1)，航路段i的水平投影為ai=(xi-xi-1,yi-yi-1)，航路段i+1的水平投影為ai+1=(xi+1-xi,yi+1-yi)，則該約束可以表示為:

(15)

(5) 最大俯仰角

最大俯仰角是指無人機(jī)在垂直方向上爬升和俯沖的性能約束限制，主要是為了降低無人機(jī)發(fā)生碰撞和墜機(jī)的風(fēng)險(xiǎn)。假設(shè)無人機(jī)允許的最大俯仰角為φ，航跡段i的縱向高度差為|zi-zi-1|，則該約束可以表示為：

(16)

2.3 航跡評(píng)價(jià)指標(biāo)

本文主要研究的代價(jià)包括航程代價(jià)、高程代價(jià)和威脅代價(jià)。代價(jià)函數(shù)表示方式為：

Fcost=ω1fL+ω2fH-ω3fT，

(17)

式中，fL為每段航路的航程代價(jià)，fH為高程代價(jià)，fT為威脅代價(jià)，ω1，ω2，ω3為各個(gè)航路代價(jià)指標(biāo)的權(quán)重，滿足ω1,ω2,ω3≥0且ω1+ω2+ω3=1，通過調(diào)整權(quán)重的取值，可以實(shí)現(xiàn)使某項(xiàng)代價(jià)指標(biāo)為航路代價(jià)的主要影響因素，體現(xiàn)航路規(guī)劃的靈活性，為綜合決策提供參考。

(1) 航程代價(jià)

航程代價(jià)需要考慮從航跡點(diǎn)到目標(biāo)點(diǎn)的飛行距離，設(shè)fL為航程代價(jià)，起始點(diǎn)S為第0個(gè)航跡點(diǎn)，某段航路共有m個(gè)航跡點(diǎn)，則該航路的航程代價(jià)可表示為：

(18)

式中，di,i+!表示兩個(gè)相鄰航跡點(diǎn)之間的距離。

(2) 高程代價(jià)

高程代價(jià)表示無人機(jī)由當(dāng)前航跡點(diǎn)飛向下一個(gè)航跡點(diǎn)處于的海拔高度所需要的做功值。無人機(jī)飛行高度越大，代價(jià)越大；反之，代價(jià)越小。設(shè)fH為高程代價(jià)，則該航路的高程代價(jià)可表示為：

(19)

式中，M為無人機(jī)在負(fù)載情況下的整機(jī)質(zhì)量，是無量綱的可變常量，hi為航跡點(diǎn)i的海拔高度，g為重力加速度，取值為10。

(3) 威脅代價(jià)

威脅代價(jià)考慮地形、天氣威脅以及禁飛區(qū)危險(xiǎn)性各代價(jià)的總和，設(shè)fT為威脅代價(jià)，共有λ個(gè)威脅，第k個(gè)威脅的中心平面坐標(biāo)為(xk,yk)，則威脅代價(jià)可表示為：

(20)

2.4 果蠅優(yōu)化算法在航路規(guī)劃中的應(yīng)用

在基于FOA做無人機(jī)航路規(guī)劃的過程中，F(xiàn)OA被用來生成連接給定起點(diǎn)和終點(diǎn)的具有最小代價(jià)函數(shù)值的B樣條曲線。

B樣條曲線的形狀由無人機(jī)起點(diǎn)和終點(diǎn)之間的一些可以自由移動(dòng)的控制點(diǎn)來決定，把曲線控制點(diǎn)的笛卡爾坐標(biāo)作為果蠅群體的食物來源。假設(shè)自定義控制點(diǎn)的數(shù)量為n，那么在規(guī)劃航路的過程中需要確定D=3n個(gè)坐標(biāo)參數(shù)，即{x1,x2,…,xD}，其中(xi,xn+i,x2n+i),i=1,2,…,n為航路曲線第i個(gè)控制點(diǎn)的三維坐標(biāo)。

設(shè)置每個(gè)果蠅的位置代表一個(gè)控制點(diǎn)的坐標(biāo)，這樣果蠅群體的所有位置都可以表示一條飛行路徑。通過FOA所得到的每條候選路徑都由代價(jià)函數(shù)來進(jìn)行評(píng)估。假設(shè)無人機(jī)飛行航路的任務(wù)空間限制在[0,Lmax]×[0,Wmax]，最大飛行高度為Hmax，在FOA第t次迭代時(shí)，第i只果蠅的位置由坐標(biāo)(Xi,1,Xi,2,…,Xi,D)和(Yi,1,Yi,2,…,Yi,D)表示，對(duì)應(yīng)的控制點(diǎn)序列由(Si,1,Si,2,…,Si,D)表示，無人機(jī)飛行代價(jià)函數(shù)作為FOA氣味濃度判斷函數(shù)。將FOA應(yīng)用于無人機(jī)路徑規(guī)劃的具體實(shí)現(xiàn)過程如算法1所示。

算法1 基于FOA的航路規(guī)劃偽代碼

3 基于改進(jìn)果蠅優(yōu)化算法的無人機(jī)航路規(guī)劃

3.1 果蠅優(yōu)化算法改進(jìn)策略

3.1.1 混沌初始化

混沌理論是指在一個(gè)完全被數(shù)學(xué)公式精確描述的確定系統(tǒng)中，即便沒有外部因素的干擾，系統(tǒng)的運(yùn)行也可能變得無法預(yù)測(cè)。混沌理論具有內(nèi)在隨機(jī)性，會(huì)產(chǎn)生與外界因素干擾完全無關(guān)的系統(tǒng)內(nèi)部自發(fā)性的自組織現(xiàn)象。混沌理論的另一個(gè)特性是初值敏感性，這種特性會(huì)對(duì)系統(tǒng)運(yùn)動(dòng)趨勢(shì)產(chǎn)生強(qiáng)烈影響，并且會(huì)使系統(tǒng)長(zhǎng)期行為變得不可預(yù)見[7]。

FOA的運(yùn)行結(jié)果高度依賴于初始條件，初始條件的微小差異將會(huì)對(duì)最終結(jié)果產(chǎn)生重大的影響，本文采用Logistic混沌映射來處理初始參數(shù)，以提高FOA的穩(wěn)定性。

Logistic映射是混沌系統(tǒng)行為的一個(gè)經(jīng)典模型，本質(zhì)上是一個(gè)時(shí)間離散的動(dòng)力系統(tǒng)，即按照式(21)進(jìn)行反復(fù)迭代。

(21)

式中，k為當(dāng)前迭代次數(shù)，μ為混沌控制參數(shù)，當(dāng)x(k)∈[0,1]并且μ=4時(shí)，上述系統(tǒng)處于完全混沌狀態(tài)，混沌變量Cx(k)可以表示為:

Cx(k+1)=4Cx(k)[1-Cx(k)]。

(22)

如果所求問題滿足xi∈[li,ui]，li和ui分別代表變量取值范圍的下界和上界，那么其與混沌變量之間可以由式(23)和式(24)進(jìn)行往返映射。

Cx(i)=(xi-li)/(ui-li)，

(23)

xi=li+Cx(i)(ui-li)，

(24)

式中，xi表示第i個(gè)混沌變量經(jīng)過混沌映射變換后轉(zhuǎn)換為常規(guī)變量的值。

本文基于混沌變量的遍歷性，使用logistic映射對(duì)果蠅群的初始位置進(jìn)行賦值，降低在搜索最優(yōu)解時(shí)初始條件的敏感性。具體過程如下：

步驟1：首先隨機(jī)生成3個(gè)M維向量Cx1=(x1,x2,…,xM)，Cy1=(y1,y2,…,yM)和Cz1=(z1,z2,…,zM)，任意分量取值在[0,1]之間。

步驟2：分別將Cx1，Cy1，Cz1帶入式(21)，得到Cx2，Cy2，Cz2，再將Cx2，Cy2，Cz2帶入式(22)，循環(huán)計(jì)算，直到迭代次數(shù)達(dá)到300。

步驟3：將步驟2中得到的300個(gè)混沌變量Cxi，Cyi，Czi(i=1,2,…,300)，根據(jù)式(23)映射到算法的規(guī)劃空間中，并以此計(jì)算目標(biāo)函數(shù)值，從中選取出較優(yōu)的Mosp個(gè)向量作為果蠅群的初始位置。

其中，M表示求解問題的維度，μ=4，為保證遍歷的充分性，混沌序列取值點(diǎn)數(shù)要大于等于300。

經(jīng)過上述過程的初始化后，果蠅群的初始位置相較于隨機(jī)分配具有一定的優(yōu)勢(shì)，降低了隨機(jī)初始化對(duì)果蠅群搜索最優(yōu)解的不良影響，一定程度上提高了算法的求解性能。

3.1.2 自適應(yīng)步長(zhǎng)

在基本FOA中，果蠅在迭代過程中的步長(zhǎng)是預(yù)設(shè)的固定值，若步長(zhǎng)取值較大，隨著多次迭代的完成，當(dāng)果蠅群體距離目標(biāo)越來越近時(shí)，局部搜索會(huì)有限制，會(huì)導(dǎo)致求解精度的下降；若步長(zhǎng)取值較小，雖然可以做到局部深度搜索，但是搜索的效率和速度都會(huì)大幅下降，甚至可能無法求得最優(yōu)解。因此，將果蠅群迭代過程中的固定步長(zhǎng)調(diào)整為線性遞減的自適應(yīng)步長(zhǎng)，以提高算法的精度，避免陷入局部最優(yōu)。步長(zhǎng)自調(diào)整過程如式(25)所示。

(25)

式中，stept為第t次迭代的步長(zhǎng)，Gmax為最大迭代次數(shù)，α為步長(zhǎng)調(diào)節(jié)因子，當(dāng)α取值不同時(shí)，步長(zhǎng)變化速率也不同，此處取α=0.1。當(dāng)Gmax取值100，step的初始值取1時(shí)，stept的數(shù)值變化曲線如圖3所示。

圖3 步長(zhǎng)變化曲線Fig.3 Step change curve

由圖3可知，隨著迭代次數(shù)t的增加，stept單調(diào)遞減，因此果蠅移動(dòng)的步長(zhǎng)可以隨著迭代次數(shù)的增長(zhǎng)而自適應(yīng)變小。將自適應(yīng)步長(zhǎng)變化帶入果蠅基于嗅覺的搜索過程，如式(26)所示。

(26)

綜上所述，使用自適應(yīng)策略調(diào)整果蠅在迭代過程中的步長(zhǎng)大小，可以使步長(zhǎng)隨著迭代次數(shù)的增加而減小，這樣不僅滿足算法在運(yùn)行初期時(shí)需要采用大步長(zhǎng)進(jìn)行全局搜索，又滿足在算法迭代后期需要采用小步長(zhǎng)進(jìn)行局部深度搜索，可以有效控制FOA的收斂速度，增加算法的求解精度。

3.1.3 模擬退火策略

模擬退火算法(Simulated Annealing Algorithm,SA)最早是由N.Metropolis等于1953年提出[8]，其出發(fā)點(diǎn)是模仿經(jīng)典粒子系統(tǒng)降溫的過程來尋找問題的極值，從而優(yōu)化求解過程。對(duì)于溫度T的每一個(gè)取值，都需要采用Metropolis[9]準(zhǔn)則進(jìn)行判斷，依概率決定是否跳出。

Metropolis準(zhǔn)則是SA的核心部分，通常表示為:

(27)

式中，Ej為新狀態(tài)的能量，Ei為當(dāng)前狀態(tài)的能量，在改進(jìn)算法中對(duì)應(yīng)的是相應(yīng)目標(biāo)函數(shù)。當(dāng)m>[0,1)區(qū)間的隨機(jī)數(shù)時(shí)接受跳出，否則不接受跳出。i為當(dāng)前狀態(tài)，j為新狀態(tài)，T表示溫度，則“跳出概率”p的表達(dá)式為:

(28)

當(dāng)新狀態(tài)的能量比舊狀態(tài)能量低時(shí)，跳出概率為1；當(dāng)新狀態(tài)的能量比舊狀態(tài)能量高時(shí)，不會(huì)立刻舍棄Ej，而是進(jìn)行概率判斷，將m與隨機(jī)數(shù)ε(0≤ε<1)比較，當(dāng)m>ε時(shí)，同樣跳出，否則舍棄Ej。由于Ej-Ei與T的值是變動(dòng)的，因此這個(gè)概率是一個(gè)動(dòng)態(tài)概率。

在FOA基于視覺搜索的過程中，所有的果蠅個(gè)體都會(huì)向當(dāng)前最優(yōu)個(gè)體的方向飛去，如果當(dāng)前最優(yōu)個(gè)體陷入局部極值，基本FOA沒有策略可以幫助果蠅跳出極值，果蠅將停止繼續(xù)進(jìn)化，算法尋優(yōu)過程將以失敗告終。為了解決這一問題，本文采用了模擬退火策略，結(jié)合SA策略的視覺搜索具體流程如下：

步驟1：根據(jù)FOA算法實(shí)現(xiàn)過程，保留本次迭代果蠅群中最優(yōu)味道濃度的果蠅，記為S(i)，同時(shí)記錄該果蠅的位置坐標(biāo)(Xi,Yi)，S(i)為當(dāng)前模型。

步驟2：確定初始溫度T0=S(i)/lg(5)。

步驟3：用式(25)和式(26)對(duì)當(dāng)前位置(Xi,Yi)進(jìn)行一定次數(shù)的擾動(dòng)，得到新的模型S(i)′，位置坐標(biāo)為(X′i,Y′i)。

步驟4：采用模擬退火策略，計(jì)算新舊模型的差值Δs=S(i)'-S(i)：若Δs≤0，則S(i)′被接受。若Δs>0，則計(jì)算概率p=epx(-Δs/T)，若p>ε，ε為[0,1]之間的隨機(jī)數(shù)，則S(i)′被接受，并以(X′i,Y′i)開始下一次的迭代尋優(yōu)；否則以原模型的位置坐標(biāo)進(jìn)行下一次迭代尋優(yōu)。

步驟5：利用T=T0×0.5進(jìn)行退溫操作。

由于SA有一定概率可以接受較差解，所以當(dāng)果蠅在陷入局部極值后可能跳出，部分果蠅可以飛向其他方向，這部分果蠅可能具備更強(qiáng)的全局搜索能力，搜尋到更佳的全局最優(yōu)解。因此，引入模擬退火策略在一定程度上解決了FOA容易陷入局部最優(yōu)的問題，對(duì)于求解多極值問題，引入模擬退火機(jī)制的FOA更具優(yōu)勢(shì)。

3.2 改進(jìn)果蠅優(yōu)化算法在航路規(guī)劃中的應(yīng)用

在FOA的基礎(chǔ)上，本文引入了混沌初始化、自適應(yīng)步長(zhǎng)和模擬退火三個(gè)策略，形成了基于混合策略的果蠅優(yōu)化算法，結(jié)合求取極大值問題，該算法運(yùn)行步驟如下：

步驟1：初始化算法相關(guān)參數(shù)，并采用混沌策略設(shè)置果蠅群初始位置(Xaxis,Yaxis)。初始化參數(shù)包括估果蠅種群規(guī)模Mosp，最大迭代次數(shù)Gmax，初始溫度T0，步長(zhǎng)初始值step0等。令當(dāng)前迭代次數(shù)t=0。

步驟2：遍歷每一只果蠅，依次計(jì)算果蠅個(gè)體與原點(diǎn)之間的距離Dist，味道濃度判定值S和味道濃度Smell。

步驟3：找出本次迭代過程中味道濃度最好的個(gè)體，保留味道濃度值和該個(gè)體對(duì)應(yīng)的位置坐標(biāo)。

步驟4：利用自適應(yīng)步長(zhǎng)公式對(duì)最佳位置的果蠅進(jìn)行混沌局部擾動(dòng)，依據(jù)Metropolis接受準(zhǔn)則，選取本次迭代過程中的最優(yōu)味道濃度值和下次尋優(yōu)的初始位置。

步驟5：更新全局最優(yōu)值。如果本次迭代得到的最優(yōu)值優(yōu)于全局最優(yōu)值，那么更新全局最優(yōu)值，否則保持不變。

步驟6：進(jìn)入迭代尋優(yōu)。進(jìn)行退溫操作，令k=k+1，重復(fù)步驟2～步驟5，直到尋得最優(yōu)解或者到達(dá)最大迭代次數(shù)。

前面已經(jīng)討論過基本FOA在無人機(jī)航路規(guī)劃過程中的應(yīng)用，本節(jié)將給出改進(jìn)后FOA在無人機(jī)航路規(guī)劃過程的應(yīng)用流程。基于改進(jìn)FOA在無人機(jī)航路規(guī)劃中的應(yīng)用流程如算法2所示。

算法2 基于改進(jìn)FOA的航路規(guī)劃偽代碼

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

為驗(yàn)證算法的有效性，本文在Windows10-Intel(R)Core(TM)i5-8250U CPU @ 1.60GHz 1.80GHz-16GB八核處理器-64bit PyCharm平臺(tái)上進(jìn)行仿真。將在同一場(chǎng)景下測(cè)試5種算法，包括本文提出的多策略融合FOA、基本FOA、文獻(xiàn)[4]提出的IFFO、粒子群算法(PSO)以及差分進(jìn)化算法(DE)。

4.1 實(shí)驗(yàn)參數(shù)

本文構(gòu)建10 km×10 km×0.2 km的三維空間，已知地形和威脅如圖4所示。

圖4 等效數(shù)字地圖仿真Fig.4 Equivalent digital map simulation map

仿真實(shí)驗(yàn)中對(duì)物流無人機(jī)的物理約束條件規(guī)定和航跡評(píng)價(jià)指標(biāo)權(quán)重值參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)

5種測(cè)試算法的主要參數(shù)如表2所示。為了進(jìn)行公平的比較，所有算法都使用相同的最大迭代次數(shù)作為停止標(biāo)準(zhǔn)，所有算法的種群大小都設(shè)置為50。

表2 算法控制參數(shù)

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

圖5展示的是5種算法進(jìn)行50次獨(dú)立運(yùn)行所得到的最優(yōu)路徑在xoy平面上的投影，圖6展示了5種測(cè)試算法得到的最佳無人機(jī)航路的飛行高度變化曲線。

從圖5和圖6可知，大多數(shù)算法都成功找到可以避開所有威脅區(qū)域的安全航路，但是在圖5中，可以明顯看出由DE生成的航路是一條不完整的曲線，這是因?yàn)镈E規(guī)劃的航路進(jìn)入了威脅區(qū)域。圖7展示了5條航路對(duì)應(yīng)的三維立體圖，分別對(duì)應(yīng)的是改進(jìn)FOA、基本FOA、IFFO、PSO和DE。

由圖7可知，改進(jìn)FOA可以生成具有威脅規(guī)避和地形跟隨特性的無人機(jī)航路，從而提高物流無人機(jī)的生存能力和執(zhí)行配送任務(wù)的有效性。表3展示了5條最佳航路的航程、規(guī)劃耗時(shí)以及代價(jià)值等數(shù)據(jù)結(jié)論，從中可以看出改進(jìn)FOA在5種測(cè)試算法中生成的路徑最短，基本FOA生成的路徑最長(zhǎng)，IFFO生成的航路長(zhǎng)度雖然和改進(jìn)FOA生成的航路長(zhǎng)度相近，但由圖7可以看出，IFFO多是進(jìn)行高程避障，而無人機(jī)在執(zhí)行任務(wù)時(shí)，應(yīng)盡量避免采用高程避障。

圖5 最優(yōu)航路xoy平面投影Fig.5 Plane projection of optimal route

圖6 最優(yōu)航路高程變化曲線Fig.6 Optimal route elevation change curve

(a) 改進(jìn)FOA最優(yōu)航路

(b) FOA最優(yōu)航路

(c) IFFO最優(yōu)航路

(d) PSO最優(yōu)航路

(e) DE最優(yōu)航路

表3 最優(yōu)航路數(shù)據(jù)結(jié)論

表4展示了5種算法分別獨(dú)立運(yùn)行50次的統(tǒng)計(jì)結(jié)果，分別展示了航路代價(jià)的最優(yōu)值、中位數(shù)、平均值、最差值和標(biāo)準(zhǔn)差值，每一項(xiàng)的最佳值用粗體突出。

一般來說，生物啟發(fā)算法的搜索能力和穩(wěn)定性可以通過平均代價(jià)成本和標(biāo)準(zhǔn)差來反映。對(duì)比統(tǒng)計(jì)結(jié)果發(fā)現(xiàn)，改進(jìn)FOA代價(jià)的最優(yōu)值、中位數(shù)、平均值和最差值在5種算法中都是最小的，這表明改進(jìn)FOA具有強(qiáng)大的尋優(yōu)性能。雖然DE在5種算法中擁有最小的標(biāo)準(zhǔn)差，但是由圖5和圖7(e)可以看出，DE算法規(guī)劃的航跡穿越了障礙物，該算法并沒有找到安全可行的航路。因此，在所有能得到安全航路的算法中，改進(jìn)FOA也擁有最小的標(biāo)準(zhǔn)差值，這進(jìn)一步證明了改進(jìn)FOA的高魯棒性。總之，在有效性和魯棒性方面，改進(jìn)FOA的性能明顯優(yōu)于其他4種算法。

表4 算法性能比較

5 結(jié)論

將FOA應(yīng)用于無人機(jī)靜態(tài)航路規(guī)劃中，并提出了FOA的改進(jìn)版本。本文提出的改進(jìn)FOA，從果蠅群位置的初始化、搜索步長(zhǎng)以及跳出局部最優(yōu)三方面對(duì)FOA進(jìn)行了改進(jìn)，成功解決了復(fù)雜地形和威脅環(huán)境下無人機(jī)靜態(tài)航路規(guī)劃問題。所提出混沌初始化策略增強(qiáng)了FOA在搜索能力方面的性能，自適應(yīng)步長(zhǎng)策略有助于FOA在收斂過程中實(shí)現(xiàn)高性能，模擬退火策略避免了FOA容易陷入局部最優(yōu)的問題，本文給出的仿真實(shí)例說明了改進(jìn)后FOA在無人機(jī)靜態(tài)航路規(guī)劃應(yīng)用中具有較強(qiáng)的魯棒性和有效性。