（计算机软件与理论专业论文）多态蚁群算法研究及其应用.pdf

山东师范人学顺 学位论文 多态蚁群算法研究及其应用 摘要 蚁群算法是2 0 世纪9 0 年代初期提出的一种新型模拟进化算法，其思想吸收了真实蚂 蚁的行为特性，通过模拟真实蚁群搜索食物的过程来完成对问题的求解。它采用有记忆的 人工蚂蚁，通过个体间的信息交流与相互协作找到从蚁穴到食物源的最短路径。这种方法 是由意大利学者d o r i g om 等人首先提出的，他们称之为蚁群系统( a n tc o l o n ys y s t e m ， a c s ) 。根据蚁群算法的特点用该算法求解旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、 指派问题( a s s i g n m e n tp r o b l e m ) 、j o b - s h o p 调度问题等等一系列经典问题，经证明取得了 系列较好的实验结果，蚁群算法现己广泛应用到很多领域。 多态蚁群算法是在针对蚁群算法收敛速度慢、容易陷入局部最优等缺点的基础之上， 通过对蚁群社会的仔细研究发现，真实蚁群社会中的所有蚂蚁不仅各司其职，而且相互依 赖、相互协作，相互之间形成一个有机的整体。在执行某项任务时，个体之间会通过各自 分泌的信息素相互联系、相互协作。这罩的“多态性 是指蚁群社会所具有多种状态的蚂 蚁群体及信息素。根据分工的不同将蚂蚁分为：侦察蚁、搜索蚁和工蚁，各种蚂蚁各司其 职。其中，侦察蚁群负责局部侦察，搜索蚁群负责全局搜索。这种改进大大提高了蚂蚁群 体之间的合作效果，增强了算法的有效性。 模拟退火算法是1 9 8 2 年由s k i r k p a t r i c k 等人提出的一种模拟金属退火机理而建立的随 机优化方法。它是源于对固体退火过程的直接简单模拟而建立的一种通用随机搜索技术， 具有较强的局部搜索能力，并能避免陷入局部最优解。j 下是由于这种优势的存在，人们成 功地将该思想引入组合优化理论，近年来该算法引起了大规模优化设计、数值分析、复杂 布局等领域广泛的重视。 本文对蚁群算法尤其是多态蚁群算法进行了较为系统地分析和研究，提出了三种改进 的算法，并将改进的多态蚁群算法应用到复杂迷宫的路径求解中，主要包括以下一些内容： ( 1 ) 蚁群算法的概述。介绍了蚁群算法的研究背景及其意义、算法的功能、思想来 源、国内外研究现状以及典型应用等等。 ( 2 ) 蚁群算法的研究。介绍了蚁群算法的三种基本模型，蚁群算法最早应用到旅行 商问题当中，简要介绍了旅行商问题，及蚁群算法基于旅行商问题的实现步骤以及算法复 杂度分析。 l 山东! j l i j 抱人学硕i 学位论文 ( 3 ) 多态蚁群算法的模型与实现。介绍了多态蚁群算法提出的背景，多态蚁群算法 的模型，多态蚁群算法存在的不足。 ( 4 ) 基本蚁群算法及多态蚁群算法的改进。基于基本蚁群算法和多态蚁群算法存在 的不足，提出了三种改进的蚁群算法：自适应调整挥发系数的逆向蚁群算法、基于模拟退 火算法的多道逆向蚁群算法和基于信息素扩散的多态蚁群算法。试验结果证明改进的算法 提高了收敛速度和寻找到最优解的能力。 ( 5 ) 结合蚁群算法在寻找最优路径上的优势，将改进后的多态蚁群算法运用到复杂 迷宫的求解最优路径当中。理论分析和试验结果证明该算法能较好的找到最优路径。 关键词：蚁群算法；多道蚁群算法；逆向蚁群算法：模拟退火：多念蚁群算法 分类号：t p 3 0 1 6 2 i j i 东师范人学硕i j 学位论文 m u l t i p l ea n tc o l o n ya l g o r i t h m sr e s e a r c ha n da p p l i c a t i o n a b s t r a c t a n tc o l o n ya l g o r i t h mi san e wt y p eo fs i m u l a t e de v o l u t i o n a r ya l g o r i t h mi nt h ee a r l y9 0 s ， w h i c ha b s o r b e dt h ei d e ao ft h eb e h a v i o ro fr e a la n t s ，b ys i m u l a t i n gt h er e a la n tc o l o n y ss e a r c h i n g f o rf o o dt oc o m p l e t et h ep r o c e s so fs o l v i n gt h ep r o b l e m i tu s e sa r t i f i c i a la n t s ，w h i c hh a v e m e m o r i e s ，t of i n dt h es h o r t e s tp a t ht of o o ds o u r c et h r o u g ht h ee x c h a n g eo fi n f o r m a t i o nb e t w e e n i n d i v i d u a l sw i t hm u t u a lc o o p e r a t i o nf r o mf o r m i c a r y t h i sm e t h o di sf i r s t l yp r o m o t e db ys e v e r a l s c h o l a r si n c l u d i n gd o r i g omf r o mi t a l i a n t h e yn a m e di tt h ea n tc o l o n ys y s t e m ( a c s ) b a s e d o nt h ec h a r a c t e r i s t i c so fa n tc o l o n ya l g o r i t h m ，s o l v i n gas e r i e so fc l a s s i c a lp r o b l e m sl i k e t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，a s s i g n m e n tp r o b l e ma n dj o b - s h o ps c h e d u l i n gp r o b l e mc a l l l e a dt oas e r i e so fc e r t i f i e dg o o dl a b o r a t o r yt e s tr e s u l t s t h u s ，t h ea n tc o l o n ya l g o r i t h mi sw i d e l y u s e di nt h ef i e l d b a s e do nt h ea n tc o l o h ya l g o r i t h m sw e a k n e s sl i k es l o wc o n v e r g e n c ea n dv u l n e r a b l e ，a l s o t h r o u g ht h ec a r e f u ls t u d ya b o u ta n tc o l o n ys o c i e t y , t h es t u d yo fp o l y m o r p h i ca n tc o l o n y a l g o r i t h mf o u n dt h a ti nt h er e a la n tc o l o n ys o c i e t y , d e s p i t ea l lt h ea n t sp e r f o r mt h e i rr e s p e c t i v e d u t i e s ，t h e y s t i l ln e e dm u t - a a lc o l l a b o i a t i o nt of o r mi n t o a n o r g a n i ci n t e g r i t y i n t h e i m p l e m e n t a t i o no fat a s k ，i n d i v i d u a l sa r ei n t e r l i n k e da n dm u t u a l l yc o o p e r a t i v et h r o u g ht h e i r s e c r e t i o no fp h e r o m o n e s p o l y m o r p h i s m r e f e r st oav a r i e t yo fa n ts o c i e t yt h a ti sw i t hv a r i o u s s t a t u s e so fg r o u p so fa n t sa n dp h e r o m o n e a c c o r d i n gt ot h ed i f f e r e n td i v i s i o no fl a b o r s ，a n t sw i l l b ed i v i d e di n t or e c o n n a i s s a n c ea n t ，s e a r c ha n dw o r k e ra n t s ，a n dt h e yw i l lp e r f o r mt h e i r r e s p e c t i v ed u t i e s a m o n gt h e m ，t h er e c o n n a i s s a n c ea n ti sr e s p o n s i b l ef o rl o c a ls u r v e i l l a n c e r e c o n n a i s s a n c e ，a n ds e a r c ha n ti sr e s p o n s i b l ef o rg l o b a ls e a r c h t h i sc a ng r e a t l ye n h a n c et h e e f f e c t i v e n e s so fc o o p e r a t i o nb e t w e e ng r o u p s ，a n dc a ne n h a n c et h ee f f e c t i v e n e s so ft h ea n tc o l o n y a l g o r i t h ma sw e l l s i m u l a t e da n n e a l i n ga l g o r i t h mi sp u tf o r w a r db ys k i r k p a t r i c ki n19 8 2 i ti sas t o c h a s t i c o p t i m i z a t i o nm e t h o d ss e tu pb ys i m u l a t i n ga n n e a l i n gm e c h a n i s mo fm e t a lw h i c hi sd e r i v e df r o m s i m p l ys i m u l a t i n gt h ea n n e a l i n gp r o c e s so fs o l i dt o s e tu po fac o m m o nr a n d o ms e a r c h t e c h n o l o g yt h a th a ss t r o n gl o c a ls e a r c ha b i l i t y , a n dc a na v o i df a l l i n gi n t ol o c a lo p t i m a ls o l u t i o n b e c a u s eo ft h ee x i s t e n c eo fs u c ha d v a n t a g e s ，i ti ss u c c e s s f u l l yi n t r o d u c e di n 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 nt h e o r y i nr e c e n ty e a r s ，i tc a u s e daw i d er a n g eo fg r e a ti m p o r t a n c ei na r e a ss u c hi l l s l a r g e s c a l eo p t i m i z a t i o na l g o r i t h md e s i g n ，n u m e r i c a la n a l y s i sa n dt h ec o m p l e xl a y o u t m o r es y s t e m a t i ca n a l y s i sa n dr e s e a r c ho fa n tc o l o n ya l g o r i t h m ，e s p e c i a l l ym u l t i p l ea n t 1 山东师范入学倾l j 学位论文 c o l o n ya l g o r i t h m sa r ep r o p o s e di nt h i sp a p e r t h r e ei m p r o v e da l g o r i t h m sa r ep r o p o s e da n d a p p l i e dt os o l v et h ec o m p l e xm a z eo ft h ep a t h t h es p e c i f i cr e s e a r c ha n di n n o v a t i o na r e 鹪 f o l l o w s ： ( 1 ) t h eo v e r v i e wo ft h ea n tc o l o n ya l g o r i t h m i ti si n t r o d u c e dt h er e s e a r c hb a c k g r o u n da n d s i g n i f i c a n c eo ft h ea n tc o l o n ya l g o r i t h m ，i t sf u n c t i o n s ，i t si d e o l o g i c a ls o u r c e ，i t sr e s e a r c ha th o m e a n da b r o a d ，a sw e l la si t st y p i c a la p p l i c a t i o n s ，a n ds oo n ( 2 ) t h er e s e a r c ho ft h ea n tc o l o n ya l g o r i t h m t h r e eb a s i cm o d e l so ft h ea n tc o l o n y a l g o r i t h ma lei n t r o d u c e d t h ea n tc o l o n ya l g o r i t h mh a sb e e nf i r s ta p p l i e dt o t h et r a v e l i n g s a l e s m a np r o b l e m i ti sb r i e f l yi n t r o d u c e dt h et r a v e l i n gs a l e s m a np r o b l e m ，r e a l i z a t i o ns t e p so f t h ea n tc o l o n ya l g o r i t h mb a s e do nt h et r a v e l i n gs a l e s m a np r o b l e m ，a sw e l la sa n a l y s i so f a l g o r i t h mc o m p l e x i t y ( 3 ) t h em o d e la n di m p l e m e n t a t i o no ft h em u l t i p l ea n tc o l o n ya l g o r i t h m i ti si n t r o d u c e dt h e b a c k g r o u n do f t h em u l t i p l ea n tc o l o n ya l g o r i t h m ，t h em o d e lo ft h em u l t i p l ea n tc o l o n ya l g o r i t h m ， a sw e l la si t si n a d e q u a c i e s ( 4 7t h eb a s i ca n tc o l o n ya l g o r i t h ma n dt h ei m p r o v e dm u l t i p l ea n tc o l o n ya l g o r i t h m a c c o r d i n gt oi n a d e q u a c i e so ft h eb a s i ca n tc o l o n ya l g o r i t h ma n dt h ei m p r o v e dm u l t i p l ea n t c o l o n ya l g o r i t h m ，t h r e ei m p r o v e da l g o r i t h m sa r ep r o p o s e d ：c o n v e r s ea n ta l g o r i t h mb a s i so f a d j u s ti n f o r m a t i o ne l e m e n th a n g o v e rc o e f f i c i e n t ，m u l t i p l ec o n v e r s ea n tc o l o n ya l g o r i t h m b a s e do ns i m u l a t e da n n e a l i n g , a sw e l la sp o l y m o r p h i ca n tc o l o n ya l g o r i t h mb a s e do n p h e r o m o n ed i f f u s i o n t e s tr e s u l t so ft h ei m p r o v e da l g o r i t h ma r ep r o v e dt oi m p r o v i n gt h e c o n v e r g e n c es p e e da n dt h ec a p a c i t yt of i n d i n gt h eo p t i m a ls o l u t i o n ( 5 ) c o m b i n e da d v a n t a g e so ft h ea n tc o l o n ya l g o r i t h mi nt h es e a r c hf o r t h eo p t i m a lp a t h ，t h e i m p r o v e dm u l t i p l ea n tc o l o n ya l g o r i t h mi sa p p l i e dt os o l v et h eo p t i m a lp a t hp r o b l e mo ft h e c o m p l e xm a z e t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mc a nf i n d t h eo l g t i m a lp a t h k e y w o r d s ：a n tc o l o n ya l g o r i t h m ；m u l t i p l ea n tc o l o n ya l g o r i t h m s ；c o n v e r s ea n ta l g o r i t h m ； s i m u l a t e da n n e a l i n g ；p o l y m o r p h i ca n tc o l o n ya l g o r i t h m c l a s s i f i c a t i o n ：t p 3 0 1 6 4 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特 别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：垂i l 风 导师签 川。 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权主 楚可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：凰 导师 签字日期：2 0 09 年歹月j 岔日 签字眺2 。夕咖f 貊 ：i 东师范人学坝f j 学位论文 1 1 研究背景及意义 第一章绪论 自然界中的许多自适应优化现象不断给人们以启示，自然生态系统和生物体可通过自 身的演化使许多在人类看起来高度复杂的优化问题得到完美的解决。自然界是人类创造力 的丰富源泉，人类认识事物的能力来源于与自然界的相互作用之中。近年来，与经典数学 规划原理截然不同、试图通过模拟自然生态系统机制以求解复杂优化问题的一些仿生优化 算法相继出现( 如遗传算法、蚁群算法、微粒群算法、人工免疫算法、人工鱼群算法、混 合蛙跳算法等等) ，这些算法不仅大大丰富了现代技术，而且也为那些传统优化技术难以 处理解决的组合优化问题提供了切实可行的解决方案。随着模拟生物机理与自然为特征的 仿生优化算法时代的悄然兴起，一些仿生优化算法已在经典n p 困难问题的求解和实际应 用中显示出了强大的生命力和进一步的发展潜力。 生物学家通过对蚂蚁的长期观察研究发现，单只蚂蚁的智能并不高，看起来没有集中 的指挥，但它们却能协同工作、集中食物、建造坚固漂亮的蚁穴并抚养后代，依靠群体能 力发挥出超出个体的智能。蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 是最新发展的一种模 拟昆虫王国中蚂蚁群体智能行为的仿生优化算法乜3 ，具有较强的鲁棒性、优良的分布式并 行计算机制、易于与其他方法结合等优点。妇h 1 。蚁群算法也是一种新型的启发式模拟进化 算法，虽然刚问世不久，但在解决许多复杂优化问题方面已显示出了特有的明显优势。其 应用范围非常广泛，例如可以应用该算法来解决交通网络中的最佳路径选择问题哺3 ，电信 网络中的流量负载分配等问题。 目前，蚁群算法也已成功地在通讯、交通及人工智能等领域中得到应用，最突出的是 求解n p 困难的组合优化问题。d o r i g om 等在最初提出蚁群算法时，利用t s p 问题与蚁群 觅食的相似性，运用了正反馈原理和分布式算法，通过模仿蚂蚁的行为解决了t s p 这个具 有典型代表的组合优化问题。随后，他们又相继利用蚁群算法解决了二次指派问题、车间 调度等问题，并做了大量的实验研究，试验结果表明，该算法具有明显的优越性。 虽然蚁群算法具有非常多的优点，但由于是一种新兴的算法，不免存在一些问题。首 先，它还远不像其它的启发式算法那样已经形成系统的分析方法和具有坚实的数学基础， 它的发展远没有形成完整的理论体系，许多理论问题和实际运用问题还有待于逐步解决， 1 山东卿范人学坝l j 学位论文 如算法模型、算法的收敛性、理论依据等。其次，到目前为止，参数的选择更多的还是依 靠实验和经验，没有定理来确定，而且它的计算时间偏长。再次，其在理论和实践方面尚 有许多问题需要更深入的研究与解决。 计算机技术的飞速发展一方面促进了优化方法的不断发展，但另一方面也使工程优化 问题同趋大型化，优化目标函数也变得越来越复杂。传统的优化方法一般很难找到这种大 型优化问题的全局最优解，因为传统的优化方法存在着许多缺点如：较强的限制性，一般 对目标函数都有较强的限制性要求( 如连续、可微、单峰等) ，在目标函数较为复杂的情况 下，要满足这一要求是很困难的，有时甚至是不可能的；初始值的选取，一般初始值的选 取对计算结果影响较大，不同的初值可能导致不同的差异较大的结果；大多数优化方法都 是根据目标函数的局部展开性质来确定下一步搜索方向的，这与求函数的整体最优解的目 标有一定的抵触；算法智能性和鲁棒性较差，对于具体优化问题需要选择具体的方法；算 法的理论可解性无法在计算机上具体实现，即方法设计过于复杂，具体实现起来较为困难。 伴随着改革开放的不断深入，我国社会经济的发展和国家综合实力的迅速增长，我国 的大型复杂结构有了长足的发展，各种类型的大型机械结构和系统、大跨度桥梁、大跨度 空间建筑结构和超高层建筑结构不断涌现。特别是进入二十一世纪后，中国经济快速发展， 各种大型复杂结构不但需求大大的增加了，而且结构的规模也同趋大型化。因为大型复杂 结构建造、营运及维护的费用都很高，所以对大型复杂结构的全局优化设计具有显著的经 济效益。 一般来说，蚁群算法主要用于求解不同的组合优化问题，主要存在两类应用：一类应 用于静态组合优化问题，另一类用于动态组合优化问题。静态问题指一次性给出问题的特 征，在解决问题过程中，问题的特征不再改变，这类问题的范例就是经典旅行商问题。动 态问题被定义为一些量的函数，这些量的值由隐含系统动态设置，因此问题在运行时问内 是变化的，而优化算法需要在线适应不断变化的环境，这类问题的典型例子是网络路由问 题。研究表明，蚁群算法已经成为解决多点路由、电网布线的一种较为有效的方法。此外， 蚁群算法还在光谱分析、露天采矿边坡临界滑动面搜索、酮群施工等多种场合得到了应用， 而且都得到了比较理想的效果。 1 2 国内外研究现状 2 1 、理论研究现状 人们从生物进化机理中受到启发，2 0 世纪5 0 年代中期出现了仿生学，提出许多如遗 山东师范：学烦i j 学位论文 传算法、进化规划、进经策略等用以解决复杂优化问题的新方法。这些对生物群落行为的 发现及以生物特性为基础演化算法的发展，引导着研究人员进一步开展对生物社会性的研 究，从而出现了基于群智能理论的蚁群算法1 ( 意大利d o r i g om ，m a n i e z z ov ，c o l o r n ia 等) 和粒子群算法( 1 9 9 5 ，j a m e sk e n n e y 和r u s s e lle b e r h a r t ) 。 1 9 9 1 年d o r i g om 最早提出了蚁群优化算法一蚂蚁系统( a n ts y s t e m ，a s ) 并将其应 用于解决计算机算法学中经典的旅行商问题( t s p ) 。从蚂蚁系统开始，基本的蚁群算法得 到了不断的发展和完善，并在t s p 以及许多实际优化问题求解中进一步得到了验证。这些 a s 改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差 异仅在于搜索控制策略方面。而且，取得了最佳结果的a c o 是通过引入局部搜索算法实现 的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各 级系统在优化问题中的求解质量。 最初提出的a s 有三种版本：a n td e n s i t y 、a n tq u a n t i t y 和a n tc y c l e 乜1 。在a n td e n s i t y 和a n tq u a n t i t y 中蚂蚁在两个位置节点间每移动一次即更新信息素，而在a n tc y c l e 中 、 当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素 被表达为反映相应行程质量的函数。通过与其他各种通用的启发式算法相比，在不大于7 5 城市的t s p 中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，a s 的解题能力大幅度下降，因此，其后的a c o 研究工作主要都集中于a s 性能的改进方面。 较早的一种改进方法是精英策略( e 1 i t i s ts t r a t e g y ) n 1 ，其思想是在算法开始后即对所有 己发现的最好路径给予额外的增强，并将随后与之对应的行程记为t g b ( 全局最优行程) ， 当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”， 从而增大了较好行程被选择的机会。这种改进型算法虽能够以更快的速度获得更好的解， 但若选择的精英过多则算法会由于较早的收敛于局部最优解而导致搜索的过早停滞即出 现“早熟”现象。 为了进一步克服a s 中暴露出的问题，文献 7 中提出了蚁群系统( a n tc o l o n ys y s t e m ， a c s ) 。该系统的提出是以该文作者较早提出的a n tq 算法m 3 为基础的。a n tq 将蚂蚁算法 和一种增强型学习算法ql e a r n i n g 有机的结合了起来，a c s 与a s 之间存在三方面的主要 差异： 首先，a c s 采用了更为大胆的行为选择规则。 其次，只增强属于全局最优解的路径上的信息素，即： 勺( t + 1 ) = ( 卜p ) 乃( t ) + p a 妒( t ) 。 3 山东帅范人学颂l ：学位论义 其中，带( f ) = 形驴；o p l 是信息素挥发参数；是从寻路开始到当前为止全局最 优路径长度。 最后，引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上 信息素都被相应的消除一部分，从而实现一种信息素的局部调整以减小已选择过的路径再 次被选择的概率。 乃= ( 1 一孝) 勺+ 弘r o ，0 孝 1 在对a s 进行直接完善的方法中，m a x m i na n ts y s t e m 是一个典型代表1 。该算法修 改了a s 的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更 好的解。为了避免搜索停滞，路径上的信息素浓度被限制在 f 。 范围内，另外，信 息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力。 另一种对a s 改进的算法是r a n kb a s e dv e r s i o na s n 蚰与“精英策略”相似，在此算法 中总是更新更好进程上的信息素，选择的标准是其行程长度( ( f ) r ( t ) l ( f ) ) 决定 的排序，且每个蚂蚁放置信息素的强度通过排序加权处理确定。 其中巧= ，铲( f ) = 夕刍，朋为每次迭代后放置信息素的蚂蚁总数。 肘 勺( f + 1 ) = ( 1 一p ) 勺( f ) + ( 万一) 巧+ m a r 萝b ( f ) 。 r = l 这种算法求解t p s 的能力与a s 精英策略a s 遗传算法和模拟退火算法进行了比较，在 大型t s p 问题中( 最多包含1 3 2 座城市) ，基于a s 的算法都显示出了优于a g 和s a 的特性， 而且在r a n kb a s e da s 和精英策略a s 均优于基本a s 的同时，前者还获得了比精英策略a s 更好的解。 多态蚁群算法更加与现实蚁群社会先接近。算法种引进了三种蚁群：侦察蚁群、收索 蚁群、工蚁群，各种蚁群有不同的信息素调控机制。试验结果表明，算法有更好的收敛性 和寻找最优解的能力。 2 、应用研究现状 随着群智能理论和应用算法研究的不断发展，研究者己尝试将其用于各种工程优化问 题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中 均表现出良好的搜索效果，并在组合优化问题中表现突出。 蚁群优化算法为解决组合优化问题提供了新思路，并很快被应用到除t s p 以外的其他 组合优化问题中，其中比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典 4 山东9 - 9 范人学倾l ：学位论文 的组合优化问题。蚁群算法在电信路由优化中电已经取得了一定的应用成果2 1 n 制，h p 公司和英国电信公司在9 0 年代中后期都丌展了这方面的研究，并设计了蚁群路由算法( a n t c o l o n yr o u t i n g ，a c r ) 。每只蚂蚁根据它在网络上的经验与性能就像蚁群优化算法中一样， 动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟， 那么就对该表项做较大的增强，同时根据信息素挥发机制实现系统的信息更新，进而使其 抛弃过期的路由信息，这样，在当前最优路由出现拥堵现象时，a c r 算法就能迅速的搜寻 另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用 研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异 步演化与a c o 的算法本质和特性非常相似。 l u m e r 和f a i e t a 将d e n e u b o u r g 提出将蚁巢分类模型应用于数据聚类分析引，起源于 对蚁群蚁卵的分类研究，基本思想是首先将待聚类数据随机地散布到一个二维平面内，然 后将虚拟蚂蚁分布到这个空问内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时 即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置标准则 将其放置在该位置，然后继续移动，重复上述数据搬运过程，按照这样的方法可实现对相 似数据的聚类。 文献 1 6 中提出了一种利用蚁群算法设计的数据分类规则提取算法。利用蚂蚁的运 动，根据通过随机搜索逐步形成相对应规则的前件和数据属性的划分，在蚁群算法的搜索 方法中定义了适合分类问题的规则构造方法、剪枝方法和信息素更新方法。该算法采用与 c 4 5 相似的墒值度量方法，并将其与信息素更新机制结合起来进行以消除墒值度量的局限 ( 局部启发性度量) 引起的误差。与典型的分类算法c n 2 相比，这种方法的准确性与c n 2 相 当，且发现的规则列表比c n 2 获得的简单。 另外，a c o 还在许多经典组合优化问题中获得了成功的应用，如二次规划问( q a p ) l i t 1 s 、 机器人路径规划、作业流程规划、图着色( g r a p hc o l o r i n g ) 等问题。经过多年来的发展， a c o 己成为能够有效解决实际二次规划问题的几种重要算法之一。a s 在作业流程计划( j o b s h o p ss c h e d u li n g ) 问题中的首个应用实例出现在文献 1 9 中，该论文说明了a s 在此领域 的应用潜力。其后的文献 2 0 利用m a x - m n ia s 解决队q a p 取得了比较理想的效果，并通 过实验中的计算数据证明采用该方法处理q a p 比较早的a s 算法更好，且与禁忌搜索算法 性能相当。文献 2 1 中利用a o c 实现了对生产流程和特料管理的综合优化，并通过与遗传、 模拟退火和禁忌搜索算法的比较证明了a c o 的工程应用价值。 此外，许多研究者还将a c o 用于了武器攻击目标分配和优化问题乜2 1 、车辆运行路径规 5 山东蛳范人学坝l ：学位论文 划2 3 1 、区域性无线电频率自动分配1 、b a y e s i a nn e t w o r k s 的训练3 和集合覆盖用优化问 题拉6 1 。c o s t a 和h e r z 还提出了一种a s 在规划问题方面的扩展应用图着色问题，并取 得了可与其他启发式算法相比的效果。 蚁群算法理论的应用方法研究证明，虽然相对于各种比较成熟的计算智能方法蚁群算 法的研究还处于初级阶段，并存在种种有待深入研究和解决的问题，但可以预言群智能的 研究代表了以后计算机研究发展的一个重要方向。 1 3 本文的主要内容及组织结构 1 3 1 主要内容 结合上面所阐述的研究背景和研究现状，本文的研究内容是实现对蚁群算法的改进， 特别是在详细分析了现有多态蚁群算法不足的基础上，对多态蚁群算法进行改进。蚁群算 法中参数的选取及信息素的调整对算法的性能影响很大，因此结合均匀设计思想对提出的 改进算法进行了合理的参数设置和寻优路径上的信息素的调整。根据以上内容，本文的主 要研究工作如下： 第一，分析基本蚁群算法和多态蚁群算法在搜索路径时存在的不足。通过理论分析， 基本蚁群算法和多态蚁群算法在进行路径搜索时收敛速度慢和有时候易限于局部最优解。 第二，针对基本蚁群算法存在的不足，本文提出了自适应调整挥发系数的逆向蚁群算 法和基于模拟退火算法的多道逆向蚁群算法。 第三，针对多态蚁群算法存在的不足，提出一种改进算法基于信息素扩散的多态蚁群 算法。 第四，结合蚁群算法在寻找最优路径上的优势，将改进后的多态蚁群算法运用到复杂 迷宫求解最优路径当中。 1 3 2 本文组织结构 本文共分为六章，各章的主要内容如下： 第一章绪论。介绍了蚁群算法的研究背景及意义、当前国内外研究现状，并给出了本 文的主要内容及组织结构。 第二章蚁群算法。内容包括：基本蚁群算法概念、模型以及算法实现，并简单分析了 6 山东帅范人学硕i ：学位论奠 基本蚁群算法的优缺点。 第三章多态蚁群算法。介绍了多态蚁群算法的模型和实现，分析了多态蚁群算法的不 足。 第四章基本蚁群算法及多态蚁群算法的改进。针对基本蚁群算法的不足，提出了自适 应调整挥发系数的逆向蚁群算法和基于模拟退火算法的多道逆向蚁群算法，针对多态蚁群 算法的不足，提出基于信息素扩散的多态蚁群算法。 第五章是改进的多态蚁群算法在迷宫最短路径问题中的应用。将改进后的多态蚁群算 法用于求解复杂迷宫中最优路径问题。 第六章结束语。对本文的研究成果进行概括并指明今后的研究方向。 7 山东9 巾北人学帧i j 学位论文 2 1 引言 第二章蚁群算法 蚁群算法是由意大利学者d o r i g om 等人1 9 9 1 年首先提出的一种新型模拟进化算法， 他们称之为蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 比 ，其思想吸收了真实蚂蚁群体的行为特 性，通过模拟真实蚁群搜索食物的过程来完成对问题的求解。算法中采用有记忆的人工蚂 蚁，通过个体问的信息交流与相互协作找到从蚁穴到食物源的最短路径。将该方法用于求 解旅行商问题( t r a v e li n gs a l e s m a np r o b l e m ，t s p ) 、指派问题( a s s i g n m e n tp r o b l e m ) 、 j o b - s h o p 调度等问题，取得了一系列较好的实验结果。本章将详细分析蚁群算法基本概念、 模型及与本文研究相关的基础知识。 2 2 蚁群算法的基本原理 2 2 1 蚁群算法概述 蚂蚁是社会性昆虫，觅食行为是蚁群一个重要而有趣的行为。虽然单只蚂蚁的行为极 其简单，但由大量的蚂蚁个体组成的蚂蚁群体却表现出极其复杂的行为，能够完成复杂的 任务。据科学家的观察和研究发现，蚂蚁在没有任何可见提示下有能力找出从蚁穴到食物 源的最短路径，并且能随环境变化适应性地搜索新的路径，产生新的选择。根据蚁群的这 一智能行为，科学家们提出了智能型的优化算法蚁群系统。 蚁群系统的第一个应用是旅行商问题，之所以选择旅行商问题，原因有二：一是因为 旅行商问题为大家所熟悉、易懂，是n p 问题；二是旅行商问题较容易阐明蚁群优化算法 的原理。下面就以旅行商问题为例来说明其原理。 2 2 2 旅行商问题 旅行商问题汹3 ，就是指旅行商按一定的顺序访问n 个城市的每个城市，使得每个城市 都被访问且仅能被访问一次而使花费的代价最小，用图论的观点来看，就是找出一个最短 的封闭路线。 9 山东师范人学硕l j 学位论爻 假设有1 3 个城市，( f ，) 表示城市f 与城市之间的连接( 在对称t s p 的情况下，l ( j ，f ) 与其含义相同。否则，表示城市，到城市i 之间的连接) ，d 。表示城市f 与城市，之问的距 离，那么我们可以将其描述成图g = ( c ，三) ( 其中c 表示城市的集合，l 表示城市间连接( 即 边) 的集合) 。那么，t s p 问题用图论的观点来说，就是从图g 中找出一条可行的优化路径， 这个路径也叫做该问题的一个解。当然，所有的可行的解必须满足其限定条件，在t s p 问 题中就是每个城市都必须被访问一次且仅被访问一次。 2 2 3 蚂蚁算法 假设6 ( f ) ( f = 1 ，2 ，z ) 为蚂蚁在时间，在城市f 的数目，聊= 岛( f ) 为蚂蚁的总数目，每 f = 1 只蚂蚁具有如下特征： ( 1 ) 选择下一个待访问的城市要以连接这两个城市间的距离和留在该边上的信息素 强度构成的概率函数作为依据； ( 2 ) 禁止蚂蚁访问已被访问过的城市，从而使蚂蚁走过的路径形成一个可行的解； ( 3 ) 当它访问了所有的城市后，才在每条已被访问的边( f ，) 上释放信息素；乇( f ) 为 边在t 时刻的信息素强度，在每一时刻每只蚂蚁都要选择下一个合法的城市，当时刻t + 甩完 成后，所有的蚂蚁都走遍了所有的城市，此时系统信息素强度的修改公式出式( 2 1 ) 所示： 乃( f + ，1