基于OpenMP 的并行蚁群算法求解协同空战火力分配

陈 昊

(中国航空工业集团公司 洛阳电光设备研究所，河南 洛阳471009)

0 引 言

空战火力分配是研究现代空战中有关火力运用和作战决策的一个重要课题。空战火力分配问题是指在超视距多机协同多目标攻击空战环境中，我方空战指挥控制系统根据敌方多架飞机的威胁权重值，及时有效地将我方机载空空导弹分配到导弹攻击区内的多个目标，以最大限度地消除敌方目标的威胁。目前，已经证明空战火力分配问题属于完全非确定多项式(non－deterministic polynomia，NP)问题［1］，传统的求解方法通常具有指数阶的时间复杂度，当我机数目、导弹数目和目标数目都很大时，将发生组合爆炸，进而在有限决策时间内难以求得问题最优解，满足不了空战决策实时性要求。

蚁群算法具有并行性计算、正反馈机制、启发式搜索、求解精度高、算法操作简单等特点，自2002 年以来，已被很多学者用来求解火力分配问题［2～6］，并取得很好的成果。然而，当分配问题规模较大时，传统的蚁群算法难以在有效时间内求得问题的最优解。为了提高算法在求解大规模火力分配问题时的时效性，以满足指挥决策实时性的要求，学者们开始将研究内容转向蚁群算法的并行优化［7～9］。

传统的协同空战火力分配大都采用一次性分配的静态火力分配模型。而在空战实际中，整个分配过程是动态的，敌我双方多个编队根据空战战术，执行多个阶段协同作战。目前，动态火力分配尚未得到实质上的解决，根据文献［10］中的“动静结合”的观点，动态火力分配中的某一特定阶段，可以作为静态分配为题进行处理。基于此思想，针对空战中第一阶段，建立了一种带毁伤概率门限的火力分配模型，在求得对目标机群最大毁伤效果的同时尽量节约导弹武器资源，以应对下一阶段的火力分配，并借鉴粗粒度并行策略，采用OpenMP 并行优化技术对蚁群系统(ant colony system，ACS)中最耗时的循环迭代、循环赋值和禁忌表更新等部分进行并行化处理，并通过各种规模的火力分配问题的仿真实验验证火力分配模型和算法的有效性。

1 协同空战火力分配模型的建立

假设在某次空战中的第一阶段，我方机群R 由M 架我机组成，分别记为 Rr(r =1，2，…，M);敌方机群 B 由 N 架敌机组成，分别记为Bj(j =1，2，…，N)。载机 Rr所挂载的空空导弹数目为dr，且导弹类型不完全一致。机群R 所挂载的总导弹数为Z，且Z ＞N。Z 枚空空导弹构成武器集合W，记为 W=(i，i=1，2，…，Z)。当 W 中的第 r 枚导弹刚好是Rr所挂载的dr枚导弹中的第i 枚导弹时，r 与l 的对应关系如式(2)所示

设机群R 所分配的导弹对目标Bj的联合毁伤概率为pj，则有

其中，pij为导弹i 对目标j 的毁伤概率，与导弹性能和具体空战态势等有关。xij为决策变量，若分配导弹i 攻击目标 j，则 xij=1;否则，xrj=0。

在以往的静态火力分配数学模型中，目标j 必须被攻击，且至少分配一枚导弹进行攻击，具体分配数目由指控系统根据实际情况给出。本文采取优先选择毁伤概率高的导弹优先攻击价值系数高的目标的“双优分配原则”，针对特定目标j 设定一个毁伤概率门限值ptj，只有当分配给目标j的联合毁伤概率高于此门限值时才分配导弹，以避免对目标j 毁伤概率很低的导弹被分配，造成不必要的武器浪费。从而可将某些将被用来攻击当前阶段处于导弹攻击区以外，或者当前时刻导弹难以命中毁伤的目标的导弹，放到下一阶段里再分配，节约了本阶段的武器弹药。因此，在本文中，目标j 根据具体情况可不分配导弹攻击。

目标j 的价值系数用vj表示。多机协同的空战主要是为了争夺制空权的空战，因此，假设参战双方机种均为战斗机，此时目标价值系数可用目标对我机的威胁系数thjr衡量。由此建立一种带有毁伤概率门限的火力分配数学模型为

其中，pij为目标j 的毁伤概率门限。式(5)表示在一个火力分配方案中，如果目标j 的联合毁伤概率pj小于ptj，则认为是无效分配，式(7)表示一枚导弹只能攻击一个目标。该数学模型的意义在于，在满足毁伤概率门限的前提下，将目标相对我机的威胁、我机导弹对目标的毁伤概率以及导弹武器资源的消耗3 个因素综合考虑，通过比较各种导弹对目标的组合对火力分配目标函数值的贡献来进行导弹的优化分配，从而达到在获得最大火力分配效能的同时，节省武器资源，且能保证威胁度大的目标被优先攻击。

2 并行蚁群算法求解火力分配问题

蚁群算法本质上是一种并行算法，具有很高的并行性［8］。现实中的蚂蚁是并行地搜寻食物，并逐渐形成一条从蚁穴到食物的最短路径，蚁群算法继承了真实蚂蚁的这种并行机制。蚁群算法在求解问题的每一次迭代过程中，每只蚂蚁根据当前路径上的信息素量和问题的启发函数，彼此独立地构建问题的解，蚂蚁之间通过信息素进行间接通信。蚁群算法所具有的这种天然的并行性为算法的并行实现提供了良好的基础。因此，把串行蚁群算法改造为并行蚁群算法是可行的。

论文提出的并行蚁群系统(parallel ant colony system，PACS)的思想可以描述为:利用PC 计算机多核的优势和粗粒度的并行策略，将串行蚁群系统(serial ant colony system，SACS)算法中的整个蚁群分为多个子蚁群(子蚁群个数等于计算机核的个数)，每个子蚁群蚂蚁个数相等。将每个子蚁群分配给一个线程处理，每个子蚁群分别进行解的搜索，根据并行策略在适当时机进行子蚁群之间的通信。每个子蚁群根据从其他子蚁群获取的有关信息，对本子蚁群的信息素矩阵和禁忌表进行修改。当达到算法的终止条件时，由其中1 个线程收集各子蚁群的最优解，比较各个最优解值的大小，从而得出算法最优解，输出所找到的全局最优解。

2.1 火力分配方案

设武器集合为W={i|i=1，2，…，Z}，目标集合为 T ={j|j=1，2，…，N}。本文选择把武器分配给目标的分配策略，一种火力分配方案就是从T 到W 的一个二元关系。在蚁群算法中，一个解就是一种火力分配方案，解成分就是序偶〈j，i〉。对于目标j，从可选武器集(尚未被分配的武器所构成的集合)中按序偶选择规则选出一件武器i 分配给该目标。

2.2 序偶选择规则

q 是一个在区间［0，1］上呈均匀分布的随机数，q0(0≤q0≤1)是算法参数。当q≤q0时，蚂蚁k 按先验知识选择序偶〈j，i〉

其中，τji(t)为序偶〈j，i〉在 t 时刻对应的信息素;α 表征信息素在选择概率上的相对重要性;ηji为序偶〈j，i〉对应的启发式函数值，本文中ηji=thjrpij;β 表征启发式函数值在选择概率上的相对重要性;allowed(t)是当前允许分配的武器集合。

2.3 信息素更新规则

信息素更新规则分为局部信息素更新规则和全局信息素更新规则。局部信息素更新在蚂蚁k 选择一个序偶〈j，i〉后进行。局部更新的目的是适当降低蚂蚁所经过的序偶的信息素强度，以避免搜索过度集中而导致搜索停止。局部更新规则表示如下

其中，τ0为信息素初始值;ρ(0 ＜ ρ ＜ 1)为局部更新规则的信息素挥发因子。全局信息素更新在一次迭代完成后进行

其中，ζ(0 ＜ζ ＜1)为全局更新规则的信息素挥发因子，Y－best 是到目前为止的全局最优解，f－best 是到目前为止的全局最优解的目标函数值。

2.4 算法的并行实现

OpenMP 是用于共享内存并行系统的多线程程序设计的一种指导性注释。OpenMP 提供了对并行算法的高层的抽象描述，程序员通过在源代码中加入专用的pragma 来指明自己的意图，由此编译器可以自动将程序进行并行化，并在必要之处加入同步互斥和通信。对于很多循环来说，都可以在其开始之前插入一条编译指导，使其以多线程执行。开发人员只需要认真考虑哪些循环应该以多线程方式执行和如何重构算法以便在多核处理器上获得更好的性能等问题［11］。当使用OpenMP 将那些最耗时的循环以多线程执行的时候，OpenMP 的能力就体现出来。

并行蚁群并行策略分为细粒度策略和粗粒度策略。粗粒度策略是指将每一个子蚁群分配到一个处理器上让其并行，并在适当时机彼此之间相互通信评出最优解。研究表明:粗粒度的并行蚁群更有潜力［12］。串行蚁群算法运算量最大的部分是循环迭代、循环赋值阶段，且这些计算大部分都集中在for 循环中，便于利用OpenMP 的编译指导语句实现程序的并行化。

采用OpenMP 和C + +语言来实现并行蚁群算法，仿真计算机具有4 核处理器，基于OpenMP 的并行蚁群算法的实现步骤如下:

1)Part A 程序初始化部分

a.初始化蚁群算法各项参数，输入目标威胁矩阵、导弹毁伤概率矩阵等;

b.设置每条路径上的初始信息素强度τ0;

c.根据计算机核的个数设置线程数为S(S =4)，用于将原来的一个蚁群分为4 个子蚁群在多核机上并行求解;

d.各个子蚁群中的每只蚂蚁被随机地放置在武器节点;

e.初始化信息素矩阵τij(t)和初始时刻每条边上的信息素增量;

f.初始化用于存放最优解的Y－best 矩阵。

2)Part B 循环部分

进入并行区，用#pragma parallel omp for 语句对循环迭代和循环赋值部分进行并行化。

a.将原始蚁群分为 4 个子蚁群(分别记为 s1，s2，s3和s4)，再分别交给4 个处理器处理使其在多核机上并行求解;

b.各子蚁群中每只蚂蚁根据式(8)和式(9)选择下一个将访问的序偶〈j，i〉。然后将该蚂蚁移动到新的序偶，并把序偶〈j，i〉添加到该蚂蚁的禁忌表中。每只蚂蚁在构建自己可行解后，按照式(10)进行信息素的局部更新;

c.在一次循环中各个蚁群中的每只蚂蚁完成一次周游，它们的禁忌表被填满，分别计算出4 个子蚁群中的每只蚂蚁求解出的目标函数值，比较它们的大小，得出本次循环最优目标函数值和最优解;

d.经过n 次循环后，所有蚂蚁均完成可行解的构建并通过通信比较得出当前最优解后，由式(11)和式(12)进行信息素的全局更新;

e.将所有蚂蚁的禁忌表清空;一次循环结束，进入下次循环;

f.上述过程不断循环重复，最优解序偶上的信息素得到加强，直到达到循环结束条件，求出最优解和最优目标函数值，输出程序结果。

3 算例仿真验证与分析

算例1 为了验证火力分配模型的有效性，假设我方4 架战斗机与敌方6 架战斗机在某空域进行超视距条件下的空战，我方每架战斗机均携带型号不完全相同的4 枚空空导弹。我方机群采用协同空战战术对进入联合攻击区内的6 个目标进行攻击。目标j 对我机r 的威胁值thjr由空战态势评估系统给出，目标威胁函数值矩阵如表1 所示。我机16 枚空空导弹对6 个目标的毁伤概率矩阵如表2 所示。设定目标j 的毁伤概率门限ptj均为0.80。目标j 可最多分配2 枚导弹同时进行攻击。最终最优火力分配方案如表3所示，表中“0”表示导弹未对该目标进行火力分配。图1给出了PACS 最优目标函数值收敛曲线。

表1 目标威胁函数值矩阵Tab 1 Target threat function value matrix

表2 导弹对目标的毁伤概率矩阵Tab 2 Damage probability matrix of missile against target

表3 最优火力分配方案Tab 3 The best weapon-target assignment solution

由表3 数据看出:采用本文提出的带毁伤概率门限的火力分配模型进行火力分配，并未一次性将16 枚导弹全部分配给6 个目标，而仅仅分配7 枚导弹便能完成空战任务，为我机编队节约了9 枚导弹。而按照以往的静态火力分配模型，本阶段中所有导弹都得分配给相应目标，这很不符合空战实际情况。

图1 PACS 收敛曲线Fig 1 PACS convergence curve

算例2 为检验基于OpenMP 的并行蚁群算法求解协同空战火力分配的时效性，分别采用提出的并行蚁群算法和串行ACS 对各种规模的火力分配问题各进行20 次仿真实验，每次均迭代300 代。实验所用 PC 计算机性能为Pentium(R)32 bit Four－Core PC，4G RAM，算法参数设置如下 α =1，β =2，m=20，ρ=0.25，ζ =0.20，q0=0.90，τ0=5。实验结果如表4 所示，图2 给出了规模分别为M =50，N =75，Z=200 和 M =100，N =150，Z =400 时，PACS 和 SACS最优目标函数值收敛曲线。

表4 SACS 和PACS 算法性能比较Tab 4 Performance comparison of SACS and PACS algorithms

图2 不同规模下的PACS 和SACS 收敛曲线Fig 2 PACS and SACS convergence curves under different scale

由图2 和表4 结果可看出:当问题规模很小时，并行算法的求解时间比串行算法求解时间略长，这是因为用OpenMP 编写的程序在运行时会产生线程创建和销毁的开销。当问题规模很小时，这个开销将大于程序本身的执行时间。随着问题规模的增加，程序本身的执行时间越来越长，程序并行占的开销在整个程序运行时间中所占的比重越来越小。当问题规模很大时，使用OpenMP 将那些最耗时的循环以多线程执行时，并行蚁群算法的能力就体现出来。

4 结 论

本文针对空战中第一阶段，提出了一种带毁伤概率门限的协同空战火力分配模型，对传统静态火力分配模型进行了改进，在求得对目标机群最大毁伤效果的同时尽量节约导弹武器资源，以应对下一阶段的火力分配。在此基础上，根据粗粒度的并行策略，采用OpenMP 并行优化技术，对蚁群系统中最耗时的循环迭代、循环赋值和禁忌表更新等部分进行并行化处理，仿真结果表明:本文提出的火力分配模型符合空战实际，基于OpenMP 并行优化的蚁群能够合理、快速的给出空战目标分配方案。

［1］ Lloyd S P，Witsenhausen H S.Weapons allocation is NP－complete［C］∥Proceedings of the IEEE Summer Simulation Conference，Reno，Vevada，1986:1054 － 1058.

［2］ 罗德林，段海滨，吴顺祥，等.基于启发式蚁群算法的协同多目标攻击空战决策研究［J］.航空学报，2006，23(6):1166 －1170.

［3］ 陈中起，张 斌，任 波.随机优化蚁群算法在空战决策中的应用［J］.电光与控制，2008，15(6):54 －57.

［4］ 刘建新，宋以胜，卢厚清，等.改进蚁群算法求解火力分配优化［J］.数学的实践与认识，2009，39(20):92 －99.

［5］ 杜天军，陈光禹，刘占辰.多目标攻击空战决策WBG 模型及其蚁群算法［J］.系统工程与电子技术，2005，27(5):861 －865.

［6］ 高 坚，佟明安.超视距多目标攻击排序及火力分配建模与解算［J］.火力与指挥控制，2004，29(3):9 －13.

［7］ Lee Zhejung，Su Shunfeng，Lee Chouyuan.Efficiently solving general weapon－target assignment problem by genetic algorithms with greed eugenics［J］.IEEE Journal on Systems，Man，and Cybernetics-part B:Cybernetics，2003，33(1):119 － 120.

［8］ 汪鹏飞.并行蚁群算法及其应用研究［D］.成都:西南交通大学，2008.

［9］ Chen Song，He Jianhua，Liu Huaiyuan.Realization and simulation of parallel ant colony algorithm to solve WTA problem［C］∥2012 International Conference on Systems and Informatics，ICSAI 2012，2012:2458 －2461.

［10］ 刘传波，邱志明，吴 玲，等.动态武器目标分配问题的研究现状与展望［J］.电光与控制，2010，17(11):43 －48.

［11］刘向娇，吴素萍，刘佳梅.基于OPENMP 求解旅行商问题的并行蚁群算法［J］.微电子学与计算机，2011，28(7):149 －155.

［12］ Ellabib I，Calamai P，Basir O.Exchange strategies for multiple ant colony system［J］.Information Sciences:An International Journal，2007，177(5):1248 － 1264.