模拟退火与蚁群混合并行算法解旅行商问题

求解TSP问题的智能优化算法主要包括蚁群算法和模拟退火算法等,这些算法求解TSP问题的速度比传统的精确求解算法有很大改进,但在问题的求解空间逐渐增加时,串行执行速度往往还是无法满足人们的需求.针对此问题,研究了蚁群算法、模拟退火算法以及两者的混合算法的并行实现方法,建立了PC机群实验平台,基于MPI环境对蚁群算法、模拟退火算法以及混合算法的并行算法进行了测试.根据理论

第3 9卷第 2期、 .9 b1 No2 3 .

河

北

工

业

大

学

学

报

2 1年 4月 00Ap i 2 1 r 0 0 l

J OU RNAL 0F HEBEIU NI VERSI TY OF TECHN 0LOG Y

文章编号：10 .3 3(00 20 4—4 0 72 7 2 1)0—0 80

模拟退火与蚁群混合并行算法解旅行商问题许智宏，宋勃，郭艳艳

(河北工业大学计算机科学与软件学院，天津 3 0 0 ) 04 1

摘要求解 T P问的智能优化算法主要包括蚁群算法和模拟退火算法等，这些算法求解 T P问题的速度比传 S题 S统的精确求解算法有很大改进，但在问题的求解空间逐渐增加时，串行执行速度往往还是无法满足人们的需求. 针对此问题，研究了蚁群算法、模拟退火算法以及两者的混合算法的并行实现方法，建立了 P C机群实验平台， 基于 MP I环境对蚁群算法、模拟退火算法以及混合算法的并行算法进行了测试.根据理论研究和实际测试的结果，比较了并行算法和传统串行算法的性能差异，总结了利用 P C机群系统求解旅行商问题的并行求解的可行性， 得出了关于并行效率等方面的一些有意义的结论.

关

键

词旅行商问；模拟退火算法；蚁群算法；混合算法；并行计算题T 13 P 8文献标识码 A

中图分类号

U sn t l n g rt m n i l td An e l gP r l l i gAn o y Al o i Co h a d S mu ae n ai a al n eAl o i m o v r v l g S l s a r b e g rt h t S l eT a e i ae m n P o lm o n

XU iho g, S Zh . n ONG BO, GUO n. n Ya ya( co l f o ue cec dE gn eig Sh o C mp tr i e n n ier,Hee iesyo T cn lg,Taj 0 10 hn ) o S n a n b i vri f eh oo y ini 3 0 3,C ia Un t nAb t a t T ei tl g n p i iai n ag r h r o v n S i l cu e n o o y ag rtm n i l tda - sr c h e l e t t z t lo t ms o li g T P man yi l d t l n l o i n i o m o i f s n a c h a dsmu ae n n

ai g t.Th s l o i ms a es n f a t d a tg s n n f se a a i o a x c l o t ms e l,ec n e e g rt a h v i i c n v n a e dr tr h nt d t n l a t g r h .Bu,t es e d h g i a a u a t r i e a i t h p e i o e o sb et e e p e e d a h c l f P i ce s r d al .F rt ep o lm, t i a e ic s e s f ni t mp s i l me t o l’ n e s e s ae o o p S t TS r a eg a u l n y o r be h h s p rd s u s d p h a a l h d t ep r l l t o s oi lme t h n oo y ag r h e me t mp e n ea t l n lo t m,t e i ltd a n a i ga dt eh b dag rt,e t b ih d t c i h mu a e e l n y r l o i s n n h i m h sa l e s acu tro Css se l se fP y t m,a dt se ep al l l o i si P . Ba e n t et e r t n r ci a t d,t ep r n t d t a l g rt e h r ea m h M I n s d o o ei a dp a t l u y h e - h h c c s f r n c i e e c sb t e a a ll l o t msa d ta i o a l o i ms r n lz d h e f a i i t f r c e i g o ma ed f r n e e we np r l g r h dt n l g rt ea i n r i a h ea a y e,t e s l y o p o e dn we b i p r l l l o i ov P i l se f Cs s i u s da ds me a al g r h t s l eTS cu t r P s s e n ea t m o n o wa d c o a i g u o cu i n b u a al l f ce c me n n f l n l so s o t r l i i n y c a p ee wee a h e e . r c iv d Ke r s T P i l td a e l ga g r h;a t o o y a g rt;h b da g rt m;p r l l o u i g y wo d S;smu ae n ai lo tm

n i n l n l o h c im y r l o i i h a a l mp t ec n

旅行商问题 (rvl gSls nPo l Taen aema rbe i m)简称 T P问题，是组合优化中最著名的问题之一，它易于描 S述而难于求解 .求解 T P问题的智能优化算法主要包括蚁群算法和模拟退火算法等，这些算法求解 T P问题 S S的速度比传统的精确求解算法有很大改进，但在问题的求解空间逐渐增加时，串行执行速度往往还是无法满足人们的需求[]文在机群环境下，基于 MP,设计了蚁群算法、模拟退火算法及两者混合的并行算法， 1 .本 - 2 I

来实现对 T P问题的求解，提高了算法的执行效率 . S MP Mesg as gIt fc息传递接口)是实现并行计算的一个库，是一种消息传递编程模型， I( saeP si e ae消 n nr 遵守语言语法中对过程或函数的调用规则，它可以被 F T AN或 C语言调用[ OR R 1 1 .自从 19 92年对 MP标准化 I

以来，MP广泛地应用于并行计算技术中，成为这种编程模型的代表和事实上的标准. I 并行策略一般可分为细粒度 (n—rie )和粗粒度 (orega e)两种 .细粒度并行指分配给单 i f ega d n cas—ri d n个处理器较少的计算实体，但随之而来的是处理器问频繁的信息交互 .粗粒度方法则相反，单个处理器负责较大规模甚至是整个种群的运算，因而减少了处理器问的信息传递 .收稿日期：2 0—70 090—9

作者简介：许智宏 (9 0) 17一，女 (汉族),副教授，博士