改进蛙跳算法求解武器目标分配问题

喻世轶,张 亮,周学广

(1.海军工程大学,湖北 武汉 430033;2.中国人民解放军91642部队,海南 三亚 572000)

武器目标分配(Weapon-target Assignment,WTA)是指依据作战目的、可使用武器的技战术性能、目标威胁等级等约束条件,结合战场态势信息,合理快速地分配武器资源,确定最佳武器目标分配方案,以实现最佳的协同作战效果或最佳的作战目的。武器-目标分配问题作为作战指挥决策过程中的一个关键环节,一直以来都受到研究人员的高度关注。如何快速高效地给出武器目标分配方案,对于缩短指挥员的决策时间,提升指挥决策效能具有重要意义。

武器-目标分配问题属于NP完全问题,求解WTA问题的计算量较大,随着决策变量的维度增加，计算量呈指数增长,因此,目前，国内外的学者通常采用智能优化算法进行求解,常用的有遗传算法[1]、粒子群算法[2]、匈牙利算法[3]、人工鱼群算法[4]、差分进化算法[5]等。其中,遗传算法因具有较强的全局搜索能力被广泛应用,并且针对其易早熟，搜索效率低,受参数影响较大的弱点,提出的改进算法也很多[6-10]。本文针对遗传算法在求解武器目标分配时计算时间较长的问题,利用蛙跳算法的快速计算性能[11],借鉴基于非支配等级和拥挤度因子的精英选择策略[12],改善初始种群的多样性和均匀度,提高了算法搜索最优解的质量,同时，计算时间相对遗传算法较短。

1 受空间约束的武器目标分配模型

1.1 问题描述及分配原则

假设我水面舰艇编队通过预警侦察体系发现有n批来袭空中目标,水面舰艇有m种不同型号的防空武器可供使用,在作战过程中的某一时刻,每类武器系统可使用的武器资源为ci(i=1,2,…，m),第i种防空武器对第j类目标的命中概率为pij(i=1,2,…，m,j=1,2,…，n)。

水面舰艇编队防空作战的武器目标分配原则如下:

1)每类武器可以对多个目标进行分配,同时每个目标可以被分配多个武器系统;

2)每种型号的防空武器在作战时间内分配的武器资源不能超过该防空武器系统的武器资源总数;

3)为确保不遗漏任何目标,每个目标至少被分配一个型号的武器;

4)根据防空武器使用的一般原则——避免资源浪费,每一类型的防空武器对同一个目标分配的最大武器资源数为3,且每个目标被分配的武器资源总数也不超过3;

5)由于每类防空武器都有射击条件,最简单的就是空间约束,因此,不能保证每类防空武器都能对每个来袭目标进行拦截;

6)分配的目标是为了获取最大作战效能,即毁伤目标的数学期望最大,同时消耗武器的成本最小。

1.2 武器目标分配模型

假设编队内有m种不同型号的防空武器,每种防空武器的资源总数为ci(i=1,2,…，m),每种防空武器的成本为ei(i=1,2,…，m),来袭空中目标为n批,目标的威胁度系数为dj(j=1,2,…，n),第i种防空武器对第j类目标的毁伤概率为pij(i=1,2,…，m,j=1,2,…，n),则武器目标分配的决策方案为

(1)

其中,xij(i=1,2,…，m,j=1,2,…，n)表示第i类武器对第j类目标分配的武器资源数,当xij>0时，表示第i类武器对第j类目标分配xij个武器资源,反之表示不分配武器资源。

另外,根据分配原则5),不是每类武器都能对所有目标进行拦截,假设分配禁忌决策为

(2)

其中,yij(i=1,2,…，m,j=1,2,…，n)表示为第i类武器对第j类目标是否能分配武器的判断变量,当yij=1时表示第i类武器对第j类目标可分配武器,反之则表示不能分配,用来作为生成初始决策种群的约束条件。

根据分配原则6)可建立防空武器目标分配模型如式(3)所示:

(3)

式(3)是一个多目标优化问题,为利于算法求解,通常将多目标转化为单目标进行求解,因此,本文将实现最大的防空作战效果和最小的武器消耗成本两个目标变为一个目标,即求解单位成本内取得的最大防空作战效果,则该模型变为

(4)

2 蛙跳算法原理

蛙跳算法是2003年提出的一种仿生学智能优化算法[13],适用于组合优化问题,参数少，计算速度快,具有全局寻优的特点。其主要思想:假设湿地有一群青蛙,可通过在湿地中不同的石头上跳跃来寻找食物。每只青蛙代表组合优化问题的一个解,且有自己的文化,个体之间通过文化来交换信息。初始时,将青蛙分成若干个子群,在子群中每个个体之间通过文化相互影响,随着子群的不断进化,实现局部搜索。当子群进化到一定阶段后,各子群之间再进行文化信息交换,实现全局搜索。重复上述过程,直到满足停止条件。

其算法模型可描述为:首先随机产生规模为N(维数为l)的初始种群P={X1,X2,…,XN},其中Xi=[xi1,xi2,…xil]表示问题的一个解。再根据目标函数计算每个解对应的适应度值,并进行降序排序。然后将初始种群分为m个子群,每个子群中有n个青蛙,即N=m×n,具体的分配方法:总群中第1只青蛙分配给第1个子群,第2只分配给第2个子群,直到第m只分配给第m个子群,第m+1只青蛙分配给第1个子群,依次类推,直到全部分配完毕。将每个子群中青蛙的最优适应度值和最差适应度值个体记为Xb、Xw,其相应的适应度值记为vb、vw,然后，在每个子群中按照式(4)进行局部搜索:

(5)

3 基于非支配等级和拥挤度因子优选的改进蛙跳算法求解武器目标分配问题

本文针对传统蛙跳算法(SFLA)全局寻优质量不高的问题进行改进,在兼顾计算时间的前提下,通过基于非支配等级和拥挤度因子的精英选择策略改进初始种群的生成,提高初始种群的多样性和均匀性,以期在有限的迭代次数中获得相对较优的最优解。

3.1 解的编码

在基于改进的蛙跳算法求解武器目标分配问题中,需要对决策变量进行变换,将多维矩阵决策变量变为一维矩阵,即X=[x11,x12,…，x1n,x21,x22,…，x2n,…,xm1,xm2,…,xmn],有利于蛙跳算法的更新计算。

3.2 初始解的生成

蛙跳算法(SFLA)的初始解通常是随机生成的,其多样性和均匀性不可控,借鉴文献[13]的思想,对初始解进行预处理,假设算法中参与迭代计算的种群规模为N,则先随机生成数倍于N的种群规模,设为mul*N。

首先，根据帕累托支配关系给初始种群进行非支配关系排序,并给每个解赋予一个非支配关系等级,假设某个个体不被其他任何个体支配,则该个体的非支配等级为1,将种群中所有非支配等级为1的个体挑选出来,剩下的个体再进行一次非支配关系排序,挑选出来的非支配个体等级为2,依次类推,直到所有的个体都被赋予非支配等级,其流程图如图1所示。

图1 非支配等级排序

图2 拥挤度因子算法流程

最后,按照精英选择策略从mul*N个个体中挑选N个作为参与迭代计算的初始种群,具体算法思想是:根据个体的两个属性值——非支配等级pareto_rank和拥挤度因子flog_crowi,所有个体按照非支配等级由低到高的顺序进行排序,从支配等级低的个体开始,依次将非支配等级对应的全体变量放入初始种群Pt,直到当某一非支配等级pareto_ranki对应的个体大小超出了种群N为止,然后对非支配等级为pareto_ranki的个体集合Ci按照拥挤度因子由大到小的顺序排序,拥挤度因子大的优先选入Pt,直到Pt的个体数量达到N为止。通过此种方法生成的初始种群相对随机生成种群具有较好的多样性和均匀度。

3.3 更新策略

搜索策略采用传统蛙跳算法(SFLA)的更新策略,基于非支配等级和拥挤度因子的精英选择策略改进蛙跳算法求解武器目标分配问题的算法流程如图3所示。

图3 基于改进蛙跳算法的武器目标分配流程图

4 仿真计算及结果分析

假设有5批从不同方位来袭的目标,水面舰艇编队有4型防空武器系统,每种武器拥有的资源总数和毁伤概率如表1所示(其中，有相同型号的武器系统和相同型号的来袭目标)。

表1 武器系统基本参数

每个目标的威胁等级系数分别为{0.204 9,0.225 6,0.181 1,0.196 9,0.190 7},4型武器系统的价值分别为{1.2,1.0,1.2,0.6}。每型武器受射界的限制,其分配禁忌决策如表2所示,该决策可作为生成初始决策种群的约束条件。

表2 武器分配禁忌表

在内存8 G,处理器为Intel(R)Core(TM)i5-5700 CPU @3.40GHz,64位操作系统的计算机上通过Matlab对算法进行实现,取参数为初始种群个数50,子群数5,子群个体10,子群迭代次数5,总群迭代次数50,计算的最优目标值为0.144 8,对应的最优决策变量为

其最优适应度值变化曲线如图4所示。

本文将该算法与传统蛙跳算法、遗传算法进行多次运算比对分析,每种算法都运行10次,运行结果如表3所示。

由表3可以看出,改进蛙跳算法相对传统蛙跳算法其寻优时间变长,但最优适应度值明显变优,且时间的增加幅度不大;改进蛙跳算法相对传统遗传算法的最优适应度值较小,但其寻优时间相对遗传算法要减少很多。而水面舰艇编队防空作战时,对时效性要求较高,改进后的蛙跳算法在时间增加相对较少的前提下,使最优度值有了较大的改善,是解决编队防空作战时武器目标分配问题的一个不错的选择。

5 结束语

本文针对空间受限的水面舰艇编队防空武器目标分配问题,提出一种基于拥挤度因子和非支配排序的改进蛙跳算法,大大改善了初始种群的多样性和均匀度,相对传统蛙跳算法提高了最优解的质量,相对传统遗传算法大大减少了寻优时间,对于防空作战这种实时性要求很高的武器目标分配来说是一个不错的选择。