武海濤 劉洋 張永夫

1．國(guó)防大學(xué)聯(lián)合作戰(zhàn)學(xué)院北京100091

作戰(zhàn)態(tài)勢(shì)評(píng)估是對(duì)戰(zhàn)場(chǎng)上敵我雙方態(tài)勢(shì)要素的定性及定量描述,并在此基礎(chǔ)上動(dòng)態(tài)分析、理解和預(yù)測(cè)戰(zhàn)場(chǎng)情況和事件的過(guò)程,是指揮員科學(xué)、合理決策的基礎(chǔ). 美國(guó)心理學(xué)家Endsley 將態(tài)勢(shì)評(píng)估分為態(tài)勢(shì)察覺(jué)、態(tài)勢(shì)理解和態(tài)勢(shì)預(yù)測(cè)3 個(gè)階段[1]. 目標(biāo)分群是態(tài)勢(shì)察覺(jué)階段的重要內(nèi)容, 它根據(jù)戰(zhàn)場(chǎng)上獲知的作戰(zhàn)目標(biāo)信息, 按照一定規(guī)則將作戰(zhàn)目標(biāo)抽象成能夠一定程度上反映敵方作戰(zhàn)體系結(jié)構(gòu)和組織關(guān)系的目標(biāo)群體[2]. 目標(biāo)分群能夠幫助指揮員理解敵方作戰(zhàn)力量結(jié)構(gòu)和所擔(dān)負(fù)的作戰(zhàn)任務(wù), 為指揮員下一步分析敵方作戰(zhàn)目標(biāo)體系結(jié)構(gòu)與運(yùn)行規(guī)律, 并實(shí)施有效火力打擊提供了重要支撐.

當(dāng)前,目標(biāo)分群方面的研究有不少,一些學(xué)者抽取目標(biāo)的空間坐標(biāo)、功能屬性、敵我關(guān)系等信息,對(duì)作戰(zhàn)目標(biāo)進(jìn)行相似度分析, 最后使用聚類算法對(duì)目標(biāo)進(jìn)行分群. Blackman 研究目標(biāo)分群較早,在研究群體跟蹤問(wèn)題時(shí),使用聚類分析將直接目標(biāo)聚類,實(shí)現(xiàn)分群[3]. Bakert 等提取目標(biāo)個(gè)體屬性,基于貝葉斯網(wǎng)絡(luò)進(jìn)行證據(jù)推理, 得到多個(gè)互斥的作戰(zhàn)目標(biāo)集合[4].李偉楠等抽取目標(biāo)空間坐標(biāo), 提出了一種基于流形距離的密度值搜索算法, 通過(guò)計(jì)算目標(biāo)空間相似度實(shí)現(xiàn)將目標(biāo)劃分為若干作戰(zhàn)空間群的目的[5]. 樊振華等為了解決目標(biāo)分群中存在的類數(shù)未知與閾值欠缺的問(wèn)題, 提出了一種基于改進(jìn)空間劃分的目標(biāo)分群方法[6]. 張緒亮等提出一種改進(jìn)的K-means 算法實(shí)現(xiàn)在敵方兵力集群相互交錯(cuò)時(shí)的目標(biāo)分群[7]. 趙昀瑤提出了一種最大最小距離的聚類算法, 克服了目標(biāo)分群中的類數(shù)未知以及聚類結(jié)果依賴初始重心的缺陷[8]. 趙鵬等提出了一種基于多Agent 的目標(biāo)分群方法, 考慮了Agent 的地形、機(jī)動(dòng)性能等因素,解決了在地形分割時(shí)出現(xiàn)的目標(biāo)分群錯(cuò)誤的問(wèn)題[9].熊紅強(qiáng)等使用高維空間的相似度函數(shù)對(duì)作戰(zhàn)目標(biāo)進(jìn)行相似度分析,實(shí)現(xiàn)按層次分群的目的[10]. 畢鵬在深入分析層次聚類算法的基礎(chǔ)上,將改進(jìn)的Chameleon算法引入目標(biāo)分群[11]. 這類方法具有分群精度高、可理解性強(qiáng)等特點(diǎn), 但是難以反映目標(biāo)體系結(jié)構(gòu)以及各個(gè)目標(biāo)之間的關(guān)系, 所以更多用于實(shí)現(xiàn)戰(zhàn)術(shù)層面的目標(biāo)分群.

另一些學(xué)者從目標(biāo)體系的角度出發(fā), 使用復(fù)雜網(wǎng)絡(luò)方法構(gòu)建目標(biāo)體系網(wǎng)絡(luò), 通過(guò)社團(tuán)檢測(cè)算法對(duì)目標(biāo)體系進(jìn)行分群. 龍真真等基于復(fù)雜網(wǎng)絡(luò)方法構(gòu)建了目標(biāo)體系網(wǎng)絡(luò), 使用復(fù)雜網(wǎng)絡(luò)算法(Clausetnewman-moore, CNM)實(shí)現(xiàn)對(duì)目標(biāo)體系網(wǎng)絡(luò)的劃分[12]. 李赟基于敵方目標(biāo)體系網(wǎng)絡(luò)模型,通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的分析, 使用遺傳算法計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)的相似度,并分別實(shí)現(xiàn)了目標(biāo)獨(dú)立分群和重疊分群[13]. 這類方法借鑒了社交網(wǎng)絡(luò)分析中的社區(qū)檢測(cè)方法, 能夠反映目標(biāo)體系結(jié)構(gòu), 可以在目標(biāo)屬性獲知較少的情況下對(duì)大規(guī)模目標(biāo)進(jìn)行分群, 但是這類方法的分群結(jié)果往往具有不小的誤差.

標(biāo)簽傳播算法屬于基于復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)的半監(jiān)督學(xué)習(xí)算法,該算法的時(shí)間復(fù)雜度接近線性、執(zhí)行時(shí)間短、分類效果好,非常適合解決大規(guī)模目標(biāo)分群?jiǎn)栴}.基于標(biāo)簽傳播算法思想,提出一種基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法. 該方法綜合考慮了目標(biāo)在作戰(zhàn)過(guò)程中的重要度、目標(biāo)之間的物理空間關(guān)系以及信息關(guān)聯(lián)等方面, 彌補(bǔ)了標(biāo)準(zhǔn)標(biāo)簽傳播算法分群結(jié)果誤差大的不足, 提高了目標(biāo)分群結(jié)果的準(zhǔn)確性和穩(wěn)定性,實(shí)現(xiàn)了快速有效分群.

1 標(biāo)簽傳播算法概述

1.1 標(biāo)簽傳播算法

標(biāo)簽傳播算法(Label Propagation Algorithm,LPA)由Raghavan 于2007年首先提出[14], 該算法的基本思想是: 標(biāo)簽信息可以通過(guò)鄰居節(jié)點(diǎn)之間的連續(xù)傳播在全局網(wǎng)絡(luò)中得到更新, 因?yàn)樯鐓^(qū)內(nèi)部聯(lián)系緊密而社區(qū)之間關(guān)聯(lián)稀疏, 所以標(biāo)簽更容易在聯(lián)系緊密的社區(qū)內(nèi)部傳播, 標(biāo)簽經(jīng)過(guò)多次迭代傳播后不再發(fā)生變化,傳播至此結(jié)束. 標(biāo)簽傳播算法主要步驟如下:

1)節(jié)點(diǎn)標(biāo)簽初始化. 為每一個(gè)節(jié)點(diǎn)隨機(jī)設(shè)置一個(gè)初始的唯一標(biāo)簽.

2)確定節(jié)點(diǎn)更新順序. 隨機(jī)對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行排序,并按順序更新節(jié)點(diǎn)標(biāo)簽.

3)節(jié)點(diǎn)標(biāo)簽傳播.對(duì)于每個(gè)節(jié)點(diǎn),將鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最多的標(biāo)簽作為該節(jié)點(diǎn)更新的標(biāo)簽. 若鄰居節(jié)點(diǎn)中個(gè)數(shù)最多的標(biāo)簽不唯一時(shí), 則從中隨機(jī)選擇一個(gè)節(jié)點(diǎn)標(biāo)簽進(jìn)行更新.

4)標(biāo)簽傳播迭代過(guò)程. 當(dāng)所有節(jié)點(diǎn)標(biāo)簽不再改變時(shí)算法結(jié)束.

標(biāo)簽傳播具體過(guò)程如圖1 所示. 圖中有1、2、3、4 個(gè)節(jié)點(diǎn),隨機(jī)賦予每個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽,分別為A、B、C、D.隨機(jī)對(duì)4 個(gè)節(jié)點(diǎn)的標(biāo)簽進(jìn)行排序,按順序更新節(jié)點(diǎn). 假設(shè)更新順序?yàn)?、2、3、4,則先從節(jié)點(diǎn)1 開(kāi)始更新,因?yàn)楣?jié)點(diǎn)1 鄰居節(jié)點(diǎn)2、3、4 中標(biāo)簽出現(xiàn)分別為B、C、D,都出現(xiàn)一次,所以隨機(jī)選擇標(biāo)簽D 作為節(jié)點(diǎn)1 的標(biāo)簽進(jìn)行更新, 此時(shí)節(jié)點(diǎn)1的標(biāo)簽變?yōu)镈.更新節(jié)點(diǎn)2 標(biāo)簽,因?yàn)榇藭r(shí)節(jié)點(diǎn)2 的鄰居節(jié)點(diǎn)中, 標(biāo)簽D 出現(xiàn)2 次, 次數(shù)最多, 所以將標(biāo)簽D 作為節(jié)點(diǎn)2 的標(biāo)簽進(jìn)行更新. 按照此過(guò)程不斷迭代,最終群體內(nèi)部的節(jié)點(diǎn)都具有了相同的標(biāo)簽,圖中所有節(jié)點(diǎn)的標(biāo)簽都更新為D, 每個(gè)節(jié)點(diǎn)的標(biāo)簽均不再改變,此時(shí)算法結(jié)束.

圖1 標(biāo)簽傳播具體過(guò)程圖Fig.1 Label propagation process

1.2 標(biāo)簽傳播算法的改進(jìn)思路

標(biāo)簽傳播算法時(shí)間復(fù)雜度接近線性、執(zhí)行時(shí)間短、分類效果好,適合大型網(wǎng)絡(luò)的社區(qū)檢測(cè), 得到了廣泛的應(yīng)用[15?16]. 但是標(biāo)簽傳播算法仍然存在一些不足: 1)標(biāo)簽傳播算法將網(wǎng)絡(luò)中所有節(jié)點(diǎn)視為同質(zhì)節(jié)點(diǎn),所以在更新標(biāo)簽時(shí)采取隨機(jī)更新策略,因?yàn)橄雀碌墓?jié)點(diǎn)傳播更快, 可能造成度數(shù)較小的節(jié)點(diǎn)影響度數(shù)較大的節(jié)點(diǎn),使得算法需要更多次迭代,并可能導(dǎo)致分群結(jié)果的錯(cuò)誤; 2)當(dāng)鄰居節(jié)點(diǎn)中個(gè)數(shù)最多的標(biāo)簽不唯一時(shí), 算法隨機(jī)選擇其中一個(gè)標(biāo)簽進(jìn)行更新, 這可能造成每一次分群結(jié)果都不相同且差異較大, 使得算法穩(wěn)定性難以保證. 此外, 標(biāo)簽傳播算法單純依靠網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行分群, 缺少對(duì)目標(biāo)個(gè)體屬性的分析, 在具體應(yīng)用過(guò)程中分群結(jié)果具有不小的誤差. 例如目標(biāo)的群體類別除了與網(wǎng)絡(luò)拓?fù)潢P(guān)系有關(guān)還與目標(biāo)之間的物理空間距離有關(guān), 作戰(zhàn)目標(biāo)在一定物理空間內(nèi)距離相對(duì)越近, 越有可能同屬一個(gè)群體.

所以算法的改進(jìn)可以從以下幾個(gè)方面入手:

1)目標(biāo)體系網(wǎng)絡(luò)構(gòu)建. 目標(biāo)體系網(wǎng)絡(luò)有其自身特點(diǎn). 目標(biāo)體系網(wǎng)絡(luò)中具有許多不同類型和功能的目標(biāo)節(jié)點(diǎn),它們?cè)谀繕?biāo)體系中發(fā)揮著不同的作用. 可以據(jù)此將目標(biāo)節(jié)點(diǎn)劃分偵察、決策和火力3 類. 根據(jù)作戰(zhàn)體系的運(yùn)行機(jī)制, 目標(biāo)體系網(wǎng)絡(luò)的中作戰(zhàn)信息流轉(zhuǎn)具有一定的規(guī)律.例如:雷達(dá)產(chǎn)生的探測(cè)信息會(huì)流向指揮所, 指揮所進(jìn)行分析研判后會(huì)將決策指令傳達(dá)到指定部隊(duì). 所以可以根據(jù)OODA 循環(huán)理論的思想,通過(guò)計(jì)算節(jié)點(diǎn)參與OODA 循環(huán)的占比衡量節(jié)點(diǎn)的重要度.

2)節(jié)點(diǎn)更新策略. 因?yàn)橄雀碌墓?jié)點(diǎn)標(biāo)簽傳播更快,如果隨機(jī)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行更新,可能會(huì)導(dǎo)致度數(shù)較小的節(jié)點(diǎn)影響度數(shù)較大的節(jié)點(diǎn), 進(jìn)而影響分群結(jié)果的準(zhǔn)確性, 雖然在迭代的過(guò)程中會(huì)不斷修正分群結(jié)果, 但是這些不必要的更新操作會(huì)耗費(fèi)大量的運(yùn)算時(shí)間,影響算法效率,尤其當(dāng)網(wǎng)絡(luò)規(guī)模非常大時(shí)這種影響更加明顯. 根據(jù)目標(biāo)體系網(wǎng)絡(luò)的特點(diǎn)計(jì)算節(jié)點(diǎn)的重要度, 按照重要度由大到小對(duì)節(jié)點(diǎn)進(jìn)行更新可以解決這個(gè)問(wèn)題.

3)標(biāo)簽選擇策略. 標(biāo)簽傳播算法在標(biāo)簽更新過(guò)程時(shí), 如果鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最大的標(biāo)簽不只一個(gè), 待更新節(jié)點(diǎn)會(huì)從中隨機(jī)選擇一個(gè)標(biāo)簽作為自己的標(biāo)簽,具有一定的隨機(jī)性,會(huì)導(dǎo)致算法結(jié)果的不穩(wěn)定. 傳統(tǒng)標(biāo)簽選擇策略所想表達(dá)的是將對(duì)待更新節(jié)點(diǎn)影響最大的標(biāo)簽作為自己的標(biāo)簽來(lái)更新. 考慮到鄰居節(jié)點(diǎn)中相同標(biāo)簽出現(xiàn)的次數(shù)越多、鄰居節(jié)點(diǎn)與待更新節(jié)點(diǎn)相似度越高、鄰居節(jié)點(diǎn)的重要度越大,標(biāo)簽的影響力就越大. 所以將鄰居節(jié)點(diǎn)中相同標(biāo)簽出現(xiàn)的次數(shù)、鄰居節(jié)點(diǎn)與待更新節(jié)點(diǎn)的相似度以及鄰居節(jié)點(diǎn)的重要度結(jié)合起來(lái)形成標(biāo)簽影響力值, 根據(jù)標(biāo)簽影響力值選擇標(biāo)簽.

2 基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群

2.1 目標(biāo)體系網(wǎng)絡(luò)構(gòu)建

敵方目標(biāo)體系具有復(fù)雜網(wǎng)絡(luò)的特征, 可以使用復(fù)雜網(wǎng)絡(luò)方法進(jìn)行構(gòu)建. 這方面的相關(guān)研究國(guó)內(nèi)外已經(jīng)有不少,具有代表性的有Cares 提出的信息化作戰(zhàn)網(wǎng)絡(luò)模型, 該模型使用網(wǎng)絡(luò)鄰接矩陣描述作戰(zhàn)體系, 將實(shí)體抽象為目標(biāo)、傳感、決策、響應(yīng)4 類[17];陳麗娜等在傳統(tǒng)規(guī)則樹(shù)形網(wǎng)絡(luò)的基礎(chǔ)上, 通過(guò)一定規(guī)則在節(jié)點(diǎn)之間隨機(jī)建立連接, 生成網(wǎng)絡(luò)化戰(zhàn)爭(zhēng)模型[18]; 劉忠等將節(jié)點(diǎn)抽象為偵察、指揮控制和火力3 類,構(gòu)建了基于屬性層和結(jié)構(gòu)層相統(tǒng)一的超網(wǎng)絡(luò)模型[19];國(guó)防大學(xué)胡曉峰等構(gòu)建了由交戰(zhàn)網(wǎng)、指控網(wǎng)、信息網(wǎng)組成的作戰(zhàn)體系超網(wǎng)絡(luò)模型[20].

本文借鑒前人對(duì)作戰(zhàn)體系網(wǎng)絡(luò)構(gòu)建的經(jīng)驗(yàn), 對(duì)目標(biāo)體系網(wǎng)絡(luò)構(gòu)建如下:

1)目標(biāo)節(jié)點(diǎn)描述

根據(jù)作戰(zhàn)目標(biāo)本身屬性以及其網(wǎng)絡(luò)特征可以將其抽象為偵察節(jié)點(diǎn)Vs、決策節(jié)點(diǎn)Vd和火力節(jié)點(diǎn)Vf3 類體目標(biāo)節(jié)點(diǎn),形式化描述如下:

其中,UNIQUE_ID表示作戰(zhàn)目標(biāo)唯一序列識(shí)別;NAME表示作戰(zhàn)目標(biāo)名稱;CATEGORY表示作戰(zhàn)目標(biāo)類別, 如雷達(dá)、機(jī)場(chǎng)以及地面部隊(duì)等等;AT-TRIBUTE表示目標(biāo)的其他屬性集合, 包括目標(biāo)的坐標(biāo)位置、機(jī)動(dòng)能力、作戰(zhàn)能力等;TYPE_ID表示作戰(zhàn)目標(biāo)所屬群體的標(biāo)簽.

2)邊描述

邊反映了作戰(zhàn)目標(biāo)間的信息交互, 形式化描述如下:

當(dāng)E(Vi,Vj)= 1 時(shí),節(jié)點(diǎn)i和節(jié)點(diǎn)j之間產(chǎn)生信息交互,E(Vi,Vj)= 0 時(shí)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間無(wú)信息關(guān)聯(lián).

3)目標(biāo)體系網(wǎng)絡(luò)模型描述

根據(jù)前述內(nèi)容, 可以將敵方目標(biāo)體系網(wǎng)絡(luò)形式化描述如下:

其中,V= {v1,v2,··· ,vn}為目標(biāo)節(jié)點(diǎn)集合,n為節(jié)點(diǎn)數(shù)量,為邊集合,表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間產(chǎn)生的信息關(guān)聯(lián)情況.

2.2 節(jié)點(diǎn)更新策略

作戰(zhàn)環(huán)理論是20 世紀(jì)70年代由美軍上校Boyd提出的理論, 該理論將作戰(zhàn)過(guò)程抽象簡(jiǎn)化為OODA循環(huán)過(guò)程[21],即偵察系統(tǒng)發(fā)現(xiàn)目標(biāo),將目標(biāo)信息傳送指揮中心,指揮中心經(jīng)過(guò)分析后做出決策,命令打擊單位對(duì)目標(biāo)實(shí)施打擊, 而后偵察系統(tǒng)對(duì)打擊效果進(jìn)行感知, 指揮中心據(jù)此作出新一輪決策. 打擊鏈?zhǔn)荗ODA 作戰(zhàn)循環(huán)在目標(biāo)體系網(wǎng)絡(luò)中的體現(xiàn), 可以將其定義為:目標(biāo)體系網(wǎng)絡(luò)G(V,E)中由偵察節(jié)點(diǎn)Vs、決策節(jié)點(diǎn)Vd和火力節(jié)點(diǎn)Vf組成的能夠執(zhí)行完整作戰(zhàn)任務(wù)的路徑.

目標(biāo)節(jié)點(diǎn)的重要度Ri可以用目標(biāo)參與打擊鏈的數(shù)量與網(wǎng)絡(luò)中打擊鏈總數(shù)量Nac的占比衡量,表示為:

打擊鏈數(shù)量計(jì)算可以理解為圖路徑搜索問(wèn)題,即從圖中搜索所有符合條件的路徑. 圖路徑搜索一般有廣度優(yōu)先搜索和深度優(yōu)先搜索兩種策略,其中,深度優(yōu)先搜索可以用于解決打擊鏈的計(jì)算問(wèn)題, 其思想是從起始節(jié)點(diǎn)出發(fā), 沿著圖中的某一條路徑一直探索,直到不能探索為止.當(dāng)不能探索后沿著相反的方向?qū)ふ业叫路种?然后沿著新路徑繼續(xù)探索,直到將圖遍歷完畢.

具體搜索過(guò)程為:如圖2 所示,以節(jié)點(diǎn)1 為起始節(jié)點(diǎn)開(kāi)始搜索. 首先從節(jié)點(diǎn)1 的鄰居節(jié)點(diǎn)2 和3 中任選一個(gè)節(jié)點(diǎn)向下搜索, 假設(shè)此處選節(jié)點(diǎn)2; 然后繼續(xù)從節(jié)點(diǎn)2 的鄰居節(jié)點(diǎn)4 和5 中任選一個(gè)節(jié)點(diǎn)向下搜索,假設(shè)此處選節(jié)點(diǎn)4; 然后繼續(xù)從節(jié)點(diǎn)4 的鄰居節(jié)點(diǎn)7 和8 中任選一個(gè)節(jié)點(diǎn)向下搜索,假設(shè)此處選節(jié)點(diǎn)7; 搜索到節(jié)點(diǎn)7 時(shí)無(wú)法繼續(xù)向下搜索, 則返回至節(jié)點(diǎn)4,發(fā)現(xiàn)尚未搜索的節(jié)點(diǎn)8,繼續(xù)向下搜索;搜索到節(jié)點(diǎn)8 時(shí)無(wú)法繼續(xù)向下搜索, 則返回節(jié)點(diǎn)4, 發(fā)現(xiàn)鄰居節(jié)點(diǎn)已經(jīng)搜索完畢, 則返回節(jié)點(diǎn)2, 發(fā)現(xiàn)尚未搜索的節(jié)點(diǎn)5,繼續(xù)向下搜索. 重復(fù)以上過(guò)程直至將圖搜索完畢,節(jié)點(diǎn)的搜索順序?yàn)?1、2、4、7、8、5、3、6.

圖2 深度優(yōu)先搜索具體過(guò)程圖Fig.2 Depth-firs search process

由打擊鏈的定義可知, 打擊鏈以偵察節(jié)點(diǎn)為起始節(jié)點(diǎn), 中間包含若干決策節(jié)點(diǎn), 終止于火力節(jié)點(diǎn).所以可以根據(jù)打擊鏈的特點(diǎn)對(duì)深度優(yōu)先搜索算法進(jìn)行改進(jìn), 通過(guò)判別條件過(guò)濾掉深度優(yōu)先搜索算法中不符合打擊鏈特征的路徑,以提高算法的效率.下面給出基于深度優(yōu)先搜索的打擊鏈數(shù)量Nac算法的具體流程.

表1 基于深度優(yōu)先搜索的打擊鏈數(shù)量算法Table 1 A strike chains algorithm based on depth-firs search

根據(jù)以上算法得到打擊鏈的數(shù)量, 進(jìn)而可以計(jì)算每個(gè)節(jié)點(diǎn)的Ri值,按照Ri值由大到小對(duì)節(jié)點(diǎn)進(jìn)行排序,最終確定目標(biāo)節(jié)點(diǎn)的更新順序.

2.3 標(biāo)簽選擇策略

標(biāo)簽傳播算法在標(biāo)簽更新過(guò)程時(shí), 如果鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最大的標(biāo)簽不只一個(gè), 待更新節(jié)點(diǎn)會(huì)從中隨機(jī)選擇一個(gè)標(biāo)簽作為自己的標(biāo)簽, 具有一定的隨機(jī)性,會(huì)導(dǎo)致算法結(jié)果的不穩(wěn)定. 標(biāo)簽選擇策略所想表達(dá)的是將對(duì)待更新節(jié)點(diǎn)影響最大的標(biāo)簽作為自己的標(biāo)簽來(lái)更新. 考慮到鄰居節(jié)點(diǎn)中相同標(biāo)簽出現(xiàn)的次數(shù)越多、鄰居節(jié)點(diǎn)與待更新節(jié)點(diǎn)相似度越高、鄰居節(jié)點(diǎn)的重要度越大,標(biāo)簽的影響力就越大.所以將鄰居節(jié)點(diǎn)中相同標(biāo)簽出現(xiàn)的次數(shù)、鄰居節(jié)點(diǎn)與待更新節(jié)點(diǎn)的相似度以及鄰居節(jié)點(diǎn)的重要度結(jié)合起來(lái)計(jì)算標(biāo)簽影響力,可以表示如下:

其中,為待更新節(jié)點(diǎn)j的標(biāo)簽為l鄰居節(jié)點(diǎn)的集合,Ri為節(jié)點(diǎn)重要度,St為節(jié)點(diǎn)與待更新節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)相似度,Sd為節(jié)點(diǎn)之間的空間距離相似度,w代表節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)相似度和節(jié)點(diǎn)空間距離相似度在標(biāo)簽影響力中占的權(quán)重,一般可以取0.5.

網(wǎng)絡(luò)結(jié)構(gòu)相似性可以使用Jaccard 相似度進(jìn)行計(jì)算:

其中,Ni、Nj分別表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集合,表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)交集的節(jié)點(diǎn)數(shù)量,表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)并集的節(jié)點(diǎn)數(shù)量;Jaccard 值介于0-1 之間,該值越接近1, 表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的網(wǎng)絡(luò)結(jié)構(gòu)相似度越高.

空間距離相似度可以用歐式距離表示, 通過(guò)隸屬度函數(shù)對(duì)空間距離劃分, 得到的空間距離相似度可以表示為:

其中,x,y,z為目標(biāo)節(jié)點(diǎn)的空間坐標(biāo),d1,d2,d3為區(qū)分隸屬度的閾值, 一般可以根據(jù)目標(biāo)體系網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最大距離dmax以及目標(biāo)的實(shí)際分布情況劃分取值.Sd取0、0.25、0.75、1 分別表示兩節(jié)點(diǎn)之間在物理空間的距離遠(yuǎn)、較遠(yuǎn)、較近、近.

綜合上述內(nèi)容可以算得待更新節(jié)點(diǎn)鄰居節(jié)點(diǎn)的各個(gè)標(biāo)簽的影響力, 選擇影響力最大的標(biāo)簽作為自己的標(biāo)簽來(lái)更新.

2.4 方法流程

基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法的具體步驟描述如表2 所示.

表2 基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法具體流程Table 2 The process of target clustering based on improved label propagation algorithm

2.5 目標(biāo)分群結(jié)果評(píng)價(jià)

較為常用的一種復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分質(zhì)量評(píng)價(jià)指標(biāo)是由Newman 和Girvan 提出的模塊度(Q modularity)[22],它可以在網(wǎng)絡(luò)劃分沒(méi)有標(biāo)準(zhǔn)的結(jié)果時(shí)評(píng)價(jià)社團(tuán)質(zhì)量劃分的優(yōu)劣,模塊度的取值在0 ～1,模塊度的值越接近1,社團(tuán)劃分質(zhì)量越高. 本文使用模塊度來(lái)評(píng)價(jià)目標(biāo)分群結(jié)果.模塊度的計(jì)算表達(dá)式如下:

其中,Aij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的連邊情況,如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連邊則Aij= 1, 否則Aij= 0,m表示網(wǎng)絡(luò)中連邊的總數(shù),ki和kj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度,δ(ci,cj)的取值為:如果點(diǎn)i和節(jié)點(diǎn)j在一個(gè)社團(tuán),即ci=cj時(shí),δ(ci,cj)=1,否則δ(ci,cj)=0.

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)說(shuō)明

實(shí)驗(yàn)分析的主要目的是為了驗(yàn)證基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法的有效性. 文獻(xiàn)[23-24]對(duì)基于復(fù)雜網(wǎng)絡(luò)的作戰(zhàn)體系網(wǎng)絡(luò)的生成方法進(jìn)行了描述, 其主要思想是首先根據(jù)軍事指揮理論按照傳統(tǒng)指揮關(guān)系構(gòu)建樹(shù)狀作戰(zhàn)體系網(wǎng)絡(luò), 然后根據(jù)聯(lián)合作戰(zhàn)的思想在同一指揮層級(jí)以及跨指揮層級(jí)之間建立指揮關(guān)系, 形成最終的作戰(zhàn)體系網(wǎng)絡(luò). 根據(jù)文獻(xiàn)[23-24]中作戰(zhàn)體系網(wǎng)絡(luò)的生成步驟, 結(jié)合文獻(xiàn)[25]提出的防空系統(tǒng)模型構(gòu)建了包含偵察、決策、火力3類節(jié)點(diǎn)的防空目標(biāo)體系網(wǎng)絡(luò),如圖3 所示. 該網(wǎng)絡(luò)共包含341 個(gè)目標(biāo)節(jié)點(diǎn),其中,決策目標(biāo)節(jié)點(diǎn)85 個(gè)(用圓形表示)、偵察節(jié)點(diǎn)126 個(gè)(用正方形表示)、火力節(jié)點(diǎn)130 個(gè)(用三角形表示), 包含指揮關(guān)系541 條.目標(biāo)體系網(wǎng)絡(luò)共包含4 個(gè)能夠相對(duì)獨(dú)立執(zhí)行防空任務(wù)的目標(biāo)群體(用虛線框區(qū)分),且按照群體內(nèi)各個(gè)作戰(zhàn)目標(biāo)相對(duì)距離較近的原則部署.

圖3 目標(biāo)體系網(wǎng)絡(luò)示意圖Fig.3 Target system networks

3.2 實(shí)驗(yàn)結(jié)果分析

根據(jù)本文提出的基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法,計(jì)算各個(gè)目標(biāo)節(jié)點(diǎn)的重要度,得到重要度排序節(jié)選如表3 所示.

表3 節(jié)點(diǎn)重要度排序表(節(jié)選)Table 3 Node importance ranking table(excerpt)

從表3 中可以看出, 決策節(jié)點(diǎn)參與打擊鏈的占比較多、排序靠前, 代表其節(jié)點(diǎn)重要度較大,與實(shí)際情況相符合, 所以可以根據(jù)該節(jié)點(diǎn)重要度排序確定節(jié)點(diǎn)更新順序.其次節(jié)點(diǎn)計(jì)算Jaccard 相似度與空間距離相似度,結(jié)合節(jié)點(diǎn)重要度得到節(jié)點(diǎn)影響力值,以此來(lái)選擇標(biāo)簽進(jìn)行更新, 經(jīng)過(guò)4 次迭代后標(biāo)簽不再發(fā)生變化,得到目標(biāo)分群結(jié)果如圖4 所示.

從圖4 中可以看出經(jīng)過(guò)4 次迭代后,網(wǎng)絡(luò)中僅存標(biāo)簽1、2、3、5,將目標(biāo)體系網(wǎng)絡(luò)劃分為4 個(gè)相對(duì)獨(dú)立的防空目標(biāo)群體(用虛線框區(qū)分),結(jié)果與實(shí)際目標(biāo)體系網(wǎng)絡(luò)部署情況相符合,計(jì)算得到模塊度Q 值為0.63,表明目標(biāo)分群質(zhì)量較好,因此,可以驗(yàn)證本文提出的基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法能夠相對(duì)合理的對(duì)作戰(zhàn)目標(biāo)進(jìn)行分群. 為了進(jìn)一步驗(yàn)證算法的穩(wěn)定性, 在相同的目標(biāo)體系網(wǎng)絡(luò)中分別使用本文所提目標(biāo)分群方法和標(biāo)準(zhǔn)標(biāo)簽傳播算法進(jìn)行目標(biāo)分群實(shí)驗(yàn),得到200 次實(shí)驗(yàn)結(jié)果,其中,本文所提方法得到的分群結(jié)果一致,表明算法穩(wěn)定性較好,而使用標(biāo)準(zhǔn)標(biāo)簽傳播算法得到的結(jié)果各不相同, 穩(wěn)定性相對(duì)較差,因此,可以驗(yàn)證本文提出的基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法具有較好的穩(wěn)定性.

圖4 改進(jìn)標(biāo)簽傳播算法目標(biāo)分群結(jié)果示意圖Fig.4 Target clustering results of improved label propagation algorithm

4 結(jié)論

根據(jù)目標(biāo)體系的特點(diǎn)構(gòu)建目標(biāo)體系網(wǎng)絡(luò), 基于復(fù)雜網(wǎng)絡(luò)社區(qū)探測(cè)的標(biāo)簽傳播算法思想, 提出了一種基于改進(jìn)標(biāo)簽傳播算法的目標(biāo)分群方法, 以防空目標(biāo)體系網(wǎng)絡(luò)為例, 對(duì)該方法的有效性和穩(wěn)定性進(jìn)行了實(shí)驗(yàn)驗(yàn)證. 該方法綜合考慮了目標(biāo)在作戰(zhàn)過(guò)程中的重要度、目標(biāo)之間的物理空間關(guān)系以及信息關(guān)聯(lián)等方面, 彌補(bǔ)了現(xiàn)有研究中單純依靠目標(biāo)個(gè)體屬性或網(wǎng)絡(luò)體系結(jié)構(gòu)的不足. 針對(duì)傳統(tǒng)標(biāo)簽傳播算法結(jié)果不穩(wěn)定的問(wèn)題, 從節(jié)點(diǎn)更新策略和標(biāo)簽選擇策略兩個(gè)方面對(duì)算法進(jìn)行了改進(jìn), 實(shí)現(xiàn)對(duì)目標(biāo)體系快速有效分群,為下一步目標(biāo)選擇提供支撐.