基于類型2區間模糊K近鄰分類器的動態武器-目標分配方法研究

王　邑, 孫金標, 肖明清, 羅繼勛

(1. 空軍指揮學院戰術系, 北京 100097; 2. 空軍工程大學航空航天工程學院, 陜西 西安 710038)

?

基于類型2區間模糊K近鄰分類器的動態武器-目標分配方法研究

王邑1, 孫金標1, 肖明清2, 羅繼勛2

(1. 空軍指揮學院戰術系, 北京 100097; 2. 空軍工程大學航空航天工程學院, 陜西 西安 710038)

摘要：動態武器-目標分配問題是戰場指揮控制決策中的關鍵問題。由于動態武器-目標分配算法是在攻擊間隙所做的決策,對計算時間的實時性要求較高。解決這一問題,可以采用機器學習的方法基于戰場輔助決策系統的武器-目標分配,從已知的決策中推理生成出新的決策,而不必每個步驟中都重新搜索新的目標分配方案。根據這種思路,提出了一種基于類型2區間模糊K近鄰分類器的武器-目標分配方法,利用分支定界法得到的分配方案作為訓練樣本,通過構造并行運行的類型2區間模糊K近鄰分類器來推導目標分配結論,實現了快速決策的目的。

關鍵詞：戰術決策; 武器-目標分配; 類型2區間模糊K近鄰分類器; 機器學習

0引言

武器-目標分配問題(weapon-target assignment, WTA)是戰場指揮決策中的關鍵問題[1]。目前,研究重點在如何解決動態武器-目標分配問題上[2],即假設武器對威脅的分配是根據前一輪攻擊戰果的總結來得到的,考慮某個離散時間段的武器-目標分配,并必須在下一輪攻擊之前給出明確的分配方案。這種在攻擊間隙中進行的觀察、決策、執行過程,其時間非常有限,因此,動態的武器-目標分配的解算時間應該在盡量短,越接近實時越好,這樣,所有的行動才能與任務目的和戰場環境約束相一致。

武器-目標分配問題通常被形式化為一類非線性整數規劃問題。該整數規劃是典型的NP完全問題[3],目前典型的解法分為解析解法和啟發式解法兩大類[4]。解析解法采用動態規劃的思路,通過全枚舉來得到最優分配方案。典型的方法如割平面法[5]、分支定界法[5]等。通常可以得到問題的全局最優解,但其計算效率太低,且枚舉數量隨問題規模上升呈指數上升,無法進行實時解算;啟發式解法從搜索算法上對目標分配的問題域進行有效地規劃,利用啟發式的搜索策略,在不進行全枚舉的前提下搜索理想的解,如遺傳算法[6]、模擬退火[7]、粒子群優化[8]、TABU搜索[9]、遺蟻群算法[10]等。

基于搜索的方法在每次使用時都需重新計算。但對于動態武器-目標分配而言,在相鄰的時間片上,戰場態勢可能并未產生劇烈變化,重新計算帶來了相當大的運算壓力,還限制了解析解法的實用價值。采用機器學習方法中的監督學習方法,能夠避免重復計算的問題。機器學習方法與搜索算法不同,構建算法與應用算法的時間不對稱,在針對決策過程進行相應的建模,即訓練過程后,模型的實際推理過程很快,推理的速度大大地優于重新搜索的速度。

本文提出一種用機器學習理論來解WTA問題的方法,該方法利用了精確解法的精度高、啟發式方法速度快的優點,用精確解構造決策模型,對從解空間到精確解的判定過程進行近似,然后實時推理出WTA問題的分配方案。采用模式分類器作為問題的核心算法,根據目標與武器的決策變量,抽象出一定的模式,將不同的目標分配方案與不同的模式對應,然后當輸入的問題參數滿足某一模式的特征以后,就輸出對應的目標分配方案。

分類器算法選用區間類型2模糊K近鄰(interval type-2 fuzzy K-nearest neighbor,IT2FKNN)分類器,K-近鄰(K-nearest neighbor, KNN)算法是一種結構簡單,效率較高的分類器,其計算速度很快,采用多個KNN實現并行計算簡單,加上采用基于區間類型2模糊集的擴展算法對重合特征、不確定性特征的區分識別能力進一步增強,總體算法的效果得到加強。

本文采用隨機數字仿真實驗驗證了方法的性能。實驗了3×4、8×16、60×120等3個WTA問題,在實際戰役仿真系統中,同時規劃武器的數量突破100以上的問題可定位為大規模WTA問題[11],這3個問題分別屬于小、中、大規模問題。通過仿真實驗,本文方法的性能滿足預期,對于小、中、大規模問題都能在有限時間內快速地解決。本研究為在大規模兵力調配中使用相關方法提供了基礎。

1方法架構及實現

1.1問題描述

武器-目標分配問題的標準描述可分為進攻型和防御型兩種[12],其中進攻型考慮了我方的打擊效果及目標的價值,防御型考慮敵我雙方的打擊效果及我方作戰單元的價值。由于這兩種表述可以相互變換,且研究中采用較多的是進攻型表述,所以,本文中以進攻型模型作為研究問題的描述,其可以由以下非線性整數規劃問題所描述[13]:

(1)

s.t.

(2)

目標函數式(1)為最小化目標的價值期望,限定條件式(2)為保證武器至少且至多被分配至一個目標,武器-目標的分配方案中可以存在某個目標同時被多個武器分配或無武器分配的情況,但不存在某一武器不被分配目標的情形。|T|表示目標的數量,|W|表示武器的數量,因為不考慮單個武器的多目標分配,故設定武器數量大于或等于目標數量。Vi是目標Ti的價值,Pik是武器Wk對于目標Ti的殺傷概率,dik是決策變量,當指派武器Wk打擊目標Ti時為1,其余時為0。若假設Vi=pi(t)·wi,pi(t)為在t時刻目標Ti的生存概率,且wi為該目標的價值,對式(1)、式(2)的不斷求取就是對動態武器-目標分配問題的求解。

1.2算法概述

算法的基本形式為

(3)

式中,算法的輸入為向量x;輸出為向量y;計算中所用訓練集由向量xtr,ytr組成。由于算法的決策依據為式(1)中的Vi和Pik。設目標數量|T|=I,武器數量|W|=K,則算法的輸入為以下I+IK維向量:

(4)

算法的輸出為IK維決策向量:

(5)

若將y按K拆分,則得到對應于K個武器的目標分配向量yk,y=[y1,…,yk,…,yK]

每個向量為I維,由于每個武器只能分配一個目標,則yk向量的所有取法為I+1個,一一對應于分配i種目標(第i維為1,其余為0)或不分配目標(全為0),若將這I+1種取法看作是類別信息,則算法式(3)可被看做是K個分類器,輸入向量為I+IK維,輸出為標量類型yk。以上的討論中可見,武器-目標分配問題可看做是一個分類問題。

圖1為算法結構圖。圖中采用了多個區間類型2模糊K近鄰算法對每個武器的目標分配方案進行解算,實際上將輸出分割為K個子集,采用這種采用瀑布型并行構造的決策模型,每個模型只考慮類型數量為I+1的分類問題,這就降低了分類的復雜度,在一定程度上避免了輸出過于復雜的問題。而且,若武器對于攻擊對象的類型是有選擇的情況下,即yk的所有取值數量少于I+1,在這種結構下產生的分類類別將更少。

圖1　算法結構圖

本文提出的方法中,采用分支定界法這種確切解法所產生的方案來構造訓練集。當問題規模變化時,訓練數據必須相應變化。為了降低重構訓練數據的計算時間,可以構造多個可能的對抗關系,并對應地訓練多個決策模型,一旦對抗關系發生了改變,分配問題中的對抗規模發生變更,則切換為備選的決策模型。這種方法在戰場上的使用的實時性和穩健性較好,但是需要很大的存儲空間來存儲和調用多個模型;另一種思路是只訓練一個決策模型,始終保持目標的數量與我方武器數量相同,這樣在實際運用中,當遇到實際目標多于我方武器數量時,則采用價值排序的方式,優先選擇價值較高的t個目標進行分配。當目標數量小于I時,例如目標數量為Ir,則在分配時將I-Ir個目標的價值設為0。

1.3區間類型2模糊K近鄰算法

區間類型2模糊K近鄰算法(IT2FKNN)是在KNN[14]的基礎上發展而來的。KNN通過將樣本與聚類間的距離進行比較,產生K個最近聚類,其最多數聚類與已知的分類規則的對應關系,構成了分類的依據,在實際使用中可以發現,在維持一定的分類精度的前提下,KNN計算速度要遠高于其他比較復雜的算法,因此在處理WTA問題中非常適用。然而,標準KNN算法的最大問題是,已知分類知識中對應的聚類必須是相同重要度的互相區分的聚類。因此,當聚類元素存在重疊關系的時候,用KNN方法就無法進行正確的分類。為克服這個缺陷,學者引入了模糊隸屬函數來描述聚類與類型的關系,即FKNN算法[15],很大地提高了分類的精度,并能夠處理類型存在交叉重疊的分類問題。然而,FKNN算法對于K的選擇存在不足,不同的K值選取對結果的影響比較大,且K值沒有一個先驗的計算公式能夠解出,因而,影響了其整體的分類精度。因此,本文引入利用區間類型2模糊集來描述的KNN算法,即IT2FKNN[16]。在FKNN中,初始值K為單值,一次計算只圍繞一個初始K值來指派聚類數據的初始模糊隸屬函數,若初始K值選取得不合理,則分類的結果就不合理。而IT2FKNN由于采用的是區間類型2模糊集,初始K不為單值,則可以合理地避免此類問題的發生。

IT2FKNN的隸屬度指派公式為

(6)

在式(6)中,樣本x的隸屬函數是其K個臨域樣本距離成反比,并與該樣本的隸屬度相關。式中對于初始隸屬度的求法,可以參照內置區間類型2模糊集的運算[17],例如,假設K=2,需兩個近鄰樣本的主要隸屬度作為邊界,并從中得到兩個主要隸屬度之間對應的內置區間類型2隸屬函數。

通過K個臨域聚類的主要隸屬函數,來間接得到xk的主要隸屬函數,假設每個聚類有nj個主要隸屬度,則xk的隸屬度規模,即參與交集運算的隸屬函數數量,計算公式為

(7)

式中,K表示聚類數；i表示類型數。

從式(7)可以得到樣本xk的主要隸屬度為

(8)

根據類型2模糊集的定義[17],樣本xk的次要隸屬度為1。所以,樣本xk的類型2隸屬函數可以寫作:

(9)

從式(8)和式(9)的推導中,得到了樣本xk的類型2隸屬函數,即為聚類指派了類型2模糊隸屬度,對于分類來說,最后計算中要得到確切的隸屬度數字,首先要求這個類型2模糊隸屬函數,對其進行降型運算,后進行標準的去模糊化運算。

降型計算如下:

對于xk和類型i,其降型后的隸屬函數為

(10)

IT2FKNN算法的步驟如下:

步驟 1給定Ik={k1,k2,…,ks},即K值的組合;

步驟 3根據式(6)計算未知樣本的隸屬度;

2仿真實驗

實驗所用算法采用C++實現,分類器采用OpenMP共享內存并行計算框架,計算機采用CPU為運行于2.4GHz的8核處理器,為了便于研究復現,采用隨機生成的測試數據進行性能評價。實驗采用了多步判斷法,隨機的敵我雙方位置、殺傷評價指標矩陣、累積生存概率及重要程度信息。

2.1仿真數據生成方法

數據生成算法的基本情況如下:

武器數量為K,|W|=K,W={W1:k};

目標數量為I,|T|=I,T={T1:i};

目標生存價值:Vi=piwi,其中,pi取目標ti累積生存概率,wi為目標ti對應的價值,設為只與敵距我戰略部署的中心距離ri有關,rmaxi為想定的敵我最大距離:

(11)

當連續計算多步WTA時,武器與目標的距離由目標相對速度Δvi、目標相對距離ri(τ-1)經遞歸計算得到,計算式為

(12)

武器毀傷效果按照加權的鐘形函數來取:

(13)

式中,aik是武器對目標的經驗殺傷概率;鐘形函數的寬度參數取常量rc;rBik是武器對目標具有最大殺傷概率時的距離;ε是人工加的擾動。

2.2實驗參數設置

實驗參數設置如表1和表2所示。

表1　實驗1參數設置

仿真中取樣1 000次,每一次取樣都得到一個目標的距離向量。對于每個取樣,按照式(13)評估目標價值和武器殺傷概率,產生[V1∶I,P1∶I,1∶k]1∶1 000用分支定界法計算對應的決策[d1∶i,1∶k]1∶1 000,這樣就形成了實驗數據。

表2　實驗2、實驗3參數設置

為了驗證算法的效果,采用KNN[14]、FKNN[15]、分支定界法[5]和遺傳算法[6]作為對比算法。分支定界法和遺傳算法及本文的方法可以按照算法計算時間和優化性能兩方面來進行比較。各引用算法均按照原論文中的描述進行構建。在計算算法的估計誤差時,采用10重互校驗(10-foldcrossvalidation),將數據樣本集隨機分割成不相交的10個子集,依次選取其中一個作為訓練集〈xtr,ytr〉,再隨機選取另一個子集作為驗證集,這樣對算法驗證檢驗10次,取其平均值。

對于分類算法,驗證指標為其分類正確率:

(14)

另一驗證指標是代價值誤差率,即精確解與近似解的代價之差,除以精確解的代價來歸一化,即

(15)

式中,E(x,y)是整數規劃問題(1)中的目標函數。

3仿真結果分析

3項仿真實驗均進行了103次,仿真結果如表3所示。通過結果可以看出,相比分支定界法和GA法,IT2FKNN能夠得到滿意的近似效果,且計算時間相比分支定界法要短得多,這與預期相同。由于IT2FKNN采用了并行處理的方式,因此多個分類器的計算時間理論上趨近于一個分類器的時間,而反之分支定界法和遺傳算法隨隨規模增大,其代價函數的計算量顯著增加,而復雜度極具增大,因為搜索類算法在每一個循環中都要重新計算代價函數,所以其計算時間可能較長。而機器學習算法一旦訓練完成,其計算時間幾乎可以忽略不計。在訓練中,算法的并行解算機制及不依賴代價函數的性質,使其更適于處理較大規模的目標分配問題。除此以外還可以看出,本文方法在大規模問題上計算時間依然較快,適用于解大規模問題。但由于分支定界法的運算時間太長,因此在大規模問題的實際應用中,宜將本文方法與啟發式搜索方法相結合,采用啟發式搜索方法的輸出作為訓練樣本,這樣才能保證方法應用的實時性。

表3　仿真實驗結果

4結論

在本研究中,提出了一種戰場上輔助決策算法,即通過基于規則的映射來機器學習過程,達到目標分配的意圖。此方法是機器學習在武器-目標分配問題研究中的有益嘗試,該方法在一定程度上保證分配精度而且計算時間較快。

目前針對動態武器-目標分配問題的方法較多,各有其適用范圍,本研究所述方法最適用于戰場運籌時間片之間,態勢未發生劇烈變化情況下的快速計算,在態勢劇烈變化,不確定性迅速上升的情況下,可結合其他方法,例如采用魯棒的分配策略抑制不確定性、裁剪戰場態勢條件、多模型決策、預判斷與預處理等,以得到更好的運算效果。

本研究中,尚有兩方面的問題未作討論,可以留作后續研究。一是,沒有討論各武器在目標分配方案中的統計聯系及組合分配方案,例如若A分配目標a,則B必分配目標b,或更進一步,將武器和目標結合成組,只考慮(AB)分配(ab)的情形,這涉及到將分配方案本身作為訓練的問題域變量帶入計算,以及挖掘武器作戰效能的關聯性關系問題。二是,沒有討論分類器本身的數據挖掘和性能優化,例如,通過分析,得到問題域的經驗維度,然后按照值來設計分類器,采用數據降維或特征選取/提取算法,將問題域壓縮為進行運算,這樣分類器的訓練時間預期將顯著縮短,但特征提取是與實際情況相關的,還需要結合問題域數據的基本特征做進一步分析。

參考文獻：

[1] Liu C B, Qiu Z M, Wu L, et al. Review on current status and prospect of researches on dynamic weapon target assignment[J].ElectronicOptics&Control, 2010, 17(11): 43-48. (劉傳波, 邱志明,吳玲,等.動態武器-目標分配問題的研究現狀與展望[J].電光與控制,2010,17(11):43-48.)

[2] Cai H P, Chen Y W. The development of the research on weapon-target assignment (WTA) problem[J].FireControlandCommandControl, 2007, 31(12): 11-15. (蔡懷平, 陳英武. 武器-目標分配 (WTA) 問題研究進展[J].火力與指揮控制, 2007, 31(12): 11-15.)

[3] Huang F, Chen Z Q, Feng J F, et al. Target assignment algorithm for air-to-ship missile based on semi-restraint stochastic searching[J].SystemsEngineeringandElectronics,2013,35(8):1676-1680.(黃峰,陳中起,馮金富,等.基于半約束隨機搜索的空艦導彈目標分配方法[J].系統工程與電子技術,2013,35(8):1676-1680.)

[4] Xin B, Chen J, Zhang J, et al. Efficient decision makings for dynamic weapon-target assignment by virtual permutation and tabu search heuristics[J].IEEETrans.onSystems,Man,andCybernetics,PartC:ApplicationsandReviews, 2010,40(6):649-662.

[5] Ahuja R K, Kumar A, Jha K C, et al. Exact and heuristic algorithms for the weapon-target assignment problem[J].OperationsResearch, 2007, 55(6): 1136-1146.

[6] Malhotra A, Jain R K. Genetic algorithm for optimal weapon allocation in multilayer defence scenario[J].DefenceScienceJournal, 2002, 51(3): 285-293.

[7] Liu S W, Wang J, Yang M, et al. Research of ACO-SA optimization strategy for solving target assignment problem in air-defense C^3I system[J].SystemsEngineeringandElectronics, 2008, 29(11): 1886-1890. (劉少偉, 王潔, 楊明, 等. 防空 C^3I 目標分配問題的 ACO-SA 混合優化策略研究[J].系統工程與電子技術, 2008, 29(11): 1886-1890.)

[8] Fan C L, Xing Q H, Zheng M F, et al. Weapon-target allocation optimization algorithm based on IDPSO[J].SystemsEngineeringandElectronics,2015,37(2):336-342.(范成禮,邢清華,鄭明發,等.基于IDPSO的武器-目標分配優化算法[J].系統工程與電子技術,2015,37(2):336-342.)

[9] Xu J Q, Bi Y M, Wang M L, et al. Modeling and realization of conventional missile fire assignment based on time-space restriction[J].SystemsEngineeringandElectronics, 2011, 33(9): 2025-2029.(徐加強,畢義明,汪民樂,等.基于時空約束的常規導彈火力分配建模與實現[J].系統工程與電子技術,2011,33(9):2025-2029.)

[10] Huang S C, Li W M. Research of ant colony algorithm for solving target assignment problem[J].SystemsEngineeringandElectronics,2005,27(1):79-80.(黃樹采,李為民.目標分配問題的蟻群算法研究[J].系統工程與電子技術,2005,27(1):79-80.)

[11] Murphey R A.Target-basedweapontargetassignmentproblems[M].US:Springer,Nonlinear Assignment Problems,2000:39-53.

[12] Paradis S, Benaskeur A, Oxenham M, et al. Threat evaluation and weapons allocation in network-centric warfare[C]∥Proc.ofthe8thIEEEInternationalConferenceonInformationFusion, 2005.

[13] Hosein P A. A class of dynamic nonlinear resource allocation problems[R]. Massachusetts: Massachusetts Institute of Technology Cambridge Lab for Information and Decision Systems, 1989.

[14] Weinberger K Q, Blitzer J, Saul L K. Distance metric learning for large margin nearest neighbor classification[C]∥Proc.oftheAdvancesinNeuralInformationProcessingSystems,2005:1473-1480.

[15] Kuncheva L I.Fuzzyclassifierdesign[M]. Springer Science & Business Media, 2000.

[16] Darwish S M, El-Zoghabi A A, Hassen O A. A modified walk recognition system for human identification based on uncertainty eigen gait[J].InternationalJournalofMachineLearningandComputing, 2014, 4(4): 346.

[17] Mendel J M, John R, Liu F. Interval type-2 fuzzy logic systems made simple[J].IEEETrans.onFuzzySystems, 2006, 14(6): 808-821.

王邑(1984-),男,工程師,博士,主要研究方向為計算智能、空軍合同戰術模擬。

E-mail:wangyiafcc@hotmail.com

孫金標(1964-),男,教授,博士研究生導師,博士,主要研究方向為空軍戰術學。

E-mail:sunjinbiao@sohu.com

肖明清(1963-),男,教授,博士研究生導師,博士,主要研究方向為武器系統檢測智能化與自動化。

E-mail:xmqing@163.com

羅繼勛(1967-),男,副教授,碩士研究生導師,博士,主要研究方向為航空武器作戰效能分析。

E-mail:luojxafeu@163.com

Research of dynamic weapon-target assignment problem based on type-2 interval fuzzy K-nearest neighbors classifier

WANG Yi1, SUN Jin-biao1, XIAO Ming-qing2, LUO Ji-xun2

(1.DepartmentofTactical,AirForceCommandCollege,Beijing100097,China; 2.CollegeofAeronauticsandAstronauticsEngineering,AirForceEngineeringUniversity,Xi’an710038,China)

Abstract:Dynamic weapon-target assignment (WTA) problem is one of the critical problem when processing the battlefield command control and decision. The WTA algorithm makes the decision at the gap of two attack periods, which needs to be calculated efficiently.When using the battlefield assistant system to make WTA decision, it is a reasonable concept to utilize the machine learning method, make new decision from the known decision to avoid the need of searching new target assignment all over again. By using this concept, an interval type-2 fuzzy K-nearest neighbors(IT2FKNN) classifier usage on the WTA problem is proposed, by using the result from branch and bound to train the model, a parrallel IT2FKNN classifier is built to infer the assignment result. The proposed method is tested to be able to make a quick decision on the WTA problem.

Keywords:tactical decision; weapon-target assignment (WTA); interval type-2 fuzzy K-nearest neighbors (IT2FKNN) classifier; machine learning

收稿日期：2015-09-15；修回日期：2015-10-29；網絡優先出版日期：2016-02-17。

基金項目：航空科學基金(20131789004)資助課題

中圖分類號：TJ 761,V 247.2

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2016.06.15

作者簡介：

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160217.1143.002.html