异步并行蚂蚁策略在网络化舰艇编队武器目标分配中的应用

李相民， 张元瀚， 代进进

(海军航空工程学院，山东 烟台 264001)

0 引言

在当前乃至未来的海战中，由美国海军首先提出的舰艇编队网络中心战理论将成为主导。作战平台呈现扁平化、网络化，形成一个整体与整体的对抗，但是这也导致了信息量的暴增，从发现目标到发射拦截导弹的过程中如果单以人力来处理这些信息，是远远不能满足作战需要的。如何合理利用编队资源，有效、科学和经济地进行防空作战，对我编队海上作战具有重要意义［1］。

目前的各种武器目标分配(Weapon Target Assignment，WTA)方法很多，主要有遗传算法以及改进的遗传算法，微分对策模型和灰色局势决策方法，这些方法实时性较弱，全局搜索能力不强，容易陷入局部最优;另外还有基于马尔科夫链的动态分配，但是预测需要过去的信息，随着时间的推移和目标的大量出现，计算工作量也将无法满足实战作战需求［2］。

本文给出了一种基于蚁群算法的异步并行蚂蚁策略。利用蚁群系统的并行性和正反馈快速收敛性等优点，对舰艇编队武器目标分配进行了研究，文章引入了综合毁伤阈值和综合毁伤矩阵Em的概念，前者在有大量目标数和武器节点数的情况下，能够大大减少计算量;后者在突发情况发生之后能保证分配继续正常进行，很大程度上满足了实战性的需要。

1 网络平台介绍

多Agent系统(Multi-Agent System，MAS)的引入为网络中心战中的编队系统提供了一个动态的分布式的网络，作为平台发挥作用。MAS中的Agent概念，源于人工智能理论，它的特性主要是具有反应性、自主性和社会性。而每个Agent不仅要求自身具备一定的处理和解决问题的能力，更要求各个Agent之间具有互相协作、共同完成某个任务的能力，这与编队内成员的功能和地位不谋而合。“网络中心战”中的作战舰艇，具备指控系统、武器系统和传感器，具备独立作战能力，而数据网络奠定了各舰之间协作的基础［3］。

在网络中，指控系统之间通过广播模块和接收模块实现资源和信息的共享和指挥协商的功能;通过公共访问服务节点来进行网外单位的进入和网内单位的退网，实现动态网络的重组。图1是MAS的主要结构功能图。

图1 舰艇编队MAS结构功能图Fig.1 The function structure of warship fleet MAS

2 基于MAS的WTA模型

2.1 约束条件

在目标分配之前，有几点必须统一。首先所有网内成员必须以整体效益最大为最高优先和最终目标;其次从威胁判断开始到目标分配所运用的算法必须一致，否则会产生计算结果的不同步和时序上的混乱;第三每个单一的成员在系统中的逻辑结构是一致的;最后，网络中的每个Agent都遵守该网络定义的语义和规则［4］。

在此基础上，由于编队作战条例和客观条件约束限制，编队武器节点在获得来袭目标数据之后，必须进行目标协商，防止资源冲突或无效分配的出现［5］。

假设我方编队成员数目为M，每个成员所拥有的武器节点为Nl(1≤l≤M)，来袭目标有A个。

1)武器节点的目标协商。

判别来袭目标的航路捷径经过哪些武器节点的协同杀伤区，即确定由参加拦截该目标的武器节点。目标j相对于武器节点i的航路捷径为pij，当pij小于最大航路捷径要求maxpi时，即pij≤maxpi，该武器节点能够拦截目标。

确定武器节点自身的工作状态，是否进入正常备战状态，该状态包括:武器节点是否损坏，能否正常工作，是否有可用导弹等，经过检查后，通过网络通报给其他武器节点，确定能够参与拦截的武器节点。为武器节点工作状态［6］:

其中:1≤m≤M;1≤i≤Nl;1≤j≤A。

2)目标分配的约束条件。

对于给出的可能分配方案来说，需要满足一定的约束条件，才能符合最终的要求。

首先，要求一个目标只能被一个防空单位分配，禁止重复分配，即

其中:1≤m≤M;1≤i≤Ni;1≤j≤A。

其次，计算后给出的武器节点数量不得超过实际给定的最大武器节点数量，Nr≤Nmax。

2.2 模型建立过程

在目标综合毁伤矩阵建立之前，应依照威胁评估算法和我方单位对目标毁伤能力数据，给出威胁度值和协同毁伤概率值，并得到综合毁伤值，具体步骤如下。

1)由指控网中的指控节点通过威胁评估算法得出来袭目标的威胁度值，进行排序，归一化处理，统一量纲，得到来袭目标威胁度值(T1，T2，T3，…，TA)。

2)各指控节点根据自身武器装备性能，结合编队其他成员的技、战术指标，给出m舰武器节点i对目标j的联合毁伤概率，即:

式中:Rg为获取目标信息的能力;Mc为通信能力;Rs为搜索跟踪目标的能力;Mt为传输信息的能力;Pd为导弹的自导能力;Pf为导弹捕捉目标的概率;Ph为导弹对目标的杀伤概率。从而给出我方武器节点在协同制导下对目标的联合毁伤概率矩阵，1≤m≤M，1≤i≤Ni，1≤j≤A。

4)经过广播模块把Em发送给其他Agent，同时通过接收模块得到其他Agent的综合毁伤矩阵，综合可以得到编队综合毁伤矩阵E:

5)建立目标函数［7］:

6)运用最优分配算法——异步并行蚂蚁策略算法进行目标分配，求取目标函数最大的目标分配方式。

在实时作战中，如果发生某成员被毁伤或数据链路被破坏而导致的该成员综合毁伤矩阵无法发送至网络时，算法可以不受影响地继续通过其他成员的综合毁伤矩阵进行多目标分配，也就是说，综合毁伤矩阵的引入使该算法能够实时进行多目标分配，即使编队中只剩几个甚至一个成员时，也能继续使用和运行，大大满足了实战的需要。

由于某个目标的威胁度或者防空武器对其毁伤效果明显过小将会导致其综合毁伤值过小，但是程序对这个明显不会被选择的值，仍然会分配时间对其进行判断和计算，这样就造成了一定的时间浪费，这里将引入一个“综合毁伤阈值”的概念，首先判断某综合毁伤值是否有被选择的资格，不超过综合毁伤阈值的综合毁伤值将不被蚁群中的蚂蚁搜索。即:

而这个阈值初始化由最初的专家系统给出，随着打击后的目标杀伤效果评估来对阈值进行修正。

3 异步并行蚂蚁系统

并行蚂蚁系统，又称并行蚂蚁，是以著名的主人/奴隶方法为基础的，适用于当前流行的MIMD体系结构处理器并行蚁群策略之一［8］。这个方法的主要思路在于:对于每一个指控节点，分配一个或多个奴隶蚂蚁，每个蚂蚁从自身作战成员出发，开始构建解决方案，而主人处理器由某一个处理能力最强的指控节点担任，对于全局的信息素进行更新和输出，以确定整个系统在一个实时的同步更新的状态下工作，而局部信息素的更新由奴隶所在的指控节点完成，这是区别同步并行蚂蚁的地方，同步并行蚂蚁中由主处理器完成局部和全局的信息素更新，通信量较大。另外，主人处理器也可以同时担当被分配到奴隶蚂蚁的工作，以保证更高效地执行。

不妨设开始时有蚂蚁k在城市r上，它选择下一个城市的准则是:

这里，q是一个在0和1之间的统一的随机数，q0是一个参数，而蚂蚁已经访问过的城市将禁止再次访问，蚂蚁还可以访问的城市形成一个集合Gk(r)，这里的参数β选择为正数，这样路径越长越受欢迎。上式表示下一个城市的选择受到当前路径上的信息量和距离影响，距离越长，信息量越多，越优先选择该城市，下式表示通过概率选择下一个城市。局部更新规则为

式中:ρ是局部信息素衰减系数且0＜ρ＜1;τ0是各条边上的初始信息素量。而当所有蚂蚁完成一次行程后，在构成当前最长路径上的信息素更新为

式中:γ是全局信息素衰减系数0＜γ＜1;Δτ(r，s)是增加的信息素，确定如下:

式中:X是常数，不妨设为100;L是当前最长路径长度。

一个蚂蚁对应一个处理器，每个普通处理器都对自己的信息素矩阵留有副本保存。

编写异步并行蚂蚁策略的主人处理器和奴隶处理器的异步处理程序流程图见图2。

图2 主人处理器和奴隶处理器异步处理程序流程Fig.2 Asynchronization processes of main processor and common processor

4 实例分析

在某时刻，由传感器网信息采集和数据融合之后，通过威胁评估，这里运用灰色区间评估确定10枚来袭反舰导弹的威胁度值如表1所示。

表1 来袭目标威胁度值表(1×10－4)Table 1 The table of coming targets'threaten level

当武器控制系统根据雷达发送的目标精确数据，实时完成航路捷径、杀伤区及发射区边界、目标到达发射区近界和远界的时间［9］等射击诸元参数的计算后［10］，利用协同制导下防空导弹毁伤概率模型确定来袭目标在杀伤区内的遭遇点的毁伤概率，得到各武器节点对来袭目标的毁伤概率矩阵，如表2所示(为方便计算和表达明确，假设编队中的武器节点数为3个，每个武器节点的火力通道数均为4个)。

表2 我武器节点对来袭目标的毁伤概率值Table 2 The damage probability of our weapon points to coming targets

最后，通过综合计算得到编队对该批目标的综合毁伤矩阵(这里综合毁伤阈值设为0.045)，可得:

其中:矩阵 e11=0.04104;e24=0.04383;e35=0.04064。小于综合毁伤效能阈值，根据步骤直接赋0值。

经过Matlab编程实现和仿真运算，图3为采用综合毁伤阈值的并行蚂蚁策略(实线)，不采用综合毁伤阈值的并行蚂蚁策略(点虚线)以及普通蚁群算法(虚线)的3种方式的效果显示图，结果表明该改进算法最好，并且随着问题的规模越大，对比效果将越明显。最后得出的分配结果为武器节点A的目标是{X4，X6，X9}武器节点 B 的目标是{X2，X5，X7，X8}，武器节点 C的目标是{X1，X3，X10}，最大综合毁伤效能值 E=1.71761。

图3 结果仿真图Fig.3 The simulation of the result

5 结束语

本文在舰艇编队的武器目标分配中引入了综合毁伤阈值和综合毁伤矩阵的概念，在算法上结合蚁群算法和并行网络的特点，使用异步的方式，更适合于目前海上编队网络中心战的作战系统，本文对该方法进行了详细的分析，并给出了简要的例子予以验证。不过，在舰艇编队多目标分配中需要考虑更多的影响因素，比如防空导弹协同杀伤区和发射区，网络的数据传输能力和编队内担任“蚂蚁”的处理器个数等，这些因素对分配的影响，在今后的工作中，将进一步研究［11］。

［1］王剑飞，武文军，范月强，等.“网络中心战”中的美国海军C4ISR系统效能评估［J］.情报指挥控制系统和仿真技术，2005，27(5):15-20.

［2］张元瀚，李相民，代进进.舰艇编队反导辅助决策系统分析［C］//火力与指挥控制2009年学术年会论文集，厦门，2009:171-173.

［3］杨轶.多Agent技术及蚂蚁算法在制造网格系统中的应用［D］.武汉:武汉理工大学，2006.

［4］王祖典.网络中心制导技术［J］.电光与控制，2005，12(4):38-39，43.

［5］PATTERSON W.A unified framework for solving multiagent target assignment problem［D］.Air Force Institute of Technology，2008.

［6］黄树彩，李为民.超视距多目标攻击排序问题中的蚁群算法［J］.人工智能及识别技术，2008，34(10):158-160.

［7］李士勇.蚁群算法及其应用［M］.哈尔滨:哈尔滨工业大学出版社，2004.

［8］程红熙，任忠斌，何清华.马尔可夫决策过程在动态WTA 中的应用［J］.电光与控制，2005，12(1):83-85.

［9］舒培贵，娄寿春.防空导弹混编火力群目标分配工程算法研究［J］.现代防御技术，2008，36(5):66-69.

［10］王步云，姜伟，徐建志.基于多Agent的编队导弹攻击火力分配的优化研究［J］.指挥控制与仿真，2008，30(2):45-48.

［11］徐长江，王乐群.基于不确定多属性决策的空中目标威胁评估技术［J］.现代防御技术，2009，37(2):5-9.