基于改進多目標簡化群優化算法求解動態武器目標分配問題

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

(大連大學通信與網絡重點實驗室 遼寧 大連 116622)

0 引 言

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

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

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

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

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

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

1 相關理論

1.1 動態多目標優化問題(DMOP)

DMOP的數學描述如式(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問題的子目標函數,各子目標間相互沖突,這樣的折中解的集合叫做Pareto最優解集、非劣解集或非支配解集,所有Pareto最優解組成的曲面為Pareto前沿。

1.2 諧波步長策略(CLARANS)

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

(2)

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

(3)

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

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

2.1 簡化群優化算法

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

(4)

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

步驟2令i=1。

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

步驟6如果i

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

2.2 MOSSOa總體步驟

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

步驟1隨機創建種群,通過非支配排序算法求得全局最優解。

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

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

步驟4更新全局最優解,如果當前階段時間已到,則轉步驟5,否則轉步驟6。

步驟5程序終止,輸出最優解。

步驟6更新當前迭代次數下的步長值,并執行步驟3。

2.3 MOSSOa具體實現

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

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

(5)

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

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

(6)

(7)

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

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

3 用DCI-HQPSOGA求解SWTA問題

3.1 DWTA問題模型

DWTA問題模型在文獻[1]中SWTA問題模型的基礎上進行構建。

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

RBIik=ci/(ci-j+1)

(8)

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

(9)

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

υi=RBIik·REIi

(10)

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

(11)

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

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

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

(12)

目標價值是對戰術、目標威脅度等指標的綜合考量[12]。

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

(13)

(14)

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

(15)

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

3.2 用DCI-HQPSOGA實現WTA

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

4 實驗與結果分析

4.1 改進多目標SSO性能測試

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

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

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

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

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

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

4.2 MOSSOa在WTA中的應用

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

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

表6 目標價值表

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

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

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

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

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

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

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

5 結 語

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