（计算机应用技术专业论文）基于分布均匀度的改进蚁群算法.pdf

基于分布均匀度的改进蚁群算法 摘要 论文题目 专业 硕士生 指导教师 基于分布均匀度的改进蚁群算法 计算机应用技术 卢栩茵 肖菁讲师 摘要 作为一种新型的群集智能算法，蚁群算法从2 0 世纪9 0 年代提出至今，被广 泛应用予求解复杂的组合优化问题，如调度问题、t s p 问题等，取得了比较好的 效果。然而蚁群算法自身也存在着不足之处：蚁群搜索的随机性容易导致全局搜 索效率低、收敛速度慢；信息素的正反馈性容易导致在搜索后期，所有个体寻找 到的解完全一致，算法不能对解空间进一步地搜索，不利于发现全局最优解甚至 更好解等等。 针对以上这些缺陷，为了解决蚁群算法加速收敛和早熟停滞现象这对矛盾， 本文在基于分布均匀度的蚁群算法【l 】提出的“聚度思想的基础上进行了改进， 提出了基于分布均匀度的改进蚁群算法，主要进行了两方面的改进： ( 1 ) 、自适应选择策略。在选择策略中，在基于分布均匀度的蚁群算法【l 】 的基础上重新定义了“城市聚度 、“选择窗口等概念，构造了一种具有自适应 功能的状态转移策略。 ( 2 ) 、自适应信息素更新策略。在信息素更新策略中，采用全局更新( 基于 蚁周模型) 和局部更新( 基于蚁密模型) 相结合的方式，并在局部更新时提出信 息素影响因子递减的思想，既结合了t s p 问题自身的特点，又能够根据解的分 布均匀程度自适应地调整信息素更新策略，保证了算法在搜索后期的高质量。首 先，将“城市聚度 引入信息素影响因子的计算中，使得算法能够根据解的实际 分布状况动态地调整信息素更新策略；其次，通过控制信息素影响因子，相对地 减少后程搜索的信息素增加量，从而减少非优路径对后继搜索的影响，使得算法 在搜索后期能有更大的可能跳出局部最优，达到提高算法整体的搜索性能的目 的。 论文的实验部分利用多种不同规模的对称t s p 问题( t r a v e l i n gs a l e s m a n 基于分布均匀度的改进蚁群算法 摘要 p r o b l e m ) 进行验证。实验结果表明，改进后的蚁群算法在整个算法运行期间能 够在有效提高搜索效率，加快收敛速度的同时较好地防止早熟、停滞现象，使算 法不易陷入局部最优解，且算法所求解具有较好的稳定性，能够固定在一个较小 的好的区间内，保证了所求解的质量。 关键词：蚁群算法，分布均匀度，优化，旅行商问题 基于分布均匀度的改进蚁群算法 a b s t r a c t t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： a ni m p r o v e da n tc o l o n ya l g o r i t h mb a s e do i l e q u i l i b r i u mo f d i s t r i b u t i o n c o m p u t e ra p p l i c a t i o na n dt e c h n o l o g y l ux u y i n x i a oj i n g ( l e c t u r e r ) a b s t r a c t s i n c ei tw a si n t r o d u c e di n 1 9 9 0 s ，a n tc o l o n ya l g o r i t h m ，an e ws w a r m i n t e l l i g e n c ea l g o r i t h m ，h a sb e e nw i d e l ya p p l i e di ns o l v i n gc o m p l e xc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，s u c ha ss c h e d u l i n gp r o b l e m ，t r a v e l i n gs a l e s m a np r o b l e ma n d s oo n ，w h i c hh a sa c h i e v e df a i r l yg o o dr e s u l t s h o w e v e ra n tc o l o n ya l g o r i t h mi t s e l f a l s oh a ss o m ed e f i c i e n c i e s f o re x a m p l e ，t h er a n d o m n e s so ft h es e a r c hl i k e l yc a u s e sa l o we f f i c i e n c yi n g l o b a ls e a r c h a n das l o ws p e e do fc o n v e r g e n c e ；t h ep o s i t i v e f e e d b a c ko fp h e r o m o n ee a s i l yr e s u l t si nt h ef a c tt h a ti nt h el a t t e rp e r i o d ，t h es o l u t i o n s t h a ta l lt h ea n t sh a v ef o u n da r ee x a c t l yt h es a l n e ，a n dt h ea l g o r i t h mc a nn o tk e e po na f u r t h e rs e a r c hi nt h es o l u t i o ns p a c es ot h a ti t su n l i k e l yt of i n do u tt h eg l o b a lo p t i m a l s o l u t i o ne v e nab e t t e ro n e i no r d e rt os e t t l et h ec o n t r a d i c t o r yb e t w e e nc o n v e r g e n c es p e e da n dp r e c o c i t ya n d s t a g n a t i o ni na n tc o l o n ya l g o r i t h m ，a ni m p r o v e da n tc o l o n ya l g o r i t h mb a s e do nt h e e q u i l i b r i u mo fd i s t r i b u t i o n i s p r e s e n t e d ，w h i c hi so nt h eb a s i so ft h ei d e ao f e q u i l i b r i u mo f d i s t r i b u t i o np r o p o s e di na n a d a p t i v ea n tc o l o n ya l g o r i t h mb a s e d o n e q u i l i b r i u mo fd i s t r i b u t i o n t l l c o m p a r e dw i t hg e n e r a la n tc o l o n ya l g o r i t h m ，t h e m e t h o dr a i s e di nt h i sp a p e rh a st w o k e yp o i n t so fi m p r o v e m e n t s ( 1 ) a d a p t i v e s e l e c t i o n s t r a t e g y o n t h eb a s i so fa na d a p t i v ea n tc o l o n y a l g o r i t h mb a s e do ne q u i l i b r i u m o fd i s t r i b u t i o n 【l 】“a g g r e g a t i o nl e v e lo f c i t y ”a n d “s e l e c t i o nw i n d o w ”a r er e d e f i n e d t oc o n s t r u c ta l li m p r o v e d a l g o r i t h mw h i c hc a na d j u s tt h es e l e c t e dp r o b a b i l i t i e so ft h ep a t h sa c c o r d i n g l y ( 2 )a d a p t i v ep h e r o m o n eu p d a t i n gs t r a t e g y t h ei m p r o v e da l g o r i t h mh a sa i i i 基于分布均匀度的改进蚁群算法 a b s t r a c t c o m b i n e dw a yo fu p d a t i n gt h eq u a n t i t yo fp h e r o m o n e ，g l o b a lp h e r o m o n e u p d a t i n g ，b a s e do na n t - c i r c l es y s t e m ，a n dl o c a lp h e r o m o n eu p d a t i n g ，b a s e d o na n t - d e n s i t ys y s t e m m o r e o v e r , t h e “p h e r o m o n ei m p a c tf a c t o r i sl e di n t o l o c a lp h e r o m o n eu p d a t i n gt oe n s u r et h eh i g hq u a l i t yo fa n t ss e a r c h i n gi nt h e l a t t e rp e r i o d ，w h i c hn o to n l yc o n s i d e r st h ec h a r a c t e r i s t i c so ft r a v e f i n g s a l e s m a np r o b l e m ，b u ta l s oh e l p sa d j u s tt h ep h e r o m o n eu p d a t i n gs t r a t e g y b a s e do nt h ee q u i l i b r i u mo ft h es o l u t i o n st h ea n t sf o u n dd u r i n gt h ep r o c e s so f s e a r c h i n ga d a p t i v e l yf i r s to fa l l ，t h e “a g g r e g a t i o nl e v e lo fc i t y i sa p p l i e di n c a l c u l a t i n gt h e p h e r o m o n ei m p a c tf a c t o r s o t h a tt h e a l g o r i t h mc a n d y n a m i c a l l ya d j u s tt h ep h e r o m o n eu p d a t i n gs t r a t e g yb a s e do nt h ee q u i l i b r i u m o ft h es o l u t i o n st h ea n t sf o u n dd u r i n gt h ep r o c e s so fs e a r c h i n g s e c o n d l y , b y c o n t r o l l i n gt h e “p h e r o m o n ei m p a c tf a c t o r ，t h ea l g o r i t h md e c r e a s e st h e q u a n t i t yo fu p d a t e dp h e r o m o n ei nt h el a t t e rh a l fc o m p a r a t i v e l y i nt h i sw a y , t h en e g a t i v ei n f l u e n c eo fn o n - o p t i m a lp a t h sc a nb er e d u c e ds oa st oa v o i dt h e o c c u r r e n c eo fp r e c o c i t ya n ds t a g n a t i o na n da c h i e v eas a t i s f a c t o r yp e r f o r m a n c e e x p e r i m e n t sh a v eb e e np u to nd i f f e r e n ts c a l e so ft s p st ov e r i f yt h ev a l i d i t ya n d c o r r e c t n e s so ft h ei m p r o v e da l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e i m p r o v e da n tc o l o n ya l g o r i t h mc a nm a i n t a i nag o o db a l a n c eb e t w e e na c c e l e r a t i n g c o n v e r g e n c ea n da v e r t i n gp r e c o c i t ya n ds t a g n a t i o n i na d d i t i o nt ot h a t ，i th a sm u c h h i g h e rs e a r c h i n ge f f i c i e n c ya n ds t a b i l i t yt h a nt h a to fg e n e r a la n tc o l o n ya l g o r i t h m a n dt h es o l u t i o n si tf o u n dc a nb ef i x e di nas m a l lr a n g ea r o u n dg l o b a lo p t i m a l s o l u t i o n ，w h i c hi sag u a r a n t e eo ft h eq u a l i t yo ft h es o l u t i o n s k e y w o r d s ：a n tc o l o n ya l g o r i t h m ，e q u i l i b r i u m o f d i s t r i b u t i o n ，o p t i m i z a t i o n ， t r a v e l i n gs a l e s m a np r o b l e m i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：卢桐刁囟 i妒 日期：2 研d 年6 月1 日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：步栩司函 日期：z df d 年6 月1 日月1 日 基于分布均匀度的改进蚁群算法第一章引言 1 1 研究背景 第一章引言 在经历了一段较长的繁荣期之后，由于无法摆脱经典计算思想的束缚，人工 智能领域的研究又一次面临着严峻的挑战。与此同时，人类对生物本质的探究逐 步深入，生命科学正以前所未有的速度高速发展着。因此，人工智能领域的科学 家们不断尝试从对生物系统的研究中获得灵感，并通过模拟自然生态机制，去获 取解决复杂计算问题的新方法【2 】。 二十世纪八十年代以来，一些与经典的数学规划原理截然不同的、试图通过 模仿自然界的内在机制来求解复杂优化问题的新型智能优化方法相继被提出1 2 1 。 例如，通过对动物神经网络的模拟提出了人工神经网络的算法模型；通过对达尔 文自然界进化理论的研究，提出了遗传算法；通过对飞禽行为的观察，提出了启 发式粒子群优化算法；基于生物免疫抗体产生记忆系统的学习机理，提出了人工 免疫算法等等 2 】。蚁群算法就是在这样的大背景下应运而生，登上了计算机科学 研究的世界舞台。 大量细致的生物研究表明，群蚂蚁能够通过相互配合，找到食物源和巢穴 之间的最短路径，而单只蚂蚁却无法完成。在寻找食物的过程中，蚂蚁个体间通 过信息素( p h e r o m o n e ) 这一化学物质进行信息传递【3 1 。蚂蚁能够感知和释放信 息素，并根据信息素浓度的差异来选取路径。因此，蚁群的行为就表现出一种信 息的正反馈效应：某一路径上经过的蚂蚁越多，该路径的信息素浓度越高，则后 继蚂蚁选择该路径的概率也就越大【2 】。 2 0 世纪9 0 年代初，意大利著名学者m a c r od o r i g o ，m a n i e z z o 与c o l o r n i 正 是受到了蚁群觅食行为( f o r a g i n gb e h a v i o r ) 的启发，提出了一种基于信息素的 间接通信机制的新型群集智能算法蚂蚁算法( a n ta l g o r i t h m ) 【4 ，5 1 。该算法 通过模拟自然界蚂蚁觅食的行为，将蚂蚁搜索的随机性、信息素分泌等元素融入 到了问题的求解过程中。 基于分布均匀度的改进蚁群算法第一章引言 1 1 1 蚁群算法的发展历程 在1 9 9 6 年，m a c r od o r i g o 等人在i e e et r a n s a c t i o n 上发表论文( ( a n ts y s t e m ： o p f i m i z a t i o nb y a c o l o n yo f c o o p e r a t i n ga g e n t s 6 1 , 文中首先论述了蚁群算法的机 制原理和数学模型，并将其与遗传算法等启发式算法进行了仿真实验比对；其次 将蚁群算法的应用扩展到了非对称t s p 问题、指派问题和调度问题，并且对蚁 群算法中参数的初始化设置对算法性能的影响做了初步的分析与讨论【6 1 ，为蚁群 算法的发展奠定了基础。 在1 9 9 9 年的学术报告和2 0 0 0 年的学术论文7 ，8 1 中，w j g u t j a h r 等人在一些 假设性的前提下，首次给出了蚁群算法的收敛性证明，在蚁群算法的发展史上具 有重大的意义。 从2 0 0 0 年m a c r od o r i g o 和e b o n a b e a u 等人首次在国际顶尖学术刊物 ( ( n a t u r e ) ) 上发表蚁群算法的研究综述开始，蚁群算法领域的研究开始走向国际 学术前沿回。 如今，在国内外众多学术期刊和国际会议上，蚁群算法已经成为了一个备受 关注的热点和前沿性课题。 1 1 2 蚁群算法的优点 蚁群算法是一种有效的群集智能搜索算法，其具备的主要优点有： ( 一) 、并行分布式计算。在求解问题的过程中，蚁群在问题空间中独立搜 索，同时构造问题的多个可行解体现了算法的并行性( 并行因子等于蚂蚁种群大 小) 。在求解复杂的组合优化问题时，计算量一般较大，并行计算模式可以显著 地减少计算时间。 ( 二) 、正反馈性。在搜索问题解的过程中，前导蚂蚁不断释放信息素引导 后继蚂蚁，通过这种信息交流，不断强化最优路径的信息，在一定程度上加快了 算法的收敛速度以及进化进程。 ( 三) 、健壮性。首先，蚁群算法的搜索结果不依赖于初始线路的选择；其 次，在搜索的过程中，算法不会因为个别蚂蚁搜索到劣质解或者问题空间发生改 变而失去效用；再次，只要对基本蚁群算法的数学模型稍作修改，便可以将其应 2 基于分布均匀度的改进蚁群算法 第一章引言 用于求解其它问题【2 】。以上三点都体现了蚁群算法的强鲁棒性。 ( 四) 、无需进行人工干预。相对于模拟退火算法这些需要进行人工调整的 算法，蚁群算法可以独立完成从初始化到获得搜索结果的整个计算过程。 1 1 3 蚁群算法的缺陷 虽然蚁群算法具备许多优点，是一种有效的随机搜索算法，但是这种算法也 存在着一些缺陷。 ( 一) 、搜索效率低，耗时长。对蚁群算法进行复杂度分析可知，蚁群算法 的时间复杂度为o ( m n 2 t ) ( 其中m 为蚂蚁的数量，1 1 为所求问题的规模，t 为算 法的迭代次数) ，这是因为在寻路的过程中，每只蚂蚁独立运动，因而算法运行 总时长与蚁群数量密切相关。当蚂蚁种群数量变大时，要使所有蚂蚁都搜索出一 条完整的路径需要耗费大量的时间【9 】。除此外，信息素的初期积累时间过长也是 导致蚁群算法运算效率低下的原因之【2 】。 ( 二) 、易出现早熟、停滞现象，陷入局部最优。基本蚁群算法在搜索进行 到一定阶段后，所有个体寻找到的解完全一致，算法不能对解空间进一步地搜索。 事实上，在基本蚁群算法中，后继蚂蚁只是单纯依赖前导蚂蚁提供的反馈信息， 不进行自身的经验积累，这样的盲从行为，是导致算法出现早熟、停滞现象的根 本原因【9 】。 ( 三) 、问题规模增大时，求解能力显著下降。以t s p 问题为例，算法的计 算复杂度主要产生于解的构造过程。因此，随着问题规模的增大，算法所消耗的 时间将以n 次幂的速度激增。除了性能下降，求解质量下降的原因在于随着问 题规模的增大，解空间迅速膨胀，因此很难在给定的终止条件内寻求到全局最优 解。 ( 四) 、算法的数学模型较薄弱。对于不同类型和规模的问题，参数选择往 往要依赖于人工经验和实验值，参数选择尚无规律性可言，不具有科学性。除此 外，算法的收敛性也是在定的假设条件下得到的一些初步证明【2 】。 基于分布均匀度的改进蚁群算法 第一章引言 1 2 研究现状分析 作为国内外启发式算法的研究热点和前沿课题，从研究方向来说，蚁群算法 的研究大致可分为理论性研究和应用性研究两种类型。 理论性研究主要包含两部分：一是针对算法本身的缺陷进行改进，并在此基 础上提出新的算法；二是针对蚁群算法理论本身进行研究，如收敛性的研究、参 数选择的研究等等。应用性研究则是将成熟的蚁群算法应用于工业、农业等不同 的领域，以帮助解决实际的问题【l o 】。 下面分别从算法的改进研究、算法的应用研究、算法的性能研究三个方面来 分析国内外学者研究蚁群算法的现状。 1 2 1 算法的改进研究 ( 一) 、针对早熟、停滞，易于陷入局部最优的缺陷的研究 国外研究现状 在1 9 9 6 年，德国学者s t u t z l et 和h o l g e rh 提出了一种最大一最小蚂蚁系统 ( m a x - m i n a n ts y s t e m ，m m a s ) 算法，通过将信息素浓度限定在特定范围内， 避免了算法过快地收敛于局部最优解，同时通过平滑机制，使得算法在搜索后期 能有更大的可能跳出局部最优，获得全局最优解1 1 4 3 】；在1 9 9 9 年，b u l l n h e i m e r 等人提出了基于优化排序的蚂蚁系统( r a n k - b a s e d a n ts y s t e m ，a s 础) 算法，该 算法在每次迭代后，都会将蚂蚁的搜索路径依次排列，并根据不同解的质量赋予 不同的权重，最后根据解的级别对信息素进行差异化更新，有效地提高了算法的 全局搜索能力1 4 1 。 国内研究现状 在2 0 0 0 年，王颖和谢剑英提出了一种自适应调整信息素挥发因子的蚁群算 法，旨在通过自适应地调整信息素挥发因子来提高算法的全局搜索能力【1 5 j ；在 2 0 0 6 年，柯良军等人提出了一种新型蚁群算法有限级信息素蚁群算法 f g a c o ，先将信息素分为有限个级别，然后利用级别的更新来实现对信息素的 更新1 6 】；在2 0 0 8 年，王健等人提出了全局自适应蚁群优化算法g a o ，该算法基 4 基于分布均匀度的改进蚁群算法第一章引言 于自适应参数的思想，对信息素更新策略和状态转移策略进行了改进，并在一定 程度上克服了参数设置对手求解问题的敏感性，提高了算法的全局优化能力1 7 1 。 ( 二) 、针对算法搜索效率低的缺陷的研究 国外研究现状 在1 9 9 6 年，l m g a m b a r d e l l a 与m a c r od o n g o 提出了新的蚁群算法a n t - q s y s t e m ，该算法利用伪随机比例状态转移规则替代蚂蚁算法中的随机比例选择规 则，在每次迭代中让信息素浓度最高的路径以较大的概率被选中，强化了最优路 径的反馈信息，使得蚁群算法能够迅速收敛，极大地提高了算法的搜索效率【1 8 ， 1 9 】 o 国内研究现状 在2 0 0 1 年，吴斌、史忠植提出了一种将相遇算法与分段算法相结合的新型 蚁群算法，其基本思想是在求解t s p 问题时，由两只蚂蚁共同完成对一条路径 的搜索，通过并行策略，极大地提高了蚂蚁单次巡游的质量和速度 2 0 1 ；在2 0 0 4 年，黄国锐等人提出了一种改进型蚁群算法，该算法通过引入信息素扩散的思想， 提高了算法的性能【2 1 1 ；在2 0 0 7 年，姚宝珍提出了一种自适应的并行蚁群算法 a p a c o ，该算法在不同的搜索阶段，自适应确定参数的最佳组合，在一定程度 上提高了算法的搜索效率2 2 】。 ( 三) 、结合其他启发式算法的研究 除了对蚁群算法自身进行改进，许多学者还在蚁群算法的基础上引入其它启 发式算法或仿生优化算法的思想，通过算法的相互融合，提高了蚁群算法的性能， 取得了相当丰硕的研究成果。 国外研究现状 在1 9 9 8 年，h m b o t e e 等人利用遗传算法求得蚁群算法在求解t s p 问题的 某个实例时，基本参数m ，n ，p ，p 的最优组合，极大地提高了蚁群算法的性能【2 3 l ； 在2 0 0 0 年，l m g a m b a r d e l l a 与m a c r od o r i g o 提出了一种混合型蚁群算法h a s ， 算法的基本思想是：在每代的搜索过程中，蚂蚁首先建立各自的解，然后以该解 为起点采用某种局部搜索策略搜索局部最优解，并以此作为蚂蚁当代搜索的最终 解【冽；同年，c o r d o n 等人提出了一种新型的蚁群算法b w a s ，该算法引入进化 计算中基于群体的增强型学习技术瞄】，且通过对每一次迭代中生成的最差解实 5 基于分布均匀度的改进蚁群算法第一章引言 施惩罚，使每代所求解逐步趋向于全局最优解闭。 ； 国内研究现状 在1 9 9 9 年，吴庆洪和张纪会等人提出了一种具有变异特征的蚁群算法，通 过有机地结合2 - o p t 算子，加快了算法的收敛速度，节省了计算时间【2 7 1 ；在2 0 0 7 年，黄美玲和白似雪提出了一种将蚁群算法和人工神经网络相结合的算法，在用 于求解t s p 问题时，引入交叉策略进行预处理，实质将t s p 问题转化为求解无 向完全图的一条h a m i l t o n 回路的问题幽1 。 1 2 2 算法的应用研究 国外研究现状 在1 9 9 4 年，c o l o m i 等人将蚁群算法应用于求解j s p ( j o b - s h o ps c h e d u l i n g p r o b l e m ，车间作业调度问题) 问题5 】；在1 9 9 9 年，v m a n i e z z o 等人又将蚁群算 法应用于求解q a p ( q u a d r a t ic a ss i g n m e n tp r o b l e m ，指派问题) 问题；在这之 后，c o s t a 和h e r z 提出了一种增强型的蚁群算法，并将其应用于求解分配类型的 问题，该算法在求解图着色问题时，所得结果完全可以和其它启发式算法的结果 相媲美【l o 】。除了以上领域，蚁群算法在通讯网络领域，特别是解决网络路由问 题方面，受到越来越多的学者关注。在1 9 9 8 年，d i c a r o 和d o r i g o 将蚁群算法应 用于求解网络路由问题，并将该算法命名为a n t n e t 算法 2 1 。 除了学术领域的研究，h p 公司和英国电信公司在2 0 世纪9 0 年代中后期都 开展了蚁群算法在电信路由方面的研究，设计了蚁群路由算法( a n tc o l o n y r o u t i n g ，a c r ) 2 1 。 国内研究现状。 在2 0 0 3 年，汪镭等人将蚁群算法应用于求解系统参数辨识问题，通过定义 信息素分布函数和相应的系统辨识求解算法，成功地解决了线性系统参数辨识问 题 2 9 1 ；在2 0 0 5 年，刘志硕等人在分析v r p ( v e h i c l er o u t i n gp r o b l e m ，车辆路径 问题) 问题与t s p 问题的相同性与差异性的基础上，将蚁群算法应用于求解v r p 问题，对蚁群算法的转移策略和信息素更新策略进行了改进，构造了一种具有自 适应功能的蚁群算法【蚓；在2 0 0 9 年，葛连升等人在蚁群算法正反馈机制的基础 上提出了一种基于树的新型蚁群算法，并用于求解度约束组播路由问题，通过模 6 基于分布均匀度的改进蚁群算法第一章引言 拟分析证明了该算法在求解度约束组播路由问题方面的有效性3 1 1 。 1 2 3 算法的性能研究 相对于算法的改进研究和应用研究，蚁群算法的性能研究要稍微滞后一些， 但同样取得了相当丰硕的研究成果。相关理论研究有： 国外研究现状 在1 9 9 9 年撰写的学术报告和2 0 0 0 年发表的学术论文中，w j g u t j a h _ r 等人在 一些假设性的前提下，首次给出了蚁群算法的收敛性证明，极大地推动了蚁群算 法的发展【7 1 。在2 0 0 0 年发表的学术论文ag r a p h - b a s e da n ts y s t e ma n di t s c o n v e r g e n c e 中，g u o a l r 从有向图论的角度提出了种基于图的蚁群系统框架 g b a s ( g r a p h - b a s e da n ts y s t e m ，图搜索蚂蚁系统) ，并通过理论证明，在 一定条件下，g b a s 蚁群算法每次迭代所得解都能以近似于1 的概率收敛到全局 最优解i s ，对于蚁群算法的发展具有里程碑式的意义；在2 0 0 2 年，s t u t z l et 和 m a c r od o r i g o 针对具有组合优化性质的极小化问题提出了一种简化的蚁群算法， 并利用该算法证明了当迭代次数趋于无穷时，算法总能搜索到全局最优解3 2 】； 在2 0 0 3 年，b a d r 等人利用蚁群算法与b r p ( b r a n c h i n gr a n d o mp r o c e s s ，分枝随 机过程) 过程的相似性，证明了蚁群算法的收敛性【3 3 1 ；在2 0 0 4 年，b l u m 等人讨 论并提出了基于h c f ( h y b e r - c u b ef r a m e w o r k ，超立方体框架) 框架的蚁群算法， 该框架通过将信息素浓度限定在 0 ，1 】之间，增强了蚁群算法的鲁棒性【卅。 国内研究现状 在2 0 0 3 年，孙焘等人将遗传算法与蚁群算法进行了融合，并在给定近似精 度的基础上从m a r k o v 随机过程的角度，对所提出的蚁群算法的收敛性进行了分 析，同时，通过对衰减度、变异率等参数的定性讨论，得出初始参数的设置会对 算法性能造成明显影响的结论，同时从理论上证明了，传统蚁群算法通常所采用 的选择概率公式是存在缺陷的【3 5 】；在2 0 0 4 年，段海滨等人以m a r k o v 链和离散 鞅为研究工具，对基本蚁群算法的a s ( a l m o s ts u r e l y ) 收敛性问题进行了理论 证吲的】。 7 基于分布均匀度的改进蚁群算法第章引言 1 3 研究的目标与意义 鉴于实际工程问题中存在的复杂性、约束性、建模困难等特点，寻找一种适 合于求解复杂问题的智能优化算法已经成为科学研究的一个重要方t 9 j 。虽然对 于蚁群算法的研究仅不到二十年，但是所有初步的研究都显示出蚁群算法在求解 复杂组合优化问题( 特别是离散优化问题) 方面具有无可替代的优越性，证明了 它是一种极具发展前景的算法1 2 。 然而正如前面分析的，蚁群算法自身也存在着一些缺陷，因此如何消除这些 缺陷对于蚁群算法的发展甚至整个智能优化领域的发展具有举足轻重的意义。 对于第一小节提及的蚁群算法的四个主要缺陷，针对缺陷( 一) 和缺陷( 二) 的改进是最为普遍的，国内外学者己经提出了很多改进的算法；缺陷( 三) 是蚁 群算法自身的特性决定的，很难有本质上的改进；针对缺陷( 四) 的研究相对较 少，但也已经有了一些初步的成果。 在本文中，主要针对缺陷( 一) 和缺陷( 二) ，对基本蚁群算法提出了以下 两点改进t ( 1 ) 、自适应选择策略。在选择策略中，在基于分布均匀度的蚁群算法【l 】 的基础上重新定义了“城市聚度”、“选择窗口”等概念，构造了一种具有自适应 功能的状态转移策略。 ( 2 ) 、自适应信息素更新策略。在信息素更新策略中，采用全局更新( 基于 蚁周模型) 和局部更新( 基于蚁密模型) 相结合的方式，并在局部更新时提出信 息素影响因子递减的思想，既结合了t s p 问题自身的特点，又能够根据解的分 布均匀程度自适应地调整信息素更新策略，保证了算法在搜索后期的高质量。首 先，将“城市聚度 引入信息素影响因子的计算中，使得算法能够根据解的实际 分布状况动态地调整信息素更新策略；其次，通过控制信息素影响因子，相对地 减少后程搜索的信息素增加量，从而减少非优路径对后继搜索的影响，使得算法 在搜索后期能有更大的可能跳出局部最优，达到提高算法整体的搜索性能的目 的。 在本文的第四部分，将基于分布均匀度的改进蚁群算法应用于求解t s p 问 题，以论证算法的正确性及有效性。t s p 问题是个典型的组合优化问题，也是一 8 基于分布均匀度的改进蚁群算法第一章引言 个n p 完全难题，是众多领域内出现的组合优化问题的集中概括和简化形式，是 各种启发式算法的间接比较标准【3 7 1 。因此，本论文通过t s p 问题来验证基于分 布均匀度的改进蚁群算法的正确性及有效性是具有非常大的实际意义的。 1 4 本文章节安排 本论文首先论述了蚁群算法的生物学基础及机制原理，其次介绍了几种经典 蚁群算法的基本思想与数学模型，对算法模型中的主要参数做了详细的分析，再 次归纳并分析了国内外学者对于蚁群算法的一些改进思路，然后在基本蚁群算法 的基础上提出了一些改进思想，并将改进后的蚁群算法应用于求解t s p 问题以 验证算法的正确性及有效性。全文共分五章，其中各章内容安排如下： 第一章，首先介绍了本课题的研究背景，对本文的研究内容和范围做出了界 定，其次从算法的改进研究、算法的应用研究、算法的性能研究三个方面详尽地 分析了国内外关于该课题的研究现状，再次指出了本课题预期达到的研究目标及 意义。 第二章，首先论述了蚁群算法的生物学基础与机制原理，其次介绍并分析了 四种与t s p 问题相关的经典蚁群算法：蚂蚁系统、蚁群系统、最大- g d , 蚂蚁系 统及蚁群优化算法。着重从各算法的基本思想及对之前算法的改进两方面进行分 析。 第三章，结合研究背景及课题研究目标，在基于分布均匀度的蚁群算法的基 础上提出了基于分布均匀度的改进蚁群算法。第一部分简单描述了t s p 问题及 其研究意义；第二部分介绍了基于t s p 问题的蚁群算法数学模型；第三部分详 细介绍了算法的改进策略：自适应选择策略与自适应信息素更新策略；第四部分 则对改进的蚁群算法进行了系统的分析。 第四章，利用数种不同规模的对称t s p 问题对算法的正确性及有效性进行 论证，并将实验结果与基本蚁群算法及一些经典蚁群算法进行了比对分析。 第五章，对本文的研究工作进行总结，并指出下一步需要继续进行的研究工 作。 9 基于分布均匀度的改进蚁群算法第二章相关理论技术 第二章相关理论技术 弟一早 个日大璀t 匕仪小 2 1 蚁群算法的生物学基础与机制原理 2 1 1 蚁群算法的生物学基础 在1 9 8 9 年，g o s s 与d e n e u b o u r g 设计了著名的“双桥实验 ，采用一个双桥 连接巢穴和食物源，用以模拟蚁群的觅食行为。该实验为蚁群算法的提出奠定了 生物学基础【3 8 】。 在第一个“对称双桥”实验中，桥的两个分支长度相同，如图2 1 所示。 1 5 c m 4 图2 - 1 蚁群觅食行为的“双桥实验一” 实验初始，两条分支的信息素浓度均为零，蚂蚁的选择没有任何偏向性，会 在两条分支间随机做出选择，并独立地释放信息素。但由于随机波动的出现，选 择某一分支的蚂蚁可能比另一分支多，导致该分支上积累的信息素浓度明显高于 另一分支，而高浓度的信息素又会诱使更多的蚂蚁再次选择这一分支，。反 复进行此实验，统计结果表明，蚁群最终选择某一分支的概率大约为5 0 t 3 s 。 实验中反映的蚂蚁的这种自组织行为需要依赖随机波动的存在，而这种随机 波动被自催化作用( s t i g m e r g y ) 和正反馈机制放大，最终形成蚁群的自组织行为 1 3 9 1 o 在第二个“非对称双桥”实验中，桥的两个分支长度不同，如图2 - 2 所示。 基于分布均匀度的改进蚁群算法第二章相关理论技术 8 ( a ) 4 分钟 b 8 分钟 图2 - 2 蚁群觅食行为的“双桥买验二” 其中，图( a ) 表示4 分钟时蚂蚁行进的路径选择情形，图( b ) 表示8 分钟 时蚂蚁行进的路径选择情形。 在这种设置条件下，实验前期的情形与实验一类似。开始的时候，两条分支 的信息素浓度均为零，蚂蚁的选择没有任何偏向性，会在两条分支间随机做出选 择，并独立地释放信息素。此时尽管会由于随机波动的出现，导致在某一分支聚 集的蚂蚁多于另一分支，但仍可以期望会有一半的蚂蚁选择较短的分支，而另外 一半选择较长的分支。然而，由于实验二与实验一设置不同，选择了较短分支的 蚂蚁在同样的行进速度下，会率先到达食物源并返回巢穴，于是当返回的蚂蚁再 次出发到达决策点时，由于两条分支的信息素浓度不再相等，短分支上的高浓度 信息素将会诱使蚂蚁选择该分支，继续行进，【3 9 1 。 与实验一相比，实验二中初始阶段的随机波动的影响大大减少，影响实验结 果的主要因素是自催化作用、差异路径长度( d i f f e r e n t i a lp a t hl e n g t h ) 和正反馈 机制等等删。 在实验基础上，g o s s 等人构建了一个数学模型。首先，假定在每条分支上残 1 2 基于分布均匀度的改进蚁群算法第二章相关理论技术 留的信息素含量与曾经过该分支的蚂蚁数成正比；其次，假定蚂蚁会根据信息素 i 浓度差异来进行选择【3 8 1 。设较短分支为a ，较长分支为b ，在某个假定的时间点， i l i a 、1 1 1 b 分别为经过分支a 和分支b 的蚂蚁数，则下一只蚂蚁选择分支a 的概 率为： 。一 帆+ 炒 旷面莳蔫两 ( 公式2 - 1 ) 选择分支b 的概率为： 风= 峨( 公式2 - 2 ) 在公式2 1 中，h 和k 为两个待匹配参数，用来匹配真实的实验数据。通过 蒙特卡罗模拟证实，当k 砣o ，h 2 时，公式2 一l 与实验数据相一致【3 1 。 除了能够找到巢穴和食物源之间的最短路径，蚁群还具有极强的适应环境变 化的能力。如图2 - 3 所示，如果在路线上突然出现障碍物，蚁群能够重新搜索并 很快识别出新的最优路径。 n e s t f o o d ( ) 乞碟 量m 州碟奢 ：j 、出 碰一茹 丌燃，键“ i 釜 曩 胛 蔫 p l e s l r 7 喊蹩烈 f 姚一删，： ( b ) f o l d 啦 ( d ) f o o d 址 图2 _ 3 蚁群的自适应特性【4 1 l 事实上，蚁群算法在计算机网络路由中的应用很大程度上源于真实蚂蚁群体 的这一自适应特性圆。 1 3 基于分布均匀度的改进蚁群算法 第二章相关理论技术 以上简单介绍了蚁群协作觅食的生物学现象，m a c r od o f i g o 等人正是受到这 - t ： 种现象的启发，提出了蚁群算法并用于求解组合优化问题的【4 】。 2 1 2 蚁群算法的机制原理 蚁群算法实际上是一类智能多主体群集系统，其具备的自组织特性使得蚁群 算法不需要对所求问题的每一方面都有详尽的了解。事实上，自组织机制的本质 是蚁群算法在没有外界条件的作用下系统的熵自动增加的动态过程，体现了从无 序到有序的动态演化【1 0 1 。 图2 _ 4 蚁群算法的逻辑结构1 川 2 2 经典蚁群算法的基本思想 2 2 1 蚂蚁系统 蚂蚁系统( a n ts y s t e m ) 是第一个蚁群算法，概括地讲，蚂蚁系统具体包括 了三个操作：初始化、构造路径和信息素更新。算法的主要步骤可