高 尚

(江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，鎮(zhèn)江 212003)

武器-目標(biāo)分配(weapon target assignment)問(wèn)題是現(xiàn)代戰(zhàn)爭(zhēng)中十分重要的問(wèn)題.Lloyd［1］等指出武器-目標(biāo)分配問(wèn)題是一個(gè)NP完全問(wèn)題.為解決這個(gè)問(wèn)題，人們提出了許多算法.Wacholker［2］提出了一種神經(jīng)網(wǎng)絡(luò)的解法，其依據(jù)Hopfield和Tank的神經(jīng)網(wǎng)絡(luò)模型，用此網(wǎng)絡(luò)解WTA問(wèn)題，此方法有時(shí)得不到穩(wěn)定解；文獻(xiàn)［3-4］對(duì)神經(jīng)網(wǎng)絡(luò)模型提出了改進(jìn)算法；文獻(xiàn)［5］用遺傳方法解決了WTA問(wèn)題；文獻(xiàn)［6-7］用蟻群算法解決了WTA問(wèn)題；文獻(xiàn)［8］用粒子群優(yōu)化算法解決了WTA問(wèn)題；文獻(xiàn)［9］用免役算法解決了WTA問(wèn)題.各種算法各有優(yōu)劣，本文用分布估計(jì)算法來(lái)解決WTA問(wèn)題.

1 WTA問(wèn)題

有 n個(gè)目標(biāo) T1，T2，…，Tn，迎擊武器分布于 m個(gè)武器平臺(tái) W1，W2，…，Wm，第 i(i=1，2，…，m)個(gè)武器平臺(tái)最多可使用ri個(gè)武器，對(duì)目標(biāo)Tj最多可使用sj個(gè)武器，武器平臺(tái)Wi迎擊目標(biāo)Tj的概率為pij(i=1，2，…，m；j=1，2，…，n)，武器最佳分配以分配迎擊武器迎擊全部目標(biāo)的失敗概率最小為目標(biāo).

若分配了武器平臺(tái)Wi迎擊目標(biāo)Tj，則xij=1，否則xij=0.WTA問(wèn)題的數(shù)學(xué)模型為

只有當(dāng) ri=1(i=1，2，…，m)，sj=1(j=1，2，…，n)時(shí)，上述問(wèn)題為可轉(zhuǎn)化為指派問(wèn)題，可以用匈牙利法解［6］.對(duì)于一般優(yōu)化問(wèn)題實(shí)質(zhì)是非線(xiàn)性0-1整數(shù)規(guī)劃問(wèn)題，屬于NP-難題，目前沒(méi)有有效的算法解此問(wèn)題.

2 基本分布估計(jì)算法

分布估計(jì)算法的概念最初在1996年被提出［10-11］，分布估計(jì)算法提出了一種全新的進(jìn)化模式.在傳統(tǒng)的遺傳算法中，用種群表示優(yōu)化問(wèn)題的一組候選解，種群中的每個(gè)個(gè)體都有相應(yīng)的適應(yīng)值，然后進(jìn)行選擇、交叉和變異等模擬自然進(jìn)化的操作，反復(fù)進(jìn)行，對(duì)問(wèn)題進(jìn)行求解.而在分布估計(jì)算法中，沒(méi)有傳統(tǒng)的交叉、變異等遺傳操作，取而代之的是概率模型的學(xué)習(xí)和采樣.分布估計(jì)算法通過(guò)一個(gè)概率模型描述候選解在空間的分布，采用統(tǒng)計(jì)學(xué)習(xí)手段從群體宏觀的角度建立一個(gè)描述解分布的概率模型，然后對(duì)概率模型隨機(jī)采樣產(chǎn)生新的種群，如此反復(fù)進(jìn)行，實(shí)現(xiàn)種群的進(jìn)化，直到終止條件.根據(jù)概率模型的復(fù)雜程度以及不同的采樣方法，分布估計(jì)算法發(fā)展了很多不同的具體實(shí)現(xiàn)方法，可以歸納為下面2個(gè)主要步驟［12-13］:首先構(gòu)建描述解空間的概率模型，通過(guò)對(duì)種群的評(píng)估，選擇優(yōu)秀的個(gè)體集合，然后采用統(tǒng)計(jì)學(xué)習(xí)等手段構(gòu)造一個(gè)描述當(dāng)前解集的概率模型；然后由概率模型隨機(jī)采樣產(chǎn)生新的種群，一般地，采用蒙特卡羅方法，對(duì)概率模型采樣得到新的種群.

遺傳算法中的交叉和變異會(huì)破壞已經(jīng)優(yōu)化好的個(gè)體，分布估計(jì)算法用建立概率模型和采樣兩大操作取代了遺傳算法中的交叉算子和變異算子，以一種帶有“全局操控”性的操作模式解決了遺傳算法存在的這一問(wèn)題.遺傳算法和分布估計(jì)算法的流程圖對(duì)比如圖1所示.并且分布估計(jì)算法不需要太多的參數(shù)設(shè)置，編程比遺傳算法簡(jiǎn)單.

圖1 分布估計(jì)算法與遺傳算法的流程異同點(diǎn)

3 解武器-目標(biāo)分配問(wèn)題的改進(jìn)分布估計(jì)算法

首先把原約束方程作為罰函數(shù)項(xiàng)加入到原目標(biāo)中，變成無(wú)約束的優(yōu)化問(wèn)題，即

式中，M1，M2為一充分大的正數(shù).這里提出用分布估計(jì)算法來(lái)解決此問(wèn)題.

解武器-目標(biāo)分配問(wèn)題的分布估計(jì)算法如下:

隨機(jī)產(chǎn)生N個(gè)(取1的概率為0.5)個(gè)體組成一個(gè)初始種群；

2)評(píng)估初始種群中所有個(gè)體的適應(yīng)度，保留最好解；

3)按適應(yīng)度從高到低的順序?qū)ΨN群進(jìn)行排序，并從中選出最優(yōu)的m個(gè)個(gè)體(m≤N)；

4)分析產(chǎn)生的m個(gè)個(gè)體所包含的信息，估計(jì)

采樣，得到N個(gè)新樣本，構(gòu)成新種群；

6)若達(dá)到算法的終止條件則結(jié)束(如達(dá)到規(guī)定迭代次數(shù)nmax)，否則執(zhí)行第2)步.

該分布估計(jì)算法的時(shí)間復(fù)雜性估算如下:以計(jì)算適應(yīng)度操作花費(fèi)最多，所以時(shí)間復(fù)雜性大約為O(Nnmax).

4 算法測(cè)試及參數(shù)設(shè)計(jì)

問(wèn)題 1［6］有 6 個(gè)目標(biāo) T1，T2，…，T6，迎擊武器分布于 4 個(gè)武器平臺(tái) W1，W2，W3，W4，每個(gè)武器平臺(tái)最多可使用武器為(2，1，2，1)，對(duì)每個(gè)目標(biāo)最多可使用1個(gè)武器，武器平臺(tái)Wi迎擊目標(biāo)Tj的概率為 pij(i=1，2，…，4；j=1，2，…，6)，如表1 所示.

表1 m=4，n=6情況迎擊概率表

問(wèn)題 2［7］有 12 個(gè)目標(biāo) T1，T2，…，T12，迎擊武器分布于5個(gè)武器平臺(tái)W1，W2，…，W5，每個(gè)武器平臺(tái)最多可使用武器為(3，3，3，3，3)，對(duì)每個(gè)目標(biāo)最多可使用1個(gè)武器，武器平臺(tái)Wi迎擊目標(biāo)Tj的概率為 pij(i=1，2，…，5；j=1，2，…，12)，如表2 所示.

表2 m=5，n=12情況迎擊概率表

采用分布估計(jì)算法，當(dāng)N=800，m=0.3N時(shí)，最好值的迭代過(guò)程如圖2所示.問(wèn)題1的最優(yōu)解“武器1迎擊目標(biāo)4和目標(biāo)6，武器2迎擊目標(biāo)2，武器3迎擊目標(biāo)1和目標(biāo)3，武器4迎擊目標(biāo)5”，或“武器1迎擊目標(biāo)3和目標(biāo)4，武器2迎擊目標(biāo)2，武器3迎擊目標(biāo)1和目標(biāo)5，武器4迎擊目標(biāo)6”迎擊全部目標(biāo)的失敗概率為1.4.

問(wèn)題2的最優(yōu)解“武器1迎擊目標(biāo)1和目標(biāo)2，武器2迎擊目標(biāo)6和目標(biāo)7，武器3迎擊目標(biāo)4、目標(biāo)9和目標(biāo)11，武器4迎擊目標(biāo)8、目標(biāo)10和目標(biāo)12，武器5迎擊目標(biāo)3和目標(biāo)5”，迎擊全部目標(biāo)的失敗概率為2.9(比文獻(xiàn)［7］結(jié)果好)，最好值的迭代過(guò)程如圖3所示.

圖2 解問(wèn)題1的迭代過(guò)程

圖3 解問(wèn)題2的迭代過(guò)程

影響分布估計(jì)算法性能的主要參數(shù)是種群的個(gè)數(shù)N和選出的種群個(gè)數(shù)m.N取不同值，m=0.3N，解問(wèn)題1和問(wèn)題2，各種算法各測(cè)試100次，統(tǒng)計(jì)數(shù)據(jù)如表3所示.從表3可知，N越小，樣本數(shù)量不足，效果不好；N越大，效果越好，當(dāng)然需要的時(shí)間也越大.因此N取適中即可，如N取800.

當(dāng)N=800時(shí)，選出的種群個(gè)數(shù)m占N的比例不同，結(jié)果也不一樣.不同的比例，解問(wèn)題1和問(wèn)題2，算法各測(cè)試100次，統(tǒng)計(jì)數(shù)據(jù)如表4所示.從表4可以看出，m/N比例越大，不能體現(xiàn)出選優(yōu)的優(yōu)勢(shì)，效果越不好；當(dāng)然m/N比例太小，也容易陷入局部極值.因此m/N比值取30%左右，效果比較好.

5 結(jié)語(yǔ)

本文的分布估計(jì)算法不僅可以解決WTA優(yōu)化問(wèn)題，為研究WTA問(wèn)題提供一種新的思路.對(duì)于整數(shù)規(guī)劃問(wèn)題，對(duì)該算法作適當(dāng)修改，也可適用.分布估計(jì)算法研究處于初期，還有許多問(wèn)題值得研究，如算法的收斂性、理論依據(jù)等.但從當(dāng)前的分布估計(jì)算法的應(yīng)用效果來(lái)看，這種新型的尋優(yōu)思想無(wú)疑具有十分光明的前景，更深入的工作還有待于進(jìn)一步展開(kāi).

表3 N取不同值結(jié)果比較

表4 m/N取不同值結(jié)果比較

References)

［1］Lloyd S P，Witsenhausen H S.Weapons allocation is NP-complete［C］//Proceedings of the IEEE Summer Simulation Conference.Reno，NV，USA，1986:1054-1058.

［2］Wacholder E.A neural network-based optimization algorithm for the static weapon-target assignment problem［J］.ORSA Journal on Computing，1989，1(4):232-246.

［3］Ressler J L，Augusteijn M F.Weapon target assignment accessibility using neural networks［C］//Proceedings of the 1992 Artificial Neural Networks in Engineering.St.Louis，MO，USA，1992:397-402.

［4］朱齊丹，胡紹勇，宋福香，等.解武器-目標(biāo)分配問(wèn)題的神經(jīng)網(wǎng)絡(luò)方法［J］.哈爾濱工程大學(xué)學(xué)報(bào)，1997，18(3):36-41.Zhu Qidan，Hu Shaoyong，Song Fuxiang，et al.A neural network algorithm of solving weapon-target assignment problem［J］.Journal of Harbin Engineering University，1997，18(3):36-41.(in Chinese)

［5］曹奇英，何張兵.WTA問(wèn)題的遺傳算法研究［J］.控制理論與應(yīng)用，2001，18(1):76-79.Cao Qiying，He Zhangbin.A genetic algorithm of solving WTA problem ［J］.Control Theory and Applications，2001，18(1):76-79.(in Chinese)

［6］高尚.武器-目標(biāo)分配問(wèn)題的蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39(3):78-79.Gao Shang.Ant colony algorithm for weapon-target assignment problem［J］.Computer Engineering and Applications，2003，39(3):78-79.(in Chinese)

［7］黃樹(shù)采，李為民.目標(biāo)分配問(wèn)題的蟻群算法研究［J］.系統(tǒng)工程與電子技術(shù)，2005，27(1):79-80；130.Huang Shucai，Li Weimin.Research of ant colony algorithm for solving target assignment problem［J］.Systems Engineering and Electronics，2005，27(1):79-80；130.(in Chinese)

［8］高尚，楊靜宇.武器-目標(biāo)分配問(wèn)題的粒子群優(yōu)化算法［J］.系統(tǒng)工程與電子技術(shù):2005，27(7):1250-1252；1259.Gao Shang，Yang Jingyu.Solving weapon-target assignment problem by particle swarm optimization algorithm［J］.Systems Engineering and Electronics，2005，27(7):1250-1252；1259.(in Chinese)

［9］Lee Z J，Lee C Y，Su，S F.An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem［J］.Applied Soft Computing Journal，2002，2(1):39-47.

［10］周樹(shù)德，孫增圻.分布估計(jì)算法綜述［J］.自動(dòng)化學(xué)報(bào)，2007，33(2):113-124.Zhou Shude，Sun Zengqi.A survey on estimation of distribution algorithms［J］.Acta Automatica Sinica，2007，33(2):113-124.(in Chinese)

［11］Muhliebe H，Paass G.From recombination of genes to the estimation of distributions I.binary parameters［C］//Lecture notes in computer science.Springer Verlag，1996，1141:178-187.

［12］Pelikan M，Godberg D E，Cantu-Paz E.Linkage problem，distribution estimation，and Bayesian networks［J］.Evolutionary Computation，2000，8(3):311-340.

［13］Paul T K，Iba H.Linear and combinatorial optimizations by estimation of distribution algorithms［C］//9th MPS Symposium on Evolutionary Computation.Information Processing Society of Japan(IPSJ)，2002:99-106.