基于改進差分進化算法的跨平臺武器目標分配方法

隆雨佟, 陳愛國, 史紅權, 曾 黎

(1. 電子科技大學計算機科學與工程學院, 四川 成都 611731; 2. 大連艦艇學院, 遼寧 大連 116018)

0 引 言

隨著信息技術和裝備水平的發(fā)展,在現代作戰(zhàn)中,武器單元的劃分粒度更加精細,一次武器通道的組織通常包括預警探測、指揮決策、跟蹤瞄準、火控解算、武器發(fā)射、制導控制等環(huán)節(jié),傳統的平臺級協同作戰(zhàn)方式指各個平臺獨立組織各自的武器通道,而在能力要素級協同作戰(zhàn)方式下武器通道中的各環(huán)節(jié)可由不同平臺交叉完成[1]。因此,跨平臺的能力要素級武器單元協同利用,已成為提高合成編隊等作戰(zhàn)體系效能的重要手段。為了更好地完成能力要素級單元協同作戰(zhàn),武器目標分配(weapon target assignment, WTA)問題中各平臺的分配方案必須分別計算,其建模與求解也面臨著更大的挑戰(zhàn)。因此,亟需一種針對跨平臺WTA問題的建模求解方法以更好地完成合成編隊內各平臺的戰(zhàn)術協同。

在建模方面,現有研究通常將整個編隊作為資源劃分的最小單位[2-3],不關注武器單元具體來自哪個平臺,若后續(xù)涉及到跨平臺協同制導則無法分辨武器的發(fā)射平臺,不利于計算平臺間的協作。文獻[4]提到了多平臺問題,但并沒有相應的約束體現平臺間的差異。另外,現有方法對WTA問題模型決策變量的編碼大致分為兩種,一種定義為某個武器單元是否參與攔截某個來襲目標[5],取值為0或1;一種定義為某類型武器單元參與攔截某個來襲目標的數量[2],取值為非負整數。在后者的定義中,單個決策變量包含的信息大于前者,而兩者的搜索空間是一樣的,因此采用后者的方式定義決策變量能大幅減少計算時間。其次,傳統WTA問題的維度只考慮了武器單元與來襲目標的數量,問題通常被描述為m個武器n個目標的形式,這種做法同樣忽略了武器與來襲目標的種類以及平臺等信息,當同種武器數量過多時編碼長度也會增加,影響求解效率[6-8]。最后,在優(yōu)化目標的選取上,不少研究把最大化毀傷概率作為優(yōu)化目標,同時規(guī)定每次攔截必須把全部資源消耗殆盡[3,5,9],這種做法難以應對多輪次打擊,在真實作戰(zhàn)場景中運用困難,所以應該把資源消耗作為優(yōu)化目標考慮進去。對此,文獻[10]將最小化來襲目標生存概率、最小化彈藥消耗量價值、最小化資產損害作為優(yōu)化目標建立了一個多目標優(yōu)化模型并利用多目標優(yōu)化算法求解,但耗時較長。文獻[11]則將最大化防空作戰(zhàn)效果與武器消耗成本的比值作為優(yōu)化目標建立為單目標優(yōu)化問題,但僅靠比值并不能獨立地反映兩個指標各自的好壞,同樣比值下的兩種分配方案的真實作戰(zhàn)效果可能相去甚遠。因此,優(yōu)化目標的選取上既要綜合考慮毀傷概率與成本消耗,也要獨立反映出兩者的好壞,才能使作戰(zhàn)綜合效益最大化。文獻[12]在建模過程中將武器平臺納入了考慮范圍,但忽略了導彈類型對毀傷概率的影響。

在算法方面,傳統WTA問題已被證明為非確定性多項式完全(non-deterministic polynomial complete, NP-C)問題[13],本文研究的跨平臺WTA問題規(guī)模由來襲目標數量、武器單元種類、平臺數量與武器單元庫存共同決定,四者中的其一增長便會導致問題求解難度呈指數級上漲。對此,學者們提出了精確算法與近似算法以解決該問題。其中,精確算法能夠準確計算出WTA問題的全局最優(yōu)解,如文獻[14]提出了最大邊際收益(maximal marginal return, MMR)算法實現對WTA問題的精確求解。文獻[15]采用動態(tài)規(guī)劃(dynamic programming, DP)也能準確計算出WTA問題的最優(yōu)解。但是精確算法對WTA問題要求較為嚴苛,只能求解比較簡單的小規(guī)模問題;對于高緯度大規(guī)模復雜約束的WTA問題,采用近似算法求解能取得更好的效果[16-19],其中元啟發(fā)式算法應用較為普遍。如文獻[4]提出了采用混沌策略的自適應差分進化算法,該算法通過計算種群適應度的方差判斷是否陷入局部最優(yōu)解,并施加混沌擾動助其跳出局部最優(yōu)。文獻[9]提出了一種基于隨機鄰域的自適應差分進化算法以提高傳統差分進化算法的性能,但求解高維問題仍有困難。文獻[20]提出了一種改進粒子群算法以提高傳統粒子群算法的后期收斂能力。文獻[21]提出了一種基于匈牙利-模擬退火的雙層搜索算法用于解決多階段WTA問題,能夠有效縮短求解時間,但適用場景較窄。文獻[22]提出了一種人工魚群算法與改進和聲搜索算法的混合算法求解WTA問題。文獻[23]提出了一種改進粒子群優(yōu)化算法分階段求解多目標WTA問題。

針對建模方面的問題,本文將決策變量定義為平臺的能力要素級武器單元數量以解決跨平臺協作問題;加入平臺資源約束使模型更貼合現實場景;采用整數編碼的形式讓模型能更高效地解決大規(guī)模問題;再將毀傷概率與成本消耗的分段聯立函數作為優(yōu)化目標,綜合考慮兩者的同時也能獨立反映兩者的優(yōu)劣。

針對算法方面的問題,應該選取快速,高效,穩(wěn)定,通用的優(yōu)化算法用于求解。結合帶存檔的自適應差分進化算法(adaptive differential evolution with optional external archive, JADE)[24]是近年來差分進化算法中比較典型的一種改進算法,尋優(yōu)能力突出,具有優(yōu)秀的可靠性與魯棒性。但經過本文實驗表明,傳統的優(yōu)化算法在搜索后期陷入局部最優(yōu)解時缺乏相應的跳出機制,致使收斂結果停留在局部最優(yōu)解上,這一現象在解決高維度大規(guī)模帶約束優(yōu)化問題時尤為突出。因此,本文利用混沌映射的遍歷性與隨機性提出了一種混沌種群重構(chaotic population reconstruction, CPR)機制,能夠幫助算法跳出局部最優(yōu)解。同時,結合JADE算法提出了CPR-JADE算法,最后通過對比實驗驗證本文方法的有效性。

1 本文方法

1.1 問題形式化定義

本文定義參數如下:

ci——i類武器單元的單位成本;

aij——第k平臺分配i類武器單元攔截第j個目標的數量;

qij——無其他因素影響下,單發(fā)i類武器單元對j類目標的基本毀傷概率;

pij——所有參與攔截第j個目標的i類武器單元的毀傷概率;

Pi——對第i個目標的毀傷概率。

首先,假定合成編隊中有n個平臺,m種武器單元,預測對方會使用r種單元進攻,某一時刻出現了t個來襲目標。先驗條件是各平臺的武器單元庫存量D,每種類型武器單元的單位成本以及單枚彈藥攔截目標的基本毀傷概率。武器單元庫存量如下:

而不同種類的武器單元具有在造價、發(fā)射時間與裝填時間上的差異,所以發(fā)射不同的武器單元有不同的成本。為了體現這些差異,本文自定義了各武器單元的成本C,如下:

C=(ci)1×m

此外,由于攔截范圍或任務執(zhí)行限制等因素,不是每個平臺都有能力攔截所有目標,所以存在平臺約束,反映為能力矩陣E,表示平臺是否能夠攔截某來襲目標,表示如下:

同時,又因為不同種類的來襲目標具有不同的射程、裝藥量、鎖定范圍與飛行速度,防空武器還具有不同的追蹤能力,所以m種武器單元在單獨攔截r種來襲目標時都有各自的毀傷概率,組成單枚武器單元毀傷概率矩陣Q=(qij)m×r?？傮w的單枚武器單元毀傷概率矩陣表示如下:

A=[A(1),A(2),…,A(n)]

因此,A(k)的列和表示針對各個來襲目標第k平臺分配武器單元參與攔截的總數量,A(k)的行和表示第k平臺每一種類型的武器單元消耗量。

1.2 跨平臺資源調度模型

該模型中將武器單元細化到各個平臺,面對多個目標來襲時能針對某一來襲目標從各平臺中隨意調配資源實施打擊,其攔截軌道如圖1所示。

圖1 跨平臺多目標攔截軌道示意圖Fig.1 Cross platform multi-target interception trajectory diagram

跨平臺資源調度模型的數學表達式為

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

模型的優(yōu)化目標為總體毀傷概率Pdam與成本消耗con的聯立函數f。在實際作戰(zhàn)中,毀傷概率應該盡量大,但不可能達到1,并且隨著Pdam越接近1邊界效益遞減越嚴重,因此需要成本消耗加以制約,同時又不能為了節(jié)約成本過分降低毀傷概率,所以本文考慮加入概率閾值Pthr,當Pdam

對于總體毀傷概率Pdam的計算,基于不同類型的武器單元對不同類型的來襲目標的毀傷概率不同這一先驗條件,所以需要分開計算針對各來襲目標的毀傷概率,而針對某一來襲目標,又要分開計算不同類型的武器單元參與攔截的毀傷概率。因為成功攔截某一來襲目標的對立事件為參與攔截該目標的所有類型的武器單元都攔截失敗,而單類型武器單元攔截失敗的概率為所有平臺發(fā)射的該類武器單元都攔截失敗的事件的概率,所以對來襲目標j的毀傷概率Pj為式(3)和式(4)。其中,pij表示來自所有平臺的參與攔截第j個來襲目標的第i類武器單元的毀傷概率。最后,用所有對來襲目標的毀傷概率求幾何平均即可作為衡量總體打擊效果的總體毀傷概率Pdam。

式(6)～式(8)為資源約束條件,式(6)表示每次分配武器單元時不得超過剩余庫存量;式(7)表示各平臺內某類武器單元的總消耗量不得超過總庫存量;式(8)表示每個來襲目標至少分配一枚武器單元參與攔截。

本文將平臺約束與資源約束式(8)定義為硬約束,當不滿足時通過式(4)與式(2)得到的值為0。將資源約束式(6)與式(7)定義為軟約束,使用罰函數法進行處理,構建輔助函數:

g(A)=f(A)+ε·h(A)

(9)

式中:A為問題的解;g(A)為增廣目標函數;ε為罰因子;h(A)為懲罰項,定義為

(10)

表示保留資源消耗量大于庫存量的解的信息,給予其一個懲罰使其往可行域靠近,當ε取值夠大就能保證增廣目標函數的最優(yōu)解與原目標函數的最優(yōu)解一致。

1.3 基于CPR-JADE算法的模型求解

在跨平臺資源調度模型中,問題規(guī)模由平臺數量、來襲目標數量以及彈藥種類的乘積決定,搜索空間由問題規(guī)模與武器單元庫存決定。由于成本消耗與庫存的約束導致可行域急劇縮小。本模型實則是一個高維度大規(guī)模帶約束優(yōu)化問題,傳統的優(yōu)化方法已不足以高效求解。而混沌映射的遍歷性與隨機性和差分進化優(yōu)秀的可靠性與魯棒性能夠很好地滿足問題需求,因此本文基于以上兩種方法提出CPR-JADE算法實現模型的高效求解。

1.3.1 JADE算法

差分進化算法是1997年由Storn等人提出的一種進化算法[25],擁有出色的尋優(yōu)能力,被廣泛運用于多個領域當中,如電力工業(yè)[26]、能源規(guī)劃[27]、生物醫(yī)藥[28]、化學安全[29]等。經典差分進化算法的迭代過程包括變異、交叉及選擇3種算子,首先父代種群里的父代個體通過差分變異產生突變向量,再通過交叉產生子代個體,然后對比父代個體與子代個體的適應度選擇進入下一代種群的個體,最終形成子代種群。

JADE算法作為近年來被提出的改進差分進化算法,受到了廣泛的關注,已有上千次引用。該算法保留了差分進化算法的交叉與選擇框架,主要在變異算子與參數的自適應調整上作了改進并引入了外部存檔機制。

在變異算子上,不同于傳統的DE/rand/1算子,JADE算法選擇了DE/current-to-pbest/1算子:

(11)

交叉算子為

(12)

式中:vij表示變異產生的第i個個體的第j維數據;xij表示原種群中第i個個體的第j維數據;jcrossover為隨機指定的某一維,保證至少一維數據會發(fā)生變異,CR∈(0,1)為交叉因子。

選擇算子為

(13)

除此之外,JADE算法的縮放因子F與交叉因子CR采用自適應調整,并且每一個個體的變異與每一維數據的交叉有獨立的F與CR。縮放因子F與交叉因子CR的調整策略如下:

Fi～N(μF,0.1),Fi∈(0,1)

(14)

CRij～N(μCR,0.1),CRij∈(0,1)

(15)

式中:Fi表示第i個個體的縮放因子;CRij表示個體中第i行第j列數據的交叉因子;N(μ,σ2)表示期望為μ,方差為σ2的正態(tài)分布。

在選擇算子中每當有子代個體淘汰掉父代個體,便將本淘汰個體的Fi與CRi分別存入集合SF與SCR中,再進一步改變期望μF與μCR的值:

μF=(1-c)μF+c·L(SF)

(16)

μCR=(1-c)μCR+c·ave(SCR)

(17)

式中:c為常數;ave(·)表示算數平均值;L(·)表示Lehmer平均值,具體為

(18)

1.3.2 CPR機制

在差分進化算法解決高維大規(guī)模帶約束的WTA問題的過程中,由于解空間復雜,算法可能會陷入局部最優(yōu)解,無法進一步更新最優(yōu)解,從而大幅降低算法的搜索效率并可能影響最終的結果,這種現象被稱為更新停滯。

混沌映射生成的混沌序列具有無序性,遍歷性,不可預測等特點[30],為了解決更新停滯現象,本文提出了基于混沌映射的CPR機制。其思想為當算法出現更新停滯現象時,代表種群中的個體基本集中在局部最優(yōu)解附近,單純依靠算法本身難以在短時間內跳出局部最優(yōu)解,因此需要一種外部機制打亂當前的搜索方向,使算法重新在全局范圍內進行搜索,從而增加搜索到全局最優(yōu)解的概率。

具體做法為當算法出現更新停滯現象時,首先通過將當前最優(yōu)解中每維的數值變換到(0, 1)的區(qū)間內,公式如下:

(19)

其次,利用混沌映射產生種群數量減一個混沌序列,最后將混沌序列映射回整數空間,替換掉原種群中除最優(yōu)個體以外的其余個體,完成種群重構。

另外,由文獻[30]提出的LTS(logistic-tent system)映射具有更優(yōu)秀的遍歷性[31],因此本文用其生成混沌序列,表達式如下:

μ∈(0,4);x∈(0,1)

(20)

式中:μ為超參數,當μ=0時模型退化為Tent映射,當μ=4退化為Logistic映射,本文取μ=2。CPR偽代碼如算法1所示。

算法 1 CPR機制輸入 當前種群Pop,種群數量num輸出 重構種群PopnewPopnew←Indbest;/* 將當前最優(yōu)個體加入新種群 */if Indbest≠ Indlast/* Indlast為上次重構之后的最優(yōu)解,初始為None */ then cur←Indbest; else cur←Indlast;end ifwhilei

1.3.3 CPR-JADE算法

本文將CPR機制與JADE算法結合提出CPR-JADE算法,流程如圖2所示。

圖2 CPR-JADE流程框圖Fig.2 Flow diagram of CPR-JADE

本文還采用混沌映射初始化種群,可使得初始種群分布更加均勻,提高優(yōu)化效率,具體操作與CPR機制類似。另外,JADE算法中的外部存檔原用于存放在選擇算子中被淘汰掉的個體,在CPR-JADE算法中也用于存放重構種群時被淘汰掉的個體。CPR-JADE偽代碼如算法2所示。

算法 2 CPR-JADE輸入 種群數量num,平臺數量Np,武器單元種類Na,來襲目標數量Ne,迭代輪數T輸出 最優(yōu)解IndbestμCR=μF=0.5; counter=0; Dim=[Np,Na×Ne]混沌序列初始化種群for t=1 to T for i=1 to num; 自適應生成F與CR/*式(14)和式(15)*/ vi, t=mutation(xi, t)/*式(11)*/ r=rand(Dim) for j=1 to Np for k=1 to Na×Ne if rand(0, 1)

2 實驗與分析

為體現CPR-JADE算法的有效性,本文選擇了差分進化算法以JADE算法作為對比,并針對不同的數據規(guī)模設置了3個不同的對照組,能更直觀地體現各算法在不同情況的表現。

2.1 實驗環(huán)境與參數設置

實驗運行環(huán)境:操作系統為Windows 10家庭版,CPU為AMD Ryzen7 4800H with Radeon Graphics 2.90 GHz,內存16 GB,編程語言為Python 3.7。

各算法的參數設置情況:基于差分進化的方法中,縮放因子F=0.8,交叉因子CR=0.8;基于JADE的方法中,μF=0.5,μCR=0.5;基于CPR-JADE的方法中,μF=0.5,μCR=0.5,K=10,其中nite為迭代次數。所有方法種群數量為10,迭代次數為150,調用評價函數次數不超過1 600。概率閾值為0.95。

實驗中,平臺最大數量為10,定義為

S=[s1,s2,…,s10]

武器單元的種類最大數量為10,定義為

F=[f1,f2,…,f10]

來襲目標的種類為3,定義為

B=[b1,b2,b3]

來襲目標最大數量為10,定義為

Bs=[b1,b2,b3,b2,b3,b1,b2,b1,b3,b1]

基本毀傷概率矩陣Q為

武器單元成本消耗C為

C=[100,105,110,115,120,125,130,135,140,145]

能力矩陣E為

各平臺武器單元庫存D為

2.2 實驗結果與對比

2.2.1 216維數據規(guī)模

在本組實驗下編隊中平臺數量、各編隊擁有武器單元種類數量與來襲目標數量均為6,分別取S、F、Bs中的前6個,因此決策變量維度為216。每種方法運行150次,平均結果如表1所示,150次中各方法最優(yōu)結果迭代曲線圖如圖3所示。

從圖3(c)可以看到,在該規(guī)模下盡管最后的結果差異比較明顯,但3種算法均能各自得出結果。其中,本文提出的CPR-JADE算法最早完成收斂且適應度最高。從反映平均結果的表1可以看到,CPR-JADE的平均適應度也為最高,而且標準差最低代表算法穩(wěn)定性較高,耗時雖然最長但仍在可接受的范圍內。

圖3 216維規(guī)模下的概率-消耗迭代圖Fig.3 Probability-consumption iterative graph under dimensional scale 216

表1 216維規(guī)模下平均結果對比Table 1 Comparison of average results under dimensional data scale 216

2.2.2 512維數據規(guī)模

在本組實驗下編隊中平臺數量、各編隊擁有武器單元種類數量與來襲目標數量均為8,因此決策變量維度為512。

每種方法運行100次,平均結果如表2所示,100次中各方法最優(yōu)結果迭代曲線圖如圖4所示。

表2 512維規(guī)模下平均結果對比Table 2 Comparison of average results under dimensional data scale 512

圖4 512維規(guī)模下的概率-消耗迭代圖Fig.4 Probability-consumption iterative graph under dimensional scale 512

觀察圖4(c)可以發(fā)現,由于問題規(guī)模的上升,搜索難度急劇增大,差分進化算法已不能完成求解,而JADE算法也陷入了局部最優(yōu)解出現了早熟收斂的現象。反之,CPR-JADE算法由于CPR機制可以幫助其在復雜問題中跳出局部最優(yōu)解才能不斷更新最優(yōu)解。平均結果方面,由于差分進化算法已不能在規(guī)定迭代輪次內完成收斂,所以適應度標準差最低,而能夠收斂的JADE算法以及CPR-JADE算法中CPR-JADE算法依然更加穩(wěn)定。

2.2.3 1 000維數據規(guī)模

在本組實驗下編隊中平臺數量、各編隊擁有武器單元種類數量與來襲目標數量均為10,因此決策變量維度為1 000。另外,由于該規(guī)模較大,為了更好地反映各算法的表現,本文把迭代輪次更改為500,調用評價函數次數不超過5 100。

同樣地,每種方法運行100次,平均結果如表3所示,100次中各方法最優(yōu)結果迭代曲線如圖5所示。

表3 1 000維規(guī)模下平均結果對比Table 3 Comparison of average results under dimensional data scale 1 000

觀察圖5(c)可以發(fā)現,3種算法的差距進一步拉開,差分進化算法仍然不能收斂,而JADE算法雖然一直在更新最優(yōu)解但是每次提升幅度較小,推斷是陷入了局部最優(yōu)解。CPR-JADE算法有兩次更新大幅提升了最優(yōu)解的適應度,代表算法跳出了局部最優(yōu)解,顯著證明了CPR機制的作用。

圖5 1 000維規(guī)模下的概率-消耗迭代圖Fig.5 Probability-consumption iterative graph under dimensional scale 1 000

平均結果方面,CPR-JADE算法依然能夠取得最高的適應度和較低的標準差,證明了算法的穩(wěn)定性和高效性,但由于此規(guī)模較大所以各算法耗時較高。

3 結束語

相較于傳統合成編隊防空中的WTA模型,本文將資源分配的最小單位細化到各平臺的能力要素級武器單元,并綜合考慮毀傷概率與武器單元成本消耗提出了跨平臺防空武器單元優(yōu)化分配模型。提出了CPR機制并結合JADE算法提出了CPR-JADE算法,以求解高維度大規(guī)模帶約束的WTA問題。再通過與差分進化、JADE在各種數據規(guī)模下的仿真實驗對比,展現了CPR-JADE算法在各種情況下的優(yōu)秀表現,滿足了本文在短時間內求得毀傷概率高于概率閾值且成本消耗盡可能小的需求,驗證了本文提出模型與算法的正確性和有效性。

后續(xù)研究計劃從兩方面開展,一是模型的建立方面,進一步引入區(qū)分多任務的跨平臺協同,如跨平臺火力打擊與制導的協同作戰(zhàn)模型;另一方面是求解方法,進化算法面對此類問題時基本可以做到快速高效求解,但隨著數據規(guī)模的上升求解效率會逐漸下降,后續(xù)考慮加入其他領域的方法,在有限的時間內實現準確求解。