PDF《火力优化分配问题 的小 生境遗传蚂蚁算法》

第25卷第

1 期2005年 1月计算机应 用Co mp u t e r Ap p l i c a t i o n s Vo

1 .

2 5 N o .

1 J a n .2

0 0

5 文章编 号:1001―9

0 8

1 (

2 0

0 5 )

0 1―

0 2

0 6―

0 4 火 力优 化分配问题 的小 生境 遗传 蚂 蚁算 法陈云飞,刘玉树 , 范洁,赵基海(北京理工 大学 信息科 学技 术学院 计 算机科 学工程 系, 北京

1 0

0 0

8 1 ) ( c y f _

9 9

0 @b i t . e d u . e n ) 摘要:火力分配 问题是 N P难题 , 经典 的求解算法存在指数级 的 时间复杂度 .文 中提 出一种 小 生境遗传算法与蚁群优化 算法相结合的 小生境遗传蚂蚁 算法 , 并针 对具体 问题 提 出蚂蚁搜 索的禁 忌 规则.对该算 法进行 了实验 , 并将 实验 结果与其他 算法进行 比较分析 , 分析结果表 明:新算法无论是 在优化性能还是在 时间性 能都取得 了非 常好 的效果 .文 中算 法对其他 的NP问题 同样适 用. 关键词 : 小生境 遗传算 法;

蚁群优化算 法;

火力分 配问题 中图分类号 :T P

3 9

1 .

9 ;

T P

3 0

1 .

6 文献标识码 : A Ni c he - ba s e d g e ne t i c & an t c o l o ny o pt i m i z a t i on a l g o r i t h m f or g e ne r a l i z e d a s s i g nme nt pr o bl e m CHEN Yu n ― f e i ,L I U Yu ― s h u ,F AN J i e ,Z HA0 j i ― h a i ( D e p a r t m e n t o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g , S c h o o l o fI n f o r m a t i o n S c i e n c e a n d T e c h n o l o g y ,B e i j i n g I n s t i t u te o fT e c h n o l o g y ,B e i j i n g

1 0

0 0

8 1 ,C h i n a Ab s t r a c t :We a p o n ― T a r g e t A s s i g n m e n t p r o b l e m ( WT A )i s N P h a r d .C l a s s i c a l me t h o d s f o r s o l v i n g s u c h p r o b l e m s a r e b a se d o n g r a p h s e a r c h a p p r o a c h e s a n d u s u a l l y r e s u l t i n e x p o n e n t i a l c o mp u t a t i o n a l c o mp l e x i t i e s . A n o v e l Ni c h i n g Ge n e t i c & A n t C o l o n y O p t i mi z a t i o n( N G A C O)a lg o r i t h m b a se d o n t h e c o mb i n a t i o n o f n i c h e ― b a s e d g e n e t i c a lg o r i t h m a nd a nt c o l o n y a lg o r i t h m Wa s p r o p o s e d .M o r e o v e r .a n i n t e n s i v e s t u d y o f h o w t o u s e t h i s a lg o r it h m i n W T A W a s ma d e .S o me e x p e r ime n t s w e r e ma d e . E x p e r ime n t r e s u l t s we r e c o mp a r e d w i t h t h o s e o b t a i n e d u s i n g o t h e r c l a s s i c a l o p t i mi z a t i o n a lg o r it h m . T h e r e s u l t s d e mo n s t r a t e d t h a t NGACO i S a n e f f e c t i v e a n d e f f i c i e n t a lg o r i t h m. a n d i S v i a b l e f or o t h e r NP ― h a r d p r ob l e m、 Ke y wo r d s :n i c h i n g g e n e t i c ;

a n t c o l o n y o p t i mi z a t i o n ;

W e a p o n ― Ta r g e t a s s i g n me n t p r o b l e m

0 引言 射击单位与 目标的合理分配是炮兵及防空兵计划火力的 重要 内容, 指在一定的准则条件下为更好地 打击 目标而对射 击单位进行的任务分配.火力分配问题在本质上属于数学规 划中的非线性整数规划 问题 , 是一种 N P难题 .到 目标为 止已经提出了很多方法用于解决这一类问题 .经典 的方法大 多是基于图的搜索 , 往往会产生 指数 级 的时间 复杂度 . 近年来 , 将多种启发式智能算法 ( 如:模拟退火 、 遗传算法 、 蚂 蚁算法、 免疫算法等) 进行交叉 、 融合生成新 的优化性能更好 的复合算法引起 了越来越 多学 者 的兴趣与关注 .在诸 多复合算法 中, 将遗传算法和蚁群 优化算法相结合是其 中的 一 个热点 .遗传算法搜索使用 目标 函数启发 , 算法 的求解速 度快 , 但对系统中反馈信息利用不够 , 求精确解效率低 ;