编队防空火力分配建模及其优化方法研究

阮旻智，李庆民，刘天华

(海军工程大学 兵器工程系，湖北 武汉430033)

在编队协同防空作战中，如何合理地部署我方兵力来迎接空中威胁目标，并确切的指出由哪些武器装备对哪些目标采取什么样的方式进行攻击，以协调各作战单元作战行为的协调指挥过程［1］，称为火力分配(WTA).在未来高技术条件下的局部海战中，水面舰艇编队将会面临十分严峻的空中威胁。防空WTA 是编队防空指挥决策中最为关键的问题之一，其目的是在现有防空武器装备的基础上，选择最优的WTA 方案，使武器系统对空中来袭的多批目标分配给它们射击最有利的火力单元［2］，最大限度地发挥编队防空武器的整体作战效能。

防空WTA 问题实质上是一种整数型非线性组合优化决策问题，属于N-P 难问题［2］。作为指控系统的一项重要辅助决策功能，WTA 与作战原则、策略、方案等因素密切相关，存在大量的变量和参量。因此，除了要建立合理的WTA 模型之外，还要在解算的方法上进行探讨，尝试一些新算法。如Kuttar提出的序列算法，分支定界法，但这些算法收敛速度很慢;Castanon 提出用非线性网络流程求准最优解的算法，但结果会产生较大的误差;Wacholker 提出了一种神经网络的解法，此方法有时得不到稳定解。近来，人们又引进各种启发式算法来解决WTA 问题，如采用蚁群算法［3］，基于神经网络的TSP 算法［4］，改进的遗传算法及采用粒子群算法与遗传算法相结合来解决WTA 问题［5］。本文引入一种新的进化计算方法——人工免疫算法，依据该算法原理，构造了有效表达编队防空作战效能的特种抗体数据结构染色体矩阵编码方案和亲和度算法，给出用于产生高效防空WTA 结果的克隆免疫算子。克隆免疫算子能够保证抗体群的多样性，通过特殊的编码方式保证得到全局最优方案，并利用二次免疫机理提高编队防空WTA 的反应速度。

1 编队防空WTA 模型

1.1 问题的描述及分配原则

编队防空WTA 是一个动态分配过程。假设一个编队通过其侦察预警系统发现有m 批空中威胁目标，编队内有k 类不同型号的防空武器系统，每种型号的防空武器的资源数为Ci，i =1，2，…，k，在武器系统的有效作用区域和时间内，每种型号的防空武器的可用资源为CTi，第i 种防空武器对第j 批目标分配一个火力单元后对目标的毁伤概率为Pij，j=1，2，…，m.

编队防空WTA 及获利原则:

1)防空武器系统只有在其有效的作用区域和作用时间内才能对目标进行WTA，否则不进行分配。

2)每种防空武器可以对多批目标进行火力单元分配，每批目标可以同时被分配多个火力单元。

3)每种型号防空武器在作战时间内分配的火力单元总数不能超过该型号武器的资源数。

4)在面对多批次空中目标时，为获得最大作战效能，每种武器应对其有效的作用区域和作用时间内的可用资源完全分配。

1.2 防空WTA 数学模型

设有m 批空中威胁目标，编队内有k 类防空武器系统，每种型号的防空武器的资源数为Ci，在有效作用区域和时间内，每种型号的防空武器的可用资源为CTi，第i 种防空武器对第j 批目标分配一个火力单元后对目标的毁伤概率为Pij.则WTA 决策矩阵为

式中:xij，i=1，2，…，k，j =1，2，…，m 为第i 种类型防空武器对第j 批目标分配的火力单元数。

对目标进行武器火力单元分配，要求分配后使整个编队防空武器系统的作战效能最大，即使毁伤目标的数学期望达到最大值，则建立的WTA 模型为

式中:ωj，j=1，2，…，m 为第j 个目标的威胁系数;Ci为第i 个武器系统的资源数;CTi为第i 个武器系统在其有效作用区域和时间内的可用资源数。

2 人工免疫系统原理

人工免疫系统(AIS)是一个信息处理技术与计算方法相结合的智能系统。它借鉴、利用生物免疫系统的性质和机制发展用于解决工程和科学问题的技术方法。生物免疫系统是一个高度进化的生物系统，它旨在区分外部有害抗原和自身组织，从而清除病原并保持有机体的稳定［6］，人们从生物免疫系统的运行机制中获取灵感，开发面向应用的免疫系统计算模型——AIS.克隆选择原理(CS)最先由Jerne提出，克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗传变异分化为多样性效应细胞(如抗体细胞)和记忆细胞，克隆选择对应着一个亲合度成熟的过程，即对抗原亲合度较低的个体在克隆选择机制的作用下，经历增殖复制和变异操作后，其亲合度逐步提高而“成熟”的过程。

编队防空WTA 过程与AIS［9］有很多相似之处，表1给出了二者之间的对比。

DeCastro 基于免疫系统的克隆选择理论提出了克隆选择算法，核心是比例复制和比例变异算子，这是一种模拟免疫系统的学习过程的进化算法。其算法步骤为［6］:

表1 AIS 与编队防空WTA 比较Tab.1 Comparison between immune system and fleet anti-aircraft firepower allocation

1)产生一个初始群体;

2)基于亲和度度量确定群体中的n 个最佳个体;

3)对群体中的这n 个最佳个体进行克隆(复制)，并使其发生变异，从而形成下一代群体;

4)从群体中选出一些最好个体加入记忆集合，并用记忆集合中的一些个体替换群体中的一些个体;

5)将群体中的d 个低亲和度的抗体予以替换，从而维持抗体的多样性;

6)返回步骤2)循环计算，直到满足结束条件。

与其它算法(如遗传算法、蚁群算法、进化策略等)相比，免疫算法有如下的特点［7-8］:

1)它在记忆单元基础上运行，确保了快速收敛于全局最优解;

2)它有计算亲和性的程序，反映了真实的免疫系统的多样性;

3)它通过促进或抑制抗体的产生，体现了免疫反应的自我调节功能。

上述特点使得免疫算法有不同于其它算法的附加优化步骤:计算亲和性、计算期望值、构造记忆单元。因此免疫算法有以下优点:

1)保存了多样性:因为免疫算法的特点即多样性和自我调节功能，所以使用这一方法能够获得许多优化问题的最优解;

2)记忆训练应用免疫算法，通过重复的优化过程，能够很快的得到最优解。因为对于曾经出现过的抗原，免疫算法产生相应抗体的速度比以前更快。虽然遗传算法和免疫算法一样，都是模拟自然进化过程的优化模型，但是在记忆训练和不同抗体的产生方面，两者有本质区别。

3 基于人工免疫的防空WTA 模型

3.1 有关定义

抗原:将空中来袭目标的态势表述为抗原。

抗体:将编队防空武器的一种WTA 方案表述为抗体。

亲和力函数:将目标毁伤概率的数学期望作为本模型中的亲和力函数。

3.2 抗体编码

抗体编码采用一种等价形式表示，具体到本文的优化模型，则按照每个火力单元分配给不同批次目标进行编码，抗体编码矩阵的维数不再由目标批数决定，而由编队防空武器系统在作战过程中可用于分配的火力单元总数确定。

解空间的等价形式为第i 个武器系统的第j 个火力单元分配的目标为Mij，即待优化的参数为Mij=(M11，M12，…，M1k，M21，…，M2k，…，Mm1，Mm2，…，Mmk)，通过这种方法可以将分配模型中的约束条件直接从抗体编码中体现出来。

编码说明，码位长度由编队内防空武器系统在作战过程中可分配的资源总数决定;若第i 个武器系统的可用资源数为ki，则该武器系统所占的码位长度为ki;如第2 个武器系统的可用资源数5，则该武器系统在抗体编码中所占的码位长度为5;抗体编码中的数字表示该码位的火力单元所分配的目标代号。

3.3 亲和度计算

本文抗原与抗体之间亲和力，可以直接采用目标函数表示，即抗原与抗体之间亲和力

3.4 新抗体的产生

新的抗体的产生通常与遗传算法差别不大，主要包括选择算子、交叉算子和变异算子。对群体中的抗体按照各自的生存力进行选择，选择下来的抗体再按一定的概率进行随机配对交叉，然后以一定的变异概率进行变异产生下一代的新抗体。

以本文算法编码为例，所用算子变换如下:

交叉算子:

交叉前

1 3 4 1 2 5 5 4 3 … … …2 3 5 1 2 2 3 3 4 2 4 … … …1 5

交叉后

2 3 3 1 2 5 5 4 3 … … …2 3 5 1 2 1 3 4 4 2 4 … … …1 5

变异算子:

变异前

5 1 2 1 3 4 4 2 4 … … …1 5

变异后

3 2 3 1 3 4 4 2 4 … … …1 5

3.5 算法实现步骤

1)初始化抗体群Ab，随机产生N 个抗体，生成初始群体;

2)对Ab 中的抗体按照亲和力由大至小按降序排列，从中选取前M 个抗体按照克隆免疫算子进行克隆，得到规模为Nc 的抗体群Abc;

3)对抗体群Abc 中的抗体按照亲和力由大至小按降序排列，进行删除操作，从中选取前E 个抗体，得到规模为Ne 的抗体群Abe;

4)合并抗体群Ab 和Abe，选出亲和力最高且互不相同的N 个抗体组成抗体群Abp;

5)随机产生规模为Nr 的抗体群Abr，选出亲和力最高的Ns 个抗体组成抗体群Abs;

6)用Abs 代替Abe 中亲和力最低的Ns 个抗体，形成规模为N 的抗体群Ab;

7)判断是否满足终止条件，不满足则转至步骤2)继续执行，满足则结束计算。

在限定条件比较多的编队防空WTA 中，步骤6)显得非常重要。它成为产生抗体多样性的主要原因，因为过多的限制条件使得交叉和变异较难产生合理的抗体。

4 仿真计算及结果分析

4.1 作战想定及仿真结果

假设有10 批空中威胁目标从不同的方位袭来，编队内共有7 种不同类型的防空武器，每种武器在规定的作战时间内可用资源数分别为C=［4，5，4，5，4，5，4］，武器系统对每批目标的毁伤概率以及目标的威胁系数矩阵，如表2所示。

表2 武器系统毁伤概率与目标威胁系数Tab.2 Weapon's damage probability and targets'threat degree

首先确定WTA 优化参数，初始化抗体群为100个，克隆免疫算子的交叉概率为0.5，变异概率为0.5，算法迭代次数200.

仿真计算所得到的最优WTA 矩阵为

对防空武器1:分别将其4 个火力单元分配给第1，2，6，9 批目标;对防空武器2:分配2 个火力单元给第1，3 批目标，分配1 个火力单元给第10 批目标;…;对防空武器7:分别将其4 个火力单元分配给第1，2，5，8 批目标。综合分配后，整个编队防空武器系统对空中来袭目标的作战效能为0.991 8.

4.2 与其它启发式算法的性能比较

通过仿真，得到免疫算法、遗传算法、粒子群算法每代抗体群的最大亲和度，如图1所示。免疫算法相比遗传算法和基本粒子群算法而言，能够获得更好的全局最优解，算法的稳定性较强。

图1 作战想定情况下3 种算法亲和度演变Fig.1 Evolution of three algorithms'affinity

免疫算法在获得较好的全局最优解和较强的稳定性的同时，是以较长的运算时间为代价的。就免疫算法和粒子群算法比较而言，粒子群算法在整个优化迭代过程中只需跟踪粒子的当前最优位置Pbest和粒子群的全局最优位置Pgbest，通过粒子临近速度匹配、消除不必要的变量、考虑多为搜索以及根据距离的加速，使得粒子群算法的实现过程简单，算法的收敛速度快等优点，但其不足是在迭代过程中易陷入局部最优解。而免疫算法需要对抗原进行识别、产生初始抗体、计算抗体亲和度、产生记忆细胞池，然后通过促进和抑制新抗体的产生来省城亲和度较高的抗体群，在该算法的每次迭代过程中都要重复上述过程，直到达到算法的终止条件为止。因此，免疫算法的算法结构和实现过程相对较为复杂，计算时间相对较长，但其最为显著的优点是能够获得更好的全局最优解，算法的稳定性较强。

5 方案库构建

虽然上述方法能根据各种作战态势给出最优的编队防空WTA 方案，但是，寻求最优解的过程是需要一定时间的。为了提高对作战态势的反应速度，可利用AIS 的二次反应机理，免疫系统中二次反应的关键是免疫库的构建。在编队防空WTA 中，实现二次快速反应的关键即为方案库的构建。可以构造各种空中威胁目标的战场态势，求解出各种态势下的火力最优分配方案，存入到预案库中。当空中目标入侵检测系统和态势判决系统工作后，即可确定战场态势，绝大部分情况下，可以在预案库中直接查找到最优WTA 预案。对一些特殊的情况，再采用解算的方法。基于人工免疫算法的编队防空WTA 系统构成，如图2所示。

图2 基于人工免疫的编队防空火力分配系统Fig.2 Fleet anti-air firepower allocation system based on artificial immune

6 结语

本文将克隆免疫算法应用到编队防空WTA 优化求解中，根据实际情况构造了有效表达编队防空作战效能的特种抗体数据结构编码方案和亲和度算法，给出用于产生高效防空WTA 结果的克隆免疫算子，并在传统免疫算法基础上对算法做了一定改进，通过实例分析验证了该算法的正确性和有效性。将改进的免疫算法与其它进化算法进行了比较，在多数情况下，改进的免疫算法相比现有进化算法而言，能够得到更优的运算结果。针对AIS 的二次免疫机理，构建编队防空WTA 方案库，将可进一步加快防空WTA 系统的解算速度。

与其它一些进化算法相比，免疫算法也有其不足之处。因此，针对现有一些进化算法的优点与不足，可以将免疫算法与其他算法有机结合，相互之间取长补短，以提高解决实际问题的能力。这将是进化算法在今后被重点研究的方向之一。

References)

［1］王红军，时进发，迟忠先.编队抗导调度的免疫算法与仿真［J］.系统仿真学报，2008，20(4):858 -861.WANG Hong-jun，SHI Jin-fa，CHI Zhong-xian.Immune algorithm and simulation of fleet anti-missile job-shop schedule［J］.Journal of System Simulation，2008，20(4):858 -861.(in Chinese)

［2］蔡怀平，陈英武.武器—目标分配(WAT)问题研究进展［J］.火力与指挥控制，2006，31(12):11 -15.CAI Huai-ping，CHEN Ying-wu.The development of the research on weapon-target(WTA)problem［J］.Fire Control and Command Control，2006，31(12):11 -15.(in Chinese)

［3］高尚.武器—目标分配的蚁群算法［J］.计算机工程与应用，2003，39(3):78 -79.GAO Shang.Ant colony algorithm for weapon-target assignment problem［J］.Computer Engineering and Application，2003，39(3):78 -79.(in Chinese)

［4］王小艺，刘载文，候朝桢，等.防空武器多目标优化分配建模与决策［J］.兵工学报，2007，28(2):228 -231.WANG Xiao-yi，LIU Zai-wen，HOU Chao-zhen，et al.Modeling and decision-making of multi-target optimization assignment for aerial defence weapon［J］.Acta Armamentarii，2007，28(2):228 -231.(in Chinese)

［5］王小艺，侯朝桢，原菊梅，等.防空火力分配建模及优化方法研究［J］.控制与决策，2006，21(8):913 -917.WANG Xiao-yi，HOU Chao-zhen，YUAN Ju-mei，et al.Modeling and optimization method on antiaircraft firepower allocation［J］.Control and Decision，2006，21(8):913 -917.(in Chinese)

［6］Timmis J，Neal M.A resource limited artificial immune system for data analysis［J］.Knowledge-Based Systems，2001，14:21 -130.

［7］Lee Z J，Lee W L.A hybrid search algorithm of ant colony optimization and genetic algorithm applied to weapon-target assignment problems［J］.Computer Science，2003，2690，(9):278 -285.

［8］Lee Z J，Su S F，Lee C Y，Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Trans on Systems，Man and Cybernetics，Part B，2003，33(1):113 -121.