武器-目标分配问题的模拟退火算法

《武器-目标分配问题的模拟退火算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com武器一目标分配问题的模拟退火算法吴平梁青(中国科学技术大学，合肥230027)摘要武嚣一目标分配(WeaponTargetAssignment)问题是一个典型的优化问题，模拟退火算法是求解此问题的一种有效方法。文章采用模拟退火算法对WTA问题进行求解，通过实验得到了理想的仿真结果。关键词模拟退火算法武器一目标分配问题优化文章编号1002—8331一(2006)04—0087—04文献标识码A中图分类号TP301．6SimulatedAnnealingAlgorithmforWeapon-TargetAssignmentProb

2、lemWuPingLiangQing(UniversityofScienceandTechnologyofChina．Hefei230027)Abstract：WeaponTargetAssignmentproblemisatypicalOptimizationProblem，SimulatedAnnealingAlgorithmisaneffectivemethodforthisproblem．ThispapersolvesWTAproblemwithSimulatedAnnealingAlgorithmandgetsidealresultsthroughexperime

3、nts．Keywords：SimulatedAnnealingAlgorithm，Weapon-TargetAssignmentproblem，optimization1引言种适合解大规模组合优化问题，特别是解NP完全问题的通用武器一目标分配(WeaponTargetAssignment)问题是现代有效的全局优化解法。它将组合优化问题与统计力学中的热平战争巾十分重要的问题，为解决这个问题，人们提了许多算衡问题类比．其基本思想是从一给定解开始，从邻域中随机产法：Kuttar提的序列算法，把分配问题假定为按顺序逐个地生另一个解．接受准则允许日标函数在有限范围内变坏。它由进行，用

4、迎击失败概率最小的方式去选择目标与迎击武器组一控制参数t决定，其作用类似于物理过程中的温度．对于控制参数t的每一取值，算法持续进行“产生新解一判断一接受或合，收敛速度很慢；Castanon提用非线性网络流程求准最优解的算法，结果会产生较大的误差；E．Wacholker提出了一种神舍弃”的迭代过程，对应着固体存某一恒定温度下趋于热平衡的过程。经过大量的解变换后，可以求得给定控制参数t值时经网络的解法，此方法有时得不到稳定解。文献【3】和【4】对WrA优化问题的相对最优解。然后减小控制参数￡的值，重复执行模型提出了改进算法。本文用模拟退火算法来解决此问题。上述迭代过程。2WTA

5、问题4WTA问题的模拟退火算法求解步骤给定战况如下：有n个目标1，r，2，⋯，迎击武器分布于4．1解空间的确定m个武器平台W1，W2，⋯Wm，第i个武器平台(i=1，2，⋯m)最解空间为问题的所有可能(可行的或不可行的)解的集合，多可使用R个武器，对目标rj(j=l，2，⋯n)最多可使用个武它限定了初始解选取和新解产生的范围。器，武器平台迎击目标巧的概率为(『=1，2，⋯n；i=l，2，根据WTA问题的数学模型．可以将该模型简化为寻求Ⅳ⋯m)，武器最佳分配以分配迎击武器迎击全部目标的失败概个目标和个武器平台上Ⅳ个武器的一一对应关系。在算法率最小为目标。实现中，将定义为问题的

6、解(为的方阵)，考虑到模型中的约束若分配了武器平台Wi迎击目标Yj，则=1，否则X=O。条件，限定的每一行和每一列有且仅有一个元素为1，其余WTA问题的数学模型为：元素均为O。若X为最优解，X(i，f)：1则表示武器最佳分配n=∑兀(1一)方案中用第i个武器迎击第f个目标。j=l14．2目标函数∑≤R(1，2，⋯m)考虑到算法的实现，根据WTA问题中模型的目标甬数，可j=1以将其转化为求解能量值：E=N-Trace(P，)∑墨≤S(『=12．．n)l其中：E为能量值；Xq=0，1』v为目标数；Trace为求迹：3模拟退火算法P，为概率矩阵的转置；模拟退火算法SAA(Simu

7、latedAnnealingAlgorithm)是一为问题的解。计算机工程与应用2006．0487维普资讯http://www.cqvip.com4．3初始解的选择6仿真结果经过大量的实验表明，模拟退火算法的最终解并不依赖初6．1实验l始解的选取。因此为了简化算法，这里可将初始解选取为N秩有4个目标1．他。乃，，迎击武器分布于4个武器平台为的单位阵。l，W2，W3．W4，每个武器平台最多可使用1个武器，对每个4．4新解的产生和接受机制目标最多可使用1个武器，武器平台迎击目标Tj的概率为4．4．1新解的产生U=1，2