基于自適應諧振理論的武器目標分配快速決策算法

張 凱,周德云,楊 振,潘 潛

(西北工業大學 電子信息學院,西安 710072)

0 概述

武器目標分配(Weapon Target Assignment,WTA)問題源于作戰指揮決策,對該問題的研究最早可追溯至1958年[1]。WTA問題算法研究包括靜態武器目標分配(Static Weapon Target Assignment,SWTA)和動態武器目標分配(Dynamic Weapon Target Assignment,DWTA)[2-3]算法研究,SWTA研究方法為建立目標生存率最小化或毀傷概率最大化問題,尋優得出接近全局最優的武器目標分配方案。DWTA研究對象為敵我雙方之間的多階段攻防博弈過程,研究目的是得到接近納什均衡點(Nash Equilibrium Point,NEP)的武器目標分配過程。

作為非線性整數組合優化問題,WTA模型求解算法主要包括確定性算法和隨機算法兩大類[4]。確定性算法有嚴格的理論依據,主要通過動態規劃找到全局最優解,如隱枚舉法、割平面法等[5-6],其中,具有代表性的是文獻[7]提出的近似分支定界算法(Branch and Bound Algorithm,BBA)。由于WTA問題屬于NP完全問題[8],確定性算法的復雜度會隨著問題規模的擴大呈指數性增長,不適用于求解大規模WTA問題。與確定性算法相比,隨機算法在求解大規模WTA問題時具有優勢。在上述算法中通常有很多個體,個體之間通過啟發式信息互相影響,在解空間中尋找高質量可行解,如進化算法[9-10]、粒子群算法[11]、蟻群算法等,但隨機算法易陷入局部最優困境。WTA問題作為指揮控制系統中重要的決策支持,其求解算法一直存在“收斂性-實時性”困境,即確定性算法雖然能保證搜索過程的持續優化,但面臨時間復雜度的維數爆炸問題,而近年來廣泛采用的集群智能算法,雖然對問題規模的敏感度不高,但其隨機搜索機制無法保證收斂性指標。目前大部分WTA算法研究重點在于如何逼近全局最優解,但在實際作戰環境中,輔助決策系統必須快速響應,具有良好的實時性[12],而目前關于快速WTA算法的研究較少。

近年來,隨著人工智能和大數據技術的迅速發展,機器學習算法被嘗試用來求解最優化問題。通過選取合適的特征集和特征映射,經過樣本數據訓練后,機器學習算法具有更快的實時性和一定的泛化能力,如文獻[13]提出模糊決策(Fuzzy Decision Maker,FDM)算法,首次將近似推理理論應用于WTA問題,利用網格劃分方法從樣本數據提取模糊映射規則,并采用小規模WTA問題仿真驗證了其可行性。在此基礎上,本文提出一種FART-NS快速決策算法。通過模糊自適應諧振理論的快速泛化能力提高算法實時性,再采用鄰域搜索策略優化由FART網絡得到的初始解,以提高求解收斂性。

1 武器目標分配數學模型

本文基于火力集合劃分視角對經典WTA問題進行建模。在w個武器和t個目標相互對抗的情況下,WTA問題可看作將武器集合W={a1,a2,…,aw}劃分為目標子集S=(S1,S2,…,St)的集合劃分問題,表示如下:

(1)

s.t.S1∪S2…∪St=W,Si∩Sj=?,?i≠j

(2)

其中,W={a1,a2,…,aw}為w個武器的集合,S=(S1,S2,…,St)為與目標相對應的t個子集,子集Si為分配給第i個目標的武器集合,例如Si={am,an,al}表示將第m個、第n個和第l個武器分配給第i個目標,第1個約束條件表示最大化武器利用率,第2個約束條件限定1個武器只能攻擊1個目標。

建立目標生存率最小化的目標函數如下:

(3)

其中,vi,i=1,2,…,t為第i個目標的威脅權值,由目標類型、位置、速度和航向等信息決定;pji,j=1,2,…,w,i=1,2,…,t為第j個武器對第i個目標的毀傷概率,由武器類型、目標類型、目標狀態和相對態勢等信息決定。

2 FART-NS快速決策算法

根據上述模型,可將WTA問題看作輸入為目標權值v和毀傷概率p、輸出為火力分配集合S的模式分類問題。因此,本文提出一種基于機器學習的FART-NS快速決策算法,算法求解過程如圖1所示。FART網絡接受問題變量I,并快速泛化得到火力劃分集合S=(S1,S2,…,St),再對初始解S進行鄰域搜索得到優化解S*,最后FART網絡吸收優化解S*進行在線更新或增量學習。

圖1 基于機器學習的FART-NS算法求解示意圖Fig.1 Schematic diagram of solving FART-NS algorithm based on machine learning

2.1 模糊自適應諧振理論

自組織神經網絡是人工智能領域應用最廣泛的一種學習模型。為解決大部分神經網絡模型的“穩定性-彈性問題”,美國Boston大學GROSSBERG于1976年提出一種無監督競爭型神經網絡模型,即自適應諧振理論(Adaptive Resonance Theory,ART)網絡[14],可在穩定原有模式類前提下學習新模式。隨著理論不斷完善,研究人員提出大量基于自適應諧振理論的改進學習模型,如ART1[15]、ART2[16]、ART3[17]、ARTMAP[18]和FART[19]等模型,這些模型具有處理二進制信號、連續模擬信號、監督學習和分級搜索等應用背景。由于在上述模型中,針對WTA模型的連續實數輸入向量,FART模型具有算法復雜度低、設置參數少和魯棒性強等優點,因此將其作為本文算法的主架構。

圖2 FART-NS決策模型

F1與F2之間聯接通道包含由底向上Wij和由頂向下Wji2種權重矢量,其中由頂向下的權值矢量稱為模板,在該模板指導下,網絡進行有選擇的學習。算法的具體步驟如下:

步驟1初始化FART網絡,將戰場態勢向量s輸入F0層進行預處理,生成目標權值向量v和毀傷概率矩陣P,組成輸入向量I:

I=(v1,v2,…,vn,p11,p12,…,pt1,pt2,…,ptw)

(4)

(5)

步驟3節點競爭。通過競爭選擇F2層中選擇函數Tj最大的模式節點J:

TJ=max{Tj:j=1,2,…,N}

(6)

如果存在不止一個最大選擇函數的模式節點,則優先選擇索引j最小的模式節點。

(7)

如果上式成立,則發生諧振;否則系統發出重置信號,令TJ=0,使F2層中的競爭獲勝節點J無效,重復執行步驟3～步驟4,直至找到節點發生諧振,轉至步驟6;如果遍歷后沒有滿足諧振的模式類,則轉至步驟5。

步驟5若沒有滿足諧振的模式類,則執行貪婪利用策略,令:

ρ1=ρ1+ψ

(8)

其中,ψ為一個極小的負步長。返回步驟2,直到找到滿足諧振的節點。

(9)

X*=fNS(X)

(10)

(11)

其中,β為學習率參數,當β=1時為快速學習法。

(12)

FART-NS算法流程如圖3所示。

圖3 FART-NS算法流程

2.2 鄰域搜索策略

假定FART網絡輸入變量為I1=(V1,P1),其中,V1=[v1,i]1×t,P1=[p1,ji]w×t。與I1匹配值最高模式節點輸入為I2,輸出為X2=[x2,ji]w×t,相應的適應度為F2:

(13)

由FART網絡計算所得解X1的適應度下界為:

(14)

由式(14)可知,FART網絡求解精度主要取決于F2、|V1-V2|和|X1-X2|,即由訓練集精度和采樣密度決定。問題變量I1和I2處于各自鄰域空間中,因此,需構造合理的鄰域空間使得X1位于X2的鄰域空間中,以X2為初始解,通過鄰域搜索逼近X1,再結合FART網絡在線學習機制,可提升FART-NS算法對于訓練集精度和采樣密度的魯棒性。

定義1(鄰域搜索) 對于特定集合Π=(OP,N),其中,OP代表一個優化問題,N為任意1個可行解s和1個實例x,N(s,x)定義為解s的領域。局部搜索問題目標是對于給定的實例x尋找一個局部最優解[20]。

鄰域搜索效果主要由初始解和鄰域空間決定。在本文中,通過FART網絡得到初始解,且根據WTA模型特點設計鄰域空間。

在一般數值優化問題中,常見鄰域構造方法有二元構造、點替換構造[21]和旋轉構造等[22-23]。但上述構造方法并不能反映WTA模型的鄰域特性,因此采用基于圖論[24-25]的鄰域空間。

在本文提出的WTA模型中,每個可行解對應t個目標子集(S1,S2,…,St),每個目標子集中元素為攻擊該目標的武器節點。根據圖論,可將不同目標子集中武器節點組成的序列i1-i2-…-ir定義為路徑交換(Path Exchanges,PE),該路徑交換表示將武器i1重新分配給武器i2所攻擊的原目標,武器i2重新分配給武器i3所攻擊的原目標,依次類推,武器ir-1重新分配給武器ir所攻擊的原目標,武器ir保持原位。同理,將閉環武器序列i1-i2-…-ir-i1定義為循環交換(Cyclic Exchanges,CE),其與路徑交換不同的是末位武器ir重新被分配給武器i1原先所攻擊的目標,從而形成閉環交換序列。

將滿足一定長度循環交換的解空間定義為X鄰域空間,即N(X′)={X|CE:X′→X}。可見該鄰域空間較全面地反映了WTA問題解空間的鄰域關系,而二元構造、點替換構造和旋轉構造可視為該鄰域空間在某一搜索方向下的特例。由于通過循環交換可使初始解到達該鄰域空間內任一解位置,因此,對此鄰域空間內尋優過程進行定義。

定義2(基于交換算子的WTA鄰域搜索) 當1個可行解X經過循環交換E后轉變為X′,若對應的目標函數F(·)滿足式(15),則稱循環交換E為負增益循環。

F(X′)-F(X)<0

(15)

對于初始可行解X,如果找到1個負增益循環E,則等價于在初始解的鄰域空間搜索到1個更優解X′。

在數值優化過程中,基于梯度構造啟發信息,因其具有計算復雜度低、效率高等優勢而被廣泛應用。但WTA模型作為組合優化問題,無法直接求得其梯度,且在上述鄰域空間中尋找局部最優解是NP完全問題。因此,根據提升圖引理構造類梯度作為啟發信息[26]。

引理1當i1-i2-…-ir-i1是1個負增益循環時,在該循環交換中,存在一個節點ih使得路徑交換ih-ih+1,ih-ih+1-ih+2,…,ih-ih+1-ih+2-…-ih+k為負增益路徑。

根據引理1,將負增益路徑作為啟發信息尋找負增益循環:先獲得長度為1的負增益路徑i1-i2,再以節點i2為起始點,擴展成長度為2的負增益路徑i1-i2-i3,重復此過程至路徑長度為R的負增益路徑,迭代過程中更新最優負增益循環E*。

在上述鄰域搜索過程中,所有解對應的目標子集均具有相同規模。考慮到WTA中目標子集規模相近的解空間也是優化方向,因此引入虛擬武器節點,使得該搜索算法除了在本文采用的鄰域空間中尋優外,還可根據啟發信息搜索到鄰域空間外距離初始解較近的解個體。

定義3(虛擬武器節點) 保持每個目標子集中有且僅有1個虛擬武器節點iv,令虛擬武器節點對任意目標殺傷概率為0,即pv·=0,且在交換算子中禁止:1)路徑交換的起始節點為iv;2)存在相鄰的虛擬武器節點對iv-iv。

根據鄰域搜索算法原理可知,在未引入虛擬武器節點時,并不能完成真實武器節點在各目標子集中的轉移。以攻擊決策變量為[k,k,…,k]1×w的極端個體為例,此時目標子集Sk={a1,a2,…,aw},Si=?,?i≠k,應用鄰域搜索算法無法改變該個體。但引入虛擬節點后,通過負增益路徑置換真實武器節點aj與目標子集Si下的虛擬節點,以完成Si中武器節點轉移,相應負增益為:

(16)

其中,Vj為置換前目標j的適應度值。引入虛擬節點后,啟發式鄰域搜索算法除了搜索未引入虛擬節點時的鄰域空間,還通過檢驗武器節點分布合理性搜索原鄰域空間外的部分解空間。當不限定交換算子長度和虛擬節點數量時,采用循環交換可實現任意兩個可行解之間的轉移,且虛擬節點數量決定鄰域空間外的尋優范圍。為避免退化為全局隨機搜索以及增大計算復雜度,不能加入過多虛擬節點。引入虛擬武器節點的循環路徑如圖4所示,循環交換P為2-4-6-iv-1-5,對應的目標子集序列為Label(P):2-4-3-4-5-6。

圖4 引入虛擬武器節點的循環路徑示意圖

本文中鄰域搜索算法步驟如下:

步驟1初始化循環交換算子長度k=1,最優負增益循環E*為?,最優負增益c*為0,由式(17)計算得到初始負增益交換集合Pk={(i,j)|cij<0}。

(17)

其中,c(i,j)表示在武器i和j分屬于不同目標子集的情況下,將武器i重新分配給武器j所攻擊的原目標k,而武器j不再攻擊原目標k時,對目標k生存概率的影響;Vk為重分配前目標k的適應度值。

步驟2移出Pk中1條路徑P,令s為P的起始節點,e為P的終止節點,根據式(14)計算循環路徑的增益c(P)+c(s,e),若滿足式(18),則更新E*和c*。

c(P)+c(s,e)

(18)

步驟3將路徑交換P對應的目標子集序列記為Label(P)。選取新節點k?Label(P),計算c(P)+c(e,k),若小于0,則將新路徑P+(e,k)加入集合Pk+1,重復此過程直至遍歷Pk=?。如果存在路徑P′使得Label(P)=Label(P′),則選擇更優路徑更新。

步驟4令k=k+1,轉至步驟2,當k=R時,算法終止。

3 仿真實驗及結果分析

在作戰指揮控制決策中,WTA問題變量由實際戰場作戰態勢決定。引入簡化態勢函數生成問題變量[13]:

(19)

其中,ri∈[0,rmax]為武器目標距離;rmax為作戰場景最大距離;aj為武器j最大殺傷概率;bj為武器j造成最大殺傷概率的距離;cj為函數標準差;ε為附加擾動。

選取BBA算法、采用精英保留策略的GA(改進GA)算法[9]和FDM算法[13]分別代表確定性算法、進化算法和機器學習算法與本文提出的FART-NS算法在Matlab平臺進行仿真對比實驗。引入3個武器-目標對抗算例,算例1采用小規模WTA問題來驗證算法可行性;算例2采用大比例冗余武器WTA問題來驗證算法改善局部最優能力;算例3采用單因子變量法檢驗算法的魯棒性。

上述算法的具體參數如下:

1)FART-NS算法:選擇參數α=0.0001,初始識別閾值ρ1=0.98,鄰域搜索中負增益循環最大路徑長度為3。

2)FDM算法:采用梯形隸屬函數,模糊變換單元和模糊分類單元的規則數量分別為110 592和732。

3)改進GA算法:種群大小為1 000,交配池大小為500,種群代數為100,采用錦標賽選擇算子,交叉概率Pc=0.8,變異概率Pm=0.2。

4)BBA算法:補充參數信息。

算例1在以下兩種規模的初始條件下隨機生成100組初始條件作為測試集:

1)令w=8,t=6,rmax=60 000,aj=[0.65∶0.02∶0.79],bj=[48 000∶-2 000∶34 000],cj=20 000,ε～N(0.05,0.4);

2)令w=20,t=12,rmax=60 000,aj=[0.47∶0.02∶0.85],bj=[50 000∶-1 000∶31 000],cj=20 000,ε～N(0.05,0.4)。

在初始條件1)中,問題規模為W8T6,武器與目標數量相當,用以驗證本文所提FART-NS算法的可行性。在初始條件2)中,問題規模為W20T12,存在大比例冗余武器,已難以得到理論最優解且求解算法易陷入局部最優,用以驗證本文所提鄰域搜索算法的尋優能力。仿真結果如圖5和表1所示。

圖5 在W8T6和W20T12問題規模下不同算法的適應度均值和計算時間比較

表1 算例1適應度和計算時間統計數據

圖5(a)為問題規模為W8T6時以BBA算法所得理論最優解為基準的FART-NS算法、FDM算法和改進GA算法偏差示意圖。在圖5(c)中,由于問題規模為W20T12時BBA算法的計算時間大于600 s,因此以FART-NS算法、FDM算法和改進GA算法計算得到的歷史最優解為基準得到3種算法的偏差。圖5(b)、圖5(d)為W8T6和W20T12問題規模下各種算法計算時間統計圖,其中小圓圈表示不在正常統計范圍內的野值。表1為W8T6和W20T12問題規模下各種算法適應度和計算時間的均值和標準差。

由上述仿真結果可知,在W8T6問題規模下,BBA算法作為確定性算法能夠保證全局最優,且計算時間在此規模下少于改進GA算法。但當問題規模上升到W20T12時,由于計算復雜度為指數級上升,BBA算法已大于600 s,不適用于求解WTA問題。相比于其他3種算法,改進GA算法計算時間對問題規模敏感度最低,其主要取決于種群大小、進化代數和進化算子。但集群智能算法的隨機搜索機制決定其適應度偏差和計算時間的均方差大于確定性算法。FDM算法的模糊映射機制決定其實時性優于其他3種算法,且在W8T6問題規模下適應度偏差優于改進GA。但隨著問題規模的擴大,FDM算法求解精度受限于模糊規則的數量,且規則庫的維護僅依靠線下更新,在W20T12問題規模下適應度偏差的均值和均方差與改進GA算法相當。同樣是基于分類思想的決策算法,FART-NS算法的計算時間均值僅次于FDM算法。由于鄰域搜索算法在初始解不同情況下負增益路徑數量也有所差別,因此其計算時間的均方差大于FDM算法。鄰域搜索算法對由FART網絡所得初始解的再優化使得適應度偏差的均值和均方差優于FDM和GA算法。

為分析各算法的實時性特點以計算其最大時間復雜度。令M為武器數量,N為目標數量。在FART-NS算法中,令D為模式節點數量,L為鄰域搜索長度,則FART網絡快速決策的時間復雜度為O(MN+D),鄰域搜索時間復雜度為O(ML),FART-NS算法時間復雜度為O(MN+D+ML)。令E為FDM算法模糊分類單元數量,則FDM算法時間復雜度為O(MN+E)。在改進GA算法中,令P為種群規模,I為種群進化代數,則種群初始化計算復雜度為O(MNP),生成子種群時間復雜度為O(MNP),改進GA算法時間復雜度為O(MNPI),BBA算法求解時間復雜度為O(MN)。

通常D和E會隨MN遞增,且MN遠小于D和E。因此FART網絡和FDM算法實時性僅依賴于模式節點或規則庫容量。而FART-NS算法計算用時取決于鄰域搜索算法的路徑長度L。對于GA算法,隨著MN的上升,為保證求解精度通常需要擴大P和I,而GA算法的優勢為時間復雜度對PI的敏感程度大于MN,如表1中所示。而WTA作為NP完全問題,用BBA算法求解呈現出明顯的指數爆炸特性。因此,在參數設置合理情況下,計算各算法復雜度依次為FDM算法

算例2為驗證本文所提鄰域搜索算法和虛擬節點對FART網絡決策的增強,在算例2中控制如下情況進行算法對比:1)是否采用鄰域搜索算法;2)鄰域搜索算法中是否引入虛擬武器節點。按照如下設定隨機生成100組初始條件作為輸入:令w=20,t=12,rmax=60 000,aj=[0.47∶0.02∶0.85],bj=[50 000∶-1 000∶31 000],cj=20 000,ε～N(0.05,0.4)。在鄰域搜索算法中,設定最大交換路徑長度為3,最大虛擬節點數量為1,迭代運行次數為4。仿真結果如圖6所示。

圖6 100例隨機輸入下FART網絡、無虛擬節點FART-NS算法和引入虛擬節點FART-NS算法的適應度

在圖6中,歷史最優解由引入虛擬節點的鄰域搜索算法計算得到,為0.055 8。以該解的值為最優適應度,采用FART網絡計算得到適應度偏差均值為2.280 9,均方差為0.634 8。未引入虛擬節點鄰域搜索的偏差均值為1.020 3,偏差均方差為0.626 2。引入虛擬節點后偏差均值為0.104 9,偏差均方差為0.052 9。FART網絡得到的初始解經引入虛擬節點鄰域搜索算法優化后,已距離理論最優解較近。

在采用鄰域搜索算法并引入虛擬武器節點后,解集適應度和標準差均得到提升。由引入虛擬武器節點的鄰域搜索原理可知,在初始解適應度較低時優化效果尤為明顯,而當初始解距離理論最優解較近時,未引入虛擬節點與引入虛擬節點搜索算法差距逐漸縮小。如算例1中W8T6問題規模下大部分待優化解即為理論最優解,此時鄰域搜索算法對仿真結果影響較小。而在W20T12問題規模下,鄰域搜索算法效果有所提升。可見,鄰域搜索算法提升了FART網絡的魯棒性,而虛擬節點的引入增強了鄰域搜索算法的魯棒性。

算例3為分析FART-NS算法中各參數對算法性能的影響,使用算例2中100組隨機初始條件作為測試集,分別改變以下參數進行單因子變量測試:1)鄰域搜索路徑步長;2)初始警戒門限值;3)訓練集容量。仿真結果如圖7所示。

圖7 搜索路徑長度、識別閾值和訓練集容量對FART-NS算法性能的影響

圖7(a)和圖7(b)分別是路徑交換長度為1～6和1～5時由FART-NS算法計算得到的適應度均值和計算時間均值。圖7(c)為識別閾值為0.85～0.99時的適應度均值。圖7(d)為訓練集容量均勻選取算例1中訓練集10%～100%時適應度均值的變化曲線,可見識別閾值和訓練集容量對FART-NS算法實時性影響較小。

由圖7可以看出,隨著搜索路徑長度的增加,適應度均值下降且梯度變小,計算時間均值上升且梯度變大,在搜索路徑長度達到3后,適應度均值下降到0.391 0以下。在識別閾值達到0.94或訓練集容量達到20%后,FART-NS算法可將適應度均值保持在0.390 6以下。在識別閾值和訓練集容量取值較低時,FART-NS算法的敏感度明顯小于降低鄰域搜索算法的路徑長度。結合算例2中仿真結果可知,鄰域搜索算法增強了FART網絡的魯棒性。

由算例1仿真結果可知,FART-NS算法最大時間復雜度為O(MN+D+ML),實際求解中計算時間通常遠小于理論最大值。這是因為鄰域搜索算法計算時間主要取決于路徑交換初始化時長度為2的負增益路徑數量,而長度為2的負增益路徑數量取決于由FART網絡所得初始解在鄰域空間中與最優解距離。當初始解距離理論最優解較近時,所需計算的負增益路徑數量較少,計算用時較短。雖然理論上通過路徑步長和虛擬節點的數量可到達任意解個體,但增大路徑長度會增加計算復雜度,因此,如果初始解適應度較差,可設定較短搜索路徑長度進行迭代計算,當適應度提升小于設定閾值或到達迭代次數后,動態提升提高路徑長度和減少虛擬節點數量有助于跳出局部最優解。由于虛擬節點目的是合理調度各目標子集下武器節點數量,因此在求解過程中應逐漸減少虛擬武器節點的數量。如在算例1中,當問題規模為W20T12時,在由FART-NS網絡得到初始解后,可將搜索路徑長度設定為3,虛擬節點數量設定為1,迭代次數為4,當適應度值下降到0.391 0或迭代次數達到4時,算法中止。然后將搜索路徑長度提升到5,虛擬節點數量設定為0,當適應度提升小于0.000 1或迭代次數達到4時,算法終止。

4 結束語

針對武器目標分配問題求解無法有效平衡收斂性和實時性的現狀,本文從武器集合劃分角度建立WTA模型,提出一種基于機器學習思想的FART-NS決策算法。通過模糊自適應諧振理論的快速泛化能力和在線學習機制提高算法實時性,并采用鄰域搜索策略對由FART網絡得到的初始解進行再優化,提升所得解的收斂性,形成魯棒的快速泛化-鄰域優化-在線學習閉環機制。仿真結果表明,該算法能較好平衡一定規模下WTA問題的實時性和收斂性。采用機器學習方法求解大規模WTA問題的難點在于對輸入向量降維,而輸入向量與指揮控制系統中威脅評估子系統密切相關,在WTA模型參數之間存在大量的耦合信息,單純從理論上求解WTA會導致其在作戰態勢下應用效率較低,下一步將結合威脅評估子系統構建特定作戰場景下的WTA模型,使求解算法更適用于實際作戰環境。