高 尚

(江苏科技大学计算机科学与工程学院，镇江 212003)

武器-目标分配(weapon target assignment)问题是现代战争中十分重要的问题.Lloyd［1］等指出武器-目标分配问题是一个NP完全问题.为解决这个问题，人们提出了许多算法.Wacholker［2］提出了一种神经网络的解法，其依据Hopfield和Tank的神经网络模型，用此网络解WTA问题，此方法有时得不到稳定解；文献［3-4］对神经网络模型提出了改进算法；文献［5］用遗传方法解决了WTA问题；文献［6-7］用蚁群算法解决了WTA问题；文献［8］用粒子群优化算法解决了WTA问题；文献［9］用免役算法解决了WTA问题.各种算法各有优劣，本文用分布估计算法来解决WTA问题.

1 WTA问题

有 n个目标 T1，T2，…，Tn，迎击武器分布于 m个武器平台 W1，W2，…，Wm，第 i(i=1，2，…，m)个武器平台最多可使用ri个武器，对目标Tj最多可使用sj个武器，武器平台Wi迎击目标Tj的概率为pij(i=1，2，…，m；j=1，2，…，n)，武器最佳分配以分配迎击武器迎击全部目标的失败概率最小为目标.

若分配了武器平台Wi迎击目标Tj，则xij=1，否则xij=0.WTA问题的数学模型为

只有当 ri=1(i=1，2，…，m)，sj=1(j=1，2，…，n)时，上述问题为可转化为指派问题，可以用匈牙利法解［6］.对于一般优化问题实质是非线性0-1整数规划问题，属于NP-难题，目前没有有效的算法解此问题.

2 基本分布估计算法

分布估计算法的概念最初在1996年被提出［10-11］，分布估计算法提出了一种全新的进化模式.在传统的遗传算法中，用种群表示优化问题的一组候选解，种群中的每个个体都有相应的适应值，然后进行选择、交叉和变异等模拟自然进化的操作，反复进行，对问题进行求解.而在分布估计算法中，没有传……