一种基于模拟退火的编队区域防空目标分配方法*

吴建刚

(海军驻武汉三江航天集团军代室 武汉 430040)



一种基于模拟退火的编队区域防空目标分配方法*

吴建刚

(海军驻武汉三江航天集团军代室 武汉 430040)

目标分配是编队对空防御指挥决策中的一个重要环节。通过对舰艇编队区域防空目标分配影响因素的分析,建立编队区域防空目标分配问题的数学模型,然后基于混合优化算法思想,将启发式搜索机制与模拟退火算法结合起来,提出一种改进的贪心模拟退火算法,给出了算法求解流程。仿真结果表明该算法是有效的和可行的,能够给出具有较好的优化分配方案。

目标分配; 编队防空; 模拟退火

Class Number TP301.6

1 引言

在网络中心战环境下,海上战场态势复杂多变,舰艇编队面临日益严重的空中威胁,如何将编队内多个平台上的多种武器有效地协同作战是一个极其复杂的问题,也是作战指挥决策中迫切需要解决的现实问题。编队区域防空作战目标分配主要研究在一定约束条件下,按照给定的目标函数对舰空导弹射击方案进行优化决策,确立舰空导弹武器资源的最优配置,从而最大限度地发挥编队防空体系的作战效能[1]。

目标分配属于NP问题,其求解方法有整数规划、神经网络、回溯算法、非线性网络流法等,这些方法存在指数计算的复杂度,当武器及目标数目增加时很难求解[2]。模拟退火算法[3]作为一种用于求解大规模组合优化问题通用而有效的全局优化解法,寻优时间并不令人满意。为此,本文在综合分析编队区域防空目标分配影响因素的基础上,建立编队区域防空作战目标分配模型,通过引入启发式规则提出一种改进的贪心模拟退火算法,以期提高算法的求解效率,优化目标分配决策。

2 舰艇编队区域防空作战目标分配模型

2.1 目标分配的原则

传统的目标分配是在单平台下进行的,在编队作战环境下,编队内有多个作战平台且各自载有多型舰空导弹,需要综合考虑目标的威胁程度大小、舰空导弹对目标的杀伤概率、舰空导弹的杀伤区以及开始目标分配的时机等因素,制定科学合理的目标分配方案,以便更好地配置编队内传感器、舰空导弹等资源,高效完成整个编队的防空任务。目标分配在编队区域防空作战中是实时动态完成的,优选方案时,应先选择未遭拦截目标数最少的方案,然后再选择拦截效果最大的方案。此外,目标分配应遵循如下原则:

1) 对于单个火力通道,进行一次射击后,如果目标被击毁,分配给该目标的火力通道立即转向其它目标,目标分配进入下一个阶段,则使用空闲的舰空导弹对可以拦截的未分配目标进行拦截;如果目标未被击毁,则火力通道继续射击直到该目标被击毁或飞离火力杀伤区。

2) 当有新目标进入拦截区域时,如果有空闲武器,则进行目标分配,否则等待武器空闲。

3) 目标分配优先级:上级指定的目标、重点目标、威胁度大的目标、射击有利的目标、先到达的目标。目标分配方案可以人工干预,以达到整体毁伤效果最优。

2.2 目标函数的确立

假设我方舰艇编队有m个舰空导弹火力通道,敌方有n个空中来袭目标,目标的威胁度分别为wj(j=1,2,…,n),第i个火力通道对第j批目标的命中概率为Pij(i=1,2,…,m;j=1,2,…,n)。各舰空导弹火力单元可以重复使用,重复使用次数由武器备弹量决定,每个火力通道只能拦截一批目标,每批目标最多可以分配Sj(j=1,2,…,n)个火力通道。若分配第i个火力通道拦截了第j批目标则用Xij=1表示,否则Xij=0。考虑拦截之后目标总的期望剩余威胁值最小作为目标函数,建立如下目标分配数学模型:

(1)

但是式(1)还不能作为最佳分配方案的充分条件,还需要考虑未遭到拦截的目标数最少[4],即:

(2)

式中:Uj表示第j批目标是否遭到拦击的指示数。如果第j批目标未遭到拦截,则Uj=1,否则Uj=0。而Uj的定义如下:

(3)

动态目标分配考虑分配过程中的动态随机因素,如上一阶段的打击效果或者新目标的出现等,需要重新产生新的目标分配方案。因此,目标分配问题还应考虑到空间约束、时间约束和资源约束等条件[5]。

1) 空间约束条件。航路捷径、目标速度和高度是决定不同高度层目标的三个重要参数,只有满足条件时火力通道才能被分配给目标。

(4)

其中,dij表示目标j相对于火力通道i的航路捷径,火力通道i能够拦截目标的最大航路捷径为dimax;目标的速度为Vj,火力通道i能够拦截目标的最大速度为Vimax;目标的高度为Hj,火力通道i能够拦截目标的最大、最小高度为Himax,Himin。

2) 时间约束条件。目标进入武器发射区的远界且未离开发射区近界这段时间之内,武器对目标开火才能奏效。假设第j批目标到达第i个火力通道发射区远界、近界的时间分别为taij和tbij,Δti为火力通道i的响应时间,则火力通道i拦截目标j的发射时间tcij必须满足的条件为

taij+Δti≤tcij≤tbij+Δti

(5)

3) 资源约束条件。火力通道空闲、无故障以及有可用导弹,才能发生导弹,火力通道状态Qi必须满足如下条件:

(6)

式(6)中:1为准备好状态,0为未准备好状态。

3 基于改进贪心模拟退火算法的目标分配

对目标分配问题的求解,本文采用改进的贪心模拟退火算法,算法借助贪心机制将启发式规则引入到模拟退火算法产生新解的过程中,采用对模拟退火算法中产生的新解进行多次贪心局部寻优过程,以保证每个产生的新解都是“优良解”,从而提高最优解的质量。同时,通过合理选择冷却进度表中的初始温度、终止温度、衰减系数、马尔可夫链长和结束准则,提高算法的求解效率。

3.1 算法实现步骤

根据贪心模拟退火算法的特点,需要进行以下步骤[6]:

1) 初始解的选择

初始解是算法搜索寻优的出发点,由目标分配问题的约束可知,初始解是每一行仅有一个元素1,每一列最多有S个元素1,其余都为0的n×m矩阵。模拟退火算法的最终优化解与初始解的选取无关,但为了提高解空间的搜索效率,借助贪心机制选取,对于有n个目标的目标分配,按目标威胁程度由大到小排列,当火力通道数量小于目标数量时(m≤n),威胁值大的目标优先分配给可用的火力通道;当火力通道数量大于目标数量时(m>n),可以用多个火力通道打击目标。

2) 目标函数

根据目标分配模型的目标函数,可以将其转化为求解能量值E:

(7)

3) 新解的产生和接受准则

新解的产生采用以下策略,选择解中被分配多于一个火力通道数量的目标,将解中任意一个该目标变为1～n中的其它目标。同时,对于产生的新解需要进行约束条件检查,使每个目标被分配的火力通道数量满足分配模型中的最大分配数量。算法采用Metropolis接受准则,即

(8)

其中,t为控制参数;Δf为新解和当前解的目标函数差。当Δf<0时,接受新解;Δf≥0时,进行如下判断:产生一个(0～1)之间的随机变量rand,若r≥rand,则接受新解,否则不接受。

4) 冷却进度表参数的选取

冷却进度表是一组控制此算法进程的参数,包括初始温度、终止温度、衰减系数、Markov链的长度和停止准则,它是影响模拟退火算法试验性能的重要因素,其合理选取是算法应用的关键。仿真中,初始温度T对仿真结果几乎没有影响,终止温度Tstop最好固定在0.01以下,衰减系数tr最好固定在0.9以上,Markov链一般取20～40。采用一个常用的衰减函数tk+1=tk×tr。

对上述算法作如下改进[7]:

1) 不同温度下迭代长度规则

当温度很高时,每个状态接受的频率基本相同,且几乎所有状态都被接受,此时同一温度迭代步数可相对较少。当温度降低时,更多的状态被拒绝,此时迭代步数应尽可能多。给定接受次数U和迭代步长上限Mmax,当在给定温度迭代次数等于Mmax时,在这一温度不再迭代,温度下降;否则,一直迭代至Mmax。

2) 最优解保留策略

保留每个温度的最优解,对下一温度解的搜索自上一温度的最好解而非上一温度的最后解开始。这样,更利于加快搜索速度,找到最优解。

3.2 算法执行流程

算法执行流程如下:

图1 改进的贪心模拟退火算法流程

Step 1:确定可以分配的火力通道数量m,再根据目标威胁评估的结果,确定武器需要打击的目标数量n;

Step 2:把m个武器对n个目标的单发命中概率从大到小进行排列,放在一个二维数组Allocation[m][n]中,确定算法的参数S、T、Tstop、tr、Mmax;

Step 3:计算解的能量值;

Step 4:若迭代次数大于Mmax,转Step 9;

Step 5:利用选择策略产生新解,对新解执行贪心算法;

Step 6:计算新解的能量值,执行Metropolis接受准则;

Step 7:记录接受次数和当前最好解;

Step 8:迭代次数增1,转Step 4;

Step 9:执行T=T*tr,迭代次数置1,转Step 3;

Step 10:输出最优解及其能量值,算法结束。

最优解即是舰艇编队区域防空目标分配的结果,算法流程如图1所示。

4 仿真分析

假设我舰艇编队有6个火力通道,敌方共有8个空中来袭目标,目标的威胁度wj(j=1,2,…,8)、我方舰空导弹对目标的毁伤概率Pij(i=1,2,…,6;j=1,2,…,8)分别如表1、表2所示。

表1 目标的威胁度

表2 我方舰空导弹对目标的毁伤概率

设初始温度T0=1.0,终止温度Tstop=0.01,温度下降系数Tr=1.0,马尔科夫链长Mmax=40,每个目标最多分配的火力通道数量S=2。仿真结果如表3所示(1表示该火力通道分配给目标,0表示该火力通道不分配给此目标),表3即为最佳目标分配方案。

为验证算法计算时间的优越性,通过增加火力通道数量和目标数量,采用遗传算法、神经网络算法与本文所提算法分别求解,各算法的求解计算时间如表4所示。

表4 不同算法计算时间的对比

通过计算结果可以看出本文提出的改进贪心模拟退火算法对遗传算法和神经网络算法在计算时间上有很大优势,能够在较短的时间内获得目标分配的最优解。

5 结语

目标分配是网络化条件下作战指挥决策中的重要研究内容,针对舰艇编队防空作战中目标分配问题的特点和需求,在建立编队防空作战目标分配模型的基础上,利用模拟退火算法并结合贪心机制,提出了一种基于改进的贪心模拟退火目标分配算法,通过算例验证了该算法的优越性。防空作战具有实时性和动态性特征,作战过程中的典型动态事件包括目标未被摧毁、新目标出现、某个火力单元受损或性能严重下降等动态随机因素影响下的目标分配问题需要下一步重点研究。

[1] 姚跃亭,赵建军,尹波波,等.舰艇编队防空目标分配优化算法研究[J].计算机与数字工程,2011,39(1):31-34.

[2] 张毅,周绍磊,孙保良.一种求解武器—目标分配问题的新方法[J].海军航空工程学院学报,2005,20(5):530-532.

[3] 吴平,梁青.武器—目标分配问题的模拟退火算法[J].计算机工程与应用,2006(4):87-90.

[4] 姜会霞,黄考利,侯继业,等.混编防空导弹火力群目标分配模型仿真[J].军械工程学院学报,2006,18(1):46-49.

[5] 蔡怀平,陈英武,邢立宁.SVNTS算法的动态武器目标分配问题研究[J].计算机工程与应用,2006(31):7-10.

[6] 骆文辉,刘少伟,周建美,等.目标分配问题的模拟退火算法[J].上海航天,2008(1):61-64.

[7] 李洪瑞,苗艳.击毁概率最大的目标武器分配的模拟退火算法[C]//中国造船工程学会电子技术学术委员会指控与计算机专业委员会,2000年学术交流会,2000.

[8] 李丹,王巨海,陈振雷.基于神经网络TSP算法的防空作战火力分配[J].火力与指挥控制,2006,31(4):42-45.

[9] 罗红英,刘进忙.遗传算法在目标优化分配中的应用[J].电光与控制,2008,15(3):18-20.

[10] 赵晨光,耿奎,李为民,等.防空导弹武器系统目标分配的多种算法[J].现代防御技术,2001,29(3):7-9.

Target Allocation Algorithm for Naval Fleet Air Defense Based on Simulated Annealing

WU Jiangang

(Military Representative Office of Navy in Sanjiang Aerospace Corp, Wuhan 430040)

Target allocation is an important part of command and decision-making in formation air defense. The mathematical model of target allocation is established through the analysis of targets assigned influencing factors for area air defense of surface warship formation. Based on the ideology of hybrid optimization algorithm, an improved greedy simulated annealing algorithm is put forward by introducing the heuristic search mechanism, and the algorithm process is given. The simulation results show that the algorithm is effective and feasible which can give an optimal allocation scheme.

target assignment, formation air defense, simulated annealing

2014年10月8日,

2014年11月29日

吴建刚,男,硕士,工程师,研究方向:导弹装备质量监管。

TP301.6

10.3969/j.issn1672-9730.2015.04.009