基于圖論與PageRank的要地反導己方目標重要性排序

王 ,滕克難,程 業,陳 健

(海軍航空大學岸防兵學院,山東 煙臺 264001)

0 引 言

在要地反導作戰中,存在需要保衛的重要目標較多與反導資源有限的現實矛盾。因此,要求在制定要地反導作戰預案時對己方保衛目標進行重要性排序,使得重點目標生存概率最大化,以達到最佳作戰效果。

目前,針對反導作戰保護目標重要性排序問題已有學者進行了相關研究。文獻[1]以目標價值為衡量尺度,給出了己方目標價值的層次結構模型與數值計算方法;文獻[2]在分析保衛目標特性的基礎上,采取德爾菲法與層次分析(analytic hierarchy process,AHP)法相結合的方法構建指標評價體系,利用逼近理想解排序技術(technique for order preference by similarity to ideal solution,TOPSIS)對己方目標重要性進行了定量排序;文獻[3]使用灰色聚類方法研究了單個作戰階段己方目標的重要度性問題,采用序關系法分析了多個階段的權值對己方目標的重要性影響。

上述研究在對目標進行重要性排序時均需要專家對相關指標進行打分、賦權值等,排序結果受人為因素影響較大。本文針對要地反導作戰問題,創新性地提出一種基于圖論和網頁排名(PageRank,PR)算法的己方目標重要性排序方法,客觀地給出己方目標重要度數值,為要地反導作戰預案的制定提供有力支持。

1 基于圖論的要地反導己方目標相互關系網絡模型

圖論思想以頂點集V和邊集E構成抽象模型的網絡圖,來描述各節點之間的相互關系。本文借鑒圖論思想將要地反導作戰時的己方目標抽象成有向網絡圖中的各節點,將各節點間的關系抽象成連接節點的邊,分別從各目標間的關系出發構建有向網絡圖,以確定各節點之間的相互關聯模型[4-10]。

在實際問題中,己方目標之間存在著復雜的相互關系,需要從中分析選取與要地反導作戰相關性較大的相互關系構建關系網絡圖。因此,考慮從要地反導作戰的作戰目的出發,分別構建靜態關系網與動態關系網。其中靜態關系網主要描述各單位之間的自然關系,構建依據主要來自各自的任務屬性、具體分工等,包括指控關系、通信關系、隸屬關系、維修關系、人員增援關系、裝備補給關系、后勤補給關系、偵查預警關系7個方面[11-15]。動態關系網主要描述各單位在作戰情況下的相互影響,主要根據各單位在作戰行動過程中發揮作用來進行構建,包括作戰制約關系、保護關系、毀傷影響關系[16-20]。具體構建規則如下。

(1) 靜態關系網

指控關系指各己方目標間的指揮控制關系,即目標i給目標j下達指令則相連,否則不相連。

通信關系指各己方目標間的情報傳遞關系,即目標i給目標j提供情報信息則相連,否則不相連。

隸屬關系指各己方目標間的上下級關系,即目標i是目標j上級則相連,否則不相連。

維修關系,即目標i能為目標j提供維修則相連,否則不相連。

人員增援關系,即目標i能為目標j提供人員增援則相連,否則不相連。

裝備補給關系,即目標i能為目標j提供作戰裝備補給則相連,否則不相連。

偵查預警關系,即目標i能為目標j提供預警情報則相連,否則不相連。

(2) 動態關系網

作戰制約關系,即在作戰時如果目標i被毀傷會導致目標j無法執行正常作戰任務則相連,否則不相連。

保護關系,即在作戰時目標i需要被目標j重點保護則相連,否則不相連。

毀傷影響關系,即在作戰時如果目標i被打擊會對目標j的安全造成直接威脅則相連,否則不相連。

按照上述規則對各目標節點進行連接即可構成要地反導己方目標相互關系模型。

2 基于PR的要地反導己方目標重要性排序

PR算法是Google公司發明的一種算法,其應用使得搜索的相關性有了質的飛躍,較好地解決了網頁搜索結果中的排序問題[21-24]。該算法具體計算步驟如下。

設向量B=[b1,b2,…,bN]T為N個網頁的排名。矩陣

為各網頁間的鏈接數目,其中am n代表第m個網頁指向第n個網頁的鏈接數。

設Bi為第i次迭代結果,則

Bi=ABi-1

(1)

在計算PR向量B時,假設所有PR均為1/N,即

顯然,通過式(1)的迭代計算,Bi最終會收斂,即Bi無限趨近于B,此時B=A×B,停止迭代運算,此時的向量B即為網頁的排名。

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

具體計算步驟如下。

設l個己方目標重要性排名向量為

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

(2)

l個己方目標在各關系下,相互聯系矩陣為

Rx=WRx-1

(3)

在計算己方目標重要性排序向量R時,假設所有PR均為1/L,即

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

3 具體步驟

本文提出的基于圖論與PR算法的要地反導作戰己方目標重要性排序方法的具體步驟如下。

步驟 1確定在要地反導作戰中的所有己方目標及數量,即確定L的取值。

步驟 2根據作戰需要確定各己方目標之間所有的相互關系,即確定g的取值。

步驟 3根據步驟1和步驟2確定己方保護目標以及各目標間的相互關系,采用有向圖模型構建全部的要地反導作戰己方目標靜態、動態關系模型。

步驟 4根據步驟3構建的模型,計算各節點之間在全部關系下的所有連接數量。

步驟 5按照具體作戰實際情況要求，結合專家建議分別對靜態、動態網絡的重要程度給出權值α和β,α+β=1。

步驟 6將α和β分別與靜態、動態關系網絡中的連接數相乘,然后加和得到相互聯系矩陣,具體公式為

W=αWJ+βWD

(4)

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

4 案例分析

根據相關資料構建要地反導作戰模型,其中主要己方保護目標包括機場、碼頭、食品庫、水庫、醫院、油料庫、彈藥裝備庫、指揮所、通信站、防空雷達、電子戰車、防空車1、防空車2和防空車3。分別從第1節確定的7個靜態方面和3個動態方面構建己方目標相互關系模型,如圖1～圖6所示。對己方各目標進行編號,并按照第2節的步驟計算出W,具體編號如表1所示。

圖1 要地反導作戰指控和通信關系網絡圖Fig.1 Network diagram of the relationship between command and communication for the anti-missile operations in important places

圖2 要地反導作戰隸屬和維修關系網絡圖Fig.2 Network diagram of the relationship between subordination and maintenance for the anti-missile operations in important places

圖3 要地反導作戰裝備補給和人員增援關系網絡圖Fig.3 Network diagram of the relationship between equipment supply and personnel reinforcement for the anti-missile operations in important places

圖4 要地反導作戰偵查和預警關系網絡圖Fig.4 Network diagram of the relationship between investigation and early warning for the anti-missile operations in important places

圖5 要地反導作戰重點保護和作戰制約關系網絡圖Fig.5 Network diagram of the relationship between key protection and operational constraints for the anti-missile operations important places

圖6 要地反導作戰毀傷影響關系網絡圖Fig.6 Network diagram of damage impact relationship for the anti-missile operations in important places

表1 要地反導作戰己方目標編號Table 1 Own target number of anti-missile operations in important places

根據本文第3節的方法計算各己方目標之間的聯系,得出靜態相互聯系矩陣WJ和動態相互聯系矩陣WD分別為

本文根據要地反導作戰實際情況,結合專家意見確定α=0.38,β=0.62,代入式(4)計算可得

取L=14,則

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

表2 要地反導作戰己方目標重要度數值Table 2 Importance value of own target for the anti-missile operations in important places

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

表3 要地反導作戰己方目標重要性排序Table 3 Importance ranking of own target for the anti-missile operations in important places

由表3的排序結果可知,本文提出方法能夠準確、全面、客觀地給出己方目標重要性排序,且基本符合要地反導作戰實際情況。

5 結 論

本文提出了基于圖論與PR算法的要地反導作戰己方保衛目標重要性排序方法,該排序方法的主要獨特之處在于:① 建立了基于圖論要地反導作戰己方目標關系模型,全面、直觀地給出了各己方目標間的相互關系;② 根據靜態、動態關系網絡的不同特點,給出各自權值,體現了己方目標間在平時和戰時不同的重要程度;③ 在構建關系模型基礎上創新性地采用PR算法對己方目標的重要性進行了排序,排序結果符合實際情況,且降低了人為因素對排序結果的影響,為要地反導作戰部署提供了一定參考。下一步考慮將模糊數學、組合賦權法等相關理論引入研究,以獲得更加完善的排序方法。