基于多群體改進螢火蟲算法的UCAV協(xié)同多目標分配

王永泉, 羅建軍

現(xiàn)代戰(zhàn)爭中，隨著戰(zhàn)場環(huán)境和戰(zhàn)術(shù)任務(wù)日趨復(fù)雜，無人作戰(zhàn)飛機(unmanned combat aerial vehicle，UCAV)協(xié)同作戰(zhàn)已成為未來信息化戰(zhàn)爭發(fā)展必然趨勢[1]，多機型無人機協(xié)同使用，將在整個作戰(zhàn)過程中發(fā)揮重要的作用[2]。合理分配兵力資源以獲取最大的打擊效果是發(fā)揮UCAV協(xié)同攻擊效果的關(guān)鍵[3]。

目前，學者們陸續(xù)提出了UCAV協(xié)同攻擊目標分配算法，對UCAV協(xié)同攻擊實戰(zhàn)應(yīng)用具有一定意義。文獻[4]通過運用整數(shù)線性規(guī)劃法，給出了目標分配最優(yōu)方案，但是算法模型復(fù)雜，計算量較大。文獻[5]在博弈論基礎(chǔ)上，提出了基于博弈論的目標分配算法，但是算法實時性值得考慮。文獻[6]基于動態(tài)任務(wù)分配問題，提出一種改進的混合再次分配策略，但該方法本質(zhì)上還屬于靜態(tài)多目標分配范疇。隨著智能啟發(fā)式計算技術(shù)的發(fā)展，智能優(yōu)化算法已開始應(yīng)用于UCAV協(xié)同攻擊目標分配問題中，并提供了新的研究思路[1]。

螢火蟲優(yōu)化(glowworm swarm optimization，GSO)[7]算法源自于自然界中螢火蟲飛行的生物學現(xiàn)象，具有運算速度快、容易實現(xiàn)、調(diào)節(jié)參數(shù)少等特點[8]，并被成功應(yīng)用于復(fù)雜函數(shù)優(yōu)化及工程技術(shù)領(lǐng)域中。本文在分析協(xié)同多目標分配問題的基礎(chǔ)上，重新設(shè)計螢火蟲離散編碼方式，并給出適合離散編碼的螢火蟲更新策略。對于基本GSO收斂效率不高的缺陷[8]，提出具有多群體性的改進螢火蟲優(yōu)化(multi-intelligence improved glowworm swarm optimization，MIGSO)算法：引入局部搜索及全局信息交換機制，并將螢火蟲優(yōu)化算法與混合蛙跳算法融合，實現(xiàn)多智能群體共同進化。最后，利用MIGSO算法求解UCAV協(xié)同多目標分配數(shù)學模型，進而得到最優(yōu)分配方案。

1 UCAV協(xié)同多目標分配數(shù)學模型

本文以UCAV執(zhí)行空對地打擊任務(wù)為背景，并已通過偵察手段獲取藍方目標信息。設(shè)紅方共有m架UCAVU={Ui,i=1,2,…,m} (Ui表示第i架無人機)，藍方共有m個目標T={Tj,j=1,2,…,n} (Tj表示第j個目標)。設(shè)oij為決策變量，oij=1表示目標Tj分配給Ui；oij=0表示目標Tj不分配給Ui。UCAV協(xié)同攻擊目標分配以作戰(zhàn)效能取得最優(yōu)為目標，而收益指標、消耗指標及航程指標是評價作戰(zhàn)效能的主要指標[9]。

定義1 收益指標 當UCAV協(xié)同攻擊全部目標后，紅方無人機獲得價值Ewin最大。

(1)

式中：Pij表示Ui攻擊Tj時的殺傷概率,Qj表示Tj的價值。

定義2 消耗指標 當UCAV協(xié)同攻擊全部目標后,紅方無人機消耗價值Eloss最小。

(2)

式中：Wij表示Ui攻擊Tj時的生存概率,Vi表示Ui的價值。

定義3 航程指標 當UCAV協(xié)同攻擊全部目標后,紅方無人機總航程D最小。

(3)

式中：Dij表示Ui攻擊Tj時飛行航程。

定義4 目標函數(shù) UCAV協(xié)同多目標分配目標函數(shù)f(xij)定義為:

maxf=ω1·Ewin-ω2·Eloss-ω3·D

(4)

式中：ω1、ω2、ω3為權(quán)重系數(shù),分別反映了不同指標重要程度。

約束條件:

2 多群體性的改進螢火蟲(MIGSO)算法

2.1 基本螢火蟲優(yōu)化(GSO)算法及改進

lk(t)=(1-ρ)lk(t-1)+γf[Xk(t)]

(5)

式中：ρ∈(0,1)為熒光素揮發(fā)因子,γ∈(0,1)為熒光素更新率。螢火蟲位置采用輪盤賭的方式進行,其可以描述為:

(6)

(7)

(8)

式中：β為決策范圍更新率,Nt為螢火蟲數(shù)目閥值,|Nk(t)|為領(lǐng)域集內(nèi)螢火蟲數(shù)量。

與其他智能算法一樣,基本GSO同樣存在收斂精度低、容易陷入局部最優(yōu)的缺陷。本文借鑒混合蛙跳算法(shuffled frog leaping algorithm,SFLA)[10]族群劃分思想,將螢火蟲群體劃分成規(guī)模相同的子族群(如圖1所示),螢火蟲首先在子族群中進行一定次數(shù)局部搜索,然后參與整個種群信息交流。局部迭代和全局信息交換提高了GSO收斂效率。螢火蟲種群劃分子族群方法為:將S只螢火蟲f[Xk(t)]降序排列,并均分到Z個族群中,每個螢火蟲族群的螢火蟲數(shù)為Q,設(shè)Ei表示第i個族群,有:

Ei(t)={Xr+Q(i-1)(t)∈S|1≤i≤Q}

(9)

圖1 GSO子族群劃分機制

2.2 混合蛙跳算法(SFLA)

SFLA也是一種基于群體智能的啟發(fā)式計算技術(shù),具有粒子群算法及Memetic算法的優(yōu)點[10]。SFLA工作過程可以描述為:隨機生成F只青蛙群體Pt={X1(t),…,Xk(t),…,XF(t)},k=1,2,…,F,第k只青蛙位置Xk(t)={xk1(t),xk2(t),…,xkn(t)}(n為目標函數(shù)維數(shù))。按函數(shù)適應(yīng)度值f[Xk(t)]將青蛙降序排列,并均分到M個族群中,每個族群的青蛙數(shù)為N。設(shè)Ej表示第j個族群,有:

Ej={Xj+M(l-1)(t)∈Pt|1≤l≤N},1≤j≤M

(10)

SFLA對每個族群中函數(shù)適應(yīng)度值最差的解Xw(t)按(11)式更新:

Xnew(t)=Xw(t)+r·[Xb(t)-Xw(t)]

(11)

式中：r∈[0,1]為隨機數(shù),Xb(t)為族群中適應(yīng)度最好的解。如果Xnew(t)位置優(yōu)于Xw(t),則用Xnew(t)替代Xw(t);否則用青蛙群體中最好的解Xg(t)代替Xb(t)重新執(zhí)行更新策略(11)式,若Xnew(t)仍然不能優(yōu)于Xw(t),則隨機生成青蛙取代Xw(t)。所有族群重復(fù)執(zhí)行局部搜索過程,直到滿足一定的搜索次數(shù)為止。

當所有族群完成局部搜索后,更新群體最優(yōu)解,然后青蛙粒子重新混合,再次劃分族群,并執(zhí)行局部搜索,直到滿足終止條件為止。

2.3 具有多智能群體的MIGSO

GSO將熒光素交流限制在領(lǐng)域集空間內(nèi),使得螢火蟲群體劃分成分為若干聚集區(qū)域,一定程度上降低了算法陷入局部最優(yōu)極值的概率,但是具有很強熒光素的螢火蟲只能對其領(lǐng)域集內(nèi)的其他個體產(chǎn)生作用,與其他的螢火蟲無法進行交流,導(dǎo)致個體最優(yōu)信息無法在群體內(nèi)傳遞,限制了算法收斂速度。SFLA具有實現(xiàn)容易、運算速度快、尋優(yōu)能力強等特點,但是對反饋信息利用不足,求解精度相對較低。

為了提高GSO跳出局部極值的能力,本文將GSO與SFLA融合,融合的方法是將種群劃分成規(guī)模相同的2個種群:GSO群和SFLA群。2個種群獨立執(zhí)行各自的搜索操作,2個種群在每次迭代結(jié)束后進行最優(yōu)信息交流,即當2種算法完成t次全局迭代后,GSO算法得到的最優(yōu)解為XGSO(t),SFLA得到的最優(yōu)解為XSFLA(t),比較兩者的目標函數(shù)值,若f[XGSO(t)]≥f[XSFLA(t)],則用XGSO(t)代替XSFLA(t)來引導(dǎo)青蛙的進化方向,否則用XSFLA(t)代替XGSO(t)來引導(dǎo)螢火蟲的進化方向,這樣GSO群和SFLA群在進化過程中,充分借鑒了另一群體的最優(yōu)信息,實現(xiàn)了不同種群協(xié)同進化,有效地增強了GSO尋優(yōu)能力。

2.4 基于MIGSO的協(xié)同多目標分配實現(xiàn)

GSO與SFLA算法最初主要應(yīng)用于連續(xù)函數(shù)優(yōu)化問題,由于UCAV協(xié)同多目標攻擊屬于離散問題,因此為了使得MIGSO能夠應(yīng)用于UCAV協(xié)同多目標攻擊問題中,本文對MIGSO粒子編碼方式進行了離散處理,并給出適合離散編碼的螢火蟲更新策略。

定義5 MIGSO中粒子編碼定義為Xk(t)=(xk1,…,xkl,…,xkn)T,其中xkl∈[0,m],Xk(t)∩[0,m]≠?。

例如:對于編碼A=(1,1,2,3,3,3,4,5,5),它表示當m=5,n=9時,目標1、2分配給第1架無人機,目標3分配給第2架無人機,目標4、5、6分配給第3架無人機,目標7分配給第4架無人機,目標8、9分配給第5架無人機。

對于離散型螢火蟲編碼方式,如果仍然采取(6)式及(11)式進行更新,則會產(chǎn)生大量不符合要求的解,嚴重降低了算法求解速度,因此本文給出了一種適合離散編碼的MIGSO粒子更新策略,具體更新策略如下:

Xk(t+1)=Xk(t)+D

(12)

(13)

2.5 MIGSO算法流程

MIGSO算法流程可以描述為:

∥初始化

1)t←0,k←0,l←0,i←0;

2) 相關(guān)參數(shù)和系數(shù)設(shè)置;

3) 設(shè)定最大循環(huán)次數(shù)Tmax,Tlocal;

4) 隨機生成螢火蟲初始群體,并均分成GSO群體和SFLA群體;

While (t≤Tmax) do

{

6) 根據(jù)(9)式和(10)式分別對2種群進行種群劃分;

∥2種群進行局部搜索

While (k≤Tlocal) do

{

While (i≤Q) do

{

7) GSO種群內(nèi)螢火蟲根據(jù)(5,8,12,13)式更新;

8)i←i+1

}

While (l≤m) do

{

9) SFLA種群內(nèi)青蛙根據(jù)(12)式、(13)式更新;

10)l←l+1

}

k←k+1

}

∥種群最優(yōu)信息交換

∥螢火蟲全局信息更新

12) 更新全局最優(yōu)解Xbest(t);

13)t←t+1

}

程序結(jié)束,輸出全局最優(yōu)解。

3 仿真分析

3.1 算例仿真

為了驗證MIGSO算法有效性,對于算例A:紅方無人作戰(zhàn)飛機m=5,ri=4,藍方地面目標n=10。無人機生存概率Wij、殺傷概率Pij、目標價值Qj及無人機價值Vi如表1～4所示,由于攻擊目標比較集中,因此設(shè)Dij在[15,25]范圍內(nèi)取隨機數(shù)。

表1 UCAV生存概率Wij

表2 UCAV殺傷概率Pij

表3 目標價值Qj

表4 UCAV價值Vi

MIGSO算法參數(shù)設(shè)置:S=200,Nt=5,Q=20,l0=5,ρ=0.3,γ=0.6,ω1=0.7,ω2=0.2,ω3=0.1,β=0.08,Smax=3。在Matlab仿真平臺中,采用MIGSO算法進行仿真,進行50次試驗,最優(yōu)分配方案如表5所示,圖2給出了MIGSO收斂曲線。

表5 目標分配方案

圖2 MIGSO收斂曲線

從表5可以看出,由于U3具有較高價值且對目標殺傷概率較低,因此分配了一個目標;對于U4,其具有較強的生存能力且對目標殺傷概率較高,因此分配了3個目標,這種目標分配方案符合作戰(zhàn)實際情況。

3.2 MIGSO算法性能分析

為了進一步分析MIGSO算法性能,分別采用GSO和MIGSO算法對算例A進行仿真,分別運行50次。仿真結(jié)果如圖3所示。

圖3 MIGSO與GSO算法性能比較

從圖3可以看出,MIGSO無論在求解精度方面還是在運算時間上都要優(yōu)于GSO算法。仿真結(jié)果表明,MIGSO算法之所以能夠快速合理地給出UCAV協(xié)同多目標分配方案,是因為MIGSO采用特殊的編碼方式及螢火蟲更新策略,同時局部搜索及全局信息交換的方式有效的改善了算法求解精度,而且MIGSO采用多種群協(xié)同進化機制,通過不同種群間最優(yōu)信息共享,實現(xiàn)了協(xié)同進化,進一步提高了算法的收斂效率。

4 結(jié) 論

研究了UCAV協(xié)同多目標分配問題,針對GSO算法的不足將其與SFLA算法融合,提出了基于多群體改進螢火蟲優(yōu)化(MIGSO)算法的UCAV目標分配算法,建立了基于收益指標、消耗指標及航程指標為準則的數(shù)學模型,并將MIGSO應(yīng)用于UCAV協(xié)同多目標分配問題中,給出了算法具體流程與仿真實例。仿真結(jié)果表明,MIGSO算法可快速有效地計算出目標分配方案,且分配結(jié)果符合作戰(zhàn)實際。

參考文獻：

[1] 劉萬俊，傅裕松，翁興偉. 有人機-無人機群協(xié)同空戰(zhàn)目標分配算法[J]. 火力與指揮控制，2012，37(5)：124-127

Liu Wanjun, Fu Yusong, Wong Xingwei. Reseach on Mission Assignment Algorithm of Cooperation Air Combat for MAV and Multi-UAV[J]. Fire Control and Command Control, 2012, 37(5): 124-127 (in Chinese)

[2] 羅賀，胡小建，付超. 多無人機協(xié)同目標分配仿真系統(tǒng)設(shè)計與實現(xiàn)[J]. 系統(tǒng)仿真學報，2009，21(11)：3246-3250

Luo He, Hu Xiaojian, Fu Chao. Design of Multi-UAVs′Target Allocating Simulation System and Its Implementation[J]. Journal of System Simulation，2009，21(11)：3246-3250 (in Chinese)

[3] 程聰，吳慶憲，劉敏,等. UCAV協(xié)同攻擊多目標的任務(wù)分配技術(shù)研究[J]. 吉林大學學報:信息科學版，2012，30(6)：609-615

Ren Cong, Wu Qingxian, Liu Min, et al. Research on Task Allocation for UCAVs Cooperatively Attacking Multiple Targets[J]. Journal of Jilin University: Information Science Edition, 2012，30(6)：609-615 (in Chinese)

[4] Griggs B J, Parnell G S. An Air Mission Planning Algorithm Using Decision Analysis and Mixed Integer Programming[J]. Operations Research, 1997, 45(5): 662-676

[5] 唐傳林，杜海文，吳文超,等. 基于博弈論的多UCAV對地攻擊目標分配[J]. 電光與控制，2011，18(10)：28-31

Tang Chuanlin, Du Haiwen, Wu Wenchao, et al. Game Theory Based Target Assignment for Multiple UCAVs in Air to Ground Attack[J]. Electronics Optics and Control, 2011, 18(10): 28-31 (in Chinese)

[6] 楊尚君，王社偉，陶軍,等. 動態(tài)環(huán)境下的多UCAV 協(xié)同任務(wù)分配研究[J]. 電光與控制，2012，19(7)：32-36

Yang Shangjun, Wang Shewei, Tao Jun, et al. Multi-UCAV Cooperative Task Allocation in Dynamic Environment[J]. Electronics Optics and Control，2012，19(7)：32-36 (in Chinese)

[7] Krishnanand K N，Ghose D. Theoretical Foundations for Rendezvous of Glowworm-Inspired Agent Swarms at Multiple Locations[J]. Robotics and Autonomous Systems，2008，56(7)：549-569

[8] Huang Zhengxin, Zhou Yongquan. Using Glowworm Swarm Optimization Algorithm for Clustering Analysis[J]. Journal of Convergence Information Technology, 2011, 6(2): 78-85

[9] 葉文，朱愛紅，潘長鵬. 多UCAV協(xié)同目標分配算法研究[J]. 系統(tǒng)工程與電子技術(shù)，2010，32(1)：104-108

Ye Wen, Zhu Aihong, Pan Changpeng. Cooperation Mission Assignment Algorithm for Multi-UCAV[J]. Systems Engineering and Electronics, 2010，32(1)：104-108 (in Chinese)

[10] Deep K, Bansal J C. Mean Particle Swarm Optimization for Function Optimization. International Journal of Computational Intelligence Studies, 2009, 1(1) : 72-92