藺文軒， 謝文俊， 張 鵬， 紀(jì)良杰

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

0 引言

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

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

1 算法原理

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

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

(1)

(2)

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

1.2 天牛須搜索算法

(3)

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

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

(4)

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

(5)

式中，σt表示t時(shí)刻天牛移動(dòng)的步長(zhǎng)。

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

(6)

每次移動(dòng)步長(zhǎng)和天牛兩須之間的距離更新算式為

(7)

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

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

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

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

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

。

(8)

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

(9)

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

Xt=Xt-1+vt

(10)

(11)

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

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

(12)

2 算法改進(jìn)

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

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

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

(13)

其速度更新項(xiàng)借鑒PSO算法思想

(14)

步長(zhǎng)更新項(xiàng)借鑒BAS算法思想

(15)

并將天牛左、右須位置更新算式進(jìn)行修正

(16)

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

(17)

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

2.2 天牛須粒子群混合算法

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

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

圖3 外層BSO流程圖

為避免算法陷入局部最優(yōu)解，在內(nèi)層循環(huán)中加入對(duì)非最優(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)位置，否則引入隨機(jī)概率P，即

(19)

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

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

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

(20)

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

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

(21)

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

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

(22)

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

(23)

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

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

表1 無(wú)人機(jī)與目標(biāo)位置坐標(biāo)

表2 無(wú)人機(jī)對(duì)各目標(biāo)執(zhí)行任務(wù)的能力與目標(biāo)價(jià)值

表3 無(wú)人機(jī)對(duì)目標(biāo)執(zhí)行任務(wù)后的生存概率

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

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

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

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

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

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

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

5 總結(jié)

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