2024年6月12日发(作者:)
第33卷第6期
2011年12月
国防科技大学学报
Vo1.33 No.6
Dec. 2011
JOURNAL OF NATIONAL UNIVERSITY OF DEFENSE TECHNOLOGY
文章编号:1001-2486(201I)06-0150—04
改进类电磁算法在武器目标分配问题中的应用
杨晓凌,邱涤珊,彭 黎,谈群
(国防科技大学信息系统工程重点实验室,湖南长沙410073)
摘要:通过基于级数的粒子编码变换方法,将武器目标分配问题的约束条件进行了化简。对原始类电
磁算法,在种群初始化、局部搜索、合力计算以及粒子移动等各步骤对其进行改造,使之适应武器目标分配
问题的整数解空间。最后通过数值实验验证了该改造后算法解决武器目标分配问题的有效性。
关键词:类电磁算法;武器目标分配;粒子编码;合力计算;粒子移动
中图分类号:TP301.6;0221.4 文献标识码:A
Application of Modiied Elfectromagnetism-like Algorithm in
Weapon-target Assignment Problem
YANGXiao—ling,QIUDi—shan,PENG Li,TANQun
(Science and Teehnolagy on Information Systems Engineering Laboratory,National Univ.of Defense Technology,Changsha 410073,China)
Abst ̄:A method of particle coding based on progression was applied to the simplification of constraints in Weapon—Ta ̄et
Assignment(WTA)mode1.The ofi ̄nal EM algorithm Was modiifed in all steps,including the initilaization of the population,
the local searching,the calculation of totl forace vector and movement along the totl faorce,and the WTA problems with integer
solution space was settled by the algorithm.Finally,the numerical experiments verified the effectiveness of the algorithm for
solving problems.
Key words:the electromagnetism-like lagorihm;Weaton-pTarget Assinment(WTA);pagrticle coding;calculation of total
force vector;movement of particle along totl fao1-13e
武器目标分配(Weapon—Target Assignment,
WTA)作为现代战争指挥控制流程的关键环节,
在如下两点局限:
(1)只能处理简单约束
其时效性和分配方案的优劣直接影响作战效果,
设计快速优化的求解算法是WTA问题研究的重
要组成部分。目前,对WTA问题的求解除隐枚
举法、分支定界法、割平面法、动态规划法等传统
算法外,近年来,又产生了许多诸如遗传算法、粒
子群算法、蚁群算法、模拟退火算法、免疫算法及
人工神经网络等现代优化算法,但是这些算法的
效率需要进一步提高…。
原始类电磁算法处理的约束是针对决策向量
的盒状约束 J:
X∈{ ∈ l ≤ ^≤ ,k=1,2,…,n)
(2)只能处理具有连续解空间的最优化问题
原始类电磁算法中,电磁力的计算方法以及
粒子的移动策略都局限于连续解空间,这种局限
性主要针对粒子问距离的计算。
本文针对原始类电磁算法的以上局限性,采
用基于级数的粒子编码方法,将WTA问题的约
束条件进行了化简。在原始类电磁算法的框架
下,在种群初始化、局部搜索、合力计算以及粒子
移动等各步骤对原始类电磁算法进行改造,使之
适应WTA问题的整数解空间。
类电磁算法作为一种启发式的全局优化方
法,最早由Birbil和Fang在2003年针对连续函数
的全局优化问题提出l2]。该算法将种群中个体
看作带电粒子,通过模拟电磁场中带电粒子间的
吸引排斥作用引导粒子朝最优解移动。类电磁算
法具有全局搜索能力强、不使用一阶和二阶导数
信息等优点,已初步应用于函数优化、项目调度等
领域。但是原始的类电磁算法在结构设计上也存
收稿日期:2011一o4-20
通过仿真计算并与遗传算法和粒子群算法等
两种典型优化算法比较,验证了改进类电磁算法
在WTA问题中应用的有效性。
・
基金项目:国家部委基金资助项目
作者简介:杨晓凌(1982一),男,博士生。
第6期 杨晓凌,等:改进类电磁算法在武器目标分配问题中的应用
1 WTA问题描述
本文研究的WTA问题是静态的,即武器对
目标的分配过程只有一次且所有武器与目标之间
只进行一次交战。所研究的模型各要素可表示为
∈{q …, 0’ … ’ 工 } E{o’ … ’
图1 基于级数的粒子编码
Fig.1 Particle coding based on progression
一
个五元组{w, ,y,P, ,其中:
w:武器平台集合,W={ ,W ,…,似 };
r:目标集合,T={t】,t2,…,t };
y:目标价值集合,V={口。, ,…, };
P:武器对目标的杀伤概率矩阵,P=
[P ]mxn,其中p 表示第 个武器平台对第_『个目
标的杀伤概率,且P ∈[0,1];
:
单个武器平台可使用的武器数量限制,可
假设对武器平台i最多可使用r 个武器;
于是WTA问题的规划模型可表示为
n m
minE=∑ 里(卜p )q
。. .
f ∥ '2,…
lx
i E Z,i=1,2,…,m =1,2,…,rt
(1)
值得一提的是,在某些WTA模型中考虑了
对单个目标的武器数量限制。而实际作战运用
中,为保证消灭某一威胁度或价值较大的目标,使
用武器往往不考虑数量限制,如进行“饱和攻
击”。因此本文采用的式(1)是合理的。
2求解WTA问题的改进类电磁算法
本文通过解向量变换简化了WTA问题的可
行解空间。针对可行解空间的离散特征,对原始
类电磁算法在种群初始化、局部搜索及粒子移动
等各步骤进行了改造。
2.1基于级数的粒子编码策略
原始类电磁算法中,对粒子的各种操作必须
在可行解空间中进行。对式(1),由于约束条件
相对复杂,若直接采用解向量对粒子进行编码,在
操作上有诸多限制,可构造一种基于级数的粒子
编码方法。
i
记 =o,Y =∑ ,则式(1)的解向量可
变换为:.),=(Y11,Yl2,…,Yl ;Y2l,),22,…,Y2 ;…;
y柑,YJ,I2,…,), ),且有 n=Y =,, —YfJ—l。种
群中粒子的编码如图1所示。
进而,式(1)可转换为
n ,,I
minE(_),) i ( ) ’
s.t.Y∈
其中力={y∈z lyi,『.1≤y ,Y ∈{O,1,…, ),i
=1,2,…,m =l,2,…,n)。
2.2类电磁机制算法的改造
为解决如式(2)的n×m维变量约束优化问
题,本文对原始类电磁算法在各个步骤均进行了
改造,使得各步骤生成的新粒子或粒子的新位置
均保持在可行解空间 中(具体算法步骤可参照
文献[2]进行适当修改)。
2.2.1种群初始化
在进行迭代计算之前,需要对种群进行初始
化,即从可行解空间 等概率选取pop—size个样
本点{Y‘¨,Y‘ ,…, ‘ }作为初始解。粒子
j, ’(k=1,2,…,Pop
—
szie)的选取方法为:
(1)采用旋转赌轮机制从集合
{o,1,…,ri)中选择任意一个整数n ’,令), ’:
,l , =1,2,…,m;
(2)采用旋转赌轮机制从集合
(,, ,,,,0 。+1,…,ri)中任意选择一个整数
凡 ,令), = ,i=1,2,…,m。
2.2.2局部搜索
局部搜索是指在初始化种群的基础上,对种
群中每个粒子,在其周围附近寻找更优的粒子,进
一
步对种群进行优化,以加快寻找最优解的速度。
由于约束条件Y∈ 的限制,搜索局限在一定范
围内,对粒子Y的每一维可定义一个正向搜索长
度和一个负向搜索长度,按正向搜索长度搜索,粒
子分量变大,按负向搜索长度搜索,粒子分量
变小。
定义 (∈(0,1])为搜索长度因子。粒子各
分量的正向搜索长度Zi,按如下方式定义:
(1)Zn=6(ri—Yn),i=1,2,…,m;
(2) 1时,若Y >,, 1,则艺 = ( -y )。
若Y <yf^,一l,贝0艺 =6(ri一),‘I,一1)(i=1,2,…,m;
=
1,2,…,n),且搜索只能在集合{), 一。,yfJ一,+
1,…,r }中进行。
粒子各分量的负向搜索长度Z ,按如下方式
定义:
(1)Z 1= fl, 1,2,…,m;
(2)_『>1时,若y >Yl,『-l,贝0 =艿(Y —
Y 一1)(i=1,2,…,m =1,2,…,n)。
国防科技大学学报
若Y <), l时,则搜索只能在集合{Y 1,YiJ一1
+
l,…,r {中进行。
2.2.3电荷及合力计算
的上界为
=rain{一△y /Ae I△e <0,
=l,2,…,117,; =0,1,…,n一1)
通过计算施加到粒子上的合力确定下一步搜
索的方向。首先计算粒子的电荷量,公式如下:
即 和JB规定了粒子在合力方向上可移动的
范围。
m +t)(3)
所示:
针对wTA问题的粒子移动策略如式(7)
其中 (.),)为粒子Y的适应度评价函数,其计算
公式为
:专 \1 .,
根据式(3)和式(4),目标函数值相对较优的
粒子将拥有较大的电荷量。由于原始类电磁算法
针对的是连续可行解空间,而WrA问题的可行
解空间是离散的,故对施加到粒子上的合力计算,
需要关注的是两个粒子间距离的计算方法。因此
本文仍采用原始类电磁算法中合力的计算方法,
其合理性在于:将本文中式(2)的整数约束条件
去掉,即将原有的离散的整数解空间换为连续的
实数解空间,解空间为式(2)的解空间的子空间,
因此在计算粒子间距离时仍采用欧式距离,得到
的合力也能够为下一步粒子的位置更新提供
指示。
2.2.4粒子移动
原始类电磁算法中,种群粒子在合力作用下,
其移动策略可由式(5)给出
的 )+A (5)
其中A~u(o,1),F‘ /IlF‘ ’lJ为合力方向上的单
位向量, 是粒子在各维上向边界移动的可行步
长组成的向量。可以看出,原始类电磁算法移动
粒子的思想是粒子沿合力方向在可行步长上进行
随机移动。
记e=F‘ ’/lIF‘ lI=(e11,e12'…,e1 ;e2l,e22,
…
,
e2 ;…;e 1,e,,|2,…,e )。设 ≥0,则Y+
表示粒子Y沿合力方向移动长度 后到达的
位置。
记e =0,Y =0 e +l=0,Y +1=rf, =1,2,
…
,
m。由Y+ize∈ ,可知
y +1we ̄i≤),iJ+1+/xe ̄j+1 (o)
记Ae =e J+1一。 ,△,, =Y J+l一), ,则由不等
式(6)可得:若△。 >O,则 ≥-Ay /△ ;若△ <
0,则 ≤一△y /△e 。
于是可确定出 的下界为
=max{一△y /_△e l△。 >0,i=1,2,…,m;
.『=0,1,…,n一1)
if,
Aye ],若[-Aye ]
Aye ≤0.5
y +
, +
3.ye j,若LA J
A >0.5一
(7)
其中入E u(o,
), ∈U(OL, ),i
{1,2,…,m},j
∈{1,2,…, }
3仿真及结果分析
本文算法在Pentium 4 CPU 2.40GHz计算机
及Windows XP平台上用Visual C++6.0编程实
现。针对如下算例进行了仿真分析。
某导弹艇编队艇数M=5,目标数量N=6。
各导弹艇装载的导弹武器数量R=[r ] =[5
4 4 6 5],目标价值系V=[ ] =[0.4
0.65 0.15 0.05 0.3 0.6];导弹艇武器
对目标的单发毁伤概率为
0.6 0.6 0.3 0.4 0.1 O.3
0.3 0.5 0.7 O.3 0.1 0.2
P:[P ] =
0.2 0.6 0.4 O.9 O.7 0.1
O.1 0.9 0.0 0.3 0.2 0.1
0.5 0.4 0.5 0.2 0.7 0.3
在仿真实验中,改进类电磁算法采用的种群
规模pop—size=20,算法最大迭代数MAXITER=
200,局部搜索迭代次数LSITER=10,局部搜索因
子 =1。计算得到的最优粒子编码为:
Y=(222225I113334I133444l333336I222245、
相应的目标分配方案为
=
(200003I102001 l120100I1200031200021)
此外,还利用粒子群算法和文献[4]给出的
遗传算法对算例进行了仿真求解,其中粒子群算
法采用的种群规模和最大迭代数与改进类电磁算
法相同,惯性系数 =0.9,加速系数c =c :
1.8;标准遗传算法采用的种群规模和最大迭代次
数与改进类电磁算法相同,交叉概率P =0.8,变
异概率P =0.8,算术交叉因子卢=0.2。分别利
用3种算法求解上述算例,收敛曲线如图2所示。
由图2可看出,改进类电磁算法与遗传算法
相比,收敛速度优势比较明显,基本上从开始迭
代,收敛曲线即位于遗传算法收敛曲线下方。与
粒子群算法相比,虽然在迭代初期得到的最优解
以及收敛速度不及粒子群算法,但是逐渐收敛速
第6期 杨晓凌,等:改进类电磁算法在武器目标分配问题中的应用 ・153・
1.1
l
类电磁算法
0.9
遗传算法
魁0.8
●
-
蓄o.7
l
鉴o.
{
萎0_5
略0.4
1
0-3
L
¨
] I
‘
\ t
0.2
l
0.1
0 20 40 60 80 100 120 140 l60 180 2oo
迭代次数
图2求解WTA问题时类电磁算法与其他
算法收敛曲线比较
Fig.2 Comparison of convergence curves between EM
algorithm and other algorithm for solving WTA
度赶超了粒子群算法,迭代到3O代左右时,即得
到了更优的目标函数值。
4结论
武器目标分配是现代条件作战指挥控制机制
中的关键环节,同时解决该问题也具有重要的理
论研究引导作用,因此对其的研究一直非常活跃。
解决武器目标分配问题的核心是提高求解的速
度。类电磁算法作为2l世纪初才提出的一种新
型全局优化算法,其强大的搜索能力已得到了验
证。但是其初衷是解决一般的连续优化问题。本
文通过对原始类电磁算法进行改造,同时对武器
目标分配模型进行了一定的变形,从而实现了对
该问题的快速求解,仿真实验结果对此进行了
验证。
与遗传算法、粒子群算法等成熟的现代优化
算法相比,类电磁算法在应用于离散优化问题时
往往需要针对具体问题进行特殊改造,可移植性
不强。对此,需要进一步做深入的研究。
参考文献:
[1]蔡怀平,陈英武.武器一目标分配(WTA)问题研究现状[J].
火力与指挥控制,2006,31(12):11—15.
[2]Birbil S I,Fang S c.An Electromagnetism-like Mechanism for
Global Optimization[J].Journal of Global Optimiaztion,
20o3,23(3):263—282.
[3]Birbil S l,Fang S C。Sheu R L.On the Convergence of a
Population・basedGlboalOptimiazitonAlgorithm[J].Journalof
Global Optimiaztion,2004,30(2):301—318.
[4] 王玮,程树昌,张玉芝.基于遗传算法的一类武器目标分
配方法研究[J].系统工程与电子技术,2008,30(9):
1708—1711.
[5]高尚,杨静字.武器一目标分配问题的粒子群优化算
法[J].系统工程与电子技术,2005,27(7):1250—1252.
[6]吴平,梁青.武器一目标分配问题的模拟退火算法[J].计
算机工程与应用,2006,4:87—90.
[7] 范洁,刘玉树,龚元明,等.基于混合蚁群算法的WTA问
题求解[J].Computer Engineering nad Applications,2005,
10:59—61.
[8]Cai H P,Liu J X,Chen Y W,et 1a.Survey fo the Research
on Dynamic Weapon Target Assignment Problem[J].Journal
of Systems Engineering and Electronics,2006,17(3):559—
565.
[9] 印峰,王耀南,杨易曼,等.结合变尺度法的改进类电磁
算法[J].智能系统学报,2010,5(3):254-259.
[1O] 韩丽霞,王宇平.求解无约束优化问题的类电磁机制算
法[J].电子学报,2009,37(3):664-668.
[11]Mirabi M,Fatemi G S M T,Jolai F.A Hybird
Elcetromagnetism—like Algorithm for Supplier Selection in
Make-to.order Planning[J].Transaction E:Industrial
Engineering,2010,17(1):1—11.
[12]Rocha A M A C,Fenrnades E M G P.A New
Electromagnetism—like Algorithm with a Popul ̄ion Shrinking
Strategy[C]//Prce.6th.WSEAS International Conference on
System Science and Simulation in Engineering,Venice,
2007,ll:307—312.
[13]Tsou c S,Hsu C H,Yu F J.Using Mulit—objcetive
Electromagnetism—like Optimization to Analyze Inventory
Tradeofs Under Pracblistic Demand[J].Journla ofScientiifc
&IndustriM Research。2008,67:569—573.
发布评论