面向?qū)Φ卮驌粑淦?目標(biāo)分配問(wèn)題的遺傳算法變量取值控制技術(shù)

王然輝， 王超

(1.61683部隊(duì)， 北京 100094；2.火箭軍工程大學(xué)， 陜西 西安 710025)

?

面向?qū)Φ卮驌粑淦?目標(biāo)分配問(wèn)題的遺傳算法變量取值控制技術(shù)

王然輝1， 王超2

(1.61683部隊(duì)， 北京 100094；2.火箭軍工程大學(xué)， 陜西 西安 710025)

對(duì)地打擊目標(biāo)與武器類(lèi)型復(fù)雜多樣，其武器- 目標(biāo)分配問(wèn)題難度較大，研究不足，而合理的武器- 目標(biāo)分配方案，可優(yōu)化資源配置，用最小的代價(jià)獲取最大的戰(zhàn)場(chǎng)收益。為此，構(gòu)建相應(yīng)數(shù)學(xué)模型，并針對(duì)采用遺傳算法進(jìn)行解算時(shí)收斂速度慢，甚至無(wú)法得出可行解等問(wèn)題，設(shè)計(jì)了一種變量取值控制方法。該方法通過(guò)約束和控制初始種群個(gè)體中變量的取值范圍來(lái)縮小搜索空間，提高搜索效率；通過(guò)改進(jìn)變異策略擴(kuò)大變量取值范圍，確保解的質(zhì)量。仿真結(jié)果表明，改進(jìn)的遺傳算法能有效地解決大規(guī)模對(duì)地打擊武器- 目標(biāo)分配問(wèn)題，且性能較優(yōu)。

兵器科學(xué)與技術(shù)； 武器- 目標(biāo)分配； 毀傷貢獻(xiàn)度； 遺傳算法； 變量取值范圍

0　引言

武器- 目標(biāo)分配(WTA)是指揮決策中的關(guān)鍵問(wèn)題，根據(jù)WTA中的目標(biāo)是否具有威脅性，可分為廣義的WTA與狹義的WTA[1]。防空武器- 目標(biāo)分配(AD-WTA)屬于典型的狹義WTA，國(guó)內(nèi)外相關(guān)文獻(xiàn)和研究成果很多，不同的算法都有各自的優(yōu)勢(shì)。對(duì)地打擊武器- 目標(biāo)分配(AG-WTA)屬于廣義WTA，由于其時(shí)效性要求沒(méi)有AD-WTA高，問(wèn)題比較復(fù)雜，相關(guān)的研究非常少見(jiàn)。

對(duì)地打擊武器- 目標(biāo)分配是現(xiàn)代戰(zhàn)爭(zhēng)中的重要問(wèn)題。從美軍近幾場(chǎng)局部戰(zhàn)爭(zhēng)中可發(fā)現(xiàn)，贏得戰(zhàn)爭(zhēng)的重要手段是大量打擊和毀傷對(duì)方地面目標(biāo)，以達(dá)削弱其作戰(zhàn)力量和癱瘓相關(guān)設(shè)施的目的，進(jìn)而快速贏得戰(zhàn)爭(zhēng)。為達(dá)成作戰(zhàn)目的，要選用大量的各型武器彈藥打擊各類(lèi)地面目標(biāo)。武器和目標(biāo)的類(lèi)型及數(shù)量眾多，若不能合理分配打擊資源，不僅需要投入過(guò)多的武器打擊目標(biāo)，造成大量的武器資源浪費(fèi)，還可能延誤戰(zhàn)機(jī)，導(dǎo)致作戰(zhàn)目的無(wú)法實(shí)現(xiàn)。因此，深入研究AG-WTA問(wèn)題，建立合理的模型，設(shè)計(jì)高效的算法，是一項(xiàng)十分必要且非常緊迫的任務(wù)。

算法研究方面，王小藝等[2]、楊飛等[3]和張蛟等[4]提出了一種針對(duì)多約束WTA問(wèn)題的粒子編碼方案及模型的適應(yīng)度函數(shù)，解決了粒子的整數(shù)域初始化問(wèn)題，提高了粒子群優(yōu)化算法的迭代效率及尋優(yōu)能力。王瑋等[5]針對(duì)遺傳算法設(shè)計(jì)了一種滿(mǎn)足約束條件的染色體編碼格式，把求解問(wèn)題轉(zhuǎn)化為無(wú)約束的組合優(yōu)化表現(xiàn)形式，為求解問(wèn)題提供了新的思路。余家祥等[6]結(jié)合遺傳算法、模擬退火算法和貪婪算法的優(yōu)點(diǎn)，綜合運(yùn)用3種算法求解艦載武器目標(biāo)分配問(wèn)題。楊山亮等[7]在遺傳算法的基礎(chǔ)上，通過(guò)對(duì)初始種群編碼機(jī)制的優(yōu)化和采用精英選擇及動(dòng)態(tài)遺傳算子的改進(jìn)算法，較好地解決了WTA問(wèn)題。

AG-WTA與AD-WTA有較大的差別。AD-WTA問(wèn)題中，用于攔截空中目標(biāo)的武器類(lèi)型與數(shù)量較少，目標(biāo)類(lèi)型與數(shù)量也不多；用于攔截單個(gè)空中來(lái)襲目標(biāo)的武器數(shù)量通常為1～2發(fā)；武器對(duì)目標(biāo)毀傷屬于0～1毀傷，無(wú)需考慮每發(fā)彈藥對(duì)目標(biāo)的累積毀傷效應(yīng)；其優(yōu)化原則是武器資源損失最小或敵方剩余目標(biāo)數(shù)最少[8]。而AG-WTA問(wèn)題中，打擊地面目標(biāo)的類(lèi)型與數(shù)量很大，使用的武器類(lèi)型多樣、數(shù)量巨大；由于地面目標(biāo)的復(fù)雜性，用于打擊單個(gè)地面目標(biāo)的武器用量也很大；不同武器，甚至不同類(lèi)型的武器作用于目標(biāo)時(shí)，要考慮累積毀傷效應(yīng)；其優(yōu)化原則是以最少的武器消耗達(dá)到預(yù)期目標(biāo)毀傷要求。因此，AG-WTA問(wèn)題的計(jì)算規(guī)模與解空間都遠(yuǎn)大于AD-WTA，現(xiàn)有WTA解決方案難以滿(mǎn)足求解AG-WTA問(wèn)題需要；且現(xiàn)有的方法存在因求解問(wèn)題的維數(shù)過(guò)大而可能導(dǎo)致算法無(wú)法搜索到符合約束條件的解或搜索時(shí)間過(guò)長(zhǎng)的問(wèn)題[9]，在實(shí)際作戰(zhàn)籌劃決策中是不允許出現(xiàn)的，因而需設(shè)計(jì)新的AG-WTA問(wèn)題解決方案。

針對(duì)求解AG-WTA問(wèn)題，本文首先構(gòu)建AG-WTA模型，提出一種基于遺傳算法的變量取值控制方法；而后定義貢獻(xiàn)度概念，并以貢獻(xiàn)度約束各型武器打擊每個(gè)目標(biāo)的用量和武器打擊單目標(biāo)的總用量，縮小變量初始化空間并使變量取值合理化，加快搜索到可行解；之后擴(kuò)大變量變異范圍，改變變異策略，消除因縮小變量取值范圍可能造成的解空間缺失的問(wèn)題，并加快算法收斂速度；最后進(jìn)行算例仿真及對(duì)比，驗(yàn)證提出方法思路的正確性和優(yōu)越性。

1　AG-WTA問(wèn)題

1.1AG-WTA過(guò)程

AG-WTA主要包括兩個(gè)階段。

第一階段：彈目匹配，即針對(duì)某具體目標(biāo)，分析武器的戰(zhàn)斗部毀傷機(jī)理、制導(dǎo)方式是否適用，預(yù)設(shè)陣地發(fā)射或防區(qū)外投射時(shí)射程能否覆蓋目標(biāo)，目標(biāo)周?chē)沫h(huán)境是否滿(mǎn)足武器的作戰(zhàn)要求等，從而選出適宜打擊該目標(biāo)的武器類(lèi)型。

第二階段：分配優(yōu)化，即綜合考慮各型武器總量約束，將適宜的武器按照效費(fèi)比最優(yōu)的方式合理分配給目標(biāo)，使所有目標(biāo)達(dá)到預(yù)期毀傷效果。

1.2AG-WTA問(wèn)題模型

彈目匹配階段涉及的因素非常多，分析過(guò)程非常復(fù)雜，但結(jié)果只有“適宜”或“不適宜”兩種，無(wú)需也無(wú)法進(jìn)行優(yōu)化。

因此，AG-WTA問(wèn)題模型主要針對(duì)分配優(yōu)化階段進(jìn)行設(shè)計(jì)。首先假設(shè)：

1)適宜的武器對(duì)目標(biāo)的毀傷概率為考慮了突防、命中和毀傷等因素的綜合毀傷概率，且同種類(lèi)型武器對(duì)同類(lèi)目標(biāo)的綜合毀傷概率相同；

2)不適宜的武器對(duì)目標(biāo)的毀傷概率為0；

3)為降低風(fēng)險(xiǎn)，所有武器平臺(tái)均在防區(qū)外進(jìn)行發(fā)射，武器的價(jià)值消耗不包含武器平臺(tái)受損部分；

4)暫不考慮目標(biāo)打擊的先后順序，以及一個(gè)波次的最大投射能力限制。

基于上述假設(shè)，簡(jiǎn)要描述AG-WTA問(wèn)題：有N型武器打擊M類(lèi)地面目標(biāo)，使得M類(lèi)目標(biāo)的毀傷分別達(dá)到C1,C2,…,CM. 其中，N型武器數(shù)量分別為N1,N2,…,NN，其價(jià)值分別為V1,V2,…,VN；M類(lèi)目標(biāo)數(shù)量分別為M1,M2,…,MM，第i型武器打擊第j類(lèi)目標(biāo)的綜合毀傷概率為pij(i=1, 2,…,N;j=1, 2,…,M)。武器- 目標(biāo)最佳分配目標(biāo)是以最小武器價(jià)值消耗滿(mǎn)足目標(biāo)毀傷要求，設(shè)第i型武器作用于第j類(lèi)第k個(gè)目標(biāo)的數(shù)量為mijk(k=1, 2,…,Mj)，武器消耗價(jià)值為V，則AG-WTA問(wèn)題模型為

(1)

(2)

2　遺傳算法的變量取值控制技術(shù)

遺傳算法的基本思想來(lái)源于生物的遺傳進(jìn)化，模擬自然界生物群體優(yōu)勝劣汰的進(jìn)化過(guò)程，能夠有效地處理多種優(yōu)化問(wèn)題[10]，經(jīng)過(guò)算法改進(jìn)[5-8,11,12]已在WTA問(wèn)題中得到了廣泛應(yīng)用[1,9]。生物群體的遺傳進(jìn)化起始于初始種群，初始種群的優(yōu)劣直接影響個(gè)體進(jìn)化的速度與方向，若遺傳算法中的初始種群相對(duì)接近于最優(yōu)個(gè)體，則將很快進(jìn)化為最優(yōu)個(gè)體。因此，可以針對(duì)遺傳算法設(shè)計(jì)一種變量取值控制技術(shù)，通過(guò)控制變量取值范圍使得初始種群個(gè)體在可行解空間內(nèi)產(chǎn)生，從而有效提高解的質(zhì)量和計(jì)算效率。

2.1控制變量取值的意義

AG-WTA問(wèn)題是NP完全問(wèn)題，算法搜索空間隨著變量數(shù)量的增加或變量取值范圍的擴(kuò)大呈指數(shù)增加。在AG-WTA問(wèn)題中，變量的個(gè)數(shù)是確定的、不可改變的，其值為武器類(lèi)型數(shù)與目標(biāo)數(shù)的積；但變量取值范圍是不確定的，因AG-WTA一般不會(huì)約束各型武器作用于每個(gè)目標(biāo)的用量，只會(huì)限制各型武器的可用數(shù)量，則在求解中作為變量取值范圍的武器用量區(qū)間是不確定的、可改變的。若變量取值范圍不作控制，即以每類(lèi)武器的數(shù)量作為變量取值范圍上界，則搜索空間內(nèi)生成的WTA方案的數(shù)量極大。

假設(shè)有N型武器，其數(shù)量分別為N1,N2,…,NN；M類(lèi)目標(biāo)，其數(shù)量分別為M1,M2,…,MM. 若以各型武器的數(shù)量作為變量取值范圍上界，則第i型武器打擊第j類(lèi)目標(biāo)的武器用量mij的取值范圍為

mij∈[0,Ni],mij為整數(shù)。

(3)

由(3)式可知，第i型武器打擊第j類(lèi)目標(biāo)時(shí)，變量mij有Ni+1個(gè)可能取值。

對(duì)于第j類(lèi)目標(biāo)，N型武器打擊該類(lèi)第k個(gè)目標(biāo)時(shí)，有N個(gè)變量，將其看作一個(gè)向量，則在這N個(gè)變量取值范圍構(gòu)成的搜索空間內(nèi)，可生成的向量數(shù)量njk為

(4)

當(dāng)N型武器打擊第j類(lèi)的所有目標(biāo)時(shí)，有N×Mj個(gè)變量，則變量取值范圍構(gòu)成的搜索空間可生成的向量數(shù)量nj為

(5)

(6)

式中：向量數(shù)量n值，即為當(dāng)N型武器打擊M類(lèi)全部目標(biāo)時(shí)，所有可能的WTA方案數(shù)量。

從(6)式可以看出，隨著變量取值范圍增大，AG-WTA方案數(shù)量n值迅速增大。但AG-WTA問(wèn)題的可行解數(shù)量為定值，只占全部分配方案數(shù)量的很少一部分，且絕大部分的可行解集中分布在搜索空間的某一區(qū)域，其分布區(qū)域和數(shù)量不受變量取值范圍的影響。因此，若能急劇縮小搜索空間，并使搜索空間包含可行解所在的空間，就可確?？焖偎阉鞯娇尚薪?。

例如，有49發(fā)同種類(lèi)型武器打擊10個(gè)同類(lèi)目標(biāo)，若以武器總量作為變量取值上界，則N1=49，M1=10，根據(jù)(6)式可解算分配方案數(shù)量n(1)為

(7)

若控制變量取值范圍，令其變量上界取值為9，則N1=9，M1=10，根據(jù)(6)式可解算分配方案數(shù)量n(2)為

n(2)=(N1+1)M1=1010.

(8)

由(7)式和(8)式解算的分配方案數(shù)量n(1)和n(2)，可得無(wú)變量取值范圍控制與有變量取值范圍控制搜索空間內(nèi)的分配方案數(shù)量之比α為

(9)

可見(jiàn)，在減小變量取值范圍上界后，搜索空間急劇縮小，搜索空間內(nèi)的分配方案數(shù)量也急劇減少，且縮小后的變量取值范圍總體是合理的，其變量取值范圍構(gòu)成的搜索空間能夠包含絕大部分可行解空間，表明變量取值范圍的合理控制能確?？焖偎阉鞯娇尚薪?。

2.2基于毀傷貢獻(xiàn)度確定取值范圍

變量取值控制方法是通過(guò)對(duì)變量取值范圍進(jìn)行一系列操作來(lái)提高搜索效率，即在遺傳算法初始化過(guò)程中縮小算法搜索空間，以縮短解算時(shí)間；在變異過(guò)程中放大變量取值范圍，確保有合理的解算結(jié)果。對(duì)于遺傳算法求解AG-WTA問(wèn)題，變量為各型武器作用于每個(gè)目標(biāo)的數(shù)量，變量取值范圍是各型武器可能作用于每個(gè)目標(biāo)的數(shù)量區(qū)間。變量取值控制由三部分構(gòu)成：一是約束各型武器作用于每個(gè)目標(biāo)的最大數(shù)量；二是約束作用于每個(gè)目標(biāo)的武器總量；三是擴(kuò)大變量變異區(qū)間并改變變異策略。

對(duì)于同一個(gè)目標(biāo)，要達(dá)到預(yù)期的毀傷效果通常會(huì)使用n枚武器進(jìn)行打擊，對(duì)于同一種武器而言，每枚武器會(huì)貢獻(xiàn)不同的毀傷值，可稱(chēng)之為毀傷貢獻(xiàn)度，用u表示。若第i型武器打擊第j類(lèi)目標(biāo)的毀傷概率為pij，則第n發(fā)的毀傷貢獻(xiàn)度為

(10)

(11)

顯而易見(jiàn)，對(duì)于同一目標(biāo)，在選擇武器時(shí)，單位價(jià)值毀傷貢獻(xiàn)度越大的武器越適宜。

2.2.1約束各型武器作用于每個(gè)目標(biāo)的數(shù)量

(12)

因此，第i型武器打擊第j類(lèi)目標(biāo)的武器用量區(qū)間上界值tij為

tij=n-1.

(13)

2.2.2約束作用于每個(gè)目標(biāo)的武器總數(shù)量

武器類(lèi)型不同、毀傷概率各異，但存在多型武器都適用于打擊同一目標(biāo)的情況，對(duì)于這種情況，在遺傳算法的種群初始化中，就會(huì)給各型適用武器都隨機(jī)賦予打擊該目標(biāo)的武器用量數(shù)值，且數(shù)值為0的可能性小，從而可能會(huì)出現(xiàn)作用于該目標(biāo)的武器數(shù)量過(guò)多，導(dǎo)致在后續(xù)的優(yōu)化中要消耗大量的時(shí)間將作用于該目標(biāo)的武器數(shù)量降到合理的范圍。顯然，打擊某個(gè)j類(lèi)目標(biāo)的武器總量，不應(yīng)大于對(duì)j類(lèi)目標(biāo)毀傷概率最小(min(pij)，i=1, 2,…,N)的武器的取值上界。設(shè)有N型武器適用于打擊第j類(lèi)目標(biāo)，則作用于該類(lèi)每個(gè)目標(biāo)的武器總數(shù)量最大值Tj為

Tj=max (tij),i=1,2,…,N.

(14)

作用于目標(biāo)的武器總數(shù)量最大值確定后，在算法程序中需對(duì)N型武器作用于該目標(biāo)的數(shù)量m1j,m2j, …,mNj進(jìn)行處理，使得滿(mǎn)足：

(15)

2.3通過(guò)定向變異放大變量取值范圍

通過(guò)對(duì)各型武器作用于每個(gè)目標(biāo)的數(shù)量和作用于每個(gè)目標(biāo)的武器總數(shù)量進(jìn)行約束，種群中個(gè)體變量可取值范圍變小，這種變量取值范圍約束總體是合理的。但當(dāng)某型武器對(duì)某類(lèi)目標(biāo)的毀傷概率較小時(shí)，約束后作用于該類(lèi)單個(gè)目標(biāo)的該型武器數(shù)量可能不足以使其達(dá)到要求的毀傷程度，導(dǎo)致約束的變量取值范圍內(nèi)無(wú)可行解。假設(shè)第i型武器打擊第j類(lèi)目標(biāo)，根據(jù)(12)式和(13)式可得第i型武器對(duì)每個(gè)第j類(lèi)目標(biāo)的武器最大用量tij，則其對(duì)第j類(lèi)目標(biāo)的最大毀傷程度βij為

βij=1-(1-pij)tij.

(16)

由(10)式和(12)式可得：當(dāng)0

(1-pij)tijpij<αj≤(1-pij)tij-1pij,

(17)

即

(18)

聯(lián)立(16)式和(18)式又可得

(19)

因此，

(20)

在變異操作過(guò)程中擴(kuò)大變量范圍，使變異過(guò)程中變量可取各型武器實(shí)有數(shù)量?jī)?nèi)的任意數(shù)值，確保搜索到可行解。變量取值范圍的擴(kuò)大增加了搜索空間，使得搜索可行解的時(shí)間變長(zhǎng)，為避免該情況，采取動(dòng)態(tài)定向變異。設(shè)某類(lèi)目標(biāo)要求的毀傷程度為alf0，種群個(gè)體中該類(lèi)目標(biāo)的實(shí)際毀傷程度為alf，若屬于該類(lèi)目標(biāo)的一個(gè)變量值為pop(i,j)，變量對(duì)應(yīng)的某型武器實(shí)有數(shù)量為bound，則在變異過(guò)程中對(duì)其的操作流程如圖1所示。

圖1　遺傳算法變異操作流程圖Fig.1　Flow chart of mutation operation of genetic algorithm

2.4基于變量取值控制技術(shù)的遺傳算法流程

變量取值范圍控制方法應(yīng)用于遺傳算法求解AG-WTA問(wèn)題的流程：

1) 約束各型武器作用于每個(gè)目標(biāo)的數(shù)量。以武器的貢獻(xiàn)度約束各型武器作用于每個(gè)目標(biāo)的數(shù)量，控制初始種群變量取值范圍。

2) 產(chǎn)生初始種群。在設(shè)定的變量取值范圍內(nèi)初始化種群。

3) 約束武器作用于每個(gè)目標(biāo)的總數(shù)量。以作用于某個(gè)目標(biāo)用量最大的單型武器使用數(shù)量max(tij)，作為所有武器作用于該目標(biāo)的最大用量，約束武器總數(shù)量Tj.

4) 控制初始種群變量值。計(jì)算種群個(gè)體中N型武器打擊同一目標(biāo)的用量總和T1j. 若Tj 0，mij=mij-1. 若T0j

5) 計(jì)算種群個(gè)體適應(yīng)值，并進(jìn)行復(fù)制和交叉操作。

6) 進(jìn)行定向變異操，流程如圖1所示。

7) 迭代終止。判斷是否滿(mǎn)足迭代次數(shù)要求，判斷是否滿(mǎn)足目標(biāo)毀傷要求，若兩個(gè)要求都滿(mǎn)足，迭代終止；否則，轉(zhuǎn)入步驟5.

2.5可行性分析

變量控制技術(shù)包括兩個(gè)環(huán)節(jié)：在初始化階段適當(dāng)約束變量取值范圍，壓縮搜索空間，提高搜索效率；在變異迭代過(guò)程中，根據(jù)需要定向微調(diào)武器用量，確保解的質(zhì)量，避免早熟。

由于對(duì)地打擊某一目標(biāo)可以是多型武器的優(yōu)化組合，使得綜合毀傷值達(dá)到預(yù)期毀傷要求，因此在種群初始化過(guò)程中，根據(jù)預(yù)期毀傷要求和每型武器的毀傷貢獻(xiàn)度，適當(dāng)約束作用于某個(gè)目標(biāo)的單型武器數(shù)量和所有武器總量，可有效地縮小搜索空間，提高索搜效率。

變異過(guò)程中，根據(jù)現(xiàn)有武器對(duì)目標(biāo)的綜合毀傷值與預(yù)期毀傷要求之差來(lái)隨機(jī)確定增加或減少武器用量。此時(shí)，武器用量不再受毀傷貢獻(xiàn)度約束。若大于0，表示武器用量偏大，則隨機(jī)減少某型武器數(shù)量；若小于0，表示武器用量偏小，則隨機(jī)增加某型武器用量。從而確保每個(gè)目標(biāo)均達(dá)到預(yù)期毀傷要求，即解可行；且盡量降低總的武器消耗價(jià)值，即解更優(yōu)。

由于采用實(shí)數(shù)編碼的方式，在變異過(guò)程中，無(wú)論是隨機(jī)增加還是減少某型武器的用量時(shí)，都只對(duì)其中的一型武器加1或減1，而不是隨意變換武器用量取值，通過(guò)反復(fù)實(shí)驗(yàn)，適當(dāng)控制變異概率，較好地避免早熟的問(wèn)題。

3　計(jì)算案例

3.1AG-WTA問(wèn)題實(shí)例

針對(duì)典型的AG-WTA問(wèn)題，基于同一背景設(shè)置4個(gè)不同案例，進(jìn)行對(duì)比分析。

案例背景：總共投入5種不同類(lèi)型武器，各型武器的價(jià)值系數(shù)，以及每個(gè)案例中的總投入量如表1所示；打擊一定數(shù)量的6類(lèi)地面目標(biāo)，每個(gè)案例中的目標(biāo)數(shù)量如表2所示；已知各型武器對(duì)每類(lèi)目標(biāo)的毀傷概率如表3所示；要求每個(gè)目標(biāo)的預(yù)期毀傷值達(dá)到0.9以上，求解最佳的武器分配方案。

表1　各類(lèi)武器的價(jià)值及總量

表2　目標(biāo)類(lèi)型及其數(shù)量

表3　武器對(duì)目標(biāo)的毀傷概率

3.2AG-WTA問(wèn)題仿真與分析

針對(duì)以上案例，運(yùn)用Matlab軟件，在相同的軟硬件(Win7 x64，Intel(R) Xeon(R) CPU E3-1240 v3 @3.4 GHz，RAM 16 GB)條件下，分別對(duì)文獻(xiàn)[7]的改進(jìn)遺傳算法和本文提出的解算方法求解AG-WTA問(wèn)題編程仿真，記錄兩種算法優(yōu)化的武器消耗價(jià)值及解算消耗的時(shí)間，其結(jié)果如表4所示。

表4　兩種改進(jìn)算法的解算結(jié)果及消耗時(shí)間對(duì)比

注：表中“變量個(gè)數(shù)”為“武器類(lèi)型數(shù)量×目標(biāo)個(gè)數(shù)”，“-”表示未解算出相應(yīng)結(jié)果。

從表4可以看出，本文采用基于毀傷貢獻(xiàn)度的變量取值控制技術(shù)對(duì)遺傳算法進(jìn)行改進(jìn)，相比文獻(xiàn)[7]改進(jìn)的遺傳算法，計(jì)算結(jié)果更優(yōu)、效率更高，而且隨著變量個(gè)數(shù)(即武器種類(lèi)和目標(biāo)數(shù)量)的增加，其效果更明顯。

4　結(jié)論

針對(duì)AG-WTA這一類(lèi)特殊問(wèn)題，本文采取變量控制的方法對(duì)遺傳算法進(jìn)行改進(jìn)，有兩個(gè)方面的優(yōu)勢(shì)：一是合理壓縮搜索空間，大大地提高計(jì)算效率；二是改進(jìn)變異策略，確保了解的質(zhì)量，有效避免早熟等現(xiàn)象。通過(guò)反復(fù)實(shí)驗(yàn)和對(duì)比分析，該方法針對(duì)大規(guī)模AG-WTA問(wèn)題，在解的質(zhì)量和計(jì)算效率方面具有明顯優(yōu)勢(shì)，且規(guī)模越大時(shí)優(yōu)勢(shì)越明顯。

需要指出的是，本方法在求解AG-WTA問(wèn)題時(shí)具有明顯優(yōu)勢(shì)，不適應(yīng)于求解AD-WTA問(wèn)題，針對(duì)于其他復(fù)雜優(yōu)化問(wèn)題是否有效還有待進(jìn)一步研究。

References)

[1]蔡懷平, 陳英武. 武器- 目標(biāo)分配(WTA)問(wèn)題研究進(jìn)展[J]. 火力與指揮控制，2006，31(12):11-15.

CAI Huai-ping，CHEN Ying-wu. The development of the research on weapon-target assignment (WTA) problem [J]. Fire Control and Command Control, 2006, 31(12):11-15. (in Chinese)

[2]王小藝, 劉載文, 侯朝楨, 等. 防空武器多目標(biāo)優(yōu)化分配建模與決策[J]. 兵工學(xué)報(bào)，2007，28(2)：228-231．

WANG Xiao-yi, LIU Zai-wen, HOU Chao-zhen, et al. Modeling and decision-making of multi-target optimization assignment for aerial defense weapon[J]. Acta Armamentarii, 2007, 28(2):228-231. (in Chinese)

[3]楊飛, 王青, 侯硯澤. 基于整數(shù)域改進(jìn)粒子群優(yōu)化算法的多平臺(tái)武器目標(biāo)分配[J]. 兵工學(xué)報(bào), 2011, 32(7):906-912.

YANG Fei, WANG Qing, HOU Yan-ze. Weapon-target assignment in multi-launcher system based on improved integer field particle swarm optimization algorithm[J]. Acta Armamentarii, 2011, 32(7):906-912. (in Chinese)

[4]張蛟, 王中許, 陳黎, 等. 具有多次攔截時(shí)機(jī)的防空火力分配建模及其優(yōu)化方法研究[J]. 兵工學(xué)報(bào), 2014, 35(10):1644-1650.

ZHANG Jiao, WANG Zhong-xu, CHEN Li, et al. Modeling and optimization on antiaircraft weapon-target assignment at multiple interception opportunity[J]. Acta Armamentarii, 2014, 35(10):1644-1650. (in Chinese)

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

WANG Wei, CHENG Shu-chang, ZHANG Yu-zhi. Research on approach for a type of weapon target assignment problem solving by genetic algorithm[J]. Systems Engineering and Electronics, 2008, 30(9):1708-1711. (in Chinese)

[6]余家祥, 王紹華, 程文鑫. 基于改進(jìn)局部搜索遺傳算法的目標(biāo)分配決策[J]. 系統(tǒng)工程與電子技術(shù), 2008，30(6):1114-1117.

YU Jia-xiang, WANG Shao-hua, CHENG Wen-xin. Target allocation decision making based on improved genetic algorithms with local search[J]. Systems Engineering and Electronics, 2008, 30(6):1114-1117. (in Chinese)

[7]楊山亮, 黃健, 劉洋, 等. 基于遺傳算法的聯(lián)合火力 WTA 問(wèn)題研究[J]. 計(jì)算機(jī)仿真, 2012, 29(3):61-63.

YANG Shan-liang, HUANG Jian, LIU Yang, et al. Analysis of weapon target assignment problem in joint fire strike solving by genetic algorithm[J]. Computer Simulation, 2012, 29(3):61-63. (in Chinese)

[8]Lee Z J, Su S F, Lee C Y. Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2003, 33(1): 113-121.

[9]李勇君, 黃卓, 郭波. 武器- 目標(biāo)分配問(wèn)題綜述[J]. 兵工自動(dòng)化, 2009, 28(11):1-5.

LI Yong-jun, HUANG Zhuo, GUO Bo. Review of weapon-target assignment problem[J]. Ordnance Industry Automation, 2009, 28(11):1-5. (in Chinese)

[10]Aytug H, Khouja M, Vergara F E. Use of genetic algorithms to solve production and operations management problems[J]. International Journal of Production Research, 2003, 41(17): 3955-4009.

[11]李平，李長(zhǎng)文. 武器目標(biāo)協(xié)同火力分配建模及算法[J]. 指揮控制與仿真, 2015, 37(2):36-40.

LI Ping, LI Chang-wen. Modeling and algorithm of weapon target cooperative fire assignment[J]. Command Control & Simulation, 2015, 37(2):36-40. (in Chinese)

[12]武從猛, 王公寶. 遺傳- 蟻群算法在目標(biāo)分配問(wèn)題中的應(yīng)用研究[J]. 兵工自動(dòng)化, 2014, 33(4):8-11.

WU Cong-meng, WANG Gong-bao. Application of genetic ant-colony algorithm in target assignment problem[J]. Ordnance Industry Automation, 2014, 33(4):8-11. (in Chinese)

Variable Value Control Technology of Genetic Algorithm for WTA of Ground Target Attacking

WANG Ran-hui1， WANG Chao2

(1.Unit 61683 of PLA, Beijing 100094, China; 2.Rocket Force University of Engineering, Xi’an 710025, Shaanxi, China)

Research on weapon-target assignment (WTA) of ground target attacking is very difficult due to a wide variety of targets and weapons. A reasonable WTA scheme is developed to optimize the allocation of limited resources, which brings the maximum battlefield gains with minimum costs. For this reason, a mathematical model is established, and the genetic algorithm is used to resolve the optimal result of weapon-target assignment. But the convergence rate of genetic algorithm is slow and can’t even give a feasible solution in solving WTA. A state variable control method is designed to overcome the insufficient of the genetic algorithm. The proposed method can reduce the search space and improve the search efficiency by restraining and controlling the value range of the initial population variables, and ensure the quality of the solution by improving the mutation strategy to expand the value range of the variables. The simulated result shows that the improved genetic algorithm can solve the WTA problem of attacking the ground targets on a large scale effectively.

ordnance science and technology; weapon-target assignment; damage contribution; genetic algorithm; value range of variables

2015-06-09

王然輝(1980—)，男，工程師。E-mail: w_ranhui@163.com

O22.6

A

1000-1093(2016)10-1889-07

10.3969/j.issn.1000-1093.2016.10.016