基于群體智能算法的無人機協(xié)同搜索

藺文軒， 謝文俊， 張 鵬， 紀良杰

(空軍工程大學(xué)，西安 710000)

0 引言

無人機參與作戰(zhàn)所執(zhí)行的任務(wù)具有高危險性和復(fù)雜性的特點，且單體無人機載荷小、執(zhí)行任務(wù)的魯棒性差，故無人機集群作戰(zhàn)成為無人機參與戰(zhàn)爭的主要作戰(zhàn)形式[1]。在無人機集群作戰(zhàn)過程中，如何將作戰(zhàn)任務(wù)適當?shù)胤峙浣o每架無人機是保證無人機集群高效、有序完成作戰(zhàn)任務(wù)的必要保證，所以無人機集群作戰(zhàn)任務(wù)分配是目前研究的重點和熱點。

無人機集群作戰(zhàn)任務(wù)分配即根據(jù)作戰(zhàn)環(huán)境的各種約束條件為無人機分配任務(wù)目標的方案。目前針對無人機集群作戰(zhàn)任務(wù)分配問題的解決方法主要為建立模型并根據(jù)模型尋優(yōu)求解。傳統(tǒng)的多無人機作戰(zhàn)任務(wù)分配模型有多車輛路由模型(MVRP)[2]、多旅行商模型(MTSP)[3]、混合線性整數(shù)規(guī)劃模型(MILP)[4]和協(xié)同任務(wù)分配模型(CMTAP)[5]等。智能優(yōu)化算法在解決任務(wù)分配問題時主要通過平衡最短求解時間和最優(yōu)分配方案進行求解，算法流程簡單，且求解質(zhì)量較高，是解決任務(wù)分配問題常用方法之一。粒子群優(yōu)化(PSO)算法憑借其算法簡單、易于實現(xiàn)的特點廣泛應(yīng)用于尋優(yōu)問題求解，但PSO算法主要適用于連續(xù)性問題，在使用PSO算法求解離散型問題時，需要對問題進行連續(xù)化處理，在完成尋優(yōu)求解后將結(jié)果離散化，即可完成離散型問題求解[6]。文獻[7]以MILP為基礎(chǔ)，根據(jù)時間、距離、角度等因素構(gòu)造了目標函數(shù)，對PSO算法改進后進行尋優(yōu)求解，加快了尋優(yōu)速度，提高了多無人機任務(wù)分配的效率，但PSO算法本身存在易陷入局部最優(yōu)解的缺陷，在解決離散型問題時尤為明顯。文獻[8]針對離散型尋優(yōu)問題，借鑒遺傳算法中的交叉變異機制，增加了粒子多樣性，提高了算法跳出局部最優(yōu)的能力。天牛須搜索(BAS)算法是一種新提出的尋優(yōu)算法，具有強大的局部尋優(yōu)能力。將天牛須搜索算法與粒子群優(yōu)化算法相融合，可以規(guī)避粒子群優(yōu)化算法的固有缺陷，適用于求解無人機集群任務(wù)分配問題。

1 算法原理

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法通過模擬鳥類運動時個體信息共享的方式實現(xiàn)對目標問題的求解。算法的主要內(nèi)容為：假設(shè)在多維搜索空間中，存在數(shù)量為N的粒子群，每個粒子的位置及速度分別表示為Xi={Xi1,Xi2,…,Xin},Vi={Vi1,Vi2,…,Vin}，每一個粒子的最優(yōu)解表示為Pi={Pi1,Pi2,…,Pin}，n為迭代次數(shù)，全局最優(yōu)解表示為Pg={Pg1,Pg2,…,Pgn},粒子群中的每個粒子根據(jù)Pi和Pg更新自己的位置和速度，具體方法為

(1)

(2)

其中:t表示當前迭代次數(shù)；Pid表示當前更新粒子最優(yōu)解;Pgd表示當前全局最優(yōu)解；ω為權(quán)重系數(shù)；k1,k2為學(xué)習(xí)因子，主要控制粒子根據(jù)現(xiàn)有信息進行判斷，對自身位置進行調(diào)整，向潛在最優(yōu)位置移動；r1,r2為[0,1]上的隨機數(shù)。

1.2 天牛須搜索算法

(3)

式中，n表示優(yōu)化參數(shù)的維度。

天牛最優(yōu)位置的更新規(guī)則為

(4)

式中,f(x)表示天牛在位置x的適應(yīng)度值。天牛根據(jù)兩須探測的適應(yīng)度差值確定下一步的尋優(yōu)方向和位置，位置Xt的更新規(guī)則為

(5)

式中，σt表示t時刻天牛移動的步長。

天牛兩須的位置更新算式為

(6)

每次移動步長和天牛兩須之間的距離更新算式為

(7)

式中:φσ,φd分別表示步長和搜索距離的衰減系數(shù);D為距離常數(shù)。天牛須搜索算法的流程如圖1所示。

圖1 天牛須搜索算法流程圖

根據(jù)算法原理可以看出天牛須搜索算法具有計算過程簡單、自主決策性強、靈活性高的特點，滿足求解多目標優(yōu)化的算法需求，即計算快、效果好、穩(wěn)定性高等。但是在求解無人機集群任務(wù)分配問題時仍有如下缺陷。

1) 天牛在尋優(yōu)的過程中，每一次的位置更新不論結(jié)果是否更優(yōu)都會導(dǎo)致搜索步長的衰減，若天牛初始位置距離最優(yōu)位置較遠，容易導(dǎo)致天牛陷入局部最優(yōu)點。改進步長更新方式，引入步長最小值σ0，避免步長無限制衰減而陷入局部最優(yōu)。步長更新算式為

σt=φσ(σt-1-σ0)+σ0

。

(8)

2) 針對多目標優(yōu)化問題算法初始的衰減步長難以取得合適值、參數(shù)調(diào)節(jié)較為復(fù)雜的情況，可以將算式進行簡化，共用一個參數(shù)c，方便參數(shù)調(diào)節(jié)。改進后搜索步長和兩須間距離的算式為

(9)

3) 有實驗表明[10],天牛須搜索算法在處理尋優(yōu)問題時對于約束邊界附近的尋優(yōu)效果較差，針對此問題，引入二階天牛搜索，在位置更新中加入速度項，即

Xt=Xt-1+vt

(10)

(11)

式中,ω0,ω1表示上個迭代過程中速度和兩須適應(yīng)度差的權(quán)重系數(shù)。

為防止速度過大對求解產(chǎn)生影響，設(shè)定最大速度vmax=ω0·σt，速度的取值約束為

(12)

2 算法改進

2.1 基于天牛須搜索的粒子群優(yōu)化算法

粒子群優(yōu)化(PSO)算法作為一種常用的尋優(yōu)方法，在解決無人機集群任務(wù)分配問題時存在搜索精度低、易陷入局部極值的缺點。為彌補算法缺陷，在PSO算法中引入天牛須搜索算法的思想，形成一種基于天牛須搜索的粒子群優(yōu)化(BSO)算法[11],該算法結(jié)合兩種算法的優(yōu)勢，克服了PSO算法早熟的缺陷，提高了尋優(yōu)速度和精度。算法的主要描述如下。

將PSO算法中每個粒子看作天牛，天牛的位置更新算式為

(13)

其速度更新項借鑒PSO算法思想

(14)

步長更新項借鑒BAS算法思想

(15)

并將天牛左、右須位置更新算式進行修正

(16)

以PSO算法中的速度向量代替原始算法的隨機方向，步長更新和搜索距離更新算式為

(17)

BSO算法以BAS算法為基礎(chǔ)，在天牛個體之間引入信息交互機制，同時借鑒PSO算法中粒子速度對位置更新的影響，使其在每一次的迭代尋優(yōu)中可以遍歷更多的區(qū)域，提高了算法的尋優(yōu)速度。

2.2 天牛須粒子群混合算法

BSO算法能夠很好地避免陷入局部最優(yōu)的問題，但是在解決無人機集群任務(wù)分配等離散型問題時的收斂速度較慢，為了加快算法的收斂速度，提出一種天牛須粒子群混合(BSO-BAS)算法，算法分為內(nèi)外兩部分：外層BSO算法負責(zé)全局尋優(yōu)，內(nèi)層BAS算法負責(zé)局部尋優(yōu)。主要思想為：在一次迭代過程中，先使用BSO算法求解全局最優(yōu)解，在全局最優(yōu)解的鄰域內(nèi)使用BAS算法再進行局部最優(yōu)值的求解，如果發(fā)現(xiàn)適應(yīng)度更高的局部最優(yōu)值則替換掉原全局最優(yōu)值，可以加快算法的尋優(yōu)速度并提高效率，同時增強算法求解問題的實時性。算法流程如圖2、圖3所示。

圖2 內(nèi)層BAS流程圖

圖3 外層BSO流程圖

為避免算法陷入局部最優(yōu)解，在內(nèi)層循環(huán)中加入對非最優(yōu)解的保留原則，設(shè)置適應(yīng)度差值Δf

Δf=f(xk+1)-f(xk)

(18)

式中：xk+1為BAS算法尋優(yōu)一次后天牛的位置；xk為外層BSO算法給定的全局最優(yōu)位置。若Δf<0，用xk+1代替xk作為全局最優(yōu)位置，否則引入隨機概率P，即

(19)

若P>0，則接受xk+1，否則不更新全局最優(yōu)解。

3 無人機集群任務(wù)分配模型

設(shè)戰(zhàn)場環(huán)境中存在數(shù)量為NU的己方無人機和數(shù)量為NT的敵方目標，計劃使用無人機對敵方目標執(zhí)行偵察或打擊任務(wù)。無人機集合記為U={U1,U2,…,UNU}，無人機Ui在t時刻的位置坐標記為(xi(t),yi(t))；敵方目標集合記為T={T1,T2,…,TNT}，目標Tj的位置坐標記為(xj,yj)；將任務(wù)分配過程劃分為NS個階段，用s={1,2,…,NS}表示。使用決策變量xijs來表示無人機Ui在各任務(wù)分配階段對任務(wù)Tj的執(zhí)行情況，其定義為

(20)

無人機集群執(zhí)行任務(wù)的總收益用函數(shù)J表示

ω3·PS,i j-ω4·Li j)xijs

(21)

式中:PE,i j表示無人機Ui對目標Tj執(zhí)行任務(wù)的能力；Vj表示目標Tj的價值；PS,i j表示Ui對Tj執(zhí)行任務(wù)后的生存概率；Li j表示Ui對Tj執(zhí)行任務(wù)時的飛行距離;ω2,ω3,ω4為權(quán)重系數(shù)。

無人機受自身能力約束，執(zhí)行任務(wù)所需消耗不能超過自身最大能力載荷，即

(22)

每一個任務(wù)分配階段都有一架無人機去執(zhí)行一個任務(wù)，即

(23)

4 實驗仿真與分析

不同類型的無人機對不同目標執(zhí)行任務(wù)的能力和代價有所差異，為驗證所提出算法的可行性和有效性，假設(shè)在10 km×10 km的戰(zhàn)場環(huán)境中存在3架不同類型的己方無人機與7個需執(zhí)行偵察或打擊任務(wù)的敵方目標。無人機與敵方目標的位置坐標如表1所示，不同無人機對各目標執(zhí)行任務(wù)的能力和執(zhí)行任務(wù)后的生存概率分別如表2和表3所示。

表1 無人機與目標位置坐標

表2 無人機對各目標執(zhí)行任務(wù)的能力與目標價值

表3 無人機對目標執(zhí)行任務(wù)后的生存概率

在實驗仿真中，尋優(yōu)問題的維數(shù)由敵方目標數(shù)量確定，執(zhí)行某一任務(wù)的無人機序號由天牛位置確定，對天牛位置通過進一法向上取整。根據(jù)戰(zhàn)場環(huán)境初始化仿真環(huán)境大小為10 km×10 km，無人機數(shù)量NU=3，敵方目標數(shù)量NT=7，算法種群大小為10，最大迭代次數(shù)為100，權(quán)重系數(shù)ω2,ω3,ω4分別為0.2,0.4和0.4。

分別使用第1章中4種算法對無人機集群任務(wù)分配問題進行求解，將任務(wù)分配給無人機的最優(yōu)解Xui=[3,2,1,1,2,2,3]，各無人機執(zhí)行任務(wù)最佳的先后順序Xoi=[1,1,1,2,2,3,2]，即任務(wù)分配方案為：U1執(zhí)行任務(wù)T3和T4，執(zhí)行順序為T3→T4；U2執(zhí)行任務(wù)T2，T5和T6，執(zhí)行順序為T2→T5→T6；U3執(zhí)行任務(wù)T1和T7，執(zhí)行順序為T1→T7。任務(wù)分配的最大收益為Jmax=0.821。4種算法的任務(wù)分配收益變化如圖4所示。

圖4 4種算法任務(wù)分配收益變化

通過實驗仿真可以看出，BSO-BAS算法能在較少的迭代次數(shù)內(nèi)求解得到最優(yōu)的分配方案，沒有陷入局部最優(yōu)解，任務(wù)分配收益明顯高于其他3種算法。為驗證所提出算法的穩(wěn)定性，對上述實驗進行20次重復(fù)仿真，仿真結(jié)果如表4和圖5所示。

表4 仿真20次各算法結(jié)果對比

圖5 4種算法20次仿真尋優(yōu)結(jié)果

通過20次仿真的結(jié)果可以看出，本文提出的BSO-BAS算法相對于其他3種算法穩(wěn)定性更高，尋優(yōu)穩(wěn)定性達90%，且平均收益值與PSO算法相比提高了19.01%，更適用于無人機集群任務(wù)分配問題求解。

5 總結(jié)

本文設(shè)計了一種天牛須粒子群混合(BSO-BAS)算法，增強了天牛的尋優(yōu)能力，避免其陷入局部極值，提高了搜索效率和算法的實時性，彌補了PSO算法和BAS算法的缺陷。通過實驗仿真驗證了該算法在解決無人機協(xié)同搜索任務(wù)分配問題時具有穩(wěn)定性良好、求解速度更快、精度更高等特點，具有一定的理論和實踐意義。