基于改進引力搜索的武器目標分配方法

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

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

?

基于改進引力搜索的武器目標分配方法

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

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

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

關鍵詞:武器目標分配；引力搜索算法；粒子群算法；混沌搜索

0引言

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

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

1WTA問題模型和引力搜索算法

1.1WTA問題模型

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

(1)

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

求解WTA問題，首先需要確定模型中的各個參數，其中，目標的威脅值可以通過人工智能或者基于知識的專家系統等方法確定；武器對目標的殺傷概率與武器射擊命中概率和目標防護能力等有關，可通過文獻[7]給出的方法確定。

1.2GSA算法

假設引力系統有N個粒子，每個粒子的位置為：

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

(2)

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

根據牛頓萬有引力定理，在時刻t，第i個粒子在第d維受第j個粒子的作用力大小為：

(3)

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

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

(4)

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

根據適應度函數，在引力質量與慣性質量相等的假設下，粒子引力質量可定義為：

(5)

其中，fiti(t)為t時刻粒子i的適應度值，fitbest(t)和fitworst(t)為群體最優和最差適應度值，對于求最小值問題，fitbest(t)和fitworst(t)定義為：

(6)

在實際中，引力質量一般單位化為：

(7)

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

(8)

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

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

(9)

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

(10)

其中，rand是[0,1]之間的隨機數。

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

(11)

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

2基于CP-GSA算法的武器目標分配方法

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

2.1PSO算法

PSO算法，也稱為微粒群算法[9]，是由美國Kennedy和Eberhart于1995年提出的一種基于群智能的隨機搜索算法。該算法模擬鳥類的覓食行為，將優化問題的搜索空間模擬為鳥類的飛行空間，將每只鳥抽象成一個沒有體積和質量的微粒，代表問題的一個候選解，將尋找問題最優解的過程比作尋找食物的過程，進而求解復雜的優化問題。

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

(12)

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

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

2.2CS算法

混沌狀態一般是由確定性方程導出的具有隨機性的運動，是自然界廣泛存在的一種非線性現象。混沌運動看似隨機，卻是由確定的方程導出的，因此具有遍歷性、隨機性和規律性等特性，能在一定范圍內按其自身規律不重復地遍歷所有狀態。因此，學者們提出利用混沌運動的這些性質進行優化搜索，以跳出局部最優，提高算法收斂速度。

2.3CP-GSA算法

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

(13)

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

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

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

(14)

其中，μ為控制變量，當μ=4，初始值取值在[0,1]時，系統進入完全混沌狀態。

混沌搜索的實現過程為：首先隨機產生一個在[0,1]區間內的初始變量Y0=[Y01,…,Y0d,…,Y0D]；然后利用式(14)產生混沌序列Y1,Y2,…,YQ(Q為混沌搜索的最大迭代次數)，并把混沌區間映射到優化變量的取值區間；最后，對每個混沌變量計算其適應函數值，得到性能最好的可行解，隨機取代群體中的一個粒子。

2.4CP-GSA求解WTA問題

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

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

(15)

式(15)中，元素的取值為0到K之間的整數。若某一元素等于0，代表這個元素對應的武器未分配給任何目標；若某一元素等于k，則代表這個元素對應的武器分配給了目標k。因此，第j個火力單元分配給目標k的個數等于元素組(15)的取值中出現k的次數。

(16)

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

在上述條件下，WTA問題的求解等價于直接求解無約束最小化問題：

(17)

此時，利用CP-GSA算法求解WTA問題的適應度函數為：

(18)

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

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

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

2)粒子適應度評價：根據式(18)計算粒子的適應度值，更新每個粒子和種群在第d維經歷的最好位置Pid(t)和Gd(t)。

3)早熟收斂判定：利用文獻[10]的適應度方差方法對是否出現早熟進行判定，若出現早熟，轉到步驟4)進行混沌搜索，否則，轉至步驟5)。

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

5)速度和位置更新：按式(16)對各個粒子的速度和位置進行更新。

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

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

8)算法終止判定：根據算法終止條件或最大迭代次數對是否終止算法進行判定，若終止，則結束優化，返回全局最優解，否則，轉至步驟2)。

利用CP-GSA算法求解WTA問題的流程圖如圖1。

3仿真實驗

本部分對所提方法的有效性進行驗證，并與利用PSO算法和GSA算法求解WTA問題的性能進行對比。

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

假設由4個地面防空作戰單元抗擊8個來襲目標，4個作戰單元具有的武器數分別為{3, 1, 2, 2}，每個目標最多可分配1個武器。目標的威脅系數和各類武器對各來襲目標的單發殺傷概率分別如表1和表2所示。

表1　目標威脅系數

表2　武器對目標的殺傷概率

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

表3　最優武器目標分配方案

表3中的分配方案表示：火力平臺1的武器迎擊目標2、目標5和目標7；火力平臺2的武器迎擊目標4；火力平臺3的武器迎擊目標1和目標3；火力平臺4的武器迎擊目標6和目標8。

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

表4　不同分配方法的適應度值情況

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

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

4結論

本文提出了利用改進GSA算法求解武器目標分配問題的方法。該方法將PSO算法的種群信息共享和CS算法融入到引力搜索的迭代過程之中，解決了GSA算法易陷入局部最優的問題，提出了改進的GSA算法，并將其直接應用到WTA問題的求解之中。仿真實驗表明，所提方法能夠快速、準確求解WTA問題，以較少的迭代次數即可獲得有效分配方法。

參考文獻:

[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]王瑋,程樹昌,張玉芝.基于遺傳算法的一類武器目標分配方法研究[J].系統工程與電子技術,2008, 30( 9) : 1708-1711．

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

[4]高尚,楊靜宇.武器-目標分配問題的粒子群優化算法[J].系統工程與電子技術,2005,27(7): 1250-1252．

[5]劉爽英,韓燮.一種求解武器目標分配問題的量子粒子群算法[J].計算機科學,2013,40(2): 235-237.

[6]李欣然,靳雁霞.應用于武器-目標分配問題的量子行為粒子群優化算法[J].計算機應用與軟件,2012, 29(12):206-209．

[7]徐克虎,黃大山,王天召.改進的人工免疫算法求解武器目標分配問題[J].系統工程與電子技術,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]劉軍民,高岳林.混沌粒子群優化算法[J].計算機應用,2008,28(2): 322-325.

*收稿日期:2016-01-17

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

中圖分類號:TN953

文獻標志碼:A

文章編號：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.