用離散粒子群優(yōu)化算法求解WTA問題

曲在濱，劉彥君，徐曉飛

(1.哈爾濱工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱，zbqu@hotmail.com; 2.哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，150080哈爾濱)

武器-目標(biāo)分配(Weapon-target Assignment，WTA)問題是現(xiàn)代戰(zhàn)爭中一個十分重要的問題，其解空間隨武器種類數(shù)和目標(biāo)總數(shù)的增加而呈指數(shù)級的增加，使其成為一個多參數(shù)、多約束NP完全問題［1-2］.對于WTA問題，國內(nèi)外主流的求解方法多采用諸如神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法和蟻群優(yōu)化等求次優(yōu)解方法，但它們的求解效率都還不是十分令人滿意，所以探索有效的求解方法解決WTA問題仍然十分重要.

目前，關(guān)于單一兵器火力分配問題的文獻(xiàn)已比較多，然而由于在現(xiàn)代作戰(zhàn)中，經(jīng)常是多種類型的兵器聯(lián)合作戰(zhàn)，故需對多種不同類型的兵器的武器-目標(biāo)分配問題進(jìn)行探討.文獻(xiàn)［3-6］雖然解決的是多種武器類型的火力分配問題，但所建立模型還是一種簡化模型，在實際使用中一般需添加額外約束條件，如對各目標(biāo)分配的武器數(shù)目限制等.本文針對多類型兵器的火力分配問題給出更實用的數(shù)學(xué)模型，并將粒子群算法求解問題的思路應(yīng)用于此問題，用實例驗證了方法的可行性及有效性.

1 問題的描述

具體問題可描述為:設(shè)有n個目標(biāo);m種類型武器;Vj為目標(biāo)j的威脅度;Wi為可分配給目標(biāo)的i類型武器數(shù)量;pij為i類型的一個武器對目標(biāo)j的殺傷概率;xij為給目標(biāo)j分配i類型武器的數(shù)量，目標(biāo)j最多可分配武器數(shù)量為Nj.WTA問題是要確定分配給各目標(biāo)的各類武器數(shù)量以使所有目標(biāo)的總期望生存值最小，這個問題可形式化為

xij≥0且為整數(shù)，i=1，2，…，m，j=1，2，…，n.式中qij=1-pij，即目標(biāo)j受到一發(fā)i類型武器打擊的生存概率.

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

粒子群優(yōu)化Particle Swarm Optimization(PSO)算法是由Kennedy等［7］在1995年提出的，此算法受鳥群覓食行為的啟發(fā)，并用于解決優(yōu)化問題.同遺傳算法相比，PSO算法不但具有遺傳算法的全局尋優(yōu)能力，還具有較強(qiáng)的局部尋優(yōu)能力.

算法將每個個體看作是在n維搜索空間中的一個沒有重量和體積的粒子，并在搜索空間中以一定的速度飛行.每個粒子的飛行速度根據(jù)其本身的飛行經(jīng)驗和群體的飛行經(jīng)驗不斷調(diào)整.每個粒子代表解空間的一個候選解，解的優(yōu)劣程度由適應(yīng)函數(shù)決定，而適應(yīng)函數(shù)根據(jù)優(yōu)化目標(biāo)定義. PSO隨機(jī)初始化一群粒子，其中第i個粒子在n維解空間的位置為xi=(xi1，xi2，…，xin).粒子通過在每一次迭代中動態(tài)跟蹤2個極值來更新其速度和位置為:

1)粒子本身從初始到當(dāng)前迭代搜索產(chǎn)生的最優(yōu)解:個體極值pi=(pi1，pi2，…，pin);

2)整個粒子種群目前的最優(yōu)解:全局極值pg=(pg1，pg2，…，pgn).

如果第i個粒子的速度表示為vi=(vi1，vi2，…，vin)，粒子根據(jù)式(1)，式(2)來動態(tài)調(diào)節(jié)自己的“飛行”，得到搜索問題的最優(yōu)解為

式中:t為迭代次數(shù);c1，c2分別為正常數(shù)，稱為學(xué)習(xí)因子，一般有c1=c2=2;r1，r2分別為(0，1)之間的隨機(jī)數(shù);ω為慣性因子.

3 離散PSO算法求解WTA問題

3.1 約束處理方法

WTA問題的解可表示為一個矩陣 X= (xij)m×n，其中xij為第i類武器分配給第j個目標(biāo)的數(shù)目.在這里，每個粒子的位置便對應(yīng)著武器的一種分配方案.對粒子群迭代中產(chǎn)生的不可行解采用修正結(jié)果值方案的方法進(jìn)行修正，使其在可行解空間范圍內(nèi)搜索.具體實現(xiàn)時利用一個可行性函數(shù)檢查新產(chǎn)生的解是否滿足所有約束.當(dāng)不滿足時，采用啟發(fā)式策略進(jìn)行調(diào)節(jié).調(diào)節(jié)策略為:

1)如果分配方案中某一目標(biāo)的武器分配總數(shù)超過約束限制，則取消對此目標(biāo)殺傷概率最小的超出數(shù)目的武器分配;如果此種武器分配數(shù)少于超出數(shù)目，則需取消此種武器的全部分配.重復(fù)步驟1)，直到各目標(biāo)滿足各自的武器分配總數(shù)約束.

2)如果分配方案中某種武器的分配不滿足約束，則在已分配這種武器的目標(biāo)中選擇“威脅度與此種武器對此目標(biāo)殺傷概率之和”最小的目標(biāo)，取消超出單位數(shù)的武器分配;如果超出單位數(shù)大于分給此目標(biāo)的武器數(shù)，則余下部分再從占用此種武器且滿足選擇準(zhǔn)則的目標(biāo)中取消分配.重復(fù)步驟2)，直到各種武器分配滿足約束為止.

本啟發(fā)式策略運用了貪心思想，盡可能使所做調(diào)節(jié)有利于提高武器對目標(biāo)打擊的有效性，從而加速找到最優(yōu)或次優(yōu)的分配方案.

3.2 離散PSO算法實現(xiàn)

本文對粒子群算法中的速度和位置進(jìn)行了重新定義.對速度進(jìn)行的重新定義為

式中:r1［Plbest(t)-Xi(t)］為第i個粒子的位置Xi的任一列以概率r1與其個體極值Plbest(t)的對應(yīng)列做減法運算，未做減法運算的列一律清零; r2［Pgbest(t)-Xi(t)］為第i個粒子的位置Xi的任一列以概率r2與全局極值Pgbest(t)的對應(yīng)列做減法運算，未做減法運算的列一律清零;⊕為對作為操作數(shù)的2個矩陣產(chǎn)生1個新的矩陣，當(dāng)2個操作數(shù)矩陣的對應(yīng)列所有元素均為0，則結(jié)果矩陣的相應(yīng)列也為全0;如果只有一列不全為0，則此列為結(jié)果矩陣的對應(yīng)列;否則任選其中一列為結(jié)果矩陣的對應(yīng)列.

上述定義解決了速度難于表示問題，而進(jìn)行位置的更新為

式中:Xi'(t)為將Xi(t)隨機(jī)選擇一行根據(jù)相應(yīng)類型武器數(shù)目對各目標(biāo)產(chǎn)生隨機(jī)分配而其余各行保持不變的結(jié)果，而“+”運算則為2個矩陣對應(yīng)元素相加.

求解WTA問題的離散PSO算法(DPSOWTA)描述為:

1)初始化粒子群，即隨機(jī)設(shè)定各粒子的初始位置X和速度V;

2)計算每個粒子的個體適應(yīng)度值(即目標(biāo)函數(shù)值);

3)將每個粒子的適應(yīng)度值與個體極值Plbest比較，若更好，則更新Plbest;

4)將每個粒子的適應(yīng)度值與全局極值Pgbest比較，若更好，則更新Pgbest;

5)根據(jù)式(3)和式(4)更新粒子的速度和位置，并使用啟發(fā)式策略調(diào)整新位置;

6)如未達(dá)到最大的迭代次數(shù)，則返回步驟2);否則結(jié)束.

算法在對每一粒子初始化時根據(jù)各類武器的數(shù)目隨機(jī)產(chǎn)生分配方案，且使其滿足各約束條件.

4 算法測試

假設(shè)有6個目標(biāo)，T1，T2，…，T6，各目標(biāo)的威脅度如表1所示.5種武器:W1，W2，W3，W4，W5的數(shù)目為{4，3，3，2，2}，對各目標(biāo)最多可使用武器數(shù)目為{1，1，2，1，1，2}，各類武器對各目標(biāo)的單發(fā)殺傷概率如表2所示.

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

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

算法具體實現(xiàn)時，為避免陷入局部最優(yōu)，若全局極值在進(jìn)化一定代數(shù)后保持不變，則只保留最優(yōu)粒子，其他粒子全部重新生成.本例中的粒子數(shù)取為30，最大迭代數(shù)為100.在P4 1.7 G/512 M微機(jī)上重復(fù)執(zhí)行算法50次得出的最優(yōu)方案的適應(yīng)度值情況如表3所示，最優(yōu)分配方案的適應(yīng)度函數(shù)值為0.634，與枚舉算法所得分配方案的適應(yīng)度函數(shù)值相同.

表3 最優(yōu)方案的適應(yīng)值情況

進(jìn)化過程中的適應(yīng)度函數(shù)值(平均值)變化情況如圖1所示，圖1中同時也給出與遺傳算法(GA)的對比.對于此例，采用枚舉算法求解大約需1 142 s，而提出的離散粒子群算法迭代100代所需平均時間為156.9 ms，所得最佳方案的適應(yīng)度平均值為0.732，與最優(yōu)值相差0.098;對遺傳算法進(jìn)行同樣次數(shù)獨立實驗，每次迭代100代所需平均時間為217.3 ms，所得最佳方案的適應(yīng)度平均值為1.061，與最優(yōu)值相差0.427，可明顯看出離散PSO算法大大優(yōu)于遺傳算法，求解精度也明顯高于文獻(xiàn)［8］提出的粒子群優(yōu)化算法.

圖1 適應(yīng)度函數(shù)值(平均值)變化情況

經(jīng)過對大量實例的計算發(fā)現(xiàn)，隨著武器和目標(biāo)數(shù)的增加，所提出離散粒子群算法對遺傳算法的優(yōu)勢也越發(fā)明顯.圖2給出當(dāng)目標(biāo)數(shù)為15，武器種類數(shù)為5，且每類武器數(shù)為(4，6，5，5，4)時2種算法執(zhí)行時的最佳適應(yīng)度值隨時間變化情況，

此例分配方案的適應(yīng)度最優(yōu)值為1.404.總而言之，使用本文提出的離散粒子群優(yōu)化算法能快速給出武器-目標(biāo)分配問題的最優(yōu)或近優(yōu)解，驗證了算法的有效性.

圖2 適應(yīng)度函數(shù)值(平均值)隨時間變化情況

5 結(jié)論

1)采用啟發(fā)式策略對粒子群迭代過程產(chǎn)生的不可行解進(jìn)行調(diào)節(jié)，使算法在可行解空間范圍內(nèi)搜索.調(diào)節(jié)利用了貪心思想，使其有利于提高武器對目標(biāo)打擊的有效性.

2)對粒子群算法中的速度和位置進(jìn)行了重新定義，使粒子群算法這一主要用于連續(xù)函數(shù)優(yōu)化的算法可以解決武器-目標(biāo)分配問題這樣的約束組合優(yōu)化問題，明顯提高了問題求解的速度和精度，拓展了粒子群優(yōu)化算法在離散空間的應(yīng)用.

3)提出的算法能快速給出武器-目標(biāo)分配問題的最優(yōu)或近優(yōu)分配方案，為解決這一NP難點問題提出了新的解決途徑.

［1］AHUJA R K，KUMAR A，JHA K，et al.Exact and heuristic methods for the weapon target assignment problem［EB/OL］.(2003-06-20)［2004-04-20］http://ssrn.com/abstract=489802.

［2］ROSENBERGER J M，HWANG H S，PALLERLA R P， et al.The generalized weapon target assignment problem［C］//Proceddings of 10thInternational Command and Control Research and Technology Symposium on The Future of C2.McLean，VA:Lockheed Martin Corporation，2005:1-13.

［3］陳紹順，王穎龍，王君.多武器系統(tǒng)的火力分配模型［J］.火力與指揮控制，2005，30(2):45-47.

［4］鄭澤席.使用多種防空武器時目標(biāo)分配的數(shù)學(xué)模型［J］.系統(tǒng)工程與電子技術(shù)，2000，22(5):15-16.

［5］解春明，楊傳春，李德勝.地地導(dǎo)彈突擊目標(biāo)火力分配模型［J］.火力與指揮控制，2004，29(6):41-44.

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

［7］KENNEDY J，EBERHART R C.Particle swarm optimization［C］//Proceedings of IEEE International conference on Neural Networks.Piscataway，NJ:IEEE Service Center，1995:1942-1948.

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