張瀅，楊任農(nóng)，左家亮，景小寧，何貴波

（空軍工程大學(xué)航空航天工程學(xué)院，陜西西安710038）

改進(jìn)分解進(jìn)化算法求解動態(tài)火力分配多目標(biāo)優(yōu)化模型

張瀅，楊任農(nóng)，左家亮，景小寧，何貴波

（空軍工程大學(xué)航空航天工程學(xué)院，陜西西安710038）

戰(zhàn)前制定合理的火力分配（WTA）方案，可以優(yōu)化資源配置，用最小的代價獲取最大的戰(zhàn)場收益。其一，建立了面向多型武器協(xié)同進(jìn)攻作戰(zhàn)的動態(tài)火力分配（DWTA）多目標(biāo)優(yōu)化模型，由多個階段靜態(tài)模型構(gòu)成，各階段靜態(tài)模型參數(shù)需根據(jù)戰(zhàn)場態(tài)勢實(shí)時獲取；其二，重點(diǎn)研究階段靜態(tài)模型求解算法。針對模型特點(diǎn)，設(shè)計了一種滿足資源約束的編碼方式，融合禁忌搜索和擁擠距離策略，提出了一種改進(jìn)分解進(jìn)化算法。對比實(shí)驗(yàn)驗(yàn)證了算法的可行性、快速性和有效性。

兵器科學(xué)與技術(shù)；多目標(biāo)優(yōu)化；動態(tài)火力分配；分解進(jìn)化算法；禁忌搜索

0 引言

火力分配（WTA）是典型的有約束組合優(yōu)化問題，具有濃厚的軍事應(yīng)用背景。WTA是指根據(jù)作戰(zhàn)意圖、武器性能等要素，將武器分配用于攻擊特定目標(biāo)的過程。

WTA可劃分為靜態(tài)火力分配（SWTA）和動態(tài)火力分配（DWTA）。SWTA只進(jìn)行一次分配，對應(yīng)一次攻擊，與時間無關(guān)。DWTA是一個多階段分配模型，每個階段對應(yīng)一次攻擊，前一階段的決策輸出僅作用于該階段的攻擊，下一階段的決策需根據(jù)前階段的攻擊結(jié)果進(jìn)行調(diào)整并重新分配。DWTA問題最早由Hosein等［1］提出，近年來對該問題的研究呈上升趨勢。建立的模型有基于資產(chǎn)的DWTA模型［1-4］和基于目標(biāo)的DWTA模型［5-7］，均屬于單目標(biāo)優(yōu)化模型。資產(chǎn)DWTA模型的目標(biāo)函數(shù)是需保護(hù)資產(chǎn)的總存活率，目標(biāo)DWTA模型的目標(biāo)函數(shù)是攻擊目標(biāo)的總毀傷率。由于涉及需保護(hù)的我方資產(chǎn)，這些模型適用于防御型作戰(zhàn)。Cai等［8］對WTA問題進(jìn)行綜述，介紹了DWTA的基本概念，對DWTA研究提出了幾點(diǎn)展望：建立考慮多型武器協(xié)同作戰(zhàn)、時間窗口和不確定性等因素的DWTA模型，以及求解這些模型的算法。

WTA屬于非確定性多項(xiàng)式（NP）完全問題［9］，理論上可以采用傳統(tǒng)的運(yùn)籌學(xué)方法，如分枝定界法、動態(tài)規(guī)劃法等，但算法收斂慢，無法在合理時間內(nèi)給出滿意解，尤其在解決大規(guī)模實(shí)際問題時更為突出［10-11］。為此，許多學(xué)者采用啟發(fā)式算法求解WTA問題，如遺傳算法［12］、免疫算法［13］、粒子群算法［14］，以及融合多種啟發(fā)式策略的混合算法［2-3，6，15-16］。

為順應(yīng)現(xiàn)代戰(zhàn)爭對快速決策的強(qiáng)烈需求，特別是涉及多型武器協(xié)同作戰(zhàn)的戰(zhàn)役行動，迫切需要研究自動求解WTA問題的模型和方法。為此，本文針對多型武器協(xié)同進(jìn)攻作戰(zhàn)的DWTA問題，建立多目標(biāo)優(yōu)化模型，結(jié)合分解進(jìn)化和禁忌搜索策略，設(shè)計一種求解該模型分解進(jìn)化的動態(tài)火力分配（D-DWTA）算法，并進(jìn)行仿真測試。

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

定義1 目標(biāo)時間窗口：目標(biāo)能被武器攻擊的暴露時間。

定義2 武器時間窗口：武器從發(fā)現(xiàn)目標(biāo)到命中目標(biāo)所需的最短時間，包括武器系統(tǒng)的反應(yīng)時間和彈藥的飛行時間。

DWTA模型由一系列SWTA模型組成，記有s個階段的DWTA模型為

階段t的決策輸出只用于指導(dǎo)該階段的攻擊，需要根據(jù)階段t的攻擊結(jié)果更新階段t+1的模型參數(shù)。每個階段SWTA模型只與戰(zhàn)場環(huán)境進(jìn)行信息交互，相鄰階段模型不直接關(guān)聯(lián)，如圖1所示。

圖1 DWTA模型示意圖Fig.1 Schematic diagram of DWTA model

考慮在對方領(lǐng)域內(nèi)進(jìn)攻作戰(zhàn)的DWTA問題，沒有需要保護(hù)的我方資產(chǎn)。假設(shè)在階段t使用m（t）型武器攻擊n（t）個目標(biāo)，該階段決策矩陣為（xij（t））n（t）×m（t），xij（t）指階段t攻擊第i個目標(biāo)需使用j型武器的數(shù)量。記

假設(shè)1 在每個階段中允許多種類型武器攻擊同一目標(biāo)。

假設(shè)2 在每階段中每個目標(biāo)至少分配1枚武器［14］。

多個武器攻擊同一目標(biāo)可能出現(xiàn)攻擊沖突。攻擊沖突是指前一個武器爆炸造成下一個武器攻擊失效的現(xiàn)象。例如，采用2枚電視制導(dǎo)炸彈攻擊目標(biāo)，第1枚炸彈爆炸后目標(biāo)周邊產(chǎn)生煙塵，使得第2枚炸彈無法準(zhǔn)確獲取目標(biāo)位置，導(dǎo)致攻擊無效。攻擊沖突主要是由各武器命中目標(biāo)的時間差所造成的，避免沖突的有效做法有3種：1）盡量使得所有武器同時命中目標(biāo)；2）拉開時間差，待爆炸影響消失后再發(fā)射下一個武器；3）根據(jù)武器特點(diǎn)合理搭配不同類型的武器。如，使用電視制導(dǎo)炸彈和GPS制導(dǎo)炸彈攻擊同一目標(biāo)就不會出現(xiàn)攻擊沖突。

定義3 武器攻擊沖突因子δ：由武器特性決定。當(dāng)同時使用多種武器攻擊時，若j型武器不會出現(xiàn)攻擊沖突，則δ=1，否則δ=0.

假設(shè)3 當(dāng)多個同型武器攻擊同一目標(biāo)，若δj=1，則攻擊間隔規(guī)定為該型武器的時間窗口；若δj=0，則采取連續(xù)攻擊方式，盡量使所有武器同時命中目標(biāo)。

假設(shè)4 當(dāng)多型武器攻擊同一目標(biāo)時，假設(shè)每型武器均能在目標(biāo)暴露的第一時間發(fā)現(xiàn)目標(biāo)，并采取第3種做法避免沖突。

模型參數(shù)定義為：

1）δj為j型武器的武器攻擊沖突因子；

2）PK（t）=（pkij（t））n×m：pkij（t）∈［0，1］是指在t階段j型武器攻擊i目標(biāo)的毀傷概率，理論上，在t階段所有的攻擊完成后，i目標(biāo)的毀傷概率為

3）Nj（t）：t階段j型武器的當(dāng)前可用資產(chǎn)。規(guī)定Nj（t）＞0，，為確保模型假設(shè)2，需滿足；

4）cj：1枚j型武器的成本。攻擊i目標(biāo)需消耗，，則所有攻擊的總消耗為；

5）vi（t）：t階段i目標(biāo)的價值。在t階段攻擊完成后，從i目標(biāo)獲得的收益為；

考慮收益最大和消耗最小這兩個目標(biāo)函數(shù)，則SWTA（t）模型如下：

3）時間窗口約束：由模型假設(shè)4，為確保武器攻擊有效，需滿足；

4）xij（t）∈N+，

在t+1階段，SWTA（t+1）模型可更新的參數(shù)有m（t+1）、n（t+1）、PK（t+1）、Nj（t+1）、vi（t+ 1）、ωi（t+1）、.如果我方獲取的戰(zhàn)場態(tài)勢信息不足或不明確，將出現(xiàn)不確定性參數(shù)，可利用模糊理論修改SWTA（t+1）模型。

2 分解進(jìn)化多目標(biāo)優(yōu)化算法

一般地，多目標(biāo)優(yōu)化問題可表述為

式中：Ω為η維決策空間；（f1，…，fξ）T∈Ψ?Rξ為ξ維目標(biāo)向量；函數(shù)F：Ω→Ψ的映射。

MOEA/D算法是由Zhang等［17］于2007年提出的一種較為新穎的算法，是將傳統(tǒng)的多目標(biāo)求解策略與進(jìn)化算法相結(jié)合的優(yōu)秀范例。算法將ξ個目標(biāo)函數(shù)的優(yōu)化問題轉(zhuǎn)化為對N個單目標(biāo)優(yōu)化子問題的求解。常用的聚合函數(shù)構(gòu)造方法有加權(quán)和法、切比雪夫法和邊界交集法等。

1）加權(quán)和法：對（2）式采用加權(quán)和法構(gòu)造N個單目標(biāo)優(yōu)化子問題，則第r（r=1，…，N）個子問題為

2）切比雪夫法：對（2）式用切比雪夫法構(gòu)造N個單目標(biāo)優(yōu)化子問題，第r（r=1，…，N）個子問題為

定理1 若可行解a*和b*分別是（3）式和（4）式的最優(yōu)解，則a*和b*是（2）式的Pareto最優(yōu)解。

證明 反證法。假設(shè)a*和b*不是（2）式的Pareto最優(yōu)解，?α，β∈Ω，有α?a*，β?b*.對于α?a*，由定義可知［18］，存在集合I1和I2，I1∪I2=｛1，2，…，ξ｝，I1∩I2=?且I2非空，使得?τ∈I1，有fτ（α）=fτ（a*），以及?τ∈I2，fτ（α）＞fτ（a*）.由于，則，即gws（α|λr）＞gws（a*|λr），這與a*是（3）式的最優(yōu)解矛盾，因此，a*是（2）式的Pareto最優(yōu)解。

同理，對于β?b*，由定義［18］可知，存在集合I1和I2，I1∪I2=｛1，2，…，ξ｝且I2非空，則?τ∈I1，有fτ（β）=fτ（b*），以及?τ∈I2，有fτ（β）＞fτ（b*）.而zτ=max｛fτ（x）|x∈Ω｝，則?τ∈｛1，…，ξ｝，有|fτ（β）-zτ|＜|fτ（b*）-zτ|.且，則gte（β| λr，z）＜gte（b*|λr，z），這與b*是（4）式的最優(yōu)解矛盾，則b*是（2）式的Pareto最優(yōu)解。證畢。

因此，通過求解單目標(biāo)優(yōu)化子問題，可以得到（2）式的Pareto最優(yōu)解。

定義3 鄰居向量：對于權(quán)向量λr∈Rξ，稱權(quán)向量λs是λr的鄰居向量，當(dāng)且僅當(dāng)?θ≥0，滿足|λr-λs|≤θ成立。θ值越小，表示權(quán)向量λr和λs關(guān)系越鄰近。

定義4 鄰居子問題：稱第r個子問題是第s個子問題的鄰居子問題，當(dāng)且僅當(dāng)對應(yīng)的權(quán)向量λs是λr的鄰居向量。一般地，鄰居子問題的最優(yōu)解近似相等。

在MOEA/D算法中，進(jìn)化種群X=｛x1，x2，…，xr，…，xN｝，其中xr是子問題r的當(dāng)前最優(yōu)解。根據(jù)鄰居關(guān)系將進(jìn)化種群X劃分為N個子種群。對?r∈｛1，…，N｝，將鄰居子問題的當(dāng)前最優(yōu)解組成子問題r的進(jìn)化子種群Xr=｛xr1，…，xrT｝.由鄰居關(guān)系定義可知，越鄰近的兩個子問題，其目標(biāo)函數(shù)越相近，最優(yōu)解的相似程度越高。

MOEA/D算法優(yōu)點(diǎn)在于，用于解決單目標(biāo)優(yōu)化問題的算法可以不需修改直接用于求解多目標(biāo)優(yōu)化問題，仿真實(shí)驗(yàn)表明該算法較其他算法相比，在解的收斂性、均勻性等性能上均表現(xiàn)良好［17，19］。

3 D-DWTA算法

如圖1所示的DWTA模型，任何階段只能確定下一階段的SWTA模型，后續(xù)階段的SWTA模型參數(shù)必須從戰(zhàn)場環(huán)境實(shí)時獲取。為此，主要研究階段SWTA模型的求解算法。（1）式形式的SWTA模型是：1）組合優(yōu)化問題，其Pareto前沿由若干有限數(shù)量的離散點(diǎn)組成；2）約束較為復(fù)雜，不易獲得可行解；3）就其軍事背景而言，對求解算法的速度要求較高，要考慮大規(guī)模WTA問題的求解效率。因此，可從以下3個方面對MOEA/D算法進(jìn)行改進(jìn)，形成DDWTA算法：

1）收斂速度：模型約束較為復(fù)雜，在種群初始化或遺傳操作時，經(jīng)常產(chǎn)生不滿足約束的個體，需要花費(fèi)大量時間重復(fù)操作或進(jìn)行不可行解修復(fù)，嚴(yán)重制約算法求解速度。為此，需要合理設(shè)計編碼方式，盡量減少算法的不可行解修復(fù)時間，提高收斂速度。

2）收斂性：定理1在一定程度上確保了MOEA/ D算法的收斂性。然而，在應(yīng)用分解類進(jìn)化算法求解某些組合優(yōu)化問題時，不能保證所有Pareto最優(yōu)解都是子問題的最優(yōu)解［20］。也就是說，定理1的逆命題不成立。為此，需在D-DWTA算法中引入某些全局搜索能力強(qiáng)的搜索策略。

3）多樣性：MOEA/D算法假設(shè)，權(quán)向量不同構(gòu)成的子問題最優(yōu)解不同?；谶@種隱性的種群多樣性保持機(jī)制，原算法沒有采取其他多樣性保持策略。對于WTA問題，可以構(gòu)造無窮個子問題，而Pareto最優(yōu)解是有限個數(shù)。如果僅僅依靠MOEA/D算法的隱性多樣性保持機(jī)制，可能導(dǎo)致種群過分集中于某些Pareto最優(yōu)解。為此，需在D-DWTA算法中引入額外的種群多樣性保持策略。

3.1 基于資源約束的整數(shù)編碼

在大規(guī)模WTA問題中，滿足約束的決策矩陣（xij）n×m為稀疏矩陣。如果直接使用模型的決策變量設(shè)計編碼，即個體基因型為x=［x11x12…x1mx21…x2m…xn1…xnm］，則在進(jìn)化時不易得到可行解。

由SWTA模型特點(diǎn)可知，在不考慮彈藥補(bǔ)給的情況下，隨著階段t的不斷增加，可用武器資產(chǎn)數(shù)量不斷減少。為此，可設(shè)計一種基于資源約束的整數(shù)序列編碼方式，確保個體滿足資源約束。記個體基因型x為

基于資源約束的編碼方式認(rèn)為同一型武器的不同個體在分配時是有區(qū)別的（即xk和xij是一種“多對一”的對應(yīng)關(guān)系），實(shí)際上增大了搜索空間，但提高了個體出現(xiàn)在可行區(qū)域的概率。

3.2 子問題構(gòu)造

由于模型只有兩個目標(biāo)函數(shù)，按照以下方式構(gòu)造N個均勻分布的權(quán)向量［21］：

式中：λr∈R2，滿足且λr≥0，r=1，2，…，N.隨著r的增加，函數(shù)f1的重要性將逐漸減小，函數(shù)f2的重要性將逐漸增加。

為了消除量綱的影響，對（3）式的第r個子問題的目標(biāo)函數(shù)做如下改進(jìn)：

3.3 D-DWTA算法描述

算法輸入：

1）如（1）式形式的SWTA模型；

2）正整數(shù)N：子問題數(shù)量；

3）正整數(shù)T：子種群規(guī)模；

4）終止準(zhǔn)則：最大進(jìn)化代數(shù)g_max.

算法輸出：

1）PS=｛x1，x2，…｝：非支配個體集合；

2）PF=｛f（x1），f（x2），…｝：近似Pareto前沿。

算法步驟：

步驟1 初始化。

1）初始化進(jìn)化種群X：隨機(jī)生成N個可行解，組成進(jìn)化種群X=｛x1，…，xN｝，置X中個體間最短距離d（X）為無窮大。

3）構(gòu)造N個子問題：將SWTA模型分解為N個（5）式形式的子問題。為每個子問題隨機(jī)或按照一定原則分配一個個體，記第r（r=1，…，N）個子問題分配的當(dāng)前最優(yōu)解為個體xr.

4）初始化進(jìn)化子種群：計算任意兩個權(quán)向量的歐氏距離組成第r個子問題的進(jìn)化子種群Xr=｛xr1，…，xrT｝.

5）初始化子問題禁忌表：置子問題r的禁忌表為空。

6）初始化非支配解集PS：將X中的非支配個體復(fù)制到PS.

步驟2 子問題進(jìn)化。

1）設(shè)置子問題指示符r=1.

2）禁忌搜索生成子代個體yr.

4）更新PS：對于PS中的所有個體，刪除被yr支配的個體。如果沒有任何個體支配yr，則將yr復(fù)制到PS.

5）若d（X）＞0，用yr更新xr，否則轉(zhuǎn)步驟2的第6步。

更新操作：若gws（yr|λr）＞gws（xr|λr），置xr= yr.

6）令r=r+1.若r＜N，轉(zhuǎn)步驟2的第2步，否則轉(zhuǎn)步驟2的第7步。

7）若d（X）＞0，轉(zhuǎn)步驟2的第8步，否則更新種群X.

更新操作：對X∪Y運(yùn)用NSGA-II算法的快速非支配排序和擁擠距離方法［22］，將前N個最優(yōu)個體復(fù)制到X，并為每個子問題分配X中一個個體。置d（X）為無窮大，轉(zhuǎn)步驟2的第2步。

8）計算d（X）：?xi，xj∈Xr且i≠j，有

步驟3 終止準(zhǔn)則判斷。

如果滿足終止準(zhǔn)則，計算并輸出PS和PF，否則轉(zhuǎn)步驟2的第1步。

對算法補(bǔ)充說明：1）步驟2的第8步中‖f（xi）-f（xj）‖表示兩個向量的歐拉距離；2）d（X）表示所有進(jìn)化子種群內(nèi)個體間最短距離的最小值。若d（X）=0，則進(jìn)行步驟2的第7步更新種群X，增加種群多樣性；3）在子問題進(jìn)化中引入禁忌搜索策略，如步驟2的第2步，提高全局搜索能力。每個子問題維持一個禁忌表，禁忌對象是子問題的目標(biāo)函數(shù)值，適應(yīng)度函數(shù)為子問題目標(biāo)函數(shù)。當(dāng)某個子問題的禁忌表已滿，但仍需要加入新的禁忌對象，則將禁忌表中的最優(yōu)對象解禁。對子問題r的禁忌搜索流程為：

1）確定候選解：從子種群Xr中隨機(jī)選擇兩個個體，通過單點(diǎn)交叉和標(biāo)準(zhǔn)變異算子產(chǎn)生候選解集。

2）判斷候選解的禁忌屬性：若候選解集中不存在非禁忌對象，轉(zhuǎn)步驟3，否則令候選解集中非禁忌對象的最佳解為yr，更新禁忌表和“best so far”狀態(tài)，轉(zhuǎn)步驟4.

3）判斷特赦準(zhǔn)則：若存在候選解優(yōu)于問題r的“best so far”狀態(tài)，則令其為yr，更新問題r的“best so far”狀態(tài)和禁忌表，否則令yr=xr.

4）結(jié)束搜索，輸出yr.

D-DWTA算法流程圖如圖2所示。

4 仿真與分析

實(shí)驗(yàn)想定：設(shè)有9個目標(biāo)和7型武器的WTA問題。為統(tǒng)一量綱，將目標(biāo)價值、武器成本和時間窗口換算為（0，1）之內(nèi)的小數(shù)。模型參數(shù)取值如下所示：

圖2 D-DWTA算法流程圖Fig.2 Flow chart of D-DWTA algorithm

在酷睿i5、主頻2.50 GHz、內(nèi)存4.0 GB、操作系統(tǒng)Windows7、Matlab2010a環(huán)境下進(jìn)行仿真測試。選取MOEA/D算法［17］和NSGA-II算法［23］與D-DWTA算法進(jìn)行性能對比。3種算法均采用相同的編碼方式，選擇、交叉和變異算子，并使用外部種群保存非支配個體。如果進(jìn)化中產(chǎn)生不滿足模型約束的個體，則重復(fù)上一步驟，直到得到滿足約束的新個體為止。每種算法分別獨(dú)立運(yùn)行30次。

定義5 每代相對C值：假設(shè)PSg_max是最終輸出的近似Pareto最優(yōu)解集，PSg是第g代進(jìn)化后得到的近似Pareto最優(yōu)解集，則每代相對C值定義為

式中：di是集合PSg中每個個體距離集合PSg_max的最小歸一化歐式距離。?ai∈PSg：

4.1 收斂速度分析

參數(shù)設(shè)置：禁忌搜索的候選解集規(guī)模為4，禁忌長度為3，禁忌表長度為20，子種群規(guī)模為5.為敘述方便，將MOEA/D算法、NSGA-II算法和D-DWTA算法簡記為算法M、算法N和算法D，平均運(yùn)行時間如表1所示。

表1 平均運(yùn)行時間Tab.1 Mean operating times

參數(shù)設(shè)置：種群規(guī)模為20，最大進(jìn)化代數(shù)為100，其他參數(shù)不變。計算得出3種算法的平均每代相對C值與進(jìn)化代數(shù)的關(guān)系如圖3所示。

D-DWTA算法的禁忌搜索和擁擠距離策略增加了計算量，使得D-DWTA算法不是3種算法中運(yùn)行時間最短的，但是收斂速度最快的。當(dāng)進(jìn)化到13代時，D-DWTA算法的平均相對C值為0.019，非常接近算法最終的近似Pareto最優(yōu)解集。

圖3 平均每代相對C值對比Fig.3 Mean C value of each generation

4.2 收斂性和多樣性分析

參數(shù)設(shè)置：禁忌搜索的候選解集規(guī)模為4，禁忌長度為3，禁忌表長度為20，種群規(guī)模為20，子種群規(guī)模為5，最大進(jìn)化代數(shù)為100.采用兩個集合C值［23］和S值［18］分別衡量3種算法的收斂性和多樣性，用盒圖表示統(tǒng)計結(jié)果，如圖4和圖5所示。

圖4 3種算法的C值統(tǒng)計特性Fig.4 C value statistical properties of 3 algorithms

圖5 3種算法的S值統(tǒng)計特性Fig.5 S value statistical properties of 3 algorithms

實(shí)驗(yàn)結(jié)果表明，與MOEA/D和NSGA-II算法相比，D-DWTA算法求解WTA實(shí)驗(yàn)想定得到的近似Pareto最優(yōu)解集是最優(yōu)的，分布是最均勻的。

5 結(jié)論

本文為解決多型武器協(xié)同進(jìn)攻作戰(zhàn)DWTA問題，建立了由多階段SWTA模型構(gòu)成的DWTA模型。設(shè)計了滿足資源約束的編碼方式縮短不可行解修復(fù)時間，提高算法求解速度。在分解進(jìn)化算法框架下，引入禁忌搜索和擁擠距離策略，提高了D-DWTA算法的收斂性和多樣性。為測試算法效率，與MOEA/D和NSGA-II算法進(jìn)行對比。從仿真結(jié)果可知，D-DWTA算法的求解速度不是最快的，但收斂速度最好，得到的近似Pareto最優(yōu)解是最優(yōu)、分布最均勻的。本文對DWTA模型的求解思路是，通過求解各階段SWTA模型最優(yōu)解得到DWTA模型的相對較優(yōu)解，下一步工作需設(shè)計全階段最優(yōu)求解算法。實(shí)驗(yàn)中為減小求解難度，所有武器都不存在攻擊沖突，即δj=1，j=1，2，…，7，這對武器性能要求比較高，需設(shè)計更為合理的實(shí)驗(yàn)想定測試算法效率。此外，考慮不確定因素的DWTA模型及其求解方法將是下一階段研究內(nèi)容。

（

）

［1］Hosein P A，Athans M.Preferential defense strategies，part II：the dynamic case，LIPS-P-2003［R］.Cambridge，UK：MIT，1990.

［2］Tokg?z A，Bulkan S.Weapon target assignment with combinatorial optimization techniques［J］.International Journal of Advanced Research in Artificial Intelligence，2013，2（7）：39-50.

［3］Xin B，Chen J，Zhang J，et al.Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabusearch heuristics［J］.IEEE Transactions on Evolutionary Computation，2010，40（6）：649-662.

［4］Xin B，Chen J，Peng Z H，et al.An efficient rule-base constructive heuristic to solve dynamic weapon-target assignment problem［J］.IEEE Transactions on Evolutionary Computation，2011，41（3）：598-606.

［5］Hosein P A，Athans M.Some analytical results for the dynamic weapon-target allocation problem，LIPS-P-1944［R］.Cambridge，UK：MIT，1990.

［6］Leboucher C，Shin Hyo-Sang，Siarry P，et al.A two-step optimisation method for dynamic weapon target assignment problem［EB/ OL］.US：INTECH，2013［2015-03-09］.http：∥dx.doi.org/ 10.5772/53606.

［7］Havens M E.Dynamic allocation of fire and sensors［D］.Monterey，CA，US：Naval Postgraduate School，2002.

［8］Cai H P，Liu J X，Chen Y W，et al.Survey of the research on dynamic weapon-target assignment problem［J］.Journal of Systems Engineering and Electronics，2005，17（3）：559-565.

［9］Lloyd S P，Witsenhausen H S.Weapon allocation is NP-complete［C］∥Proceedings of IEEE Summer Simulation Conference.Reno，NV，US：IEEE，1986：1054-1058.

［10］Ravindra K A，Arvind K，Krishna C J，et al.Exact and heuristic algorithms for the weapon-target assignment problem［J］.Operations Research，2007，55（6）：1136-1146.

［11］Sikanen T.Solving weapon target assignment problem with dynamic programming，Technology Report 55670［R］.［2014-01-10］.http：∥www.sal.tkk.fi/Optinnot/Mat-2.108/pdf-files/esik08b.pdf.

［12］Bryant A J.String-and permutation-coded genetic algorithms for the static weapon-target assignment problem［C］∥Proceedings of the Genetic and Evolutionary Computation Conference.Montral，Canada：IEEE，2009：2553-2558.

［13］阮旻智，李慶民，劉天花.編隊(duì)防空火力分配建模及其優(yōu)化方法研究［J］.兵工學(xué)報，2010，31（11）：1525-1529. RUAN Min-zhi，LI Qing-min，LIU Tian-hua.Modeling and optimization on fleet antiaircraft firepower allocation［J］.Acta Armamentarii，2010，31（11）：1525-1529.（in Chinese）

［14］劉曉，劉忠，侯文姝，等.火力分配多目標(biāo)規(guī)劃模型的改進(jìn)MOPSO算法［J］.系統(tǒng)工程與電子技術(shù)，2013，35（2）：326-330. LIU Xiao，LIU Zhong，HOU Wen-shu，et al.Improved MOPSO algorithm for multi-objective programming model of weapon-target assignment［J］.Systems Engineering and Electronics，2013，35（2）：326-330.（in Chinese）

［15］Leboucher C，Shin Hyo-Sang，Stephane L M，et al.Novel evolutionary game based multi-objective optimisation for dynamic weapon target assignment［C］∥19th World Congress of the International Federation of Automatic Control.Cape Town，South Africa：International Federation of Automatic Control，2014：3936-3941.

［16］丁鑄，馬大為，于存貴，等.基于禁忌搜索與微粒群優(yōu)化算法的混合優(yōu)化策略算法在目標(biāo)分配問題上的應(yīng)用［J］.兵工學(xué)報，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 Armamentarii，2007，28（9）：1127-1131.（in Chinese）

［17］Zhang Q F，Li H.MOEA/D：a multiobjective evolutionary algorithm based on decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

［18］公茂果，焦李成，楊咚咚，等.進(jìn)化多目標(biāo)優(yōu)化算法研究［J］.軟件學(xué)報，2009，20（2）：271-289. GONG Mao-guo，JIAO Li-cheng，YANG Dong-dong，et al.Research on evolutionary multi-objective optimization algorithms［J］.Journal of Software，2009，20（2）：271-289.（in Chinese）

［19］Li H，Zhang Q F.Multi-objective optimization problems with complicated pareto sets，MOEA/D and NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2009，2（3）：284-302.

［20］Ehrgott M，Gandibleux X.A survey and annotated bibliography of multiobjective combinatorial optimization［J］.OR Spectrum，2000，22（4）：425-460.

［21］Mei Y，Tang K，Yao X.Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem［J］.IEEE Transactions on Evolutionary Computation，2011，15（2）：151-165.

［22］Deb K，Pratab A，Agarwal S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，2（6）：182-197.

［23］Zitzler E，Thiele L.Multiobjective evolutionary algorithms：a comparative case study and the strength Pareto approach［J］. IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.

Improved Decomposition-Based Evolutionary Algorithm for Multi-objective Optimization Model of Dynamic Weapon-target Assignment

ZHANG Ying，YANG Ren-nong，ZUO Jia-liang，JING Xiao-ning，HE Gui-bo
（Aeronautics and Astronautics Engineering Institute，Air Force Engineering University，Xi'an 710038，Shaanxi，China）

A reasonable weapon-target assignment（WTA）scheme is developed to optimize the allocation of limited resources，which brings the maximum awards with minimum costs.A dynamic weapon-target assignment（DWTA）multi-objective optimization model is established，especially for the offensive operation with multi-weapon.The proposed model is composed of several stage static models.The parameters of each stage model are obtained from the battlefield in real time.An algorithm is elaborately studied to solve the stage model based on the hypothesis to deal with the dynamic model.According to the characteristic of the proposed model，an encoding mode is constructed to satisfy the resource constraints.An improved decomposition-based evolutionary algorithm is proposed by mixing of tabu search and crowding distance strategies.Comparative experiments prove that the proposed algorithm is feasible，fast and efficient.

ordnance science and technology；multi-objective optimization；dynamic weapon-target assignment；decomposition-based evolutionary algorithm；tabu search

TP391

A

1000-1093（2015）08-1533-08

10.3969/j.issn.1000-1093.2015.08.022

2014-04-22

張瀅（1988—），女，博士研究生。E-mail：zhangying1988@126.com；楊任農(nóng)（1969—），男，教授，博士生導(dǎo)師。E-mail：cmproof@gmail.com