用离散粒子群优化算法求解WTA问题

曲在滨，刘彦君，徐晓飞

(1.哈尔滨工业大学计算机科学与技术学院，150001哈尔滨，zbqu@hotmail.com; 2.哈尔滨理工大学计算机科学与技术学院，150080哈尔滨)

武器-目标分配(Weapon-target Assignment，WTA)问题是现代战争中一个十分重要的问题，其解空间随武器种类数和目标总数的增加而呈指数级的增加，使其成为一个多参数、多约束NP完全问题［1-2］.对于WTA问题，国内外主流的求解方法多采用诸如神经网络、遗传算法、模拟退火算法和蚁群优化等求次优解方法，但它们的求解效率都还不是十分令人满意，所以探索有效的求解方法解决WTA问题仍然十分重要.

目前，关于单一兵器火力分配问题的文献已比较多，然而由于在现代作战中，经常是多种类型的兵器联合作战，故需对多种不同类型的兵器的武器-目标分配问题进行探讨.文献［3-6］虽然解决的是多种武器类型的火力分配问题，但所建立模型还是一种简化模型，在实际使用中一般需添加额外约束条件，如对各目标分配的武器数目限制等.本文针对多类型兵器的火力分配问题给出更实用的数学模型，并将粒子群算法求解问题的思路应用于此问题，用实例验证了方法的可行性及有效性.

1 问题的描述

具体问题可描述为:设有n个目标;m种类型武器;Vj为目标j的威胁度;Wi为可分配给目标的i类型武器数量;pij为i类型的一个武器对目标j的杀伤概率;xij为给目标j分配i类型武器的数量，目标j最多可分配武器数量为Nj.WTA问题是要确定分配给各目标的各类武器数量以使所有目标的总期望生存值最小，这个问题可形式化为

xij≥0且为整数，i=1，2，…，m，j=1，2，…，n.式中qij=1-pij，即目标j受到一发i类型武器打击的生存概率.

2 粒子群优化算法

粒子群优化Particle Swarm Optimization(PSO)算法是由Kennedy等［7］在1995年提出的，此算法受鸟群觅食行为的启发，并用于解决优化问题.同遗传算法相比，PSO算法不但具有遗传算法的全局寻优能力，还具有较强的局部寻优能力.

算法将每个个体看作是在n维搜索空间中的一个没有重量和体积的粒子，并在搜索空间中以一定的速度飞行.每个粒子的飞行速度根据其本身的飞行经验和群体的飞行经验不断调整.每个粒子代表解空间的一个候选解，解的优劣程度由适应函数决定，而适应函数根据优化目标定义. PSO随机初始化一群粒子，其中第i个粒子在n维解空间的位置为xi=(xi1，xi2，…，xin).粒子通过在每一次迭代中动态跟踪2个极值来更新其速度和位置为:

1)粒子本身从初始到当前迭代搜索产生的最优解:个体极值pi=(pi1，pi2，…，pin);

2)整个粒子种群目前的最优解:全局极值pg=(pg1，pg2，…，pgn).

如果第i个粒子的速度表示为vi=(vi1，vi2，…，vin)，粒子根据式(1)，式(2)来动态调节自己的“飞行”，得到搜索问题的最优解为

式中:t为迭代次数;c1，c2分别为正常数，称为学习因子，一般有c1=c2=2;r1，r2分别为(0，1)之间的随机数;ω为惯性因子.

3 离散PSO算法求解WTA问题

3.1 约束处理方法

WTA问题的解可表示为一个矩阵 X= (xij)m×n，其中xij为第i类武器分配给第j个目标的数目.在这里，每个粒子的位置便对应着武器的一种分配方案.对粒子群迭代中产生的不可行解采用修正结果值方案的方法进行修正，使其在可行解空间范围内搜索.具体实现时利用一个可行性函数检查新产生的解是否满足所有约束.当不满足时，采用启发式策略进行调节.调节策略为:

1)如果分配方案中某一目标的武器分配总数超过约束限制，则取消对此目标杀伤概率最小的超出数目的武器分配;如果此种武器分配数少于超出数目，则需取消此种武器的全部分配.重复步骤1)，直到各目标满足各自的武器分配总数约束.

2)如果分配方案中某种武器的分配不满足约束，则在已分配这种武器的目标中选择“威胁度与此种武器对此目标杀伤概率之和”最小的目标，取消超出单位数的武器分配;如果超出单位数大于分给此目标的武器数，则余下部分再从占用此种武器且满足选择准则的目标中取消分配.重复步骤2)，直到各种武器分配满足约束为止.

本启发式策略运用了贪心思想，尽可能使所做调节有利于提高武器对目标打击的有效性，从而加速找到最优或次优的分配方案.

3.2 离散PSO算法实现

本文对粒子群算法中的速度和位置进行了重新定义.对速度进行的重新定义为

式中:r1［Plbest(t)-Xi(t)］为第i个粒子的位置Xi的任一列以概率r1与其个体极值Plbest(t)的对应列做减法运算，未做减法运算的列一律清零; r2［Pgbest(t)-Xi(t)］为第i个粒子的位置Xi的任一列以概率r2与全局极值Pgbest(t)的对应列做减法运算，未做减法运算的列一律清零;⊕为对作为操作数的2个矩阵产生1个新的矩阵，当2个操作数矩阵的对应列所有元素均为0，则结果矩阵的相应列也为全0;如果只有一列不全为0，则此列为结果矩阵的对应列;否则任选其中一列为结果矩阵的对应列.

上述定义解决了速度难于表示问题，而进行位置的更新为

式中:Xi'(t)为将Xi(t)随机选择一行根据相应类型武器数目对各目标产生随机分配而其余各行保持不变的结果，而“+”运算则为2个矩阵对应元素相加.

求解WTA问题的离散PSO算法(DPSOWTA)描述为:

1)初始化粒子群，即随机设定各粒子的初始位置X和速度V;

2)计算每个粒子的个体适应度值(即目标函数值);

3)将每个粒子的适应度值与个体极值Plbest比较，若更好，则更新Plbest;

4)将每个粒子的适应度值与全局极值Pgbest比较，若更好，则更新Pgbest;

5)根据式(3)和式(4)更新粒子的速度和位置，并使用启发式策略调整新位置;

6)如未达到最大的迭代次数，则返回步骤2);否则结束.

算法在对每一粒子初始化时根据各类武器的数目随机产生分配方案，且使其满足各约束条件.

4 算法测试

假设有6个目标，T1，T2，…，T6，各目标的威胁度如表1所示.5种武器:W1，W2，W3，W4，W5的数目为{4，3，3，2，2}，对各目标最多可使用武器数目为{1，1，2，1，1，2}，各类武器对各目标的单发杀伤概率如表2所示.

表1 各目标的威胁性系数

表2 武器对目标的杀伤概率表

算法具体实现时，为避免陷入局部最优，若全局极值在进化一定代数后保持不变，则只保留最优粒子，其他粒子全部重新生成.本例中的粒子数取为30，最大迭代数为100.在P4 1.7 G/512 M微机上重复执行算法50次得出的最优方案的适应度值情况如表3所示，最优分配方案的适应度函数值为0.634，与枚举算法所得分配方案的适应度函数值相同.

表3 最优方案的适应值情况

进化过程中的适应度函数值(平均值)变化情况如图1所示，图1中同时也给出与遗传算法(GA)的对比.对于此例，采用枚举算法求解大约需1 142 s，而提出的离散粒子群算法迭代100代所需平均时间为156.9 ms，所得最佳方案的适应度平均值为0.732，与最优值相差0.098;对遗传算法进行同样次数独立实验，每次迭代100代所需平均时间为217.3 ms，所得最佳方案的适应度平均值为1.061，与最优值相差0.427，可明显看出离散PSO算法大大优于遗传算法，求解精度也明显高于文献［8］提出的粒子群优化算法.

图1 适应度函数值(平均值)变化情况

经过对大量实例的计算发现，随着武器和目标数的增加，所提出离散粒子群算法对遗传算法的优势也越发明显.图2给出当目标数为15，武器种类数为5，且每类武器数为(4，6，5，5，4)时2种算法执行时的最佳适应度值随时间变化情况，

此例分配方案的适应度最优值为1.404.总而言之，使用本文提出的离散粒子群优化算法能快速给出武器-目标分配问题的最优或近优解，验证了算法的有效性.

图2 适应度函数值(平均值)随时间变化情况

5 结论

1)采用启发式策略对粒子群迭代过程产生的不可行解进行调节，使算法在可行解空间范围内搜索.调节利用了贪心思想，使其有利于提高武器对目标打击的有效性.

2)对粒子群算法中的速度和位置进行了重新定义，使粒子群算法这一主要用于连续函数优化的算法可以解决武器-目标分配问题这样的约束组合优化问题，明显提高了问题求解的速度和精度，拓展了粒子群优化算法在离散空间的应用.

3)提出的算法能快速给出武器-目标分配问题的最优或近优分配方案，为解决这一NP难点问题提出了新的解决途径.

［1］AHUJA R K，KUMAR A，JHA K，et al.Exact and heuristic methods for the weapon target assignment problem［EB/OL］.(2003-06-20)［2004-04-20］http://ssrn.com/abstract=489802.

［2］ROSENBERGER J M，HWANG H S，PALLERLA R P， et al.The generalized weapon target assignment problem［C］//Proceddings of 10thInternational Command and Control Research and Technology Symposium on The Future of C2.McLean，VA:Lockheed Martin Corporation，2005:1-13.

［3］陈绍顺，王颖龙，王君.多武器系统的火力分配模型［J］.火力与指挥控制，2005，30(2):45-47.

［4］郑泽席.使用多种防空武器时目标分配的数学模型［J］.系统工程与电子技术，2000，22(5):15-16.

［5］解春明，杨传春，李德胜.地地导弹突击目标火力分配模型［J］.火力与指挥控制，2004，29(6):41-44.

［6］王玮，程树昌，张玉芝.基于遗传算法的一类武器目标分配方法研究［J］.系统工程与电子技术，2008，30(9):1708-1711.

［7］KENNEDY J，EBERHART R C.Particle swarm optimization［C］//Proceedings of IEEE International conference on Neural Networks.Piscataway，NJ:IEEE Service Center，1995:1942-1948.

［8］高尚，杨静宇.武器-目标分配问题的粒子群优化算法［J］.系统工程与电子技术，2005，27(7):1250-1252.