基于圖論與PageRank的要地反導(dǎo)己方目標(biāo)重要性排序

王 ,滕克難,程 業(yè),陳 健

(海軍航空大學(xué)岸防兵學(xué)院,山東 煙臺(tái) 264001)

0 引 言

在要地反導(dǎo)作戰(zhàn)中,存在需要保衛(wèi)的重要目標(biāo)較多與反導(dǎo)資源有限的現(xiàn)實(shí)矛盾。因此,要求在制定要地反導(dǎo)作戰(zhàn)預(yù)案時(shí)對(duì)己方保衛(wèi)目標(biāo)進(jìn)行重要性排序,使得重點(diǎn)目標(biāo)生存概率最大化,以達(dá)到最佳作戰(zhàn)效果。

目前,針對(duì)反導(dǎo)作戰(zhàn)保護(hù)目標(biāo)重要性排序問(wèn)題已有學(xué)者進(jìn)行了相關(guān)研究。文獻(xiàn)[1]以目標(biāo)價(jià)值為衡量尺度,給出了己方目標(biāo)價(jià)值的層次結(jié)構(gòu)模型與數(shù)值計(jì)算方法;文獻(xiàn)[2]在分析保衛(wèi)目標(biāo)特性的基礎(chǔ)上,采取德?tīng)柗品ㄅc層次分析(analytic hierarchy process,AHP)法相結(jié)合的方法構(gòu)建指標(biāo)評(píng)價(jià)體系,利用逼近理想解排序技術(shù)(technique for order preference by similarity to ideal solution,TOPSIS)對(duì)己方目標(biāo)重要性進(jìn)行了定量排序;文獻(xiàn)[3]使用灰色聚類(lèi)方法研究了單個(gè)作戰(zhàn)階段己方目標(biāo)的重要度性問(wèn)題,采用序關(guān)系法分析了多個(gè)階段的權(quán)值對(duì)己方目標(biāo)的重要性影響。

上述研究在對(duì)目標(biāo)進(jìn)行重要性排序時(shí)均需要專(zhuān)家對(duì)相關(guān)指標(biāo)進(jìn)行打分、賦權(quán)值等,排序結(jié)果受人為因素影響較大。本文針對(duì)要地反導(dǎo)作戰(zhàn)問(wèn)題,創(chuàng)新性地提出一種基于圖論和網(wǎng)頁(yè)排名(PageRank,PR)算法的己方目標(biāo)重要性排序方法,客觀地給出己方目標(biāo)重要度數(shù)值,為要地反導(dǎo)作戰(zhàn)預(yù)案的制定提供有力支持。

1 基于圖論的要地反導(dǎo)己方目標(biāo)相互關(guān)系網(wǎng)絡(luò)模型

圖論思想以頂點(diǎn)集V和邊集E構(gòu)成抽象模型的網(wǎng)絡(luò)圖,來(lái)描述各節(jié)點(diǎn)之間的相互關(guān)系。本文借鑒圖論思想將要地反導(dǎo)作戰(zhàn)時(shí)的己方目標(biāo)抽象成有向網(wǎng)絡(luò)圖中的各節(jié)點(diǎn),將各節(jié)點(diǎn)間的關(guān)系抽象成連接節(jié)點(diǎn)的邊,分別從各目標(biāo)間的關(guān)系出發(fā)構(gòu)建有向網(wǎng)絡(luò)圖,以確定各節(jié)點(diǎn)之間的相互關(guān)聯(lián)模型[4-10]。

在實(shí)際問(wèn)題中,己方目標(biāo)之間存在著復(fù)雜的相互關(guān)系,需要從中分析選取與要地反導(dǎo)作戰(zhàn)相關(guān)性較大的相互關(guān)系構(gòu)建關(guān)系網(wǎng)絡(luò)圖。因此,考慮從要地反導(dǎo)作戰(zhàn)的作戰(zhàn)目的出發(fā),分別構(gòu)建靜態(tài)關(guān)系網(wǎng)與動(dòng)態(tài)關(guān)系網(wǎng)。其中靜態(tài)關(guān)系網(wǎng)主要描述各單位之間的自然關(guān)系,構(gòu)建依據(jù)主要來(lái)自各自的任務(wù)屬性、具體分工等,包括指控關(guān)系、通信關(guān)系、隸屬關(guān)系、維修關(guān)系、人員增援關(guān)系、裝備補(bǔ)給關(guān)系、后勤補(bǔ)給關(guān)系、偵查預(yù)警關(guān)系7個(gè)方面[11-15]。動(dòng)態(tài)關(guān)系網(wǎng)主要描述各單位在作戰(zhàn)情況下的相互影響,主要根據(jù)各單位在作戰(zhàn)行動(dòng)過(guò)程中發(fā)揮作用來(lái)進(jìn)行構(gòu)建,包括作戰(zhàn)制約關(guān)系、保護(hù)關(guān)系、毀傷影響關(guān)系[16-20]。具體構(gòu)建規(guī)則如下。

(1) 靜態(tài)關(guān)系網(wǎng)

指控關(guān)系指各己方目標(biāo)間的指揮控制關(guān)系,即目標(biāo)i給目標(biāo)j下達(dá)指令則相連,否則不相連。

通信關(guān)系指各己方目標(biāo)間的情報(bào)傳遞關(guān)系,即目標(biāo)i給目標(biāo)j提供情報(bào)信息則相連,否則不相連。

隸屬關(guān)系指各己方目標(biāo)間的上下級(jí)關(guān)系,即目標(biāo)i是目標(biāo)j上級(jí)則相連,否則不相連。

維修關(guān)系,即目標(biāo)i能為目標(biāo)j提供維修則相連,否則不相連。

人員增援關(guān)系,即目標(biāo)i能為目標(biāo)j提供人員增援則相連,否則不相連。

裝備補(bǔ)給關(guān)系,即目標(biāo)i能為目標(biāo)j提供作戰(zhàn)裝備補(bǔ)給則相連,否則不相連。

偵查預(yù)警關(guān)系,即目標(biāo)i能為目標(biāo)j提供預(yù)警情報(bào)則相連,否則不相連。

(2) 動(dòng)態(tài)關(guān)系網(wǎng)

作戰(zhàn)制約關(guān)系,即在作戰(zhàn)時(shí)如果目標(biāo)i被毀傷會(huì)導(dǎo)致目標(biāo)j無(wú)法執(zhí)行正常作戰(zhàn)任務(wù)則相連,否則不相連。

保護(hù)關(guān)系,即在作戰(zhàn)時(shí)目標(biāo)i需要被目標(biāo)j重點(diǎn)保護(hù)則相連,否則不相連。

毀傷影響關(guān)系,即在作戰(zhàn)時(shí)如果目標(biāo)i被打擊會(huì)對(duì)目標(biāo)j的安全造成直接威脅則相連,否則不相連。

按照上述規(guī)則對(duì)各目標(biāo)節(jié)點(diǎn)進(jìn)行連接即可構(gòu)成要地反導(dǎo)己方目標(biāo)相互關(guān)系模型。

2 基于PR的要地反導(dǎo)己方目標(biāo)重要性排序

PR算法是Google公司發(fā)明的一種算法,其應(yīng)用使得搜索的相關(guān)性有了質(zhì)的飛躍,較好地解決了網(wǎng)頁(yè)搜索結(jié)果中的排序問(wèn)題[21-24]。該算法具體計(jì)算步驟如下。

設(shè)向量B=[b1,b2,…,bN]T為N個(gè)網(wǎng)頁(yè)的排名。矩陣

為各網(wǎng)頁(yè)間的鏈接數(shù)目,其中am n代表第m個(gè)網(wǎng)頁(yè)指向第n個(gè)網(wǎng)頁(yè)的鏈接數(shù)。

設(shè)Bi為第i次迭代結(jié)果,則

Bi=ABi-1

(1)

在計(jì)算PR向量B時(shí),假設(shè)所有PR均為1/N,即

顯然,通過(guò)式(1)的迭代計(jì)算,Bi最終會(huì)收斂,即Bi無(wú)限趨近于B,此時(shí)B=A×B,停止迭代運(yùn)算,此時(shí)的向量B即為網(wǎng)頁(yè)的排名。

本文考慮借鑒PR算法思想,將要地反導(dǎo)作戰(zhàn)時(shí)己方每個(gè)目標(biāo)視作一個(gè)網(wǎng)頁(yè),將各目標(biāo)在不同關(guān)系下的連接視作各網(wǎng)頁(yè)之間的鏈接數(shù)。由于己方目標(biāo)之間的聯(lián)系數(shù)目均為已知,因此代入式(1)即可計(jì)算出向量B。使用PR算法得出的結(jié)果特點(diǎn)是被鏈接越多的PR越靠前,這與目標(biāo)的重要程度排序的目標(biāo)一致,即各關(guān)系網(wǎng)中連接線數(shù)量越多的節(jié)點(diǎn)越重要,排名越靠前[25-30]。

具體計(jì)算步驟如下。

設(shè)l個(gè)己方目標(biāo)重要性排名向量為

R=[r1,r2,…,rl]T

(2)

l個(gè)己方目標(biāo)在各關(guān)系下,相互聯(lián)系矩陣為

Rx=WRx-1

(3)

在計(jì)算己方目標(biāo)重要性排序向量R時(shí),假設(shè)所有PR均為1/L,即

通過(guò)式(3)的迭代計(jì)算最終可得到己方目標(biāo)重要性排名向量R。

3 具體步驟

本文提出的基于圖論與PR算法的要地反導(dǎo)作戰(zhàn)己方目標(biāo)重要性排序方法的具體步驟如下。

步驟 1確定在要地反導(dǎo)作戰(zhàn)中的所有己方目標(biāo)及數(shù)量,即確定L的取值。

步驟 2根據(jù)作戰(zhàn)需要確定各己方目標(biāo)之間所有的相互關(guān)系,即確定g的取值。

步驟 3根據(jù)步驟1和步驟2確定己方保護(hù)目標(biāo)以及各目標(biāo)間的相互關(guān)系,采用有向圖模型構(gòu)建全部的要地反導(dǎo)作戰(zhàn)己方目標(biāo)靜態(tài)、動(dòng)態(tài)關(guān)系模型。

步驟 4根據(jù)步驟3構(gòu)建的模型,計(jì)算各節(jié)點(diǎn)之間在全部關(guān)系下的所有連接數(shù)量。

步驟 5按照具體作戰(zhàn)實(shí)際情況要求，結(jié)合專(zhuān)家建議分別對(duì)靜態(tài)、動(dòng)態(tài)網(wǎng)絡(luò)的重要程度給出權(quán)值α和β,α+β=1。

步驟 6將α和β分別與靜態(tài)、動(dòng)態(tài)關(guān)系網(wǎng)絡(luò)中的連接數(shù)相乘,然后加和得到相互聯(lián)系矩陣,具體公式為

W=αWJ+βWD

(4)

步驟 7將L和W代入式(3)進(jìn)行迭代計(jì)算,最終獲得己方保護(hù)目標(biāo)的重要性排名向量R。

4 案例分析

根據(jù)相關(guān)資料構(gòu)建要地反導(dǎo)作戰(zhàn)模型,其中主要己方保護(hù)目標(biāo)包括機(jī)場(chǎng)、碼頭、食品庫(kù)、水庫(kù)、醫(yī)院、油料庫(kù)、彈藥裝備庫(kù)、指揮所、通信站、防空雷達(dá)、電子戰(zhàn)車(chē)、防空車(chē)1、防空車(chē)2和防空車(chē)3。分別從第1節(jié)確定的7個(gè)靜態(tài)方面和3個(gè)動(dòng)態(tài)方面構(gòu)建己方目標(biāo)相互關(guān)系模型,如圖1～圖6所示。對(duì)己方各目標(biāo)進(jìn)行編號(hào),并按照第2節(jié)的步驟計(jì)算出W,具體編號(hào)如表1所示。

圖1 要地反導(dǎo)作戰(zhàn)指控和通信關(guān)系網(wǎng)絡(luò)圖Fig.1 Network diagram of the relationship between command and communication for the anti-missile operations in important places

圖2 要地反導(dǎo)作戰(zhàn)隸屬和維修關(guān)系網(wǎng)絡(luò)圖Fig.2 Network diagram of the relationship between subordination and maintenance for the anti-missile operations in important places

圖3 要地反導(dǎo)作戰(zhàn)裝備補(bǔ)給和人員增援關(guān)系網(wǎng)絡(luò)圖Fig.3 Network diagram of the relationship between equipment supply and personnel reinforcement for the anti-missile operations in important places

圖4 要地反導(dǎo)作戰(zhàn)偵查和預(yù)警關(guān)系網(wǎng)絡(luò)圖Fig.4 Network diagram of the relationship between investigation and early warning for the anti-missile operations in important places

圖5 要地反導(dǎo)作戰(zhàn)重點(diǎn)保護(hù)和作戰(zhàn)制約關(guān)系網(wǎng)絡(luò)圖Fig.5 Network diagram of the relationship between key protection and operational constraints for the anti-missile operations important places

圖6 要地反導(dǎo)作戰(zhàn)毀傷影響關(guān)系網(wǎng)絡(luò)圖Fig.6 Network diagram of damage impact relationship for the anti-missile operations in important places

表1 要地反導(dǎo)作戰(zhàn)己方目標(biāo)編號(hào)Table 1 Own target number of anti-missile operations in important places

根據(jù)本文第3節(jié)的方法計(jì)算各己方目標(biāo)之間的聯(lián)系,得出靜態(tài)相互聯(lián)系矩陣WJ和動(dòng)態(tài)相互聯(lián)系矩陣WD分別為

本文根據(jù)要地反導(dǎo)作戰(zhàn)實(shí)際情況,結(jié)合專(zhuān)家意見(jiàn)確定α=0.38,β=0.62,代入式(4)計(jì)算可得

取L=14,則

采用Matlab仿真軟件計(jì)算目標(biāo)重要性,按照式(3)進(jìn)行計(jì)算,選擇迭代次數(shù)為10,得到己方各目標(biāo)重要度結(jié)果如表2所示。

表2 要地反導(dǎo)作戰(zhàn)己方目標(biāo)重要度數(shù)值Table 2 Importance value of own target for the anti-missile operations in important places

由表2可知己方目標(biāo)重要程度的排序,具體如表3所示。

表3 要地反導(dǎo)作戰(zhàn)己方目標(biāo)重要性排序Table 3 Importance ranking of own target for the anti-missile operations in important places

由表3的排序結(jié)果可知,本文提出方法能夠準(zhǔn)確、全面、客觀地給出己方目標(biāo)重要性排序,且基本符合要地反導(dǎo)作戰(zhàn)實(shí)際情況。

5 結(jié) 論

本文提出了基于圖論與PR算法的要地反導(dǎo)作戰(zhàn)己方保衛(wèi)目標(biāo)重要性排序方法,該排序方法的主要獨(dú)特之處在于:① 建立了基于圖論要地反導(dǎo)作戰(zhàn)己方目標(biāo)關(guān)系模型,全面、直觀地給出了各己方目標(biāo)間的相互關(guān)系;② 根據(jù)靜態(tài)、動(dòng)態(tài)關(guān)系網(wǎng)絡(luò)的不同特點(diǎn),給出各自權(quán)值,體現(xiàn)了己方目標(biāo)間在平時(shí)和戰(zhàn)時(shí)不同的重要程度;③ 在構(gòu)建關(guān)系模型基礎(chǔ)上創(chuàng)新性地采用PR算法對(duì)己方目標(biāo)的重要性進(jìn)行了排序,排序結(jié)果符合實(shí)際情況,且降低了人為因素對(duì)排序結(jié)果的影響,為要地反導(dǎo)作戰(zhàn)部署提供了一定參考。下一步考慮將模糊數(shù)學(xué)、組合賦權(quán)法等相關(guān)理論引入研究,以獲得更加完善的排序方法。