使用貪心模擬退火算法求解WTA問(wèn)題

傅 勉,王丹丹

(安徽新華學(xué)院 商學(xué)院，安徽 合肥 230088)

0 引 言

武器-目標(biāo)分配(weapon-target assignment,WTA)是管理學(xué)領(lǐng)域中的一個(gè)經(jīng)典難題。隨著武器-目標(biāo)分配問(wèn)題規(guī)模的擴(kuò)大，它的解也會(huì)空前巨大，使得武器-目標(biāo)分配問(wèn)題成為了NP難題。很多學(xué)者嘗試使用智能算法解決WTA問(wèn)題，文獻(xiàn)[1]使用蟻群算法求解WTA問(wèn)題，文獻(xiàn)[2]使用模擬退火算法求解WTA問(wèn)題，但都是針對(duì)武器數(shù)量和目標(biāo)數(shù)量，是一一對(duì)應(yīng)的這種特殊情況進(jìn)行計(jì)算的。文獻(xiàn)[3]使用遺傳算法求解WTA問(wèn)題，但目標(biāo)所分配的武器數(shù)量是事先確定的，不是十分符合現(xiàn)實(shí)情況。文獻(xiàn)[4]使用神經(jīng)網(wǎng)絡(luò)算法求解WTA問(wèn)題，但求解質(zhì)量不是很高?；诋?dāng)前智能算法在求解WTA問(wèn)題上的不足，本文提出將貪心機(jī)制融入模擬退火算法中，通過(guò)不斷貪心尋優(yōu)得到WTA問(wèn)題的最優(yōu)解。

1 WTA問(wèn)題

現(xiàn)有WTA問(wèn)題描述為武器m個(gè)，目標(biāo)n個(gè)，它們之間關(guān)系是1個(gè)武器必須且只能對(duì)應(yīng)1個(gè)目標(biāo)，1個(gè)武器最多可以打擊Ri個(gè)目標(biāo)(i=1，…，n)，1個(gè)目標(biāo)最多可以被Sj(j=1,2…,m)個(gè)武器打擊。Pij(i=1,2...,m;j=1,2…,n)表示武器對(duì)目標(biāo)的命中概率，Xij表示某武器是否打擊某目標(biāo)，1表示打擊，0表示不打擊。最優(yōu)目標(biāo)是武器打擊所有目標(biāo)的成功概率最大。構(gòu)建WTA問(wèn)題模型如下

(1)

2 貪心模擬退火算法設(shè)計(jì)思想

貪心模擬退火算法的思想是基于模擬退火算法容易陷入局部最優(yōu)解這一缺陷，將貪心思想融入模擬退火算法中，在每次模擬退火算法產(chǎn)生新解后對(duì)其進(jìn)行局部貪心搜索，尋找到更優(yōu)解，進(jìn)而提高求解質(zhì)量。

2.1 解編碼確定

為了實(shí)現(xiàn)成功概率最大目標(biāo)，把全部的m個(gè)武器用于打擊所有目標(biāo)，那么解的編碼長(zhǎng)度就是武器數(shù)目m，使用整數(shù)編碼方式，將解記為A=c1,c2,…,ci，…，cn，其中ci指的是第i個(gè)武器打擊目標(biāo)的具體編號(hào)，因此，這個(gè)解就是每個(gè)武器對(duì)應(yīng)的打擊目標(biāo)的具體編號(hào)。舉例說(shuō)明：解(1 2 3 2)表示4個(gè)武器，打擊的是3個(gè)目標(biāo)；具體分配是武器1打擊目標(biāo)1，武器2、4打擊目標(biāo)2，武器3打擊目標(biāo)3。

2.2 目標(biāo)函數(shù)

根據(jù)前面WTA問(wèn)題描述的目標(biāo)，可以把最大成功概率、最小失敗概率建立目標(biāo)函數(shù)

(2)

2.3 新解的產(chǎn)生與接受準(zhǔn)則

2.3.1 新解的產(chǎn)生

產(chǎn)生新解主要是2種策略交叉使用產(chǎn)生，每次運(yùn)行時(shí)會(huì)隨機(jī)使用某一個(gè)策略生成新的解。策略1是兩點(diǎn)翻轉(zhuǎn)策略，主要過(guò)程：在某一個(gè)解編碼串中隨機(jī)地確定2個(gè)點(diǎn)，然后將2點(diǎn)之間的編碼翻轉(zhuǎn)順序逆序排列，比如原始解A=1 2 3 2，如果隨機(jī)選中的是2和3，那么經(jīng)過(guò)翻轉(zhuǎn)策略后，A'=1 3 2 2?？梢钥闯觯D(zhuǎn)策略僅僅改變了每個(gè)武器對(duì)每個(gè)打擊目標(biāo)的打擊順序，但沒(méi)有改變每一個(gè)目標(biāo)實(shí)際被分配的具體武器數(shù)量。因此，需要考慮WTA中會(huì)出現(xiàn)這樣一種情況：武器數(shù)量大于目標(biāo)數(shù)量，即每一個(gè)目標(biāo)被分配的打擊武器數(shù)量可以是Sj(j=1,2…,n)個(gè)，為了達(dá)到原定的成功概率最大這個(gè)目標(biāo)，需要隨時(shí)地修正打擊目標(biāo)的武器數(shù)量。因此，另一個(gè)策略是：選擇那些打擊武器數(shù)量超過(guò)一個(gè)的被打擊目標(biāo)，將解空間中所有的這類目標(biāo)變更為1-n中的其他目標(biāo)。比如：原始解A=2 3 1 3，目標(biāo)是3，其打擊武器是武器2和武器4，把第1個(gè)目標(biāo)3轉(zhuǎn)化為打擊目標(biāo)2，因此，產(chǎn)生的新解就是A'=2 2 1 3。

2.3.2 接受準(zhǔn)則

本文使用Metropolis作為接受準(zhǔn)則，即

(3)

其中，參數(shù)Δf是新產(chǎn)生解和當(dāng)前解的差值，參數(shù)t是控制參數(shù)。當(dāng)Δf<0，可以接受新產(chǎn)生解；當(dāng)Δf≥0時(shí)，需要進(jìn)行以下的判斷：隨機(jī)生成1個(gè)0～1之間的隨機(jī)數(shù)，若r大于等于這個(gè)隨機(jī)數(shù)，那么接受這個(gè)新解；否則，不接受這個(gè)新解。

2.3.3 冷卻進(jìn)度表等參數(shù)的選擇

冷卻進(jìn)度表是控制模擬退火算法的基本參數(shù)，主要包括開(kāi)始溫度、結(jié)束溫度、衰減系數(shù)、Markov鏈的長(zhǎng)度和結(jié)束規(guī)則，合理選擇冷卻進(jìn)度表參數(shù)是應(yīng)用該算法的關(guān)鍵環(huán)節(jié)。在仿真實(shí)驗(yàn)中，文章借鑒文獻(xiàn)中給出的冷卻進(jìn)度表參數(shù)選取[5-6]，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證得到如下結(jié)論：開(kāi)始溫度T對(duì)仿真實(shí)驗(yàn)結(jié)果影響不大，結(jié)束溫度Tstop最好控制在低于0.01，衰減系數(shù)tr選擇大于0.9，Markov鏈長(zhǎng)度可以取21～41。衰減函數(shù)設(shè)置：tk+1=tk*tr。

2.4 貪心機(jī)制

把貪心算法思想融入模擬退火算法中提高局部尋優(yōu)的能力，貪心算法的思想是盡可能使每一個(gè)武器都能最大限度地去選擇那些能夠提高命中概率的打擊目標(biāo)，具體實(shí)現(xiàn)步驟：

1)針對(duì)具體的WTA問(wèn)題，按照從大到小的順序排列所有武器的命中概率，放入1個(gè)二維的數(shù)組optimal_target[m][n]中。比如說(shuō)，如果是m=6，n=5這樣的一個(gè)問(wèn)題，這個(gè)問(wèn)題有5個(gè)目標(biāo)，需要儲(chǔ)存每一個(gè)武器的前面3個(gè)最優(yōu)秀目標(biāo)科，并將其放入二維的數(shù)組optimal_target[6][3]里面(表1)。

表1 optimal_target[6][3]數(shù)組值

2)如果需要執(zhí)行貪心算法的解是5、4、1、3、5、2。

3)設(shè)定貪心算法執(zhí)行次數(shù)times是1。

4)隨機(jī)地選擇解5、4、1、3、5、2中的某一個(gè)位置，如果是位置4，那么對(duì)應(yīng)的是目標(biāo)3和武器4。

5)在這個(gè)二維的數(shù)組當(dāng)中，第4個(gè)武器的最優(yōu)目標(biāo)是optimal_target[4][1]等于5，它對(duì)應(yīng)的武器是1。然后，計(jì)算這2個(gè)武器對(duì)這個(gè)目標(biāo)的單發(fā)命中概率的和為a=P43+P15；如果把武器4的最優(yōu)良目標(biāo)5配置給它，那么就需要把目標(biāo)3和目標(biāo)5進(jìn)行互換，然后計(jì)算互換后的單發(fā)命中概率的和b=P45+P13。如果b大于a，表示該解使得目標(biāo)函數(shù)向更優(yōu)良發(fā)展，那么可以互換目標(biāo)5和目標(biāo)3；否則，需要進(jìn)一步尋找稍弱一點(diǎn)的最優(yōu)目標(biāo)optimal_target[4][2]=4，那么得到a=P43+P24。如果互換目標(biāo)3和目標(biāo)4之后，算出b=P44+P23，假如b大于a，那么互換目標(biāo)3和目標(biāo)4；否則的話，需要繼續(xù)尋找下一個(gè)最優(yōu)良目標(biāo)，直到找到best_target[4][3]。

6)若執(zhí)行次數(shù)times>m/2，貪心算法執(zhí)行結(jié)束，轉(zhuǎn)到步驟7；否則，執(zhí)行次數(shù)times增加1次，并且轉(zhuǎn)到步驟(4)。

7)輸出貪心算法執(zhí)行后得到的最優(yōu)解。

2.5 貪心模擬退火算法描述

步驟1：確定武器-目標(biāo)分配問(wèn)題的相關(guān)參數(shù)m、n、R、S、P，給出冷卻進(jìn)度表的相關(guān)參數(shù)T、Tstop、tr，鏈長(zhǎng)度Mmax，計(jì)算機(jī)隨機(jī)地生成1個(gè)開(kāi)始解；

步驟2：計(jì)算初始解的能量值大??；

步驟3：如果T

步驟4：如果迭代的次數(shù)>Mmax，那么轉(zhuǎn)到步驟9；

步驟5：隨機(jī)地選擇新解產(chǎn)生中的某一個(gè)策略以生成新的解，并對(duì)這個(gè)新產(chǎn)生的解執(zhí)行貪心尋優(yōu)過(guò)程；

步驟6：計(jì)算新產(chǎn)生解的能量值大小，執(zhí)行前面分析的具體接受準(zhǔn)則；

步驟7：保留優(yōu)化過(guò)程中生成的最優(yōu)解和它的能量值；

步驟8：增加迭代數(shù)，然后轉(zhuǎn)到步驟4；

步驟9：計(jì)算T=T*tr，迭代次數(shù)設(shè)置為1，轉(zhuǎn)到步驟3；

步驟10：輸出執(zhí)行得到的最優(yōu)解和最優(yōu)能量值。

3 仿真實(shí)驗(yàn)

某地艦艇聯(lián)隊(duì)有m=14個(gè)武器，其攻擊的目標(biāo)數(shù)分別是n=12、10、8、6、4個(gè)，Sj=4(j=1,2，…,n)。單發(fā)命中概率見(jiàn)表2。

表2 命中概率

仿真程序在MATLAB中進(jìn)行編制。主要使用的基本參數(shù)T取1，Tstop取0.01，tr取0.95，Mmax取為20，采用前面構(gòu)建的貪心模擬退火程序，得到了最優(yōu)方案(圖1)。在圖1中，目標(biāo)數(shù)分別是12、10、8、6、4時(shí)，使用不同符號(hào)(▲△□○◇)表示分配的結(jié)果?？梢钥闯觯〉昧俗顑?yōu)分配方案。

武器分配結(jié)果目標(biāo)12345678910111213141◇▲□◇?△◇?□○?△○2◇□▲△□○◇?◇□3▲□◇○◇?□○◇?○?△◇4◇◇?▲◇○?△□○◇5○▲△□○○?□6▲△□○○7□▲△?□△8▲△□△□▲9△?▲△?▲10△?▲11?▲12?▲

圖1 分配結(jié)果圖

為了方便比較，分別使用相同的數(shù)據(jù)采用遺傳算法和神經(jīng)網(wǎng)絡(luò)算法以及貪心模擬退火算法對(duì)上面5個(gè)案例進(jìn)行求解。表3給出這幾種算法的求解結(jié)果及其比較。很顯然，貪心模擬退火算法的求解結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于其他兩種算法的結(jié)果，證明了本文使用方法的有效性。

表3 不同算法最優(yōu)值比較

4 結(jié) 論

WTA問(wèn)題是典型的NP難題，文章針對(duì)當(dāng)前學(xué)術(shù)界在求解WTA問(wèn)題中存在不足，提出了將貪心算法融入模擬退火算法中，構(gòu)建了貪心模擬退火算法。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性和可借鑒性。