基于图论与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算法对己方目标的重要性进行了排序,排序结果符合实际情况,且降低了人为因素对排序结果的影响,为要地反导作战部署提供了一定参考。下一步考虑将模糊数学、组合赋权法等相关理论引入研究,以获得更加完善的排序方法。