基于Memetic算法的舰艇编队防空兵力配置

李大鹏， 谭乐祖， 杨明军， 杨根源

(1.海军航空工程学院指挥系，山东 烟台 264001; 2.中国人民解放军91991部队，浙江舟山 316000;3.海军信息化专家委员会，北京 100073)

0 引言

舰艇编队对抗已经成为了现代海战中的主要对抗形式，而随着海战攻防对抗技术的发展，海上防空作战领域不断出现各种先进的反舰导弹，已经成为了水面舰艇编队的最大威胁。舰艇编队防空兵力配置是防空作战决策的基础，直接关系着防空作战效能。根据作战对象、交战环境、敌我双方的作战态势等，充分发挥各自优势，补充不足，将舰艇组合成具有多层次、全方位、大范围的海上防空作战系统，成为各国海军专家、学者们的一个研究热点［1－2］。本文根据舰艇编队防空作战的具体战术特点，设计了基于火力杀伤能力的舰艇编队兵力配置模型，然后基于Memetic算法设计了优化算法。

1 基于有限元网格划分的防区数学描述

根据对舰艇编队对空防御作战空间的分析，为了合理地对舰艇编队防空兵力进行优化配置，本文采用有限元网格划分的方法对编队防空作战空间进行离散化处理。根据目前舰艇编队的兵力配置现状，区域型防空舰艇一般都是以编队指挥舰为中心按一定的前出距离，在整个威胁扇面角上以环形或扇形的方式进行配置。舰艇编队对空防御空间可以认为是以编队指挥舰为中心，以ψ为威胁扇面角的扇形区域内。根据防区的几何形状，采用极坐标形式，使用等极角的射线和等长的极径对扇形防区进行分割［3］，分割结果如图1所示。

图1 网格划分示意图Fig.1 Sketch map of area grids

根据划分的结果可以将网格的交叉点作为舰艇兵力的候选配置点，其坐标表示为 pij(ρij，θij)，其中 ρij表示编队前出舰艇的距离，θij表示前出的方位角度。根据图1所示，距离编队指挥舰越近的地方，网格数量越多，即可配置的候选位置越多，这符合编队防空舰艇兵力配置的实际情况。

2 基于火力杀伤能力的舰艇兵力配置模型

假设舰艇编队有s艘舰艇担任对空防御任务，分别为 1，2，…，k，…，s，可用 Ts来表示舰艇的集合;在极坐标体系下，编队舰艇配置区域在极角(0，θmax)、极径(0，ρmax)范围内，编队主威胁轴方向为极角θmax/2;根据防区网格划分，可以将防空区域划分为m×n的网格，其中将极角划分成 m 份，分别为 1，2，…，i，…，m，可用Tm表示极角划分的集合，将极径划分成n份，分别为 1，2，…，j，…，n，可用 Tn表示极径的集合。

为建立模型需要，首先对涉及的主要变量作以下说明。

2.1 约束矩阵(δij)m×n

在舰艇编队的实际配置过程中，由于存在各方面条件的限制，并不是每个区域都适合部署舰艇兵力。根据所划分的网格，本文定义约束系数δij，它表示第i行第j列网格是否适合部署舰艇兵力，即

据此，可以建立一个与网格行列数相同的约束矩阵(δij)m×n，矩阵中的每一个元素对应表示网格中相应位置的约束情况。

2.2 配置决策矩阵(xijk)m×n×s

为了更加直观地刻画整个舰艇作战区域防空舰艇兵力配置情况，本文以矩阵的形式表述舰艇兵力的配置方案。根据网格划分方法，对应第i行第j列网格的配置情况用变量xijk表示，其中k表示舰艇编号。xijk表示在第i行第j列网格是否配置第k艘舰艇，即

据此，可建立一个 m×n×s的配置决策矩阵(xijk)m×n×s，通过此矩阵可以直观地显示舰艇兵力配置的方案。

根据配置决策矩阵的物理含义，必须满足如下约束条件

即对于某一艘舰艇k而言，在所有的网格中只能配置一次;对于每个可配置舰艇的网格(i，j)，最多只能配置一艘舰艇。

2.3 单舰火力杀伤能力矩阵(pijk(θt))m×n×s

设第k艘舰艇位于网格(i，j)点，其舰载防空导弹的射程为Dkmax，对目标的杀伤概率为pk。根据所建模型，可以求得其对来袭方向极角为θt的目标拦截次数为lk(θt)，则舰艇对该目标的杀伤能力可以表示为

据此，可以建立一个m×n×s的单舰火力杀伤能力矩阵(pijk(θt))m×n×s。

2.4 编队火力杀伤能力系数p'(θt)

为描述舰艇编队承担对空防御作战任务的全部舰艇整体上对目标可能造成的毁伤程度，根据所得的单舰火力杀伤能力矩阵，引入编队火力杀伤能力系数p'(θt)。p'(θt)表示舰艇编队对来袭方向角为θt的目标的火力杀伤能力，可以表示为

2.5 火力杀伤要求约束矩阵(c(θt))m×1

在舰艇编队的主要防空作战区域内，舰艇兵力的配置必须保证舰载火力单元对任一可能来袭方向的目标具备一定的火力杀伤能力，以免目标在未受舰载火力抗击的情况下就突防成功。特别是在舰艇编队舰艇兵力有限的情况下，为追求理想的配置效果，必须优先满足对舰艇编队主要防空作战区域的火力杀伤要求μ(θt)。显然，必须满足以下关系

对于各方向的火力杀伤能力标准μ(θt)，可以根据具体作战情况由指挥员确定。

2.6 拦截距离贡献系数λ

引入拦截距离贡献系数λ，表示对目标不同的拦截距离具有不同的贡献程度，以体现防空作战的舰艇梯次配置的原则，即［3］

其中，λ∈(0，1)，d表示编队舰艇兵力对任一来袭方向目标的平均拦截距离大小，λ的大小可以结合指挥员的经验制定。

结合上述变量的定义，本文以舰艇编队所有参与配置的舰艇兵力对所有可能来袭方向目标的总火力杀伤能力为配置目标。优化配置问题的目标函数可以表示为

约束条件为

3 基于Memetic法的兵力配置决策模型的求解

文化基因算法(Memetic Algorithm)是建立在模拟文化进化基础上的优化算法，其实质就是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体［4－5］。该算法结合了进化算法和邻域搜索算法。交叉和变异后的每个个体都要通过邻域搜索过程加以改善，从而使进化不再盲目，克服了进化算法的随机性，加快了搜索速度，还可有效防止算法的早熟收敛。

3.1 适应度函数的构建

适应度函数是对解质量评估的标准，它对整个算法的质量有重要的影响作用，一般情况下，可以直接将目标函数选择为适应度函数。对于约束优化问题，首先必须将约束最优化转化为无约束优化问题［6－7］。本文基于惩罚函数的方式将其转化为无约束优化问题，再以无约束优化问题的目标函数作为适应度函数来引导搜索。

式中，γ1，γ2就是惩罚函数，惩罚策略主要问题是如何设计惩罚函数，从而有效引导搜索到解空间的最优区域。

根据这种惩罚策略，可以定义适应度函数为

3.2 全局搜索操作

1)初始化。

根据待配置的舰艇数量s，将每一艘舰艇作为一个粒子，即粒子总数为s。第k个粒子(舰艇)的当前位置可以用xk=(x1k，x2k)表示，将xk代入适应度函数即可计算出相应的适应值Fk=F(xk)，第k个粒子(舰艇)的速度用vk=(v1k，v2k)表示，它决定粒子的飞行方向和距离;pk=(p1k，p2k)表示第k个粒子(舰艇)曾经到达过的最优位置，称为个体最优位置，其对应的适应度值记为pbestk;同理，pg=(p1g，p2g)表示整个种群迄今搜索到的最优位置，其对应的粒子编号为g，最大适应度值为gbest=max{pbestk}。

根据所划分的m×n网格防空区域，除去那些在实际情况下不适合配置舰艇的网格，可以均匀分布的方式随机产生初始位置 xk=(x1k，x2k);vk=(v1k，v2k)，通常也限定在一定范围内，同样可以均匀分布的方式在［－vmax，vmax］随机产生。

2)评价粒子的适应度。

对于每个粒子，根据式(11)的适应度函数，可计算每个粒子的适应度值大小:首先，将其适应度值与所经历的最优位置的适应值pbestk进行比较，若较大，则将其作为当前的个体最优位置，更新 pg=(p1g，p2g)与pbestk;其次，将其适应度值与全局最优适应度值gbest进行比较，若较大，则将其作为当前全局最优位置，并更新相应的 pg=(p1g，p2g)、gbest=max{pbestk}。

3)更新粒子的速度和位置。

在更新完上述的个体最优位置和全局最优位置后，对粒子的速度和位置进行更新，更新公式如下［8］

惯性权值ω类似于模拟退火中的温度值，代表粒子原先的速度在多大程度上得到保留，取较大值时，全局收敛能力较强，取较小值时，局部收敛能力较强;c1、c2取(0，2)之间的随机数，记忆因子c1调节粒子飞向个体最优威胁方向的步长，记忆因子c2调节粒子向全局最优位置飞行的步长;每维粒子的速度都会被限制在一个最大速度vmax，如果某一维更新后的速度超过用户设定的vmax，那么这一维的速度就被限定为vmax，即

4)执行交叉操作。

根据粒子群优化算法的特性，它会出现早熟收敛现象，粒子也可能会出现“聚集”现象。针对这些问题，为提高运算的精度，借鉴遗传算法中的杂交概念，在每次迭代中，根据杂交概率选取指定数量的粒子放入杂交池内，池中的粒子随机两两杂交，产生同样数目的子代粒子C(child)，并用子代粒子替换父代粒子P(parent)。子代位置由父代位置进行算术交叉得到，具体操作为

其中，p为(0，1)之间的随机数。

子代的速度可表示为

根据上述杂交后产生的子代及其位置与速度公式，对原先的父代进行替换，再次按照原先的步骤进行下次循环迭代。

5)终止条件判断。

根据初始设定的迭代进化代数Nmax，判断是否达到终止条件，若进化代数小于Nmax，则继续进行循环迭代;若进化代数等于或大于Nmax，则停止迭代，进化结束。

3.3 局部搜索操作

本文采用基于模拟退火算法的加权法对执行交叉操作之后的粒子进行局部搜索，搜索主要步骤如下［9－10］。

1)初始化:设置初始温度Tbegin、终止温度Tend、冷却度ξ、最大迭代次数Wmax。

2)本文用两个档案IA和EA来管理优化过程中产生的非劣解，其中IA存放局部搜索得到的非劣解，EA存放进化过程中的所有非劣解。

3)根据交叉操作产生的种群Pop，计算个体的目标值，将Pop中的非劣解放入EA。

4)对于每一粒子x∈Pop，设置为空集，将放入档案IA中，并计算其适应度值。

5)迭代次数W=0，T=Tbegin;构造x的可行邻域解x'。

7)令W=W+1，如果 W＜Wmax，则转到步骤5);否则，令 T= ξT。

8)如果T＞Tend，则令 W=0，并转到步骤5);否则，终止循环，并且返回x，并用档案IA更新档案EA。

4 仿真结果分析

假定舰艇编队防空作战兵力配置区域为半径100 n mile，角度120°的扇形区域。舰艇装备及其舰载武器的性能如表1所示。

表1 舰艇装备及其性能参数Table 1 Warship equipment and parameters

根据舰艇编队配置区域的大小，取极角3°、极径1 n mile对区域进行网格划分，形成25行100列的网格。舰艇按 1、2、3、…、10 进行编号。

设粒子群规模为30，粒子最大速度Vmax=2.5，其惯性权值表示为 ω =0.3+0.5*(1－i/Nmax)，记忆因子c1=2.0，记忆因子 c2=1.8，最大迭代次数 Nmax=1000，惩罚系数γ1=200，惩罚系数γ2=2;模拟退火初始温度Tbegin=0.1、终止温度 Tend=0.01、冷却度 ξ=0.96、最大迭代次数Wmax=50(注:算法中速度、温度为抽象的量，为计算方便不带单位)。

根据Memetic法的设计步骤，对舰艇编队兵力配置问题进行求解，配置效果如图2所示。

图2 舰艇兵力配置示意图Fig.2 Sketch map of warship disposition

为了比较基于Memetic法的算法效率，即主要比较算法是否可以在有限时间内提供更优的结果。本文仍然采用上述的基本参数作为基本粒子群算法参数，选择算法运行时间为横轴，取前300 s的结果进行比较，结果如图3所示。根据仿真结果可知采用Memetic法确实能够有效提高算法效率，以适应战场瞬息万变的态势。

图3 算法效率的比较Fig.3 Comparison of arithmetic efficiency

5 结束语

本文对舰艇编队防空作战兵力配置问题进行了研究，对编队配置区域进行有限元网格化，建立了基于火力杀伤能力的舰艇编队防空兵力配置模型，针对所建立的模型，设计了一种基于Memetic算法的优化求解方法，仿真显示，该方法能够有效对模型进行求解，提高了求解效率，下一步的主要工作是研究防空任务时变条件下的兵力配置问题。

［1］ 王玮，王军，由大德.基于遗传算法的海上舰艇编队配置方法研究［J］.控制与决策，2003，18(6):736－739.

［2］ 谭安胜，邱延鹏，汪德虎.新型驱护舰编队防空队形配置［J］.火力与指挥控制，2003，28(6):5－9.

［3］ 陈杰，陈晨，张娟.基于Memetic算法的要地防空优化部署方法［J］.自动化学报，2010，36(2):242－248.

［4］ GONG M G，JIAO L C，LIU F.Memetic computation based on regulation between neural and immune systems:The framework and a case study［J］.Science China Information Sciences，2010，53(8):1519－1527.

［5］ NGUYEN Q H，ONG Y S，KRASNOGOR N.A study on the design issues of memetic algorithm［J］.Proceedings of IEEE Congress on Evolutionary Computation，Washington USA:IEEE，2007:2390－2397.

［6］ 魏静萱.单目标和多目标优化问题的进化算法［D］.西安:西安电子科技大学，2009.

［7］ 魏静萱，王宇平.基于新模型的多目标Memetic算法及收敛性分析［J］.控制理论与应用，2008，25(6):389－392.

［8］ 郭秀萍，杨根科，吴智铭.一种混合自适应多目标Memetic算法［J］.控制与决策，2006，21(11):1234－1238.

［9］ 郭秀萍，杨根科，吴智铭.一种基于模拟退火的多目标Memetic算法［J］.信息与控制，2007，36(1):29－33.

［10］ 寇晓丽，刘三阳.基于模拟退火的粒子群算法求解约束优化问题［J］.吉林大学学报:工学版，2007，37(1):136－140.