夏維， 劉新學， 范陽濤， 元鋒剛

(1.火箭軍工程大學 初級指揮學院， 陜西 西安 710025；2.91033部隊， 山東 青島 266034)

?

基于改進型多目標粒子群優(yōu)化算法的武器-目標分配

夏維1， 劉新學1， 范陽濤1， 元鋒剛2

(1.火箭軍工程大學 初級指揮學院， 陜西 西安 710025；2.91033部隊， 山東 青島 266034)

在作戰(zhàn)中武器- 目標分配(WTA)問題包含眾多的變量，是典型的非確定性多項式完全問題。針對毀傷效能最大和用彈量最少兩個目標函數(shù)，建立了基于改進型多目標粒子群優(yōu)化(MOPSO-Ⅱ)算法的WTA模型。由于粒子群優(yōu)化算法存在“維數(shù)災難”瓶頸，應用了變量隨機分解策略和合作協(xié)同進化框架，按照帶精英策略的非支配排序遺傳(NSGA-Ⅱ)算法中的排序方法對粒子群編碼數(shù)據(jù)進行非支配排序。通過實例仿真分析，結(jié)果表明MOPSO-Ⅱ算法比NSGA-Ⅱ算法具有更好的求解精度與運行效率，能夠獲得滿意的分配結(jié)果，且計算快速有效，比較適合較大規(guī)模的WTA問題實時求解。

兵器科學與技術(shù)； 多目標優(yōu)化； 粒子群優(yōu)化； 火力分配； Pareto集； 武器- 目標分配

0 引言

武器- 目標分配(WTA)問題，歷來是作戰(zhàn)指揮輔助決策研究中的核心內(nèi)容之一，其解空間隨著武器數(shù)目和目標總數(shù)的增加而呈指數(shù)級遞增，是多參數(shù)、多約束的離散非確定性多項式(NP)完全問題[1]。WTA的核心思想是如何設(shè)計采用高效且健壯的算法，把具有不同殺傷力和價值成本的武器合理分配到不同的射擊目標上，以構(gòu)成整體優(yōu)化的火力打擊體系，使得作戰(zhàn)效能最大。目前用于求解WTA問題的常用算法有遺傳算法[2-3]、粒子群優(yōu)化算法[4-9]、蟻群算法[10]、量子算法[11]、人工免疫算法[12]等，還有的采用算法的混合優(yōu)化策略，如貪心算法與遺傳算法結(jié)合[13]、禁忌搜索與微粒群優(yōu)化結(jié)合[14]、蟻群算法與模擬退火算法結(jié)合[15-16]等。這些方法在提供了一種新思路的同時大都能夠獲得滿意解，但都不同程度地存在著如下缺陷：易早熟、進化速度慢或者算法設(shè)計實現(xiàn)困難；絕大多數(shù)都針對的是某一時刻一種武器對應一批目標的作戰(zhàn)背景，距離實戰(zhàn)的標準要求甚遠；算例中武器和目標的規(guī)模通常較小，面對規(guī)模較大、變量眾多的WTA問題則比較束手無策。

本文在傳統(tǒng)WTA問題追求最大作戰(zhàn)效能的同時，新增“耗彈量最少”這一目標函數(shù)，將單目標優(yōu)化問題轉(zhuǎn)化為多目標優(yōu)化，從而使得算法研究在未來作戰(zhàn)中具有更加積極的現(xiàn)實意義。為解決傳統(tǒng)多目標粒子群優(yōu)化(MOPSO)算法中因“維數(shù)災難”所導致的優(yōu)化性能降低的問題，本文根據(jù)Potter等[17]提出的“分而治之”策略，提出一種新的改進型多目標粒子群優(yōu)化(MOPSO-Ⅱ)算法，構(gòu)造了有效表達武器- 目標分配的粒子編碼、解碼方案，并通過引入變量隨機分解策略和合作協(xié)同框架，將大規(guī)模的變量問題分解到若干個維度適中的變量組——子種群當中，之后通過子種群之間的合作協(xié)同來實現(xiàn)對整個問題的求解，極大地提高了算法的求解效率，最后還通過仿真實例對比測試，驗證了改進算法的快速性和精確性。

1 理論基礎(chǔ)

1.1 WTA數(shù)學模型與數(shù)學性質(zhì)

(1)

式中：xij表示第i類導彈對第j個目標分配的火力單元個數(shù)。第i類型號的每枚導彈對第j個目標的殺傷概率為eij，且0≤eij≤1,i=1,2,…,m,j=1,2,…,n，則殺傷概率矩陣為

(2)

約束條件為：

1)第i類型號最多可以發(fā)射ci枚導彈，即

2)進攻方對目標Tj最多可使用sj枚導彈，即

3)總分配導彈數(shù)目必須小于等于全部型號導彈所擁有的總數(shù)，即

1.2 多目標優(yōu)化與Pareto集

多目標優(yōu)化問題的最優(yōu)解通常稱為Pareto最優(yōu)解，如果用函數(shù)f來定義多目標優(yōu)化問題，且函數(shù)把m維的決策變量X映射到n維的目標向量Y上，則該多目標優(yōu)化問題的數(shù)學描述為

(3)

式中：X=(x1,x2,…,xm)由m個決策變量xi構(gòu)成；Y由n個需要同時優(yōu)化的目標函數(shù)fi(X)構(gòu)成；約束條件g(X)由r個等式或不等式gi(X)≤0構(gòu)成。則由多目標優(yōu)化問題(3)式可引出如下定義：

定義1 Pareto支配。設(shè)f:Rm→Rk,x1,x2∈Ω?Rm，稱解x1支配解x2當且僅當f(x1)部分地優(yōu)于f(x2)，即?i∈{1,2,…,k},fi(x1)≤fi(x2)∧?i∈{1,2,…,k},fi(x1)

定義2 Pareto最優(yōu)解。解x*∈Ω稱之為解集合Ω的Pareto優(yōu)化解當且僅當集合{x|x?x*,x∈Ω}=?.

定義3 Pareto最優(yōu)解集，即所有Pareto最優(yōu)解組成的集合。對于給定的多目標優(yōu)化問題，設(shè)其定義域為Ω，則其Pareto最優(yōu)集X*定義為：X*={x*|?x∈Ω∶xx*}.

多目標WTA問題優(yōu)化中，各目標之間往往互相沖突且計算困難，在規(guī)模較大的情況下，尋求使各目標同時達到最優(yōu)的絕對最優(yōu)解是不現(xiàn)實的，只能獲得滿意解，也即Pareto解，并且它不是唯一的。

1.3 多目標優(yōu)化模型

WTA多目標優(yōu)化模型具有毀傷效能指標最大和用彈量最少兩個目標函數(shù)。

用一定數(shù)量的第i類型號導彈攻擊第j個目標的殺傷概率可表示為

Pij=1-(1-eij)xij.

(4)

則所有的m種型號導彈對目標j的毀傷概率Pj為

(5)

(6)

為便于多目標計算，取目標函數(shù)f1=1-f最小來表示對敵毀傷期望f最大。

決策方案中，使用的導彈數(shù)目為

(7)

根據(jù)目標函數(shù)f1、f2和火力分配原則所構(gòu)成的約束條件，建立WTA多目標規(guī)劃數(shù)學模型為

(8)

1.4 MOPSO算法

粒子群優(yōu)化(PSO)算法是由Kennedy等[20]于1995年提出的一種新型智能優(yōu)化算法，源于對鳥群覓食行為中相互協(xié)作的研究，是一種大范疇群體智能算法。PSO算法利用粒子的個體認知和社會交互引導群體收斂到潛在的全局最優(yōu)區(qū)域。假設(shè)D維解空間存在N個粒子，基本的PSO算法可表示為

vid(t+1)=ωvid(t)+C1r1(pid-xid(t))+

C2r2(pgd-xid(t))，

(9)

xid(t+1)=xid(t)+vid(t+1)，

(10)

式中：vid為粒子的速度向量；xid為當前粒子的位置；pid為粒子本身所找到的最優(yōu)解pb；pgd為整個種群目前找到的最優(yōu)解gb；r1與r2是介于[0,1]間的隨機數(shù)；ω、C1和C2分別為控制這3部分內(nèi)容的學習因子，ω又叫慣性權(quán)重，正常數(shù)C1和C2被稱為加速因子。

1.5 合作協(xié)同進化框架

圖1 合作協(xié)同進化中的變量分解示意圖Fig.1 Schematic diagram of variable decomposition in cooperative co-evolution frame

2 MOPSO-Ⅱ算法

為解決現(xiàn)實作戰(zhàn)中因大規(guī)模變量所導致的“維數(shù)災難”問題，MOPSO-II算法根據(jù)“分而治之”的策略，通過引入變量隨機分解策略和合作協(xié)同框架，將大規(guī)模的變量隨機分解成若干個維度適中的變量組——子種群，并通過子種群之間的合作協(xié)同來求解WTA問題。

2.1 粒子編碼與解碼

由于MOPSO算法研究的是具有連續(xù)變量的數(shù)值優(yōu)化問題，無法直接用于求解WTA多目標規(guī)劃這一非線性組合優(yōu)化決策問題，因此，首先需要把解空間上的向量編碼成類似遺傳算法中基因的形式。

所采用的編碼方式不僅要能表示問題的解，還應盡量滿足WTA多目標規(guī)劃模型中所設(shè)定的約束條件，為此本文考慮設(shè)計了如圖2所示的編碼結(jié)構(gòu)方案。圖2中，武器系統(tǒng)包含有m種型號的導彈，其中第i種型號導彈有ci枚，本文里的編碼方案用長為c1+c2+…+cm的整數(shù)串來表示一個粒子；其中p1,p2,…,pc1代表第1個武器系統(tǒng)W1所擁有的c1個導彈武器分配方案，pc1+1,pc1+2,…,pc1+c2代表第2個武器系統(tǒng)W2所擁有的c2個導彈武器分配方案,則pc1+c2+…+cm-1+1,pc1+c2+…+cm-1+2,…,pc1+c2+…+cm代表第m個武器系統(tǒng)Wm所擁有的cm個導彈武器分配方案。記粒子的維數(shù)為D，也即c1+c2+…+cm=D.

圖2 MOPSO-II算法編碼結(jié)構(gòu)圖Fig.2 Coding structure chart of MOPSO-Ⅱ algorithm

假設(shè)WTA火力分配問題中有T1,T2,…,Tn共n個打擊目標，故在粒子編碼p1,p2,…,pn過程中，每一維的pi取值均限定為0～n的整數(shù)，即pi∈[0,n]. 如pi=k，則表示pi所對應的型號導彈分配給了目標Tk，如pi=0，則代表pi所對應的型號導彈本輪沒有分配。

由此可知，本文所采用編碼方式能夠滿足(8)式中的約束條件1和條件3. 而約束條件2卻并不一定滿足，即上述編碼方式有可能出現(xiàn)攻擊方對擬打擊的目標Tj使用導彈數(shù)目多于sj的情況。因此在對編碼進行初始化和MOPSO-II算法操作產(chǎn)生新粒子時，應檢查新粒子是否符合約束條件2，若不滿足還需重新初始化粒子直至約束條件2成立為止。

解碼時，從左至右依次掃描整個編碼。掃描至pk時，首先得到pk所對應的導彈型號i，接著檢查pk取值，若pk=0則說明pk所對應型號的導彈沒有分配給任何目標；若pk=j則說明pk對應型號的導彈被分配給了第j個目標。

2.2 變量隨機分解策略

盡管早期已有合作協(xié)同框架的思想，且在解決大規(guī)模獨立變量方面具有良好的效果，但是當變量之間不再相互獨立而是有所聯(lián)系時，仍然沿用原有框架進行優(yōu)化的效果變得不再理想。其主要原因是多目標優(yōu)化問題中，大規(guī)模的變量之間往往存在內(nèi)嵌關(guān)聯(lián)，簡單機械地進行變量分解會丟失大量重要的內(nèi)嵌關(guān)聯(lián)信息，導致優(yōu)化效果低下。本文采用變量隨機分解策略，將D維決策向量組隨機分配到K個子元素中，以增加關(guān)聯(lián)變量分到同一組的概率，每個子元素的維度為λ，且滿足D=λK，K個子元素均被設(shè)成含有NP個粒子的子種群，具體分解過程如圖3所示。

圖3 變量隨機分解過程圖Fig.3 Process chart of variable random decomposition

2.3 適應度評價

MOPSO算法在優(yōu)化武器- 目標分配問題時，需要通過適應度來評價各子種群中單個粒子當前位置的優(yōu)劣。本文在優(yōu)化過程中，按照“導彈打擊目標的失敗概率與粒子適應度呈反比”的思想，以攻擊方打擊所有目標的失敗概率加權(quán)和最小為目標，相應的適應度函數(shù)為

(11)

式中：向量p*為一個完整的編碼方案；qij代表i型導彈攻擊目標j的成功概率，qij的值由C3I系統(tǒng)提供。計算適應度函數(shù)時，首先對p*進行解碼，得到分配方案矩陣，然后利用(11)式對單個粒子的適應度進行計算。

2.4 算法框架描述

首先評估各子種群的適應度，為區(qū)分單個粒子適應度函數(shù)，定義b(j,z)為子種群適應度函數(shù)：

(12)

將得到的適應度代入(8)式，可得到目標函數(shù)f1(b(j,z))、f2(b(j,z))，首先把編碼粒子群隨機分解成K個子種群，并按照帶精英策略的非支配排序遺傳算法(NSGA-II)中的排序方法對子種群各粒子進行非支配排序，隨機選擇非支配排序等級最高粒子中的一個作為子種群j的最優(yōu)位置。以子種群2為例，種群間的協(xié)同進化過程如圖4所示。分別用MOPSO算法從1到K對子種群進行優(yōu)化，將所求出的各子種群的解進行非支配排序，若滿足終止條件，則將各個子種群的最優(yōu)非支配解作為最終輸出結(jié)果。若終止條件不滿足，則將父代子種群的最優(yōu)非支配解集保留并轉(zhuǎn)入下一輪迭代。

圖4 子種群間的協(xié)同示意圖Fig.4 Schematic diagram of cooperation between subgroups

為避免算法陷入“局部最優(yōu)”問題，本文采用經(jīng)典算法NSGA-II中的擁擠距離排序法，并與一個變異操作算子共同維護外部種群中解的分布。一個粒子的擁擠距離為與其相鄰的兩個粒子在每個子目標上的距離之和，其值越大說明解集越分散、密度越小、多樣性更好。如圖5中所示的A、B兩點的擁擠距離值為與之對應的矩形長、寬之和，且A點的擁擠距離明顯大于B點，說明相較于點B來說，A點周圍的解比較稀疏，對外部種群多樣性的維持也更為重要，若要在兩點之間有所選擇，應選擇裁掉點B.

圖5 基于擁擠距離的多樣性策略原理Fig.5 Multifarious tactical principle based on crowding distance

基于上述擁擠距離，若以下兩個條件有任何一個滿足，便對外部種群進行更新操作：1)內(nèi)部種群產(chǎn)生的新粒子支配外部種群中的某個或某些粒子；2)外部種群中的粒子數(shù)已達到最大容量Nmax.

對外部種群進行更新操作的具體步驟為：

1) 依據(jù)目標函數(shù)值降序排列所有粒子。

2) 利用(13)式計算每個粒子的擁擠距離：

Cd=

(13)

式中：n表示目標函數(shù)個數(shù)；xp與xn為粒子xd的前后兩個粒子。

3) 給邊界上的兩個粒子分配最大的擁擠距離，以保留這兩個解，利用邊界點強化粒子群搜索的全局性。

4) 判斷外部種群規(guī)模。若當前外部種群未滿，直接添加新的非支配粒子，并刪除外部種群中被支配的粒子；若外部種群已滿，選擇擁擠距離最小的個體進行替代。

2.5 算法流程

MOPSO-II優(yōu)化算法的流程圖如圖6所示，具體步驟如下：

1) 初始化D維變量及參數(shù)。每個子種群的粒子個數(shù)為NP，根據(jù)粒子編碼方案初始化粒子的位置和速度，計算粒子的適應度值，對粒子進行非支配排序，隨機選擇非支配等級最高的粒子中的一個作為Gbest，設(shè)定最大周期CycleMax，子種群數(shù)量NumespMax，種群最大迭代次數(shù)GenMax；

2)Cycle=1，周期開始執(zhí)行，將D維變量隨機分成NumespMax個子種群，每個子種群粒子個數(shù)為NP；

3)Numesp=1，對第1個子種群進行迭代處理；

4)Gen=1，對子種群進行迭代，以粒子當前位置為個體最優(yōu)位置，步驟1中的Gbest為全局最優(yōu)位置，按照(7)式和(8)式更新種群中粒子的速度和位置，用(13)式評價粒子的適應度，按照NSGA-II中的擁擠距離排序法對各粒子進行非支配排序，隨機選出非支配等級最高中的一個粒子作為Gbest，更新個體最優(yōu)和全局最優(yōu)，進入下一輪的迭代，Gen=Gen+1；

5) 當Gen=GenMax滿足時，進行外部種群維護，即Numesp=Numesp+1，跳入下一個子種群處理。在下一個子種群處理過程中，將上一個子種群中得到的Gbest作為全局最優(yōu)進行更新，其他操作同步驟4；

6) 當Numesp=NumespMax時，重新進行變量隨機分解，重復執(zhí)行步驟3～步驟5；

7) 通常情況下，當Cycle=CycleMax成立時便輸出結(jié)果，程序結(jié)束。

2.6 算法時間復雜度分析

假定優(yōu)化問題的目標數(shù)目為M，劃分的子種群數(shù)目為S，子種群的粒子規(guī)模為N，外部種群規(guī)模為N′，則由文獻[21-22]可知NSGA-II算法的時間復雜度為O(MS2N2)。MOPSO-II算法的時間復雜度可估計如下：

1) 生成初始粒子群體的時間為O(SN)，粒子飛行速度的初始化時間為O(SN)，粒子歷史最優(yōu)位置的初始化時間為O(N)，按照初始值計算種群中粒子適應度的時間為O(MN)，對粒子進行非支配排序的時間為O(SNlnN)，為外部種群中的粒子賦予生存期值的時間為O(N′)，因此初始化過程總的時間復雜度為O(SNlnN)。

2) 計算子種群中粒子適應度的時間為O(MN)，更新粒子歷史最優(yōu)位置的時間亦為O(MN)，從外部種群中隨機選擇全局最優(yōu)解所需時間為O(MN′)，按照NSGA-II算法中的非支配排序方法排序粒子的時間復雜度為O(MN2)，執(zhí)行變異操作的時間復雜度為O(N)，選擇非支配粒子加入外部種群，并對其進行維護的時間復雜度為O(MNlnN)，子種群迭代過程的時間復雜度為O(MN)+O(MN)+O(MN′)+O(MN2)+O(N)+O(MNlnN)=O(MN2)，因此，種群的時間復雜度為O(MSN2)。

3) 輸出外部種群中所有解個體的時間為O(N′)。因此，MOPSO-II算法的時間復雜度應為O(SNlnN)+O(MSN2)+O(N′)=O(MSN2). 由此可見，相比于NSGA-II算法的時間復雜度O(MS2N2)來說，MOPSO-Ⅱ算法的要小。

3 仿真及算例分析

為了驗證本文所使用的MOPSO-II算法求解多平臺WTA問題的有效性及性能，在Intel(R)Core(TM)2 Duo CPU E8600，2.0 GB RAM，Windows XP實驗平臺上，在Matlab 7.12.0實驗環(huán)境下進行仿真計算。

假設(shè)進攻方有10種不同型號的導彈，需要同時對12個不同類型的目標進行火力打擊，戰(zhàn)局假設(shè)數(shù)據(jù)如表1所示。

目標的重要度系數(shù)和每種型號導彈對各目標的毀傷概率分別由如下威脅系數(shù)矩陣和殺傷概率矩陣給出。

表1 戰(zhàn)局假設(shè)數(shù)據(jù)

W=[0.12 0.08 0.13 0.14 0.11 0.01 0.06 0.10 0.05 0.04 0.07 0.09],

MOPSO-II算法中設(shè)置控制參數(shù)如下：慣性權(quán)重ω=0.9，學習因子C1=C2=2，種群規(guī)模的大小為100、200，算法終止的條件為最大迭代次數(shù)200，變異概率為0.1，分組大小為50. 程序獨立運行20次得到的結(jié)果如表2所示。

表2 算法統(tǒng)計結(jié)果

MOPSO-II算法和NSGA-II算法求解該實戰(zhàn)問題仿真運行時間及仿真結(jié)果分別如圖7～圖9所示。

圖7 兩種算法運行時間對比圖Fig.7 Comparison of running times of two algorithms

圖8 NSGA-II算法仿真圖Fig.8 Simulation of NSGA-II algorithm

圖9 MOPSO-II算法仿真圖Fig.9 Simulation of MOPSO-II algorithm

由圖7可知，在種群規(guī)模較小時，兩種算法所花費的運行時間差別不大，但是隨著規(guī)模的增加，MOPSO-Ⅱ算法的運行效率更高，時間花費更少。當種群規(guī)模為300，迭代為200時，仿真結(jié)果如圖8和圖9所示，圖中的每個解均代表一種分配方案。例如：f2=19，1-f1=0.14時，其染色體所對應的編碼方案為[2 8 1 7 3 9 6 9 6 10 9 10 2 3 6 5 8]，導彈與目標分配如表3所示。

由圖8和圖9可知，兩種算法均體現(xiàn)了增加導彈數(shù)量對打擊目標毀傷效能的影響，都能為決策者提供可靠依據(jù)，但圖9中的Pareto前沿分布性和收斂性更好，尤其是當0.65

表3 目標分配方案

4 結(jié)論

針對作戰(zhàn)中武器- 目標火力分配問題包含眾多變量的實際，本文將遺傳算法、PSO算法和Pareto集多目標優(yōu)化算法結(jié)合在一起，提出了基于大規(guī)模變量隨機分解的MOPSO-Ⅱ化算法，并建立了基于毀傷效能最大和用彈量最少兩個目標函數(shù)的火力分配模型。按照“分而治之”的策略在算法中引入變量隨機分解策略和合作協(xié)調(diào)進化框架，有效克服了傳統(tǒng)單目標優(yōu)化算法效率低下獲取權(quán)重不易、PSO算法存在“維數(shù)災難”的缺點，實例仿真結(jié)果表明MOPSO-Ⅱ算法比NSGA-Ⅱ算法具有更好的求解精度與運行效率，能夠獲得滿意的分配結(jié)果且計算快速有效，比較適合較大規(guī)模的復雜WTA問題實時求解，但在簡化模型結(jié)構(gòu)和避免陷入局部最優(yōu)方面還有待進一步深入研究。

References)

[1] Lloyd S P, W H S. Weapon allocations is NP-complete[C]∥IEEE Summer Conference on simulation. Reno, Nevada: IEEE, 1986:88-95.

[2] 許建中. 基于遺傳算法的武器目標分配模糊多目標規(guī)劃[J]. 軍事運籌與系統(tǒng)工程, 2010, 24(3):70-74. XU Jian-zhong. Weapon-target assignment with fuzzy multi-objective ranking genetic algorithm[J]. Military Operation Research and System Engineering, 2010, 24(3):70-74.(in Chinese)

[3] 袁形形. 遺傳多目標優(yōu)化算法的研究[D]. 北京:中國地質(zhì)大學, 2010. YUAN Xing-xing. Research of multi-objective evolutionary algorithms[D]. Beijing: China University of Geosciences,2010.(in Chinese)

[4] 曲在濱, 劉彥君, 徐曉飛. 用離散粒子群優(yōu)化算法求解WTA問題[J]. 哈爾濱工業(yè)大學學報, 2011, 43 (3):67-69,101. QU Zai-bin, LIU Yan-jun, XU Xiao-fei. Discrete particle swarm optimization for solving WTA problem[J]. Journal of Harbin Institute of Technology, 2011, 43(3):67-69,101.(in Chinese)

[5] 肖嶸, 趙成旺, 王護利, 等. 多群協(xié)同PSO優(yōu)化算法的WTA問題求解[J]. 計算機仿真, 2010, 27(9): 12-14, 28. XIAO Rong, ZHAO Cheng-wang, WANG Hu-li, et al. Multi swarms cooperative particle swarm optimization for solving WTA problem[J] Computer Simulation, 2010, 27(9): 12-14,28.(in Chinese)

[6] 劉慧慧. 基于多種群協(xié)同的多目標粒子群優(yōu)化算法研究[D]. 南京:南京郵電大學, 2014. LIU Hui-hui. Study on multi-populations for multi-objective optimization PSO algorithm and its application [D]. Nanjing: Nanjing University of Posts and Tele-communications, 2014.(in Chinese)

[7] 謝承旺, 李凱, 徐君, 等. 一種改進型多目標粒子群優(yōu)化算法MOPSO-Ⅱ[J]. 武漢大學學報:理學版, 2014, 60(2):144-150. XIE Cheng-wang, LI Kai, XU Jun, et al. An Improved multi-objective particle swarm optimization algorithm MOPSO-Ⅱ[J]. Journal of Wuhan University: Natural Science Edition, 2014, 60(2):144-150.(in Chinese)

[8] Hu X, Eberhart R. Multi-objective optimization using dynamic neighborhood particle swarm optimization[DB/OL]. [2013-02-09]. http:∥www.swarmintelli gence.org/papers/CEC2002 Multi-objective.pdf.

[9] Clello C C, Pulido G T, Lechunga M S. Handling multiple objectives with particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3):256-279.

[10] 崔莉莉. 基于蟻群算法的武器- 目標分配問題研究[D]. 上海:上海交通大學, 2011. CUI Li-li. Ant colony algorithm for solving the weapon-target assignment problem[D]. Shanghai:Shanghai Jiao Tong University, 2011. (in Chinese)

[11] 張毅, 楊秀霞, 周紹磊. 基于量子分布估計算法的火力分配問題研究[J]. 電光與控制, 2013, 20(12):18-21. ZHANG Yi, YANG Xiu-xia, ZHOU Shao-lei. Fire assignment based on quantum-inspired estimation of distribution algorithm[J]. Electronics Optics & Control, 2013, 20(12):18-21.(in Chinese)

[12] 阮旻智, 李慶民, 劉天華. 編隊防空火力分配建模及其優(yōu)化方法研究[J]. 兵工學報, 2010, 31(11):1525-1529. RUAN Min-zhi, LI Qing-min, LIU Tian-hua. Modeling and optimization on fleet antiaircraft firepower allocation[J]. Acta Armammentarii, 2010, 31(11):1525-1529.(in Chinese)

[13] 張海兵, 徐誠, 李世永. 貪心遺傳算法及其在武器目標分配問題中的應用[J]. 彈道學報, 2007, 19(2):40-43. ZHANG Hai-bing, XU Cheng, LI Shi-yong. GGA and its application to weapon target assignment[J]. Journal of Ballistics, 2007,19(2): 40-43.(in Chinese)

[14] 丁鑄, 馬大為, 于存貴, 等. 基于禁忌搜索與微粒群優(yōu)化算法的混合優(yōu)化策略算法在目標分配問題上的應用[J]. 兵工學報, 2007, 28(9):1127-1131. DING Zhu, MA Da-wei, YU Cun-gui, et al. Application of hybrid optimization strategy algorithm based on tabu search and particle swarm optimization algorithms for weapon- target assignment problems[J]. Acta Armamment-arii, 2007, 28(9):1127-1131.(in Chinese)

[15] 麻士東, 龔光紅, 韓亮, 等. 目標分配的蟻群- 模擬退火算法及其改進[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33 (5):1182-1186. MA Shi-dong, GONG Guang-hong, HAN Liang, et al. Hybrid strategy with ant colony and simulated annealing algorithm and its improvement in target assignment[J]. Systems Engineering and Electronics, 2011, 33(5):1182-1186.(in Chinese)

[16] 郭業(yè)才, 張苗青. 基于混合蛙跳算法的多模盲均橫算法[J]. 兵工學報, 2015, 36(7):1280-1287. GUO Ye-cai, ZHANG Miao-qing. A multi-modulus blind equalization algorithm based on shuffled frog leaping algorithm of hybrid optimization[J]. Acta Armammentarii, 2015, 36(7):1280-1287.(in Chinese)

[17] Potter M A, De Jong K A. A cooperative co-evolutionary approach to function optimization, parallel problem solving from nature, PPSN III[J]. Lecture Notes in Computer Science, 1994, 866: 249-257.

[18] Kennedy J, Eberhart R. Particle swarm optimization[C]∥1995 IEEE International Conference on Neural Networks. Piscataway, NJ, US:IEEE, 1995:1942- 1948.

[19] Li X, Yao X. Cooperatively coevolving particle swarms for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(2):271-289.

[20] Antonio L M, Coello C. Use of cooperative co-evolution for solving large scale multi-objective optimization problems[C] ∥2013 IEEE Congress on Evolutionary Computation. Cancun, Mexico:IEEE, 2013: 2758-2765.

[21] Deb K, Pratab A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ [J]. IEEE Transactions on Evolutionary Computation, 2002, 4(6):182-197.

[22] Ahuja R K, Kumar A, Jha K C, et al. Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research, 2007, 55(6):1136-1146.

Weapon-target Assignment with an Improved Multi-objective Particle Swarm Optimization Algorithm

XIA Wei1， LIU Xin-xue1， FAN Yang-tao1， YUAN Feng-gang2

(1.Elementary Command College, Rocket Force University of Engineering, Xi’an 710025, Shaanxi, China; 2.Unit 91033 of PLA, Qingdao 266034, Shandong, China)

Weapon-target assignment (WTA) with numerous variables in modern campaign is a typical non-deterministic polynomial (NP) complete problem. An optimization model based on improved multi-objective swarm optimization algorithm (MOPSO-II) is established to solve the objective functions of maximum damage probability and minimum ammunition consumption. Since “curse of dimensionality” occurs in the objective swarm optimization algorithm (PSO), the random variable decomposition strategy and cooperative co-evolution evolutionary frame are used for variable decomposition, and also all swarms are composited by using the non-dominated set algorithm in NSGA-II. The simulated results show that MOPSO-II is quicker and more effective than NSGA-II, and can give good WTA quickly, especially when the scale of WTA problem is large.

ordnance science and technology; multi-objective optimization; particle swarm optimization; firepower distribution; Pareto set; weapon-target assignment

2016-01-07

國家自然科學基金青年基金項目(61304001)

夏維(1982—)，男，博士研究生。E-mail:xiawei66@163.com； 劉新學(1964—)，男，教授，博士生導師。E-mail:liyax@sina.com

E920.8

A

1000-1093(2016)11-2085-09

10.3969/j.issn.1000-1093.2016.11.017