邱少明，胡宏章，杜秀麗，呂亞娜

(大連大學(xué) 信息工程學(xué)院，遼寧 大連 116622)

0 引言

火力分配屬于武器-目標(biāo)分配(weapon target assignment,WTA)的一種，一直以來是防空作戰(zhàn)研究的熱點，最初來源于防空領(lǐng)域的資源分配問題[1]，其重在解決在復(fù)雜多變的多武器、多目標(biāo)戰(zhàn)場環(huán)境下，如何根據(jù)一定的分配準(zhǔn)則，將武器分配給相應(yīng)目標(biāo)，以期獲取最大作戰(zhàn)收益。不過此過程屬于多參數(shù)、多約束的非確定性多項式完全問題[2]。而對于動態(tài)武器目標(biāo)分配(dynamic weapon target assignment,DWTA)，需要滿足資源、時間、空間等要求，也需要能夠適應(yīng)對戰(zhàn)場態(tài)勢的動態(tài)變化等[3]。傳統(tǒng)的解決方法一般為隱枚舉法、分支定界法、割平面法、動態(tài)規(guī)劃法等，但此類算法收斂慢，難以在合理時間內(nèi)提供滿意解[4]，進(jìn)而較難為指揮員提供有力輔助。

目前針對WTA問題，大多研究都是基于遺傳算法(genetic algorithm,GA)和粒子群算法(particle swarm optimization,PSO)兩大經(jīng)典群體智能算法開展的。在遺傳算法方面，牛曉博等[5]提出了一種快速非支配排序與錦標(biāo)賽選擇相結(jié)合的選擇策略，并以此改進(jìn)帶精英策略的非支配遺傳算法，較好地解決了艦艇編隊的目標(biāo)分配問題。董朝陽等[6]通過設(shè)計合適的適應(yīng)度函數(shù)以及自適應(yīng)的變異概率調(diào)節(jié)機制，提高了算法的尋優(yōu)能力。王然輝等[7]針對遺傳算法收斂速度慢甚至無法收斂的問題，設(shè)計了一種變量取值控制法，能有效減低武器消耗價值。但由于限制了初始種群個體的取值范圍，導(dǎo)致產(chǎn)生初始解的速度偏慢，致使總體求解時間偏長。翟世梅等[8]結(jié)合遺傳算法全局搜索能力強和禁忌搜索算法局部尋優(yōu)能力強的優(yōu)點，綜合運用2種算法求解導(dǎo)彈武器-作戰(zhàn)窗口分配問題。楊進(jìn)帥等[9]引入非隸屬度函數(shù)描述WTA問題的目標(biāo)要求和約束條件，利用模擬退火的Meta-Lamarckian學(xué)習(xí)策略和自適應(yīng)變異改進(jìn)了遺傳算法，有效地提高了算法的收斂速度。同樣地在粒子群算法方面，夏維等[10]將遺傳算法、粒子群算法、Pareto集多目標(biāo)優(yōu)化算法結(jié)合使用，提出了基于大規(guī)模變量隨機分解的改進(jìn)型多目標(biāo)粒子群優(yōu)化算法，有效解決了傳統(tǒng)算法權(quán)重獲取難問題，也適用于較大規(guī)模下的WTA問題。李檳檳等[11]將粒子群中的記憶信息和群體共享信息能力及混沌搜索思想引入到引力搜索算法中，提高了算法的局部搜索能力，能在較少的迭代次數(shù)下得到較優(yōu)解。蘇丁為等[12]用直覺模糊熵來提高粒子群種群的多樣性，進(jìn)而控制算法的收斂速度，提高了算法的尋優(yōu)能力。王順宏等[13]針對更復(fù)雜的對地打擊武器-目標(biāo)分配問題，通過自適應(yīng)選擇慣性權(quán)重和改進(jìn)粒子初始約束，使得改進(jìn)后的粒子群算法效率更高。上述進(jìn)化算法和混合優(yōu)化算法在解決武器目標(biāo)分配問題時，都不同程度地存在易早熟、進(jìn)化速度慢或算法實現(xiàn)復(fù)雜等不足；算例中的武器目標(biāo)規(guī)模通常較小，在較大規(guī)模下分配優(yōu)勢不明顯。

基于上述研究，本文提出了一種基于動態(tài)差分進(jìn)化改進(jìn)蝙蝠算法的動態(tài)火力分配方法。主要貢獻(xiàn)如下：

(1) 綜合考慮武器打擊目標(biāo)效率和目標(biāo)威脅度，構(gòu)建了動態(tài)火力分配模型和相應(yīng)的適應(yīng)度函數(shù)；

(2) 應(yīng)用改進(jìn)的蝙蝠算法求解動態(tài)火力分配問題，并設(shè)計了蝙蝠個體結(jié)構(gòu)；

(3) 為降低算法陷入局部最優(yōu)概率，引入了DDE/rand/2變異策略，提高了解的精度；

(4) 設(shè)計了動態(tài)火力分配方法的仿真對比實驗，對算法的收斂精度和求解效率做了較為詳細(xì)的分析。

1 動態(tài)火力分配模型

(1)

因為真實作戰(zhàn)需要考慮諸元因素，是一個極其復(fù)雜的過程。故本文綜合分配模型復(fù)雜度和算法實現(xiàn)代價的考慮，對火力分配過程進(jìn)行了一定程度的抽象化，為得到對來襲目標(biāo)打擊效果的最大化，采用了如式(2)所示的動態(tài)火力分配模型。

(2)

2 蝙蝠算法

近些年新興元啟發(fā)式算法越來越多地被運用到武器-目標(biāo)分配問題上，如人工蜂群算法[15]和蟻群算法[16]，而蝙蝠算法(bat algorithm,BA)[17]是劍橋大學(xué)的Xin-She Yang在2010年提出的一種搜索全局最優(yōu)解的有效方法。蝙蝠算法和粒子群算法均屬于群體智能啟發(fā)式算法，類似地BA也可分為全局搜索和局部搜索2部分。

2.1 BA的全局搜索

fs=fmin+(fmax-fmin)β,

(3)

(4)

(5)

2.2 BA的局部搜索

局部搜索指在最佳位置集中選定一個位置后，令每只蝙蝠在該位置周圍隨機飛行產(chǎn)生一個新的位置：

(6)

(7)

(8)

3 基于DDE-BA算法的動態(tài)火力分配方法

為解決“早熟”問題，本文將動態(tài)差分進(jìn)化(dynamic differential evolution，DDE)算法中的變異算子引入，利用基于DDE/rand/2的變異策略對蝙蝠個體進(jìn)行差分變異，從而提高動態(tài)火力分配問題解的精度。

3.1 動態(tài)差分進(jìn)化算法

DDE算法是在差分進(jìn)化(differential evolution，DE)算法上改進(jìn)而來的，DE算法包括變異、交叉和選擇3種操作[18]。但DE算法結(jié)構(gòu)在種群更新方面是靜態(tài)的，而非動態(tài)更新的，所以本文采用了個體能動態(tài)更新的DDE算法。DDE中一個新生成的試驗向量如果比目標(biāo)向量更優(yōu)，試驗向量就直接代替目標(biāo)矢量立即進(jìn)入到當(dāng)前種群并參與其后的進(jìn)化過程，從而能加快算法的收斂。

本文采用DDE/rand/2策略生成的比例差分矢量對當(dāng)前代種群個體進(jìn)行擾動：

(9)

3.2 DDE-BA解決動態(tài)火力分配問題

從火力分配模型可以看出，火力分配屬于依據(jù)目標(biāo)函數(shù)進(jìn)行的整數(shù)規(guī)劃問題。本文引入了DDE算法的變異算子，依據(jù)分配模型構(gòu)建了適應(yīng)度函數(shù)，使用DDE-BA算法解決了動態(tài)火力分配問題。

3.2.1 蝙蝠個體結(jié)構(gòu)

本文直接采用公式(1)的矩陣表示一個蝙蝠個體當(dāng)前所處位置，進(jìn)而利用每個蝙蝠在二維搜索空間m×n中對火力分配問題進(jìn)行求解。其中蝙蝠個體的結(jié)構(gòu)如圖2所示。

圖1 DDE算法中變異矢量的生成Fig.1 Generation of Mutation Vectors in DDE Algorithm

圖2 蝙蝠結(jié)構(gòu)Fig.2 Structure of bat

3.2.2 初始化蝙蝠個體

本文中的火力分配問題，依據(jù)式(2)中的約束條件得知某一時刻分配出的武器數(shù)量需要滿足實際戰(zhàn)場上某類武器總數(shù)量的約束，因此在初始化生成火力分配問題可行解時，要滿足上述的約束條件。但可行解的生成速度勢必會影響到算法整體的搜索效率，而在有約束的情況下，適當(dāng)放寬約束條件可以大大加快可行解的生成速度，故本文按照式(10)來放寬每類武器的數(shù)量約束。

(10)

3.2.3 構(gòu)建適應(yīng)度函數(shù)

前期為加快初始種群的生成，放寬了武器數(shù)量的限制，所以可能造成分配給目標(biāo)的武器數(shù)量越過上限；另外后期蝙蝠在搜索過程中的隨機飛行也會出現(xiàn)分配方案中的武器數(shù)量不滿足式(2)中的約束條件，這樣會導(dǎo)致偏離真實作戰(zhàn)中武器數(shù)量的情況，從而失去了問題求解的意義。所以本文采用懲罰函數(shù)來核查蝙蝠個體對約束條件的違反情況，具體做法是對于每個單獨的蝙蝠個體，利用式(2)計算得出其目標(biāo)函數(shù)值Tar(Xt)；此外再按式(11)和(12)來計算蝙蝠個體的懲罰值。

G(Xt)=-Pun·Ct，

(11)

(12)

式中:Pun是一個大數(shù)量級的正實整數(shù)。在迭代過程中使用式(13)所示的適應(yīng)度函數(shù)值來尋優(yōu)，當(dāng)最終適應(yīng)度值收斂達(dá)到當(dāng)前搜索的最大值時，目標(biāo)函數(shù)值也達(dá)到了最大值，此時蝙蝠個體位置對應(yīng)的分配矩陣則為當(dāng)前最優(yōu)的武器-目標(biāo)分配方案。

Fit(Xt)=Tar(Xt)+G(Xt).

(13)

3.2.4 算法終止條件

本文算法的收斂準(zhǔn)則如下：①連續(xù)20次迭代過程中適應(yīng)度值不變；②若不滿足準(zhǔn)則①，確定基本迭代次數(shù)Iter=500，到達(dá)迭代次數(shù)后取一增量ΔIter=20，再經(jīng)過ΔIter代后，若平均適應(yīng)度值無明顯提升(<0.3%)。當(dāng)滿足以上收斂準(zhǔn)則時，就確定算法達(dá)到了收斂狀態(tài)，此時終止算法，并選取適應(yīng)值最大的蝙蝠個體對應(yīng)的分配方案作為火力分配問題的最優(yōu)解輸出。

3.2.5 算法流程

經(jīng)過上述步驟，利用DDE-BA算法解決動態(tài)火力分配問題的流程圖如圖3所示。

圖3 DDE-BA算法求解流程圖Fig.3 Solution flowchart of DDE-BA algorithm

4 仿真校驗

表1 武器火力數(shù)量Table 1 Number of weapons firepower

表2 目標(biāo)威脅度Table 2 Target Threat Degree

表3 武器打擊目標(biāo)效率Table 3 Weapon strike target efficiency

另外對本文3.5.2中“初始化參數(shù)”部分作如下設(shè)置，設(shè)算法種群規(guī)模NP為30，各個蝙蝠響度A和脈沖發(fā)射率r初始均為0.5，聲波頻率f初始為0，其最大取值fmax為2，最小取值fmin為0。差分變異算子中的縮放因子ε取0.5，懲罰函數(shù)中大數(shù)量級的正實整數(shù)Pun取10 000。為驗證本文所提算法解決動態(tài)火力分配問題的有效性和其較高的收斂精度，特設(shè)計了仿真對比試驗，得到了如圖4所示的DDE-BA與其他幾種算法的收斂對比圖。

圖4 DDE-BA與其他幾種算法的收斂對比圖Fig.4 Convergence contrast graph of DDE-BA and other algorithms

從圖4可以看出，4種算法的火力分配目標(biāo)值都隨著迭代次數(shù)的增加而增加，隨后達(dá)到一個穩(wěn)定的值。這驗證了本文在解決動態(tài)火力分配問題時，將其抽象為第1節(jié)的模型后，使其變成了一個有約束條件下的求最大值的整數(shù)規(guī)劃問題。

當(dāng)分別用這4種算法對第1節(jié)的模型進(jìn)行求解，由圖4可以看到，DDE-BA算法在270次迭代后收斂，最終的火力分配目標(biāo)值為5.059。而BA算法在490次迭代后獲得的目標(biāo)值為5.054，文獻(xiàn)[13]的PSO算法在430次迭代后獲得的目標(biāo)值為5.054，而改進(jìn)GA算法在480次迭代后獲得的目標(biāo)值為5.05。由此可見，本文的DDE-BA算法能在較少的迭代次數(shù)下獲得較高的火力分配目標(biāo)值，說明DDE-BA算法在同等條件下比BA、文獻(xiàn)[13]的PSO和改進(jìn)GA算法具有更高的收斂精度。

同時本文算法收斂后所得解如表4所示，對應(yīng)模型中的變量xij。對照表1可以看出每類武器都被合理地分配給了相應(yīng)的目標(biāo)，沒有出現(xiàn)違背武器數(shù)量約束的情況，每個目標(biāo)也保證了至少分配了一個武器，武器-目標(biāo)分配結(jié)果較合理。

為進(jìn)一步討論DDE-BA算法的收斂速率，對DDE-BA、改進(jìn)GA和文獻(xiàn)[13]的PSO算法在以下3種不同規(guī)模進(jìn)行連續(xù)隨機的50次試驗后，得到3種算法在3種規(guī)模下求解時間如表5所示。

表4 最優(yōu)的武器-目標(biāo)分配結(jié)果Table 4 Optimal Weapon-Target Assignment Results

表5 DDE-BA與另2種算法運算時間的比較

5 結(jié)束語

本文提出了基于DDE改進(jìn)BA算法求解動態(tài)火力分配問題的方法。該方法在算法初始種群階段，適當(dāng)放寬武器數(shù)量的約束，加快了算法初始解的生成，也在一定程度上加快了解的生成效率。其次將DDE算法中產(chǎn)生變異矢量的差分變異機制引入到BA算法的迭代尋優(yōu)過程當(dāng)中，提高了BA算法的收斂精度，可以收獲更大的武器目標(biāo)分配效益值。最后的仿真結(jié)果也表明，本文算法在較大規(guī)模下的武器-目標(biāo)分配問題中，縮短了求解時間，提高了BA算法的收斂速率，從而能為動態(tài)火力分配問題的求解提供一種新的思路。