（管理科学与工程专业论文）蚁群优化算法及其应用.pdf

中文摘要 蚁群优化算法及其应用 摘要 组合优化问题是运筹学的个重要分支，许多现实中的优化问题都 可以描述为组合优化问题进行求解，其应用范围涵盖了诸如生产布局、 交通运输、能源开发、最优设计、经济决策、企业管理、都市建设、公 用事业、农业规划、资源分配、信息处理、军事决策等诸多领域，因此 对于组合优化问题求解方法的研究具有非常重要的现实意义。 计算复杂性理论证明了大多数组合优化j 题是难口j 题，即求解 这一类问题所需要的计算时问随着问题规模的增大而呈现指数性增长。 由于当今社会信息化的高度发展，现实中需要求解的组合优化问题的难 度和规模迅速扩大，以往传统的运筹学求解方法已经无法在可接受的时 间范围内给出这一类难问题的解，由此对多项式时间近似算法的 研究提出了现实的迫切需求。 目前，对于多项式时问近似算法的研究已经形成了一系列富有成效 的现代优化方法，这一类方法又称为现代启发式算法，包括禁忌搜索算 法、模拟退火算法、神经网络、蚁群优化算法、粒子群优化算法等等。 本文的土要研究对象是蚁群优化算法。蚁群优化算法是近年来发展 起来的一种群体智能优化方法，来自于对自然界中蚂蚁寻找食物的整体 性能力的模仿，因此它又是一种人工智能方法。自然科学的研究表明， 蚂蚁在行走时会在所经过的路径上释放一种称为信息素的化学物质。蚂 蚁就是通过释放和追随信息索的方式达到交流和协作的日的，并从整体 上体现为一种涌现现象。事实上，这种信息素表示蚂蚁在问题求解过程 中的一种分布式的信息，是蚂蚁在问题求解过程中的一种经验累积。蚁 群优化算法就是通过模仿蚂蚁这种信息素放置和追随的方式建立了自己 独特的寻优机制。 蚁群优化算法从诞生之日起就得到了广泛的关注，大量的研究文献 充分证明了蚁群优化算法的优越性和受关注程度。日前，蚁群优化算法 已经被成功地应用到了多个组合优化问题中。但是在蚁群优化算法的研 究过程中还存在着些明显的不足，上要体现为：( 1 ) 数学模型的建立 和相关理论性的研究还有待于完善；( 2 ) 整体求解质量还有待于提高； 上海变通大学博士学位论文 ( 3 ) 蚁群优化算法的应用深度和广度都还有待于进一步拓展；( 4 ) 蚁 群优化算法的影响力和研究力量还有待于加强。 本文对于蚁群优化算法的研究主要包括三个方面的内容：( 1 ) 算法 模型和收敛性理论；( 2 ) 算法的改进和创新；( 3 ) 算法应用深度和广 度的拓展。在算法模型和收敛性理论方面，本文将蚁群优化算法的迭代 过程描述为一种时齐的马尔可夫过程，并运用稳态分布极限概率的理论 证明了蚁群优化算法的收敛性，并对影响收敛性能的一些参数设置和方 法进行了讨论。在算法改进和创新方面，本文提出了三种创新的算法： 首先，本文将模拟退火机制引入蚁群优化算法中，设计了一种新型的混 合算法s a c o ；其次，本文提出了一种应用于二进制空问的二进制蚁群 优化算法b a s ；最后，本文设计了一种应用于连续空间的蚁群优化算 法d a c o 。在算法应用领域，本文成功提高了蚁群优化算法在旅行商问 题和多维背包问题中的求解能力，首次将蚁群优化算法应用于二进制函 数优化问题，并突破了蚁群优化算法在连续空间中的应用限制和乏力现 象。 具体来说，本文的主要研究_ 作和研究成果包括： 】简要介绍了组合优化问题及其求解方法，利用计算复杂性理论论证 了使用多项式近似算法求解一难问题的必要性，并总结了处理 r p 一难问题的一些土要的现代肩发式方法。 2 综述了蚁群优化算法的起源、发展和应用倩况，提出了目前研究中 的一些不足以及一些可行的研究方向。 3 利用随机理论中的马尔可夫链理论建立了蚁群优化算法的算法模 型，并证明了蚁群优化算法的有条件收敛性：即在无限次迭代次数 的前提下，具有精英蚂蚁策略和防止信息素扩散机制的蚁群优化算 法能够以概率1 收敛到问题的最优解。在此基础上，本文讨论了 蚁群优化算法收敛速度的影响因素，提出：( 1 ) 蚁群规模并不影 响算法的收敛性但会影响算法的计算时间；( 2 ) 在蚁群优化算 法的过程中使用局部搜索方法可以显著地提高算法的收敛速度； ( 3 ) 信息素的更新规j l 【l j 和参数设置可以显著地影响算法的收敛速 度，但影响方向不可确定。 4 在蚁群优化算法的信息素更新过程中，引入模拟退火算法中的退火 机制，设计了一种新型的混合型算法s a c o 。s a c o 能够以一定的 中文摘要 概率接受非最优解进行信息素的更新，从而显性增加了算法跳出局 部晟优的机制，扩展了算法在迭代初期的搜索范围。旅行商问题的 实验证明，s a c o 显著提高了蚁群优化算法在求解该类口j 题时的效 果。 5 针对二进制空间的特征，本文设计了一种二进制的蚁群优化算法 b a s ，并讨论了该算法的收敛性能。b a s 将信息素直接放置于每一 个变量的选择路径上，通过特殊设计的信息素更新规则，使得信息 素可以直接代表选择概率，从而减少了算法的计算时间。通过在二 进制函数问题和多维背包问题中的成功应用，充分说明了b a s 算法 的有效性和实用性。 6 以往的蚁群优化算法在处理连续空间时总是存在着严重的求解 质量问题。本文设计了一种应用于连续空问的蚁群优化算法 d a c o ，d a c o 利用j e 态分布作为各个变量值的选择概率模式， 通过将信息素放置于均值和方差上的方法，利用特殊的信息素更 新规则使得算法能够迅速有效地收敛到最优解附近的领域，极大 地提高了算法的求解速度。在连续空间函数优化问题中的实验证 明，d a c o 显著提高了蚁群优化算法处理连续空间函数优化问题的 能力，并且豪小逊色于其他优秀的现代启发式算法。 本文的创新性主要体现在以下四个方面： 1 利用随机理论中的马尔可夫过程，证明了蚁群优化算法的收敛性， 并讨论了算法的收敛性能，得出了一些有关算法收敛速度的结论。 2 将模拟退火机制引入蚁群优化算法中，显性地增加了跳出局部最优 解的机制，并验证了该算法的有效性。 3 提出了蚁群优化算法的二进制模型，讨论了该算法的收敛性能，并 通过实验证明了该算法的实用性。 4 设计了一种新型的应用于连续空间的蚁群优化算法，显著拓展了蚁 群优化算法在处理连续空间问题中的求解能力。 总体来说，本文从蚁群优化算法的数学模型着于，证明了算法的收 敛性，并据此提出了三种创新算法，通过实验证明了这些算法的有效性 和实川性。本义的研究充实了蚁群优化算法的理论基础，丰富了算法的 一n 1 上海变通大学博士学位论文 应用能力，对于蚁群优化算法的发展具有一定的理论和现实意义。 关键词：p 难问题，现代启发式算法，蚁群优化算法，收敛性，计 算复杂性 英文摘要 a n tc o l o n yo p t i m i z a t i o na n di t sa p p l i c a t i o n s a b s t ra c t c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mi sa l li m p o r t a n th a u c ho fo p e r a t i o nr e s e a r c h ， m a n yp r a c t i c a lo p t i m i z a t i o np r o b l e m sc a nb ed w n i b c d ac o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m , i t sa p p l i c a t i o ni n c l u d e sal m g en u m b e ro fs u b j e c t s 。s u c ha s ；v m d u c t i o nl a y o u t ， c o m m u n i c a t i o na n dt r a n s p o r t a t i o n , e n c i g ye x p l o r a t i o n , o p t i m i z e dd o s i g n , e c o n i cd i - s o n b l l s i e 锆m a n a g e m e n t ，m m o p o l i t a ne o n s m l c t i o n , p u b l i cp r o j e c t , a 面c i l l 咄l a y o u t ，s o - s o u r c ea l l o c a t i o n , i n f o r m a t i o nh a n d l i n g ，a n dm i l i t a r yd e c i s i o nc t cs o ，t h es t u d yo f s o l u t i o n m e t h o d s t oc o m b i n a t o r i a l o p t i m i z a t i o n h a s i t s t h e o r e t i c a l a n d p r a c t i c a l i m p o r t a n c e t h ec o m p u t a t i o n a lc o m p l e x i t yt h e o r yp r o v e st h a tm a n yc o n l b i n a t o r i a lo p t i m i z a t i o n i sa p - h a r d , w h i c hm e n u st h a tt h ec o m p u t a t i o n a lt i m en e e d e df o rs o l v i n gt h e s ep r o b l e m si s c x p o n v n t i a le n l a r g e d t h es c a l eo f t h ep r o b l e mi n c r e a s e s b a u s eo f t h eh i g h l yd e v e l o p e d i n f o r m a t i o n t e c h n o l o g y , t h ed i f f i c u l t y a n ds c a l e s o f t h e r e a l w o r l d c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e ma r ei n c r e a s i n gr a p i d l yt h en o r m a lo p e r a t i o nr e s e a r c hm e t h o d sa r cn ol o n g e ra b l e t os o l v et h e s ep r o b l e m si na na c c e p t a b l et i m e t h u sc o i l l e st h er e q u i r e m e n to f a p p r o x i m a t a a l g o r i t h m sw i t hp o l y n o m i a lc o m p u t i n gt i m e c 眦饥t l y , av a s ts t u d yo f t h ea p p r o x i m a t ea l g o r i t h m sr e s u l to f s ts e r i e so f s u c c e s s f u l m o d e r no p t i m i z a t i o nm e t h o d s ，w h i c hi sa l s oc a l l e dm e t a - h e u r i s t i c s , i n c l u d i n gt a b us e a r c h ， s i m u l a t e da n n e a l i n g 。目脚n c l w 毗kc o tc o l o n yo p t i m i z a t i o i l , a n dp a r t i c l es w a r mo p t i m i z a - t i o ne t o t h em a i ns t u d ys u b j e c to f t h i sd i s s c r t a f i c oi sa n tc o l o n yo p t i m i z a t i o n a n tc o l o n yo l v t i m i z a t i o ni sar e c e n t l yd e v e l o p e ds w k i t ni n t e l l i g e n c ea l g o r i t h m ，w h i c hc o m e sf r o mt h ei m i - t a t i o r l o f t h e p m h - f i n d m g a b i l i t y o f r e a la n t s s o i t i sa l s oa k i n d o f a r t i f i c i a l i n t e l l i g e n c et h e s t i l d yo f n a t u r a ls c i e n c ef i n d st h a ta n t sr e l e a s eak i n do f c h e m i c a l ，c a l l e dp h a r o m o n e ，o nt h e p a t h s 血e yp a s s e d a n t s ep h e r o m o n ea sam e d i af o rc o m m u n i c a t i o nc o dc o o p e r a t i o n ，a n d a p p e a r s a w h o l ea sa t le m e r g e n c y i n f a c t p h e m m s t n er e p r e s e n t s a k i n do f d i s t r i b u t e d i n - f o r m a t i o n a b o u t t h e p r o b l e ms o l v i n g p r o c e s s ，a n d i s a k i n d o f “p e i e n c e a c c t m m l a t e d d u t i n g t h ep r o b l e ms o l v i n gp r o c e s s t h ea n tc o l o n yo p t i m i z a t i o ni m i t a t e st h i sp h e s o l n o n er e l e a s i n g c o df o l l o w i n gb e h a v i o rt oe s t a b l i s hi t ss p e c i a lo p t i m i z a t i o ns y s a m a 一v 一 上海变通人学博士学位论文 a n tc o k m yo p t i m i z a t i o nh a sr a i s e dg r ta t t e n t i o ns i n c ei t sb i r t h m a n yl i t e r a t u r es h o w i t sa d v a n t a g e s a n d d e g r e e o f a t t e m i o n s o f a r , a n t c o l o n y o p t i r n i z z t i o n h a s b e e ns u c c e s s f u l l y a p p l i e dt om a n yc o m b i n a t o r i a lp r o b l e r m ，b u tt h e ma r cs t i l ls o m eo b v i o u si n s u f f i c i e n c yi n c n r r e a rs t u d y , w h i c hi n c l u d e s ：( 1 ) t h ee s t a b l i s h m e n to f t h em a t h e m a t i c a lm o d e la n dr e l a t i v e t h e o r e t i c a ls t u d yi sn o tc o m p l e t e ( 2 ) s o l u t i o nq u a l i t yo fa n tc o l o n yo p t i m i z a t i o ni st ob e i m p r o v e d ( 3 ) 1 kd e p t ha n ds c o p eo f a p p l i c a t i o n si st ob ee x t e n d e d ( 4 ) t h ei n f l u e n c ea n d r e s e a r c hs t r e n g t ho f a n tc o l o n yo p t i m i z a t i o ni st ob ee n h a n c e & t h er e s e a r c ho ft h i sd i s s e r t a t i o nt ot h ea n tc o l o n yo p t i m i z a t i o nf o c u s e so nt h r e ea s p e e r s ：( i ) a l g o r i t h m m o d e la n d t f l e o r jo f c o n c a r g e n c e ( 2 ) t h e i m p r o v e m e n t a n d i n n o v a t i o n o fn e wa l g o r i t h m s ( 3 ) e x t e n d i n go fa p p l i c a t i o nd e p t ha n ds c o p e i na s p e c to fa l g o r i t h m m o d e la n dc o n v e r g e n c et h e o r y , t h i sd i s s e r t a t i o nd e s c r i b e st h ei t e r a t i o np r o c e s so f a n tc o l o n y o p t i m i z a t i o na sat i m e - h o m o g e n e o u sm a r k n vp r o c e s s p r o v e st h ec o n v e r g e n c eo f a n tc o l o n y o p t i m i z a t i o nb yu s i n gs t a t i o n a r yd i s t r i b u t i o np r o h a b i l i t yt h e o r y , a n dd i s c u s st h ef a c t o r st h a t i n f l u e n c et h ec o n v e r g e n c es p e e d i nt h ea s p e c to fa l g o r i t h mi m p r n v m u e n ta n di n n o v a t i o n , t h i sd i s s e r t a t i o np r a i s e st h r e en e wa l g o r i t h m s ：f i r s t l y , w ei n u o d u c ct h ea n n e a l i n gs y s t e m i n t oa n tc o l o n y o p t i m i z a t i m x a n d f o r m a d w a l g o r i t h mc a l l e d s a c o ；s e c o n d l y , w e p r o p o s e 8 b i n a r ya n tc o l o n y o p t i m i z a t i o n , b a s ，i n d e a l m g w i t h b i n a r y o p t i n n z a t i o n p r o b l e m s f i n a l l y , w c p r o p o s ea d i r e c t a n tc o l o n y o p t i m i z a t i o n ( i ) a c o ) i n d e a l i n g w i t h o p t i m i z a f i o n p r o b l e m s i nc o n t i n u o u sd o r r m mi nt h ea s p e c to f a p p l i c a t i o n , w ei m p r o v et h es o l v i n gc a p a b i l i t yo f o n t c o l o n yo p t i m i z a t i o ni nt r a v e l i n gs a l e s m a np r o b l e ma n dm u l u d i m e n s i o n a lk n a p s a c kp r o b - e m ，a p p l y t h e a n t c o l o n y o p t i m i z a t i o n f o r t h e f i r s t t i m e i nb i n a j yo p t i n n z a t i o n p r o b l e m ，a n d b r e a k t h r o t i 吐t h er e s t r i c t i o n a n d p o o r p c r f o r n m n e e o f a n t c o l o n y o p t i m i z a t i o n i n c o n t i n u o u s d o m a i n s p e c f i c a l k t h e m a i n r e s e a r c hw o r k a n dc o n a i b u t i o n o f t h i s d i s s e r t a t i o n i n c l u d e s ： 1 b r i e f l yi n t r o d u c e st h ec o m b i n a t o r i a lo p t i m i z a t i o na n di t ss o l v i n gm e t h o d s ，d e m o n - s t r a t e s t h e n e c e s s i t y o f u s i n g p o l y n o m i a la p p r o x i m a t ea l g o r i t h m s i n d e a l i n g w i t h n 7 - h a r d p r o b l e m s ，a n ds u m m a r i z e ss o m e m a r e m c t a - h e a r i s t i c i n s o l v i n g n f - h a r d p r o b - l e m s 2 g t v c sad e t a i lr e v i e wa b o u tt h eo r i g m , d e v e l o p m e n ta n da p f l i c a r i o no fa l q tc o l o n y o p t i m i z a t i o n , p o i n t so u ts o m ei n s u i f c i e n c yi nc u r r e n tr e s e a r c hw o r k , a n dp r o p o s e s s t o n mm a n i p u l a b l e 删o l l sf o rf n r t h e sr e s e a r c h 3 e s t a b l i s h e st h ea l g o r i t h mm o d e lo f a n tc o l o n yo p t i m i z a t i o nb yu s i n gm a r k o vt h e o r y , a n dp r o v e st h ec o n d i t i o n a lc o n v e r g e n c eo fa n tc o l o n yo p t i m i z a t i o n ：i np r c r n i s eo f i n - f i n i t ei t e r a t i o nn u m b e r s ，t h o s ea n tc o l o n yo p t i m i z a t i o nh a v i n ge l i t ea n ts t r a t e g ya n d 一一 英文摘要 p h e r o m o n el i m i ts y s t e mw i l lh a v eap r o b a b i l i t yo f1c o n v e r g i n gt ot h eo p t i m a b u s e d o n t h i s p r o v e ，t h i s d i s s e r t a t i o n d i s c u s s e s t h e f a c t o r s t o i n f l u e n c e t h e e o n v e l g e n c es p e e d ， e n d c o n c l u d e s t h a t ：( i ) t h e a n t c o l o n y s c a l e d u e s n o t a f f e c t t h e c o n v e r g e n c e ，b u t a f f e c t s t h ec o m p u t a t i o n a ls p e e d 但) i n c o r p o r a t i o n o f a l o c a ls e s r o h i n a n t c o l o n y o p t i m i z a t i o n d o e si n c t e a s et h ec o n v e r g e n c es p e e d ( 3 】t h ep h e o r f l o l l eu p d a t es t r a t e g ya n dr e l a t i v e p a r a m e t e rs e t t i n gm a y a f f e c tn o t a b l yt h ec o n v e r g e n e as p e e do f a n tc o l o n yo p t i m i z a - t i o n , b u t t h ea f f e c te f f o r ti sn o ta s c e r t a i n e d 4 i n l r o d u c e sa na n n e a l i n gs y s t e mi n t oa n tc o l o n yo p t i m i z a t i o n , a a df o r m sun e wh y b r i d a l g o r i t h mc a l l e ds a c os a c oi sa b l et oe c e e p rs t o c h a s t i c a l l yi n f e r i o rs o l u t i o n sf o r t h ep h e r o m o n eu p d a t ep r o c e s s , t h u si n c o r p o r a t e sas y s t e mo f j u m p i n go u to f al o c a l o p t i m a , w h i c he n l a r g e st h es e a r c ha “a sd u r i n gt h ei n i t i a ls t e p so fi t e r a t i o n se x t r a m e n t a lr e 自l l s i n t r a v e l i n gs a l e s m a n p r o b l e ms h o w t h a t s a c oo b v i o u s l y n l c t e a s e s t h e s o l v i n ga b i l i i yo f a n tc o l o n yo p t i m i z a t i o ni nd e a l i n gw i t ht h i sk i n do f p r o b l e r n s 5 d e s i g n sab i n a r ya t l tc o l o n yq 砌m i n m o d e l ，c a l l e db a s ，i nd e a l i n gw i t hb i n a r y o p t h n i z a t i o np r o b l e m s ，a n da n a l y z e st h ec o n v e r g e n c ec h a r a c t e r i s t i c so f t h ea l g o r i t h m i nb a s ，p h a o l t l o n ef i r ed i r e c t l yp u to n t ot h es e l e c t i n gp a t h sf o re a c hv a r i a b l e a n d f 疆e s 锄t t h e s e l e c t i n g p r o b a b i l i t i e s d u e t 0 8s p e c i a l f h e r o m o n e u p d a t e s 昀妲融w h i c h g r e a t l yd e l t e u s e st h ec o m p u t a t i o nt i m e a p p l i c a t i o no f b a si nb i n a r yf u n c t i o no p t i - m i z a t i o n p r o b l e m a n d m u l t i d i m e n s i o n a l k n a p s a c k p r o b l e ms h o w t h ee f f e c t i v e n e s sa n d p r a c f i c a b i l i t yo f b a s 6 a n tc o l o n yo p t i m i z a t i o nh a ss o m ed i f l = i c u 崎i nd e a l i n gw i t ho p t i m i z a t i o np r o b l a n m i nc o n t i n u o u sd o m a i n t h i sd i s s e r t a t i o nd e s i g n sas p e c i a la n tc o l o n yo p t i m i z a t i o n , c a l l e dd a c 0 ，i nc o n t i n u o u sd o m a i n d a c 0l i s t sn o r m a ld i s t r i b u t i o na st h es e l e c t i n g p r o b a b i l i t yf o re a c hv a r i a b l eb yp u t t i n gp h t o t n o n ed i r e c t l yo f tm e a ne n dv a r i a n c e d a c oi sa b l et of i n dt h eo p t i m aq u i c k l ya n de f f e c t i v e l yw i t ht h eh e l po fas p e c i f i c 曲e r o m o n eu p d a t es t r a t e g ye x p e r i m e n t a lr e s u l t si nc o n t i n u o u sf t m c t i o no p t i m i z a t i o n p r o b l e m p r o v e t h e c a p a b i l i t y o f d a c o i n d e a l i n g w i t h p r o b l e m s i n c o n t i n u o u s d o m a i n , a n d t h er e s u l t s a g ec o m p a r a b l e t o o t h e rs t a t e - o f - a n m m - h e u r i s t i c s t h e i n n o v a t i v e p o i n t s o f t h i sd i s s e r t a t i o n h a v e f o u r a s p e c t sa s f o l l o w i n g ： i t h i sd i s s e r t a t i o n p r o v e s t h ec o n v e r g e n c e o f a n t c o l o n y o p t i m i z a t i o n b y u s i n g m a r k o v p r o c e s s ，a n d d i s c u s s e s t h e c o n v e r g e n c ec h a r a c t e r i s t i c s o f t h e a l g o r i t h m ，c o n c l u d e s w i t h s o m ef a c t o r sa f f e c t i n gt h ec o n v e r g e n c es p e e d 一 上海交通大学博士学位论文 2 b yi n c o r p o r a t i n gt h ea n n e a l i n gs y s t e mi n t oa t l tc o l o n yo p t i m i z a t i o n , t h i sd i s s e r t a t i o n i n t r o d u c e sal o c a lo p t i m aa v o i d a n c es y s t e mi n t ot h ea l g o r i t h m ，a n dt e s t i f i e si t se f f e c - f i v e n e s sb ye x p e r i m e n t s 3 t m sd i s s e r t a t i o ni n t r o d u c e sab i n a r ym o d e lo f a n tc o l o n yo p t i m i z a t i o na n dd i s c u s s e s i t se o n v e r g e n o ec h a r a c t e r i s t i c s ，p e r i m t a ir e s u l t ss h o wt h ep r a c t i c a l 时o f t h ea l g o - r i t h m 4 1 1 i i sd i s s e r t a t i o nd e s i g n sa n e wc o n t i n u o u sa n tc o l o n yo p t i m i z a t i o n , n o t a b l ye x p a n d s t h ea p p l i c a t i o na b i l i t yo f a n tc o l o n y o p t i m i z a t i o n i nd e a l i n g w i t ho p t i m i z a t i o n p r o b - l e m si nc o n t i n u o u sd c m a i n o v e r a l l ，t h i sd i s s e r t a t i o ns t a r t sf r o mt h em a t h e m a t i c a lm o d e lo fa n tc o l o n yo p t i m j z a - t i o n , p r o v e si t sc o n v e r g e n c e , p r o p o s e st h r e en c wi n n o v a t i v ea l g o r i t h m s ，a n dt e s t i f i e st h e i r e f f e c t i v e n e s sa n dp r a c t i c a l n yt h r o u g he x p e r i m e n t so nv a r i o u so p t i m i z a t i o np r o b l e m st h e c o n t r i b u t i o no f t h ed i s s e r t a t i o ne n h a n c e st h et h e o r e t i c a lb a s e m e n to fa n tc o l o n yo p t i m i z a - t i o n ，e n r i c h e st h ei n n o v a t i o na n da p p l i c a t i o na b i l i t yo f t h ea l g o r i t h m a n di ss i g n i l i g a n tb o t h i nt h e o r ya n da p p l i c a t i o nf o rt h ed e v e l o p m e n to f a n tc o l o n yo p t i m i z a t i o n k e yw o r d s ：, w p - h a r dp r o b l e m , m g t a - h e u r i s t i g s ，a n tc o l o n yo p t i m i z a t i o n , c o m e r - g c n c e ，c o m p u t a t i o n a lc o m p l e x i t y 插图 1 1 论文结构图 插图 2 1 各类问题的假设关系圈 2 2 简单禁忌搜索算法 2 3 模拟退火算法 2 4 遗传算法基本流程图 2 5 二进制粒子群优化算法基本流程图 3 1 取桥实验 3 2 蚁群优化算法基本流程图， 模拟退火算法的算法流程， a c s 算法的算法流程 s a c o 算法的计算复杂性分析， $ a c o 参数设置：平均值与最优值的百分比误差随t m 罅的变化趋势图 b a s 的算法流程 二进制蚁群优化算法解的结构 b a s 中蚂蚁的行走路线图， 参数m 的测试结果， 修改算子的伪代码 参数p 的实验结果 p s o p 的算法流程 p s o r 的算法流程 p s o r 和p s o - p 的性能比较 i f 态分布的特征 c f 设置的实验结果 参数m 的测试结果 参数p 的测试结果 i 一 6 ”m 拇饥” 拍 弱卯印拍 加饥=2盯鲥s： 盼：兮 s ” “配们“甜的卵矾的 他 上海交通大学博士学位论文 表格 2 1 多项式和指数时间复杂性函数的速度比较 2 2 现代启发式算法， 3 1 蚁群优化算法的发展历程 3 2 蚁群优化算法在路径问题中的应用