邱少明 王雪珂 杜秀麗 馮江惠 王建偉

(大連大學(xué)通信與網(wǎng)絡(luò)重點實驗室 遼寧 大連 116622)

0 引 言

武器-目標分配問題(Weapon Target Assignment,WTA)提供武器資源的分配方案,是一種非確定性多項式(Non-deterministic Polynomial,NP)完全問題。目前重點研究多個判別標準下求解最優(yōu)分配方案的問題,因此?？醋鞫嗄繕藘?yōu)化問題(Multi-objective Optimization Problem,MOP),WTA通常分為靜態(tài)武器目標分配問題(Static Weapon Target Assignment,SWTA)和動態(tài)武器目標分配問題(Dynamic Weapon Target Assignment,DWTA),SWTA的分配是對武器的一次完全分配,而DWTA的出現(xiàn)是由于作戰(zhàn)時目標在空間和時間上的不確定性,使部分武器不能高效地投入戰(zhàn)斗,或新出現(xiàn)的目標使分配過程更加復(fù)雜造成的。DWTA的研究大部分都與實際作戰(zhàn)環(huán)境結(jié)合,模型中觸及諸多要素,過程也更為復(fù)雜,所以目前研究結(jié)果較少。在算法模型上,由于目標群的出現(xiàn)屬于隨機過程,且整個武器系統(tǒng)的空間分布形態(tài)多樣,不同類型目標出現(xiàn)的時空分布不同,所以,對DWTA的模型研究十分復(fù)雜,目前主要研究在特定的作戰(zhàn)態(tài)勢下,通過假設(shè)一些條件來簡化和分析問題。DWTA分配階段是通過在有限時間內(nèi),合理地分配各階段的WTA方案,最終得到WTA最優(yōu)方案。Kline等[1]系統(tǒng)地總結(jié)了從1958年到2018年為止,SWTA和DWTA模型從基礎(chǔ)模型到適應(yīng)各種復(fù)雜變體的改進模型,并分析了這些模型的利弊,本文的模型有一部分也參考了該文中的模型設(shè)計。

對DWTA問題的研究主要在于尋求一種有效算法,解決時間因素對武器目標對分配過程的影響,目前很多研究仍然局限于沒有從分配的動態(tài)過程解決問題,或局限于靜態(tài)分配的思想,例如,Chen等[2]提出的基于禁忌搜索的拍賣算法和基于貪婪局部搜索的Memetic算法解決帶約束的WTA問題就局限于靜態(tài)分配的思想。劉傳波[3]通過在DWTA問題中提出Memetic算法,設(shè)置每個目標的截止時間來動態(tài)調(diào)整武器的作戰(zhàn)狀態(tài),并用遺傳算法結(jié)合模擬退火算法平衡算法的開發(fā)和探索。該算法具有任意時間輸出特性,在性能和動態(tài)隨機過程表現(xiàn)出色,符合實際武器目標分配的需求。邱少明等[4]在蝙蝠算法初始部分,放寬部分約束條件,并結(jié)合差分進化算法,求解效率更高效。

DWTA問題可以體現(xiàn)作戰(zhàn)過程的隨機性,近年來考慮了時間因素的DWTA逐漸成為研究的重要方向。Kalyanam等[5]提出通過隨機動態(tài)規(guī)劃得到最大預(yù)期累積獎勵的最優(yōu)閉環(huán)控制策略,通過對目標設(shè)置閾值控制武器對目標的分配。Wang等[6]針對離散粒子群優(yōu)化算法(DPSO)解決大規(guī)模及復(fù)雜離散問題時收斂慢甚至無收斂的問題,提出一種基于直覺模糊熵的離散粒子群算法,通過制定粒子群直覺模糊參數(shù)的選擇策略及速度突變機制和位置突變策略,改善了可能的次優(yōu)位置及鄰域,用該算法解決DWTA問題,可以得到較好的全局最優(yōu)解。Chang等[7]提出了一種改進的人工蜂群(ABC)算法,利用基于規(guī)則的啟發(fā)式因子對種群進行初始化,解決了傳統(tǒng)ABC算法收斂慢的問題,并將該算法根據(jù)DWTA的特點用整數(shù)編碼來解決DWTA問題,加快了求解過程,并提高了解的準確性,由此表明ABC算法是一種有效的SI優(yōu)化算法。

DWTA是在SWTA的基礎(chǔ)上發(fā)展而來,是下一步研究的重點。該領(lǐng)域的研究仍處于起步階段,其中在DWTA模型中大多問題都是基于特定的假設(shè)簡化環(huán)境,進行對應(yīng)的計算,對不確定因素的影響不能準確量化,再加上時間、地點、氣候、地形和武器性能等約束條件偏少,因此目前的各種模型還不能普適化。在算法方面,目前的算法也普遍具有收斂速度慢、面對大規(guī)模問題時收斂精度低、不能滿足DWTA對時間的要求等問題,因此必須對現(xiàn)有算法進行組合與改進,研究如何加快算法運行時間,以及如何平衡求解精度與求解效率的問題。

有很多優(yōu)秀的智能計算算法可以改造為多目標優(yōu)化算法,為求解多目標問題服務(wù),例如Yeh[8]提出的單目標簡化群優(yōu)化算法(Simplified Swarm Optimization,SSO)就在收斂性方面得到了比粒子群優(yōu)化算法(PSO)更好的效果,所以將這些算法及其變體算法的多目標實現(xiàn)應(yīng)用到WTA問題中,有望得到更高的收斂效率和更優(yōu)的解。

本文首先在單目標諧波簡化群優(yōu)化算法的基礎(chǔ)上,將單變量搜索機制轉(zhuǎn)變?yōu)槿兞克阉鳈C制,并引入非支配排序算法,支持多目標優(yōu)化的進化算法應(yīng)用。由于此前沒有對該算法進行過多目標情況下的研究,所以將該算法與多目標簡化群優(yōu)化算法、多目標單變量諧波簡化群優(yōu)化算法用ZDT系列多目標測試函數(shù)進行性能方面的對比分析,然后將算法運用到DWTA中研究其求解效率。仿真驗證多目標簡化群優(yōu)化算法的收斂性和多樣性,結(jié)果表明將該算法應(yīng)用到DWTA問題中時,在求解精度較高的情況下,求解效率相對其他算法有較大提升。

1 相關(guān)理論

1.1 動態(tài)多目標優(yōu)化問題(DMOP)

DMOP的數(shù)學(xué)描述如式(1)所示。

(1)

s.t.gi(X,t)≤0i=1,2,…,p

X∈Ω(t)?Rnt∈[t0,ts]

式中:t∈[t0,tx]?R,X=(x1,x2,…,xn)T是Rn空間的n維向量;gi(x,t)叫作基于時間變量t的約束條件,Ω(t)={x|gi(x,t)≤0,i=1,2,…,p}是決策變量空間,且僅當所有目標上的決策向量X1不比另一個決策向量X2差時,叫作X1支配X2;fi(X,t),i=1,2,…,m為階段t問題的子目標函數(shù),各子目標間相互沖突,這樣的折中解的集合叫做Pareto最優(yōu)解集、非劣解集或非支配解集,所有Pareto最優(yōu)解組成的曲面為Pareto前沿。

1.2 諧波步長策略(CLARANS)

諧波步長策略(Harmonic Step-length Strategy,HSS)旨在改善傳統(tǒng)連續(xù)SSO中步長固定對求解帶來的影響[9],為了提高開發(fā)性能,根據(jù)諧波序列,HSS如下:

(2)

式中:Δi,k是i代第k個變量的步長;Uk和Lk是第k個變量的上限和下限;i是當前代數(shù);k是當前變量的索引;Nvar是變量數(shù);符號“· ”是下限函數(shù)。式(2)中的1.25是文獻[9]中已被證明的可得到更優(yōu)值的初始步長。經(jīng)過實驗,Δ=1.25的效果勝過其他取值。1、1/2、1/3和1/4等的順序被稱為諧波序列,基于諧波序列提出的HSS可以表示為:

(3)

讓每一代步長持續(xù)50代。步長Δi,k的值從一個生成周期減少到另一個生成周期。gBest和某些解決方案經(jīng)過長期運行或幾代后接近最佳值。這些解決方案的更新僅需稍作更改即可更接近最佳狀態(tài),而不會脫離最佳狀態(tài)。使用諧波序列,因此將步長從HSS的早期固定生成調(diào)整為后期動態(tài)生成,以克服連續(xù)SSO固定步長的障礙。

2 基于改進多目標SSO(MOSSOa)

2.1 簡化群優(yōu)化算法

SSO是Yeh[8]提出的一種新的基于總體的優(yōu)化算法,以彌補粒子群優(yōu)化算法(PSO)在解決離散問題方面的不足。由于該算法的簡單性、效率和靈活性,它特別適合解決多變量優(yōu)化問題。SSO與PSO一樣,還使用搜索空間內(nèi)的大量隨機解進行初始化,然后由更新機制指導(dǎo)搜索以尋找最佳解,更新機制表示為:

(4)

令Nsol和Nitr分別表示總體大小和迭代總數(shù)。SSO的總體步驟概述如下:

步驟2令i=1。

步驟5如果F(Pi)比全局最優(yōu)解F(G)好,則G=Pi。

步驟6如果i

步驟7若t=Nitr,程序結(jié)束;否則t=t+1,返回步驟2。

2.2 MOSSOa總體步驟

改進多目標SSO的整體步驟簡述如下:

步驟1隨機創(chuàng)建種群,通過非支配排序算法求得全局最優(yōu)解。

步驟2當前代數(shù)為1,根據(jù)式(2)設(shè)置步長的初始值。

步驟3重新計算粒子中的每個變量。

步驟4更新全局最優(yōu)解,如果當前階段時間已到,則轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟6。

步驟5程序終止,輸出最優(yōu)解。

步驟6更新當前迭代次數(shù)下的步長值,并執(zhí)行步驟3。

2.3 MOSSOa具體實現(xiàn)

在SSO中,全局最優(yōu)方案gBest在產(chǎn)生新種群方面起著關(guān)鍵作用,SSO在擴展到多目標進化算法時,全局最優(yōu)方案應(yīng)被一種非支配方案代替,這里選用非支配排序算法求Pareto解,非支配排序算法有兩步,首先對粒子劃分等級,其次在同一級中,根據(jù)每個粒子的擁擠距離進行統(tǒng)一排序,擁擠距離越近,說明多樣性越差,粒子在同等級時擁擠距離近的應(yīng)排在較后的位置。

文獻[10]中已證明SSO中用個體最優(yōu)解pBest更新個體的一種方案可以被丟棄,從而獲得更有效的解決方案,這樣做不會影響求解質(zhì)量,因此使用文獻[9]中式(2)關(guān)于連續(xù)SSO的更新機制,去掉利用pBest更新的一項,如式(5)所示。

(5)

在更新機制中增加步長元素,步長間隔為[-1,1]。但是即使這樣也不能得到很好的解,因此文獻[9]中通過將步長中的間隔從[-1,1]修改為[-0.5,0.5],并將SSO中的三個參數(shù)cr、cg和cw從固定的一個值變成每個解都有對應(yīng)的值。另外在更新過程中,對每個解中的每個變量都進行更新,這里稱為全變量更新機制(Update Mechanism all-variable,UMa),對應(yīng)的有單變量更新機制(Update Mechanism one-variable,UM1)。如果步長太長,則更新機制無法收斂到最佳狀態(tài);相反,如果步長太短,則沒有足夠的動力來尋找解,即尋找解的周期會變長。當步長固定時,不能通過動態(tài)調(diào)整使粒子接近最終點,因此將HSS機制運用到步長的更新中,使步長隨著迭代動態(tài)更新。

綜上,結(jié)合2.1節(jié)的原始SSO更新機制和1.2節(jié)的HSS策略,改進后的粒子更新公式如式(6)和式(7)所示。

(6)

(7)

式中:Xi+1,j是更新后的個體;j表示階段數(shù);k表示第k個變量;σ1,k和σ2,k是在[-0.5,0.5]之間產(chǎn)生的統(tǒng)一隨機變量;ρk是[0,1]間的統(tǒng)一隨機變量;Δk的步長用式(3)進行改進;gk表示全局最優(yōu)解的第k個變量。

在式(7)中,只能將解決方案更新為更好的值;否則,UMa將保留原始解決方案,然后再進行更新。式(6)是UMa中最重要的部分,其背后的概念是每個變量都更新為其自身的鄰域,即gBest的鄰域。通過上述方案改進解的質(zhì)量。

3 用DCI-HQPSOGA求解SWTA問題

3.1 DWTA問題模型

DWTA問題模型在文獻[1]中SWTA問題模型的基礎(chǔ)上進行構(gòu)建。

DWTA模型中對目標的約束條件可以分為對目標的空間約束和時間約束兩種,這里將模型簡化,只考慮對目標的時間約束,DWTA模型在SWTA模型的基礎(chǔ)上,將分配過程分為兩個階段,每個階段隨機選擇若干個目標,作為該時間環(huán)境下可打擊的目標,對所選擇的目標隨機分配武器,分配的合理度用資源耗費均衡性指標(Resource-consumption Balance Index,RBI)來衡量[11],假設(shè)一共有t個階段,第k個階段所耗費武器的資源溢價系數(shù)的計算式為:

RBIik=ci/(ci-j+1)

(8)

假設(shè)現(xiàn)階段所使用武器的比例占總武器數(shù)量的比例為Bi,可用式(9)表示。

(9)

該指標中的資源溢價系數(shù)可以判斷當前階段的武器供給負荷,通過將武器供給負荷量化,得到資源溢價系數(shù),與作戰(zhàn)成本相關(guān)聯(lián),來保證資源消耗的均衡性。

υi=RBIik·REIi

(10)

則武器i第k次調(diào)度資源耗費指數(shù)表示為式(11),其中Ni為當前階段的剩余武器總數(shù)量。

(11)

資源耗費指數(shù)要近似或小于目標現(xiàn)階段的價值比例r,以保證在下一階段有足夠的武器資源,實際上該資源耗費均衡性指標相當于一個約束條件。

式中:xij表示分配給目標j的第i種武器的數(shù)量。

構(gòu)建兩個目標函數(shù):目標生存概率最小函數(shù)f1和武器彈藥消耗最少函數(shù)f2。第i種武器對目標j的毀傷概率為pij,第i種武器打擊目標j時目標j的生存概率為qij=1-pij、價值為Vj。f1計算式表示為:

(12)

目標價值是對戰(zhàn)術(shù)、目標威脅度等指標的綜合考量[12]。

設(shè)武器消耗量取決于武器使用個數(shù)與其對于目標的價值,則f2計算式表示為:

(13)

(14)

綜上所述,DWTA模型如式(15)所示。

(15)

i=1,2,…,m,j=1,2,…,n,k=1,2,…,t

3.2 用DCI-HQPSOGA實現(xiàn)WTA

DWTA問題種群的初始化使用各類武器對目標的毀傷概率表和目標價值表,種群規(guī)模為PSize=50,武器種類數(shù)m=10,每種武器數(shù)對應(yīng)為C=[3,1,1,5,1,1,1,8,1,10],目標數(shù)n=8。在此基礎(chǔ)上,加入“階段”這個時間環(huán)境,假設(shè)當前有兩個階段,第一階段出現(xiàn)目標的比例用一個隨機值r表示,然后從目標集合中隨機挑選出占總數(shù)量比例為r的目標,作為當前要打擊的對象。武器的分配滿足約束條件,其中武器在現(xiàn)階段分配的資源耗費指數(shù)不能大于r,以保證后續(xù)階段武器處于可防御狀態(tài),否則武器數(shù)量過少,將不能勝任防御任務(wù)。對于每個階段的時間要求,根據(jù)武器的總數(shù)量以及以往學(xué)習(xí)經(jīng)驗中對作戰(zhàn)規(guī)模的了解,為每個階段設(shè)定1 s的分配時間。

4 實驗與結(jié)果分析

4.1 改進多目標SSO性能測試

因本文算法在迭代過程中會更新所有變量,記為MOSSOa,MOSSO1算法與MOSSOa其他地方相同,唯一不同的地方是在對粒子迭代更新時MOSSO1只隨機更新粒子中的一個變量。首先,采用兩目標測試函數(shù)ZDT2-ZDT4對比分析MOSSO、MOSSO1和MOSSOa三種算法的性能,三個測試函數(shù)是兩目標最小化問題,其中ZDT4具有219個局部最優(yōu)值,干擾全局Pareto前沿的搜索,可檢測算法克服陷入局部最優(yōu)的能力[15];再用GD(世代距離)、IGD(反世代距離)、HV(超體積指標)和Spacing(均勻性度量指標)檢測算法收斂性和多樣性,GD度量解的收斂性,Spacing度量解分布的均勻性,IGD和HV綜合度量解的收斂性和多樣性,多樣性包括體現(xiàn)粒子分布均勻程度的均勻性和整個解集在目標空間中分布廣泛程度的廣泛性,GD、Spacing和IGD值越小越好,HV值越大越好。MOSSO1算法在文獻[9]中作為一種單目標算法被提出,這里將其改造成多目標算法進行分析,除了只更新粒子中的一個變量,其他地方都與MOSSOa保持一致。實驗種群數(shù)和迭代次數(shù)均為100,取20次運行的最好結(jié)果,所求Pareto前沿如圖1所示,四種性能指標結(jié)果如表1-表4所示。

表1 三種算法在GD指標上的比較

表2 三種算法在IGD指標上的比較

表3 三種算法在HV指標上的比較

圖1 三種算法在ZDT1-ZDT4上的Pareto前沿

可以看出,MOSSOa算法與真實Pareto曲線重合得最多,MOSSO算法次之,最差的是MOSSO1算法。在ZDT2和ZDT3中,MOSSOa算法的值較其他兩種算法有明顯的優(yōu)勢,說明MOSSOa算法無論從收斂性還是多樣性來看都優(yōu)于其他兩種算法,但是算法在ZDT4函數(shù)上效果低于其他兩種算法,說明算法在跳出局部最優(yōu)方面沒有MOSSO算法好,MOSSO算法保留了個體最優(yōu)解,可以找到多個峰值,從而避免了陷入局部最優(yōu),所以在ZDT4函數(shù)上效果最好,但是這樣也影響了收斂效率。綜上,MOSSOa算法較優(yōu)于其他兩種算法。

4.2 MOSSOa在WTA中的應(yīng)用

各類型武器對目標的毀傷概率表和目標價值表如表5和表6所示[16],其中Wi表示第i種武器。迭代次數(shù)為3 000,武器種類數(shù)m=10,每種武器數(shù)對應(yīng)為C=[3,1,1,5,1,1,1,8,1,10],目標數(shù)n=8。

表5 武器對目標毀傷概率值表

表6 目標價值表

假設(shè)當前有兩個階段,第一階段出現(xiàn)目標的比例用一個隨機值r表示,然后從目標集合中隨機挑選出占總數(shù)量比例為r的目標,作為當前要打擊的對象。武器的分配滿足約束條件,其中武器在現(xiàn)階段分配的資源耗費指數(shù)不能大于r,以保證后續(xù)階段武器處于可防御狀態(tài),否則武器數(shù)量過少,將不能勝任防御任務(wù)。對于每個階段的時間要求,根據(jù)武器的總數(shù)量以及以往學(xué)習(xí)經(jīng)驗中對作戰(zhàn)規(guī)模的了解,為每個階段設(shè)定1 s的分配時間。

改進多目標SSO在DWTA問題中的求解效果主要通過各階段的求解質(zhì)量和求解效率兩方面來驗證,為進行對比分析,MOSSO算法和MOSSOa算法也實現(xiàn)了在DWTA各階段的求解,為了直觀地表示求解質(zhì)量的高低,將兩個目標函數(shù)作歸一化求和處理并作求解質(zhì)量曲線,三種算法在兩個階段的收斂情況如表7所示,三種算法的求解質(zhì)量和求解效率如圖2所示。

表7 三種算法在兩個階段的收斂情況表

圖2 三種算法在DWTA問題中的收斂效果

可以看出,在兩個階段中,MOSSOa比其他兩個算法求解質(zhì)量更高。MOSSO和MOSSO1兩者各在一個階段中比另一個好,則不能看出哪個更優(yōu)秀。算法在每個階段執(zhí)行的時間相同,迭代的次數(shù)不同,線條周長越長,代表迭代次數(shù)越多,從第一階段明顯看出,MOSSO1的線條最長,因此其迭代次數(shù)最多,說明算法執(zhí)行一次的時間最快,但也因此犧牲了求解質(zhì)量。從表7可以看出,MOSSOa比MOSSO迭代次數(shù)多,算法執(zhí)行時間更快,但還是沒有MOSSO1快,因為MOSSO1在每個粒子中只隨機選擇一個變量進行更新。而MOSSO中,每個粒子需要使用兩個以上的方程式,生成兩個隨機數(shù)、四個乘法和三個求和,才能移至下一個迭代。由于MOSSOa不需要使用速度,它僅使用幾個隨機數(shù),粒子的每個變量只循環(huán)一次。所以與MOSSO算法相比,MOSSOa算法消耗更少的計算時間,效率更高。

在MOPSO中,所有粒子將根據(jù)粒子的局部和全局最佳值連續(xù)移動,這意味著該算法不會吸收外部新鮮值中的任何其他成分,而MOSSOa可以顯示出其效率,尤其是在覆蓋后重新定位目標對象時。MOSSOa具有靈活的粒子自適應(yīng)搜索窗口以及自適應(yīng)參數(shù)。

MOSSOa的更新機制比其他主要算法的更新機制簡單得多,使用以上方法可以有效地維持粒子的多樣性,同時保持較高的求解效率。

5 結(jié) 語

本文主要圍繞DWTA問題,對適于求解該問題的算法進行研究。將MOSSOa算法應(yīng)用于DWTA模型,并進行收斂速度和精度分析。本文算法首先將非支配排序算法引入SSOa算法中,使其變?yōu)槎嗄繕藘?yōu)化算法;其次在SSOa算法中引入HSS策略,在更新過程中動態(tài)改變步長,獲得更為多樣化的解,在ZDT測試函數(shù)中的測試效果表明算法收斂性較好。將算法應(yīng)用于具有RBI指標衡量的DWTA算法中,證明了在保證每個階段分配合理的情況下,算法可以求得較優(yōu)的解。算法的解決對滿足實際應(yīng)用條件的武器目標分配問題進行繼續(xù)深入研究具有深刻的現(xiàn)實意義,繼續(xù)提高算法處理的時效性及靈活性是下一步研究的重點。