夏維， 劉新學(xué)， 范陽(yáng)濤， 元鋒剛

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

?

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

夏維1， 劉新學(xué)1， 范陽(yáng)濤1， 元鋒剛2

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

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

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

0 引言

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

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

1 理論基礎(chǔ)

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

(1)

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

(2)

約束條件為：

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

2)進(jìn)攻方對(duì)目標(biāo)Tj最多可使用sj枚導(dǎo)彈，即

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

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

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

(3)

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

定義1 Pareto支配。設(shè)f:Rm→Rk,x1,x2∈Ω?Rm，稱解x1支配解x2當(dāng)且僅當(dāng)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)化解當(dāng)且僅當(dāng)集合{x|x?x*,x∈Ω}=?.

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

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

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

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

用一定數(shù)量的第i類型號(hào)導(dǎo)彈攻擊第j個(gè)目標(biāo)的殺傷概率可表示為

Pij=1-(1-eij)xij.

(4)

則所有的m種型號(hào)導(dǎo)彈對(duì)目標(biāo)j的毀傷概率Pj為

(5)

(6)

為便于多目標(biāo)計(jì)算，取目標(biāo)函數(shù)f1=1-f最小來(lái)表示對(duì)敵毀傷期望f最大。

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

(7)

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

(8)

1.4 MOPSO算法

粒子群優(yōu)化(PSO)算法是由Kennedy等[20]于1995年提出的一種新型智能優(yōu)化算法，源于對(duì)鳥(niǎo)群覓食行為中相互協(xié)作的研究，是一種大范疇群體智能算法。PSO算法利用粒子的個(gè)體認(rèn)知和社會(huì)交互引導(dǎo)群體收斂到潛在的全局最優(yōu)區(qū)域。假設(shè)D維解空間存在N個(gè)粒子，基本的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為當(dāng)前粒子的位置；pid為粒子本身所找到的最優(yōu)解pb；pgd為整個(gè)種群目前找到的最優(yōu)解gb；r1與r2是介于[0,1]間的隨機(jī)數(shù)；ω、C1和C2分別為控制這3部分內(nèi)容的學(xué)習(xí)因子，ω又叫慣性權(quán)重，正常數(shù)C1和C2被稱為加速因子。

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

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

2 MOPSO-Ⅱ算法

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

2.1 粒子編碼與解碼

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

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

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

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

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

解碼時(shí)，從左至右依次掃描整個(gè)編碼。掃描至pk時(shí)，首先得到pk所對(duì)應(yīng)的導(dǎo)彈型號(hào)i，接著檢查pk取值，若pk=0則說(shuō)明pk所對(duì)應(yīng)型號(hào)的導(dǎo)彈沒(méi)有分配給任何目標(biāo)；若pk=j則說(shuō)明pk對(duì)應(yīng)型號(hào)的導(dǎo)彈被分配給了第j個(gè)目標(biāo)。

2.2 變量隨機(jī)分解策略

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

圖3 變量隨機(jī)分解過(guò)程圖Fig.3 Process chart of variable random decomposition

2.3 適應(yīng)度評(píng)價(jià)

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

(11)

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

2.4 算法框架描述

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

(12)

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

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

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

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

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

對(duì)外部種群進(jìn)行更新操作的具體步驟為：

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

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

Cd=

(13)

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

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

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

2.5 算法流程

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

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

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

3)Numesp=1，對(duì)第1個(gè)子種群進(jìn)行迭代處理；

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

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

6) 當(dāng)Numesp=NumespMax時(shí)，重新進(jìn)行變量隨機(jī)分解，重復(fù)執(zhí)行步驟3～步驟5；

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

2.6 算法時(shí)間復(fù)雜度分析

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

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

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

3) 輸出外部種群中所有解個(gè)體的時(shí)間為O(N′)。因此，MOPSO-II算法的時(shí)間復(fù)雜度應(yīng)為O(SNlnN)+O(MSN2)+O(N′)=O(MSN2). 由此可見(jiàn)，相比于NSGA-II算法的時(shí)間復(fù)雜度O(MS2N2)來(lái)說(shuō)，MOPSO-Ⅱ算法的要小。

3 仿真及算例分析

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

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

目標(biāo)的重要度系數(shù)和每種型號(hào)導(dǎo)彈對(duì)各目標(biāo)的毀傷概率分別由如下威脅系數(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，學(xué)習(xí)因子C1=C2=2，種群規(guī)模的大小為100、200，算法終止的條件為最大迭代次數(shù)200，變異概率為0.1，分組大小為50. 程序獨(dú)立運(yùn)行20次得到的結(jié)果如表2所示。

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

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

圖7 兩種算法運(yùn)行時(shí)間對(duì)比圖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ī)模較小時(shí)，兩種算法所花費(fèi)的運(yùn)行時(shí)間差別不大，但是隨著規(guī)模的增加，MOPSO-Ⅱ算法的運(yùn)行效率更高，時(shí)間花費(fèi)更少。當(dāng)種群規(guī)模為300，迭代為200時(shí)，仿真結(jié)果如圖8和圖9所示，圖中的每個(gè)解均代表一種分配方案。例如：f2=19，1-f1=0.14時(shí)，其染色體所對(duì)應(yīng)的編碼方案為[2 8 1 7 3 9 6 9 6 10 9 10 2 3 6 5 8]，導(dǎo)彈與目標(biāo)分配如表3所示。

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

表3 目標(biāo)分配方案

4 結(jié)論

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

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] 許建中. 基于遺傳算法的武器目標(biāo)分配模糊多目標(biāo)規(guī)劃[J]. 軍事運(yùn)籌與系統(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] 袁形形. 遺傳多目標(biāo)優(yōu)化算法的研究[D]. 北京:中國(guó)地質(zhì)大學(xué), 2010. YUAN Xing-xing. Research of multi-objective evolutionary algorithms[D]. Beijing: China University of Geosciences,2010.(in Chinese)

[4] 曲在濱, 劉彥君, 徐曉飛. 用離散粒子群優(yōu)化算法求解WTA問(wèn)題[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 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] 肖嶸, 趙成旺, 王護(hù)利, 等. 多群協(xié)同PSO優(yōu)化算法的WTA問(wèn)題求解[J]. 計(jì)算機(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é)同的多目標(biāo)粒子群優(yōu)化算法研究[D]. 南京:南京郵電大學(xué), 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] 謝承旺, 李凱, 徐君, 等. 一種改進(jìn)型多目標(biāo)粒子群優(yōu)化算法MOPSO-Ⅱ[J]. 武漢大學(xué)學(xué)報(bào):理學(xué)版, 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] 崔莉莉. 基于蟻群算法的武器- 目標(biāo)分配問(wèn)題研究[D]. 上海:上海交通大學(xué), 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ì)算法的火力分配問(wèn)題研究[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] 阮旻智, 李慶民, 劉天華. 編隊(duì)防空火力分配建模及其優(yōu)化方法研究[J]. 兵工學(xué)報(bào), 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] 張海兵, 徐誠(chéng), 李世永. 貪心遺傳算法及其在武器目標(biāo)分配問(wèn)題中的應(yīng)用[J]. 彈道學(xué)報(bào), 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)化策略算法在目標(biāo)分配問(wèn)題上的應(yīng)用[J]. 兵工學(xué)報(bào), 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] 麻士東, 龔光紅, 韓亮, 等. 目標(biāo)分配的蟻群- 模擬退火算法及其改進(jìn)[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]. 兵工學(xué)報(bào), 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

國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61304001)

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

E920.8

A

1000-1093(2016)11-2085-09

10.3969/j.issn.1000-1093.2016.11.017