基于改進(jìn)引力搜索的武器目標(biāo)分配方法

李檳檳，何廣軍，張明亮，尤曉亮，田德偉

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

?

基于改進(jìn)引力搜索的武器目標(biāo)分配方法

李檳檳，何廣軍，張明亮，尤曉亮，田德偉

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

摘要:針對(duì)目前武器目標(biāo)分配(WTA)問(wèn)題所用引力搜索算法(GSA)存在著早熟收斂的問(wèn)題，提出了基于改進(jìn)GSA的武器目標(biāo)分配方法。該方法首先將粒子群算法(PSO)的記憶信息和群體共享信息能力引入到GSA算法之中，再將混沌搜索(CS)的思想嵌入到改進(jìn)的GSA算法之中，提出了CP-GSA算法；然后利用提出的CP-GSA算法直接求解WTA最小化問(wèn)題，進(jìn)行武器目標(biāo)分配。仿真實(shí)驗(yàn)表明：所提出的方法能夠有效解決WTA問(wèn)題，提高分配性能，在4個(gè)地面防空作戰(zhàn)單元抗擊8個(gè)來(lái)襲目標(biāo)的情況下，迭代41次即可得到最優(yōu)解，適應(yīng)度值為1.18，與枚舉法所得的最優(yōu)適應(yīng)度值相等。

關(guān)鍵詞:武器目標(biāo)分配；引力搜索算法；粒子群算法；混沌搜索

0引言

武器目標(biāo)分配(WTA)問(wèn)題是現(xiàn)代信息化戰(zhàn)爭(zhēng)中十分重要的問(wèn)題[1]，但是由于它的解空間大小隨著武器和目標(biāo)數(shù)量的增加而呈指數(shù)增加，因此是一個(gè)NP完全問(wèn)題，需要尋求快速、有效的方法以滿足實(shí)時(shí)需要。目前，智能算法被廣泛應(yīng)用到WTA的求解之中，如遺傳算法[2](GA)、蟻群算法[3](ACA)、PSO算法[4-6]和人工免疫算法[7](AIA)等。

GSA算法[8]是伊朗的克曼大學(xué)教授EsmatRashedi等人于2009年提出的新型智能算法，其全局搜索能力明顯優(yōu)于現(xiàn)有PSO算法、GA算法等仿生智能優(yōu)化算法，受到了人們的普遍關(guān)注和研究，因此，將GSA算法應(yīng)用到WTA問(wèn)題的求解之中具有較大潛力。但是，與其他進(jìn)化算法一樣，現(xiàn)有GSA算法不可避免地存在著早熟收斂問(wèn)題，影響了利用GSA算法求解WTA問(wèn)題的收斂速度和精度。本文針對(duì)上述問(wèn)題，提出了基于改進(jìn)GSA的武器目標(biāo)分配方法。

1WTA問(wèn)題模型和引力搜索算法

1.1WTA問(wèn)題模型

假設(shè)J個(gè)地面防空作戰(zhàn)單元聯(lián)合抗擊K個(gè)空中目標(biāo)，WTA問(wèn)題的求解是要確定分配給各目標(biāo)的不同作戰(zhàn)單元武器的數(shù)量，以使得所有目標(biāo)的總期望生存值最小。因此，WTA問(wèn)題可以描述求解X的最小化問(wèn)題：

(1)

式(1)中，X是由xjk,j=1,2,…,J;k=1,2,…,K構(gòu)成的矩陣；ωk為第k個(gè)目標(biāo)的威脅值；xjk≥0為第j個(gè)火力單元分配給第k個(gè)目標(biāo)的武器數(shù)；pjk為第j個(gè)火力單元對(duì)第k個(gè)目標(biāo)的殺傷概率；Vk為分配給第k個(gè)目標(biāo)的最大武器數(shù)目；Uj為給第j個(gè)火力單元可分配的最大武器數(shù)目。

求解WTA問(wèn)題，首先需要確定模型中的各個(gè)參數(shù)，其中，目標(biāo)的威脅值可以通過(guò)人工智能或者基于知識(shí)的專(zhuān)家系統(tǒng)等方法確定；武器對(duì)目標(biāo)的殺傷概率與武器射擊命中概率和目標(biāo)防護(hù)能力等有關(guān)，可通過(guò)文獻(xiàn)[7]給出的方法確定。

1.2GSA算法

假設(shè)引力系統(tǒng)有N個(gè)粒子，每個(gè)粒子的位置為：

Xi=(Xi1,…,Xid…,XiD), i=1,2,…,N

(2)

式(2)中，Xid為第i個(gè)粒子在第d維上的位置。

根據(jù)牛頓萬(wàn)有引力定理，在時(shí)刻t，第i個(gè)粒子在第d維受第j個(gè)粒子的作用力大小為：

(3)

式(3)中，Mi(t)和Mj(t)分別為粒子j和粒子i的引力質(zhì)量，G(t)是在t時(shí)刻的引力常數(shù)，可以表示為：

G(t)=G0exp(-αt/T)

(4)

其中G0=100，α=20，T是最大迭代次數(shù)。

根據(jù)適應(yīng)度函數(shù)，在引力質(zhì)量與慣性質(zhì)量相等的假設(shè)下，粒子引力質(zhì)量可定義為：

(5)

其中，fiti(t)為t時(shí)刻粒子i的適應(yīng)度值，fitbest(t)和fitworst(t)為群體最優(yōu)和最差適應(yīng)度值，對(duì)于求最小值問(wèn)題，fitbest(t)和fitworst(t)定義為：

(6)

在實(shí)際中，引力質(zhì)量一般單位化為：

(7)

因此，第i個(gè)粒子在第d維上受到總作用力是其他所有粒子作用力的總和：

(8)

根據(jù)牛頓第二定理，在時(shí)刻t，粒子i在第d維上的加速度aid(t)可以表示為：

aid(t)=Fid(t)/Mi(t)

(9)

在時(shí)刻t+1，粒子速度及位置更新為：

(10)

其中，rand是[0,1]之間的隨機(jī)數(shù)。

假設(shè)最大速度為Vmax，最小速度Vmin，在迭代的過(guò)程中，所有粒子的速度Vid(t)都應(yīng)該在[Vmin,Vmax]區(qū)間中，即滿足

(11)

引力搜索算法根據(jù)式(10)不斷更新自身所在位置，直至達(dá)到迭代終止條件，此時(shí)，粒子所在的最好位置即為問(wèn)題的解。

2基于CP-GSA算法的武器目標(biāo)分配方法

從GSA算法的基本步驟可以看出，GSA在位置更新的過(guò)程中，只有個(gè)體當(dāng)前位置在起作用，并沒(méi)有利用群體之間的信息共享，因此，學(xué)者們提出將PSO算法的位置更新方法與引力搜索算法相結(jié)合，改善了性能，但在迭代后期容易陷入局部最優(yōu)，使得算法收斂速度下降，求解精度有待進(jìn)一步提高。因此，利用早熟判斷機(jī)制，在改進(jìn)的CS算法陷入早熟收斂時(shí)，進(jìn)行混沌搜索，以跳出局部最優(yōu)，提高收斂速度和精度。

2.1PSO算法

PSO算法，也稱(chēng)為微粒群算法[9]，是由美國(guó)Kennedy和Eberhart于1995年提出的一種基于群智能的隨機(jī)搜索算法。該算法模擬鳥(niǎo)類(lèi)的覓食行為，將優(yōu)化問(wèn)題的搜索空間模擬為鳥(niǎo)類(lèi)的飛行空間，將每只鳥(niǎo)抽象成一個(gè)沒(méi)有體積和質(zhì)量的微粒，代表問(wèn)題的一個(gè)候選解，將尋找問(wèn)題最優(yōu)解的過(guò)程比作尋找食物的過(guò)程，進(jìn)而求解復(fù)雜的優(yōu)化問(wèn)題。

PSO算法的數(shù)學(xué)描述如下，假設(shè)種群規(guī)模為N，在迭代時(shí)刻t，每個(gè)粒子在D維空間中的坐標(biāo)位置可以表示為Xi=(Xi1,…,Xid,…,XiD)；粒子的速度表示為Vi(t)=(Vi1(t),…,Vid(t),…,ViD(t))。坐標(biāo)位置和速度在t+1時(shí)刻，按照下式進(jìn)行調(diào)整：

(12)

式(12)中，w(t)為慣性權(quán)值，c1和c2為加速系數(shù)，均為正實(shí)數(shù)；rand表示在[0,1]內(nèi)均勻分布的隨機(jī)數(shù)；Pi(t)表示第i個(gè)粒子經(jīng)歷過(guò)的最好位置，G(t)表示所有粒子經(jīng)歷的最好位置。

可以看出，式(12)由3部分組成，第1部分為“慣性”部分，表示粒子保持先前的速度；第2部分為“認(rèn)知”部分，表示粒子本身的思考，所以c1又稱(chēng)為認(rèn)知系數(shù)；第3部分為“社會(huì)”部分，表示粒子間的信息共享與相互合作，所以c2又稱(chēng)為社會(huì)系數(shù)。

2.2CS算法

混沌狀態(tài)一般是由確定性方程導(dǎo)出的具有隨機(jī)性的運(yùn)動(dòng)，是自然界廣泛存在的一種非線性現(xiàn)象?；煦邕\(yùn)動(dòng)看似隨機(jī)，卻是由確定的方程導(dǎo)出的，因此具有遍歷性、隨機(jī)性和規(guī)律性等特性，能在一定范圍內(nèi)按其自身規(guī)律不重復(fù)地遍歷所有狀態(tài)。因此，學(xué)者們提出利用混沌運(yùn)動(dòng)的這些性質(zhì)進(jìn)行優(yōu)化搜索，以跳出局部最優(yōu)，提高算法收斂速度。

2.3CP-GSA算法

根據(jù)上述分析，我們采用CS和PSO算法的群體信息共享改善引力搜索算法的性能，提出CP-GSA算法，使得粒子即遵守運(yùn)動(dòng)定律，又具有記憶和群體信息交流能力，在算法后期能夠快速收斂。在CP-GSA算法中，粒子位置和速度的更新方式為：

(13)

其中，Pid(t)表示第i個(gè)粒子在在第d維上經(jīng)歷過(guò)的最好位置，Gd(t)表示所有粒子在第d維上經(jīng)歷過(guò)的最好位置。

當(dāng)判定算法早熟后，利用CS算法使得算法跳出局部最優(yōu)，混沌搜索中用到的混沌方程是Logistic方程，其表達(dá)式為：

Yi+1=μYi(1-Yi)|i=1,2,…;μ∈(2,4]

(14)

其中，μ為控制變量，當(dāng)μ=4，初始值取值在[0,1]時(shí)，系統(tǒng)進(jìn)入完全混沌狀態(tài)。

混沌搜索的實(shí)現(xiàn)過(guò)程為：首先隨機(jī)產(chǎn)生一個(gè)在[0,1]區(qū)間內(nèi)的初始變量Y0=[Y01,…,Y0d,…,Y0D]；然后利用式(14)產(chǎn)生混沌序列Y1,Y2,…,YQ(Q為混沌搜索的最大迭代次數(shù))，并把混沌區(qū)間映射到優(yōu)化變量的取值區(qū)間；最后，對(duì)每個(gè)混沌變量計(jì)算其適應(yīng)函數(shù)值，得到性能最好的可行解，隨機(jī)取代群體中的一個(gè)粒子。

2.4CP-GSA求解WTA問(wèn)題

在確定WTA模型中的各個(gè)參數(shù)后，利用所提出的CP-GSA算法求解WTA問(wèn)題，即求解矩陣X。由于GSA算法是對(duì)向量進(jìn)行求解的，用來(lái)求解矩陣存在速度的表示問(wèn)題，因此，按照文獻(xiàn)[5]的方法，我們用一個(gè)長(zhǎng)度為U1+U2+…+UJ的整數(shù)串P表示一個(gè)粒子，即粒子的維數(shù)為D=U1+U2+…+UJ，第j個(gè)火力單元的分配方案對(duì)應(yīng)于元素組：

PU1+U2+…+Uj-1+1,PU1+U2+…+Uj-1+2,…,PU1+U2+…+Uj

(15)

式(15)中，元素的取值為0到K之間的整數(shù)。若某一元素等于0，代表這個(gè)元素對(duì)應(yīng)的武器未分配給任何目標(biāo)；若某一元素等于k，則代表這個(gè)元素對(duì)應(yīng)的武器分配給了目標(biāo)k。因此，第j個(gè)火力單元分配給目標(biāo)k的個(gè)數(shù)等于元素組(15)的取值中出現(xiàn)k的次數(shù)。

(16)

在利用CP-GSA算法求解WTA問(wèn)題時(shí)，WTA問(wèn)題的第一個(gè)約束條件在利用整數(shù)串P表示粒子的情況下已經(jīng)得到滿足；按照第二個(gè)約束條件，整數(shù)串P的元素值等于k的個(gè)數(shù)應(yīng)不大于Vk，因此我們約定若大于Vk，則隨機(jī)刪除元素，使得元素值等于k的個(gè)數(shù)等于Vk，在這種情況下，最大速度和最小速度也是不需要設(shè)定的。

在上述條件下，WTA問(wèn)題的求解等價(jià)于直接求解無(wú)約束最小化問(wèn)題：

(17)

此時(shí)，利用CP-GSA算法求解WTA問(wèn)題的適應(yīng)度函數(shù)為：

(18)

其中，xjk是X的第(j, k)個(gè)元素。

因此，CP-GSA算法求解WTA問(wèn)題的具體步驟為：

1)種群初始化：根據(jù)問(wèn)題規(guī)模和變量個(gè)數(shù)確定種群大小N和維數(shù)D=U1+U2+…+UJ；隨機(jī)設(shè)置粒子的初始位置X和初始速度V；設(shè)定最大迭代次數(shù)T、慣性權(quán)值w(t)、加速系數(shù)c1和c2以及混沌搜索的最大迭代次數(shù)Q。

2)粒子適應(yīng)度評(píng)價(jià)：根據(jù)式(18)計(jì)算粒子的適應(yīng)度值，更新每個(gè)粒子和種群在第d維經(jīng)歷的最好位置Pid(t)和Gd(t)。

3)早熟收斂判定：利用文獻(xiàn)[10]的適應(yīng)度方差方法對(duì)是否出現(xiàn)早熟進(jìn)行判定，若出現(xiàn)早熟，轉(zhuǎn)到步驟4)進(jìn)行混沌搜索，否則，轉(zhuǎn)至步驟5)。

4)混沌搜索：隨機(jī)產(chǎn)生初始變量Y0，利用式(14)產(chǎn)生混沌序列，用性能最好的解隨機(jī)取代群體中的一個(gè)粒子。

5)速度和位置更新：按式(16)對(duì)各個(gè)粒子的速度和位置進(jìn)行更新。

6)約束條件判定：判斷每個(gè)粒子的位置是否滿足第二個(gè)約束條件，如滿足轉(zhuǎn)至步驟8)，否則，轉(zhuǎn)至步驟7)。

7)刪除多余元素：根據(jù)Vk, k=1,2,…,K隨機(jī)刪除多余的元素，使得粒子的各維取值等于k的個(gè)數(shù)等于Vk。

8)算法終止判定：根據(jù)算法終止條件或最大迭代次數(shù)對(duì)是否終止算法進(jìn)行判定，若終止，則結(jié)束優(yōu)化，返回全局最優(yōu)解，否則，轉(zhuǎn)至步驟2)。

利用CP-GSA算法求解WTA問(wèn)題的流程圖如圖1。

3仿真實(shí)驗(yàn)

本部分對(duì)所提方法的有效性進(jìn)行驗(yàn)證，并與利用PSO算法和GSA算法求解WTA問(wèn)題的性能進(jìn)行對(duì)比。

圖1　CP-GSA求解WTA問(wèn)題流程圖Fig. 1　The flow chart of CP-GSA for solving WTA problem

假設(shè)由4個(gè)地面防空作戰(zhàn)單元抗擊8個(gè)來(lái)襲目標(biāo)，4個(gè)作戰(zhàn)單元具有的武器數(shù)分別為{3, 1, 2, 2}，每個(gè)目標(biāo)最多可分配1個(gè)武器。目標(biāo)的威脅系數(shù)和各類(lèi)武器對(duì)各來(lái)襲目標(biāo)的單發(fā)殺傷概率分別如表1和表2所示。

表1　目標(biāo)威脅系數(shù)

表2　武器對(duì)目標(biāo)的殺傷概率

CP-GSA算法的參數(shù)設(shè)置為：粒子數(shù)N=50，最大迭代次數(shù)T=200，加速系數(shù)c1=c2=2，混沌迭代次數(shù)Q=50。利用CP-GSA算法求解WTA問(wèn)題，在第41代得到最優(yōu)解，適應(yīng)度值為1.18，與枚舉法所得最優(yōu)適應(yīng)度值相等，最優(yōu)分配方案如表3所示。

表3　最優(yōu)武器目標(biāo)分配方案

表3中的分配方案表示：火力平臺(tái)1的武器迎擊目標(biāo)2、目標(biāo)5和目標(biāo)7；火力平臺(tái)2的武器迎擊目標(biāo)4；火力平臺(tái)3的武器迎擊目標(biāo)1和目標(biāo)3；火力平臺(tái)4的武器迎擊目標(biāo)6和目標(biāo)8。

對(duì)利用PSO算法、GSA算法和CP-GSA算法求解WTA問(wèn)題分別運(yùn)行50次，可以得到不同算法最優(yōu)分配方案的適應(yīng)度值情況如表4所示。運(yùn)行200次，得到三種不同算法的收斂曲線如圖2所示。

表4　不同分配方法的適應(yīng)度值情況

圖2　算法收斂曲線Fig.2　The curves of algorithms’ convergence

從表4和圖2可以看出，CP-GSA算法的性能最優(yōu)，GSA算法次之，PSO算法最差。這是由于PSO算法和GSA算法的粒子在算法后期陷入了局部最優(yōu)，算法性能有待提高，而CP-GSA算法中的粒子既遵守運(yùn)動(dòng)定律，又具有記憶和群體信息交流能力，在算法后期利用混沌搜索使得算法能夠快速跳出局部最優(yōu)、快速收斂，在保證全局搜索能力的情況下，提高了局部搜索能力。

4結(jié)論

本文提出了利用改進(jìn)GSA算法求解武器目標(biāo)分配問(wèn)題的方法。該方法將PSO算法的種群信息共享和CS算法融入到引力搜索的迭代過(guò)程之中，解決了GSA算法易陷入局部最優(yōu)的問(wèn)題，提出了改進(jìn)的GSA算法，并將其直接應(yīng)用到WTA問(wèn)題的求解之中。仿真實(shí)驗(yàn)表明，所提方法能夠快速、準(zhǔn)確求解WTA問(wèn)題，以較少的迭代次數(shù)即可獲得有效分配方法。

參考文獻(xiàn):

[1]Sahin M A, Leblebicioglu K. A standard expert system for weapon target assignment problem[C] //Proc. of the International Symposium on Performance Evaluation of Computer & Telecommunication Systems, 2009:221-224.

[2]王瑋,程樹(shù)昌,張玉芝.基于遺傳算法的一類(lèi)武器目標(biāo)分配方法研究[J].系統(tǒng)工程與電子技術(shù),2008, 30( 9) : 1708-1711．

[3]蘇淼,錢(qián)海,王煦法.基于免疫記憶的蟻群算法的WTA問(wèn)題求解[J].計(jì)算機(jī)工程,2008,34(4): 215-217．

[4]高尚,楊靜宇.武器-目標(biāo)分配問(wèn)題的粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù),2005,27(7): 1250-1252．

[5]劉爽英,韓燮.一種求解武器目標(biāo)分配問(wèn)題的量子粒子群算法[J].計(jì)算機(jī)科學(xué),2013,40(2): 235-237.

[6]李欣然,靳雁霞.應(yīng)用于武器-目標(biāo)分配問(wèn)題的量子行為粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件,2012, 29(12):206-209．

[7]徐克虎,黃大山,王天召.改進(jìn)的人工免疫算法求解武器目標(biāo)分配問(wèn)題[J].系統(tǒng)工程與電子技術(shù),2013, 35(10):2121-2127.

[8] Rashedi E, Nezamabadi H and Saryazdi S. GSA: gravitational search algorithm[J]. Information Science, 2009, 179(13) : 2232-2248．

[9]Kennedy J, Eberhart R. Particle Swarm Optimization [C]//Proc. of IEEE International Conference on Neural Networks. Perth, Australia: [s.n.], 1995.

[10]劉軍民,高岳林.混沌粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2008,28(2): 322-325.

*收稿日期:2016-01-17

作者簡(jiǎn)介:李檳檳(1990—)，男，江西上饒人，碩士研究生，研究方向：目標(biāo)攻擊決策關(guān)鍵技術(shù)。E-mail：983692659@qq.com。

中圖分類(lèi)號(hào):TN953

文獻(xiàn)標(biāo)志碼:A

文章編號(hào)：1008-1194(2016)03-0061-05

WeaponTargetAssignmentMethodBasedonModifiedGravitationSearchAlgorithm

LIBinbin,HEGuangjun,ZHANGMingliang,YOUXiaoliang,TIANDewei

(AirForceEngineeringUniversity,ShaanxiXi’an, 710051)

Abstract:Aimed at the problem of premature convergence in the weapon target assignment (WTA) when using gravitation search algorithm (GSA), a modified GSA was proposed in this paper. Firstly, the abilities to memorize information and share information of particle swarm optimization (PSO) algorithm were introduced into the process of GSA. Then, the operation of chaos search (CS) was also inserted into the improved GSA algorithm, and the modified GSA, named CP-GSA algorithm was proposed. At last, the CP-GSA algorithm was applied directly to solve the WTA minimization problem. The simulation results demonstrated that the proposed method could solve the WTA problem effectively. Specially, to attack eight targets using four air defense units, the proposed method could find the best solution by only 41 iterative operations, and the finest value was 1.18, which was equivalent to that obtained by enumeration method.

Key words:weapon target assignment, gravitation search algorithm, particle swarm optimization, chaos search.