（控制理论与控制工程专业论文）蚁群群体智能网络可视化试验平台设计.pdf

浙江理工大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。 本人授权浙江理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在 不保密占： 学位论文作者虢叩喇 日期：纠口年j 月b 日 年解密后使用本版权书。 雌名：炉彳 日期：扣f 拜岁月，) 日 ， 浙江理t 大学硕十学位论文 摘要 群体智能( s w a r mi n t e l l i g e n c e ) 是在仿生学机理启发下提出的用于求 解并行性分布式问题的一类算法。由于这类算法具有分布式计算、正反馈、鲁棒 性和并行性等优点，在计算机仿真、模式识别、数据挖掘和网络通讯等诸多领域 都得到了广泛的应用。蚁群算法是群体智能中现阶段研究较为深入的一种高效的 优化算法。它基于蚁群在觅食中所体现出的高度智能性，为蚁群整体建立了一个 相互通讯和协调的数学模型，并将该数学模型成功应用于传统的旅行商问题的求 解过程中，取得了令人满意的最优解。 本文对蚁群算法的原理及其基本的数学模型进行了探讨和分析，在此基础上 研究了蚁群算法在实际应用中存在的某些局限性，同时参考了其它不同类型智能 算法的优势，对传统的蚁群算法理论提出了一些比较有效的改进，并建立了一个 基于网络的蚁群算法基础性试验平台。本文具体主要完成了以下工作： 1 为解决传统的蚁群算法中所依赖的数学模型过于理想的问题，本文针对一 类蚁群中个体不完全能控且在运输和转移的过程中随时可能发生停止或停滞的 情况，提出了一种双重约束下的蚁群算法，在确保整个交通运输系统安全的前提 下，引入了网络虚断的概念，通过修改网络间两类不同类型的非可达节点之间距 离的方法对网络节点间的连接关系进行较正，比较有效地解决了此类问题并获取 了完全符合安全性要求的系统最优解。 2 针对蚁群算法稳定性较差和所获得的解的质量不高的问题，本文将贪婪算 法应用到蚁群算法中。根据贪婪算法中局部最优的思想，本文提出了一种基于最 小距离均衡系数的负反馈蚁群算法，利用最小距离均衡系数得出系统的最优控制 策略，并将之作为一种反向的抑制因素附加到蚁群算法的求解过程中，提高了解 的质量。 3 为了改善最小距离均衡系数算法中局部最优的特性过强所导致的整个算 法所能获取的“最优解”的质量较差的问题，本文提出了节点间距离预判断的思 想，改进了最小距离均衡系数算法，提升了最小距离均衡系数算法的在求取最优 解过程中整体性能。 4 构建了基于i n t e r n e t 的蚁群算法可视化基础实验环境。该实验可以在 i 任意操作系统中借由任意 台上开发并验证一些新的 关键词：群体智能；t s p ： a b s t r a c t s w a r mi n t e l l i g e n c e ( s w a r mi n t e l l i g e n c e ) w h i c hw a s i n s p i r e db vt h e b i o n i c sm e c h a n i s mw a sp r o p o s e df o rt h ep a r a l l e l i s mo fd i s t r i b u t e dp r o b l e ms o l v i n g a n dc o m p l e xo p t i m i z a t i o nf o rac l a s so fc o m b i n a t o r i a lp r o b l e m s s i n c et h i sd i s t r i b u t e d c o m p u t i n ga l g o r i t h mh a v et h ee d g e so ft h e p o s i t i v ef e e d b a c k r o b u s t n e s sa n d p a r a l l e l i s m ，e t c ，i th a sb e e nw i d e l yu s e di nt h ec o m p u t e r s i m u l a t i o n ，p a t t e r n r e c o g n i t i o n , d a t am i n i n g ，n e t w o r kc o m m u n i c a t i o n sa n dm a n yo t h e rf i e l d s a n tc o i o n v a l g o r i t h mi so ft h ef i e l do fs w a r mi n t e l l i g e n c e i th a sb e e np r o v e dt ob ea ne f f i c i e n t o p t i m i z a t i o na l g o r i t h mb ym o r ea n dm o r ei n d e p t hs t u d y a n tc o l o n ya l g o r i t h mi s b a s e do nt h ef o r a g i n go fa n tc o l o n yw h i c hd e m o n s t r a t e st h eh i g hl e v e li n t e l l i g e n t i t h a se s t a b l i s h e dam a t h e m a t i c a lm o d e lo fm u t u a lc o m m u n i c a t i o n 锄dc o o r d i n a t i o nf o r t h ea n tc o l o n ya saw h o l e ，a n dt h em o d e lh a sb e e n s u c c e s s f u l l ya p p l i e dt ot h e t r a d i t i o n a lt s p p r o b l e mt oo b t a i nt h em o s ts a t i s f a c t o r yo p t i m a ls o l u t i o n i nt h i sp a p e r , t h et h e o r yo fs w a r mi n t e l l i g e n c eo fa n tc o l o n ya l g o r i t h ma n di t s b a s i cp r i n c i p l eo ft h em a t h e m a t i c a lm o d e lw e r ed i s c u s s e d b a s e do nt h es t l l d vo f t h e a p p l i c a t i o no fa n tc o l o n ya l g o r i t h mi nt h ep r a c t i c a la p p l i c a t i o n ，w ep o i n to u ts o m e l i m i t a t i o n so ft h ea p p l i c a t i o nw h i c he x i s tb yn o wa n dm a d es o m em o r ee f i e c t i v e i m p r o v e m e n t so nt h et r a d i t i o n a la n tc o l o n ya l g o r i t h mt h e o r yr e f e rt os o m eo t h e r d i f f e r e n ti n t e l l i g e n ta l g o r i t h m b yt h es a m et i m e ，i no r d e rt o f u r t h e re x p a l l dt l l e a u d i e n c eo fa n t c o l o n ya l g o r i t h m ，w ea l s oe s t a b l i s h e daw e b b a s e da n tc 0 1 0 n v a l g o r i t h mt e s tp l a t f o r m t h i sa r t i c l em a i n l yf i n i s h e dt h ef o l l o w i n gs p e c i f i cw o r k s ： 1 t or e s o l v et h ep r o b l e mt h a tt r a d i t i o n a lm a t h e m a t i c a lm o d e l sw h i c ha n tc 0 1 0 n v a l g o r i t h mr e l i e so na r et o oi d e a l ，i nt h i sp a p e rw et a k eo n ek i n do fs p e c i a ls i t u a t i o n s w h e r et h ei n d i v i d u a li nt h ea n tc o l o n yi sn o tc o m p l e t e l yc o n t r o l l a b l ea n dt h ep r o c e s s o ft r a n s p o r t a t i o nm a yg e ti n t o s t a g n a n ti na n yg i v e nt i m ei n t oe o n s i d e r a t i o na n d p r e s e n to n ed u a l 。c o n s t r a i n e da n tc o l o n ya l g o r i t h mt oe n s u r et h es a f e t yo ft h ee n t i r e t r a n s p o r t a t i o ns y s t e m t h i sd u a l c o n s t r a i n e da n tc o l o n ya l g o r i t h ml e a d st h ec o n c e p to f v i r t u a lb r e a ki n t ot h ew h o l et r a n s p o r t a t i o nn e t w o r ka n dm o d i f i e st h ed i s t a n c eb e t w e e n i t t 浙江理1 二大学硕士学位论文 t w od i f f e r e n t t y p e so fu n r e a c h a b l en o d e s i nt h en e t w o r kt o r e c o n s t r u c tt h e c o n n e c t i v i t yo fn e t w o r k u n d e rt h ep r e m i s eo fs a f e t y , w eo b t a i nt h eo p t i m a ls o l u t i o n w h i c hf u l l yc o m p l i e sw i t ht h es y s t e mr e q u i r e m e n t so f s u c hp r o b l e m si nt h i sw a y 2 t or e s o l v et h ep r o b l e mt h a tt h ea n tc o l o n ya l g o r i t h mi so f t e n p r o n et of a l li n t o l o c a lo p t i m u m ，i nt h i s p a p e rw ei n t r o d u c et h ei d e ao fg r e e d ya l g o r i t h mi n t ot h e a p p l i c a t i o n so fa n tc o l o n ya l g o r i t h m a c c o r d i n gt ot h ei d e ao fl o c a lo p t i m u mi nt h e g r e e d ya l g o r i t h m ，t h i sp a p e rp r e s e n t so n ek i n do fn e g a t i v ef e e d b a c ka n tc o l o n y a l g o r i t h mb a s e do nm i n i m u md i s t a n c eb a l a n c ef a c t o r t h eb a l a n c ef a c t o ro ft h e m i n i m u md i s t a n c eo p t i m a lc o n t r o ls t r a t e g yi su s e da san e g a t i v ef e e d b a c kw h i c hi s a t t a c h e dt ot h ea n tc o l o n ya l g o r i t h mf o rs o l v i n gt h ep r o b l e ma n dt h i sh y b r i da l g o r i t h m i m p r o v et h eq u a l i t yo fo p t i m a ls o l u t i o nw h i c ht h et r a d i t i o n a la n tc o l o n ya l g o r i t h m m a yo b t a i n 3 t or e s o l v et h ep r o b l e mt h a tt h e s t r a t e g yo fl o c a lo p t i m u mi nm i n i m u m d i s t a n c eb a l a n c ef a c t o ra l g o r i t h mm a yl e a dt oo n e o p t i m a ls o l u t i o no fp o o rq u a l i t y , t h i sp a p e ra d v a n c e dt h ei d e ao fe s t i m a t e st oj u d g et h ed i s t a n c eb e t w e e nt h en o d e s b a s e do nt h i si d e aw ep r e s e n to n ei m p r o v e da l g o r i t h mf o rt h em i n i m u md i s t a n c e b a l a n c ef a c t o rt o i m p r o v et h eq u a l i t yo ft h eo p t i m a ls o l u t i o na n de n h a n c et h e p e r f o r m a n c eo ft h ep r o c e s sa saw h o l e 4 t h i sp a p e ra l s oe s t a b l i s h e dt h ei n t e r n e t - b a s e dv i s u a l i z a t i o no fa n tc o l o n y a l g o r i t h m u s e r sw i t ha n yo p e r a t i n gs y s t e mc a nu s ea n yb r o w s e rw h i c hs u p p o r t e d j a v ap l u g i nt oa c c e s st h e p l a t f o r m i tp r o v i d e st h ep o s s i b i l i t yf o rt h eu s e r st o d e v e l o ps o m en e wa l g o r i t h mo ft h e i ro w no nt h i sp l a t f o r m k e y w o r d s ：s w a r mi n t e l l i g e n c e ；t s p ；a n t c o l o n ya l g o r i t h m ；a n tc o l o n y o p t i m i z a t i o n ；g r e e d ya l g o r i t h m ；j a v a i v a b s t r a c t i l l 第1 章绪论i 1 1 引言i 1 2 群体智能的基本概念1 1 3 蚁群算法的研究4 1 4 论文的主要工作和结构6 第2 章蚁群算法的基本原理8 2 1 蚁群中的智能性8 2 2 蚁群算法的数学模型1l 2 3 蚁群算法的研究和发展1 3 第3 章蚁群算法的改进。15 3 i 双重约束下的蚁群算法1 5 3 1 1 双重约束的基本概念1 5 3 1 2 双重约束下改进的算法1 5 3 1 3 仿真实验及结果分析1 8 3 2 改进的负反馈蚁群算法1 9 3 2 1 最小距离均衡系数算法的概念1 9 3 2 2 基于最小距离均衡系数的负反馈蚁群算法2 l 3 2 3 仿真实验及结果分析2 3 3 3 改进的最小距离均衡系数算法2 4 3 3 1 最小距离均衡系数算法中存在的问题2 4 3 3 2 最小距离均衡系数算法。2 6 3 3 3 仿真实验及结果分析2 8 1 浙江理t 大学硕+ 学位论文 - - - _ - _ _ _ _ _ _ - - _ _ - _ _ _ _ - - - - _ 一一 第4 章系统软件设计。3 0 4 1 系统总体设计思想3 0 4 i 1 目前实验室研究存在的不足3 0 4 1 2b r o w s e r s e r v e r 开发结构3 0 4 1 3j a v a 在b s 开发中的优势3 2 4 2 系统需求分析3 3 4 2 1 基本功能需求3 3 4 2 2 扩展开发需求3 3 4 3 系统开发的技术框架3 4 4 3 1 开发架构3 4 4 3 2 技术描述3 4 4 4 系统运作的基本结构和流程3 6 4 5 系统的实现3 7 4 5 1 系统于用户交互的实现3 7 4 5 2 系统于服务器端的交互的实现4 0 4 6 系统最终的运行效果4 1 第5 章结论与展望。4 7 参考文献4 8 致谢5 4 附录：主程序源代码( 部分) 5 5 攻读研究生期问所取得的研究成果6 9 2 浙江理工大学硕十学位论文 第1 章绪论 本章概述了群体智能的概念提出和发展的过程，介绍了在群体智能的领域中 目前发展比较成熟的几类不同算法及其各自相关的应用范围，在此基础上着重描 述了在自然界蚁群中的所广泛存在的群体智能及由此而被提出的蚁群算法的基 本概念和基本思想。 1 1 引言 “物竟天择，适者生存是自然界生物进化发展的基本法则，生存斗争及适 者生存的过程就是自然选择的过程。自然界生物在长期的进化过程中，通过一系 列的运动来适应环境，以提高适应环境的能力，主动地适应环境。这是一个长期 的、缓慢的、连续的过程。生物在进化过程中所呈现出来的诸如遗传、变异、停 滞等特性最终导致了种群的多样性。据世界上最全面的动植物名录澳大利亚 世界存活物种显示，科学家已记录在册的地球物种已增加到1 9 0 万种。该报 告同时还指出地球上的物种总数实际上要远高于该数据，接近1 1 0 0 万种。 在长期的进化过程中，由于生物的生存和发展的过程必然与周围环境发生着 一定的联系，生物进化并形成了许多本能以适应自然界环境的变化，这其中有些 令人惊叹的先天性本能是人类所无法比拟的。人类生活在自然界中并与周围的生 物为邻，这些各种各样的奇异的先天性本能，吸引着人们去想象和模仿。自古以 来，自然界就是人类各种科学技术原理及重大发明的源泉。人类在很早就开始了 向自然界的生物学习并将研究所得广泛的应用于生产和生活：船只的产生是对自 然界鱼类的模仿，而船桨则是基于对鱼鳍的运动观测得到的；现代工业生产线中 所广泛使用的抓钩则来自于对鸟类爪子的模拟；根据变色龙随环境的改变的特性 而发明的各种设施被广泛用于军事伪装。 1 2 群体智能的基本概念 在人们向自然界生物不断的学习过程中，有一类动物的行为引起了科学家广 泛的关注，这就是自然界所广泛存在的群体智能( s w a r mi n t e l l i g e n c e ， 浙江理工大学硕七学位论文 s i ) 1 1 1 。按照d o r i g o 等人在s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt o a r t i f i c i a ls y s t e m s 一书中给出的定义，群体智能是指任何一种由昆虫群 体或其它动物社会行为机制而激发设计出的算法或解决问题的分布式策略1 2 1 。简 单的说，群体智能是指营群居性生活的生物群体作为不可分割的有机整体所表现 出的高效的智能性。 在自然界中存在很多群居生活的社会性动物，作为一个整体它们在运动和繁 衍过程中可以表现出高度的智能性和自组织性：大雁在高速飞行中可以在保持互 不碰撞的前提下维持恒定的阵列前进1 3 l ：鱼聚集成群可以有效地逃避捕食者，发 现异常都可带动整个鱼群逃避i 们l ；蚂蚁成群则有利于寻找食物，在发现食物可 带动整个蚁群来进行搬运工作；同样的，单只蜜蜂行为能力非常有限，它几乎不 可能独立存在于自然世界中，而多个蜜蜂形成的蜂群则具有非常强的生存能力 1 8 j o 群体智育g ( s w a r mi n t e l l i g e n c e ，s i ) 的概念即是源于此。 典型的群体智能系统的主体是由一群构造相对简单的生物体。在这个群体中 每个生物体的智能性和感知能力都相当有限，同时每个主体同种群中的其它主体 以及于它自身所处的环境之间只能进行某些简单的交互。令人惊讶的是，尽管通 常没有某种特定的集中控制机制来指示这些主体之间如何进行信息分享和任务 协作，但这些构造相对简单的个体的仅仅依靠某些简单的局部交互行为就可以涌 现出复杂的全局智能性i 引。这种复杂的全局智能性一般都具有以下三个基本特征 i ! o - 1 1 l ： 灵活性( f l e x i b i l i t y ) ：整个群体可以适应周围随时变化的环境； 稳健性( r o b u s t n e s s ) ：即使某个个体失败，整个群体仍然能完成任务； 自我组织( s e l f o r g a n i z a t i o n ) ：群体活动既不受中央控制，也不受局部 监管； 作为一个活动的整体，社会性动物群体所拥有的这种特性能够帮助个体很好 地适应环境，而这种适应性并非通过群体内部多个个体感知和判断能力的简单叠 加所获得的。由于群体内部个体之间存在着交互协作的能力。每个低智能性的个 体所能获得的信息远大于它通过自身感觉器官的取得。尽管人们早就意识到这种 群体中个体之间交互协作能力对整个种群存在具有重大的意义，但是这种简单的 协作究竟是如何最终体现成为一种群体的高度智能性，其中的运行机制却不为人 2 浙江理丁大学硕十学位论文 所知。对于这些现象的一种可能的解释是：群体中的每个低智能性的个体都遵从 某些特定的行为准则，当种群中的每一个体按照这些准则相互发生作用时就可以 使得该种群整体表现出上述的复杂智能性行为1 1 2 l 。 为了进一步研究这些全局智能性的形成的机理，c r a i g 砌三y n o l d s 在1 9 8 6 年提出一个仿真生物群体行为的计算机模型b o l d 。b o i d 是一个人工鸟群系统， 其中每只人工鸟被称为一个b o l d 。在整个b o l d 模型中存在有三种行为模式： 分离、列队及聚集。模型中的每只b o l d 能够感知周围一定范围内其它b o i d 的 飞行信息，根据获取得到的周围其它个体的运动信息并结合其自身当前的飞行状 态，每只b o l d 按照以下三条行为规则的指导下做出下一步的飞行路线决策1 1 3 1 ： 凝聚：每只鸟都向它邻近同伴的平均位置移动； 对齐：每只鸟都把自己前进的方向和它邻近同伴的平均方向保持一致； 分隔：每只鸟在飞行时都要避免碰上身边其它同伴； 可以看出，整个b o l d 系统模型中的每一个体的行为都是建立在其对周围环 境的局部感知的层面上，正如研究人员在自然界中所观测到的一样，整个b o l d 系统中并不存在集中的控制者或者某些全局性的控制规则。按照以上的三条控制 和运动规则，i 也y n o l d s 建立了整个b o l d 系统的数学模型并进行了计算机仿 真。实验结果表明：整个b o i d 系统可以体现出高度智能的自组织性。b o l d 系 统中的每一个体能够在快相撞时自动分开，遇到障碍物分开后又重新合拢。在没 有一个最高组织者和协调者的情况下，整个群体组织得非常有效，群体之间相互 协调能力非常的好，这就是最早的一种群体智能模型。随后1 9 9 4 年，m i l l o n a s 在研究此类问题中首次提出了适用于群体智能的五个基本准则1 1 4 l ： 1 1 p r o x i m i t yp r i n c i p l ( 邻近性原则) ：群内个体具有执行简单的时间或 空间上的评估和计算的能力； 2 】q u a l i t yp r i n c i p l e ( 品质性原则) ：群内个体可以对环境( 包括群 内其它个体) 的关键性因素的改变做出响应； 3 】p r i n c i p l eo fd i v e r s er e s p o n s e ( 多样性反应原则) ：群内不同个 体对环境中的某一变化所表现出的响应行为具有多样性： 4 1 s t a b i l i t yp r i n c i p l e ( 稳定性原则) ：并非每次环境的变化都必然会 导致整个群体行为模式的改变； 浙江理工大学硕十学位论文 【5 a d a p t a b i l i t yp r i n c i p l e ( 应性原则) ：在周围环境发生变化时，若 出现群体值得付出代价的改变机遇，群体必须能够改变自身的行为； 在前人工作的基础上，1 9 9 9 年由牛津大学出版社出版的b o n a b e a u 和 d o r i g o 等人编写了专著群体智能：从自然到人工系统( s w a r m i n t e l l i g e n c e ：f r o mn 删r a l1 da i 盯i f i c i a ls y s t e m ) ，这被普遍认为 是群体智能的概念被正式提出的一个重要标志。 目前群体智能中存在很多不同的研究方向，其中理论方法及其相关的应用均 比较成熟的主要有蚁群优化算法0 1 量1 们、蚂蚁聚类算法1 1 7 - 1 8 j 、粒子群优化算法1 1 9 2 们， 还有对蚂蚁分工的研究2 1 也i ，虽然这些算法都是作为群体智能的某种体现，但是 它们的基本思想和应用范围都有着极大的不同，其各自具体的研究范围如下表 1 1 所示。 表1 1 群体智能算法 群体智能行为群体智能算法应用领域 蚁群觅食蚁群优化算法t s p 问题以及各种组合优化问题 蚂蚁公墓形成、幼虫分类k l s 算法、l s 算法用于数据分析和图的划分 蚂蚁分工任务分配算法任务分配 鸟群觅食粒子群优化算法函数优化问题、神经网络训练等 1 3 蚁群算法的研究 蚂蚁个体是自然界感知能力比较弱小的一类物种。蚂蚁没有视觉，个体之间 的交流主要通过气味进行1 矧。此外，研究发现蚂蚁所能感受到的空间是二维的， 而非自然界中的其他高等智能动物所能感知到的三维空间，因而蚂蚁没有高度的 概念。就蚁群中的每只蚂蚁的智能性而言，在长期的自然界竞争中蚂蚁应处于绝 对的劣势。然而事实恰恰相反，作为一个种群，蚂蚁展现出了极强的生命力。世 界各地的蚂蚁的分布都极为广泛。据估计蚂蚁的种类在1 4 0 0 0 种左右，我国就有 约有3 0 0 种。除此之外，蚂蚁还有着极强的适应不同环境的能力，从沙漠到森林， 从热带到寒带，从平原到高山均有踪迹。由于其个体有限的感知能力不可能为整 个蚁群其在生存的进化和竞争中带来任何优势，所以研究人员认为，蚂蚁的这种 4 浙江理工大学硕士学位论文 生存优势的得以体现的主要原因在于蚁群中个体间协调和交流。 经过长期的观察和研究，科学家发现蚁群中这种高效的智能性的实施主要依 赖的是蚁群中一类被称为“信息素 的物质的交流。蚁群中的信息素是多种复杂 和化学物质的混合，对于处于同一种群中个体而言，每种特定的信息素成分都指 示了某些对种群的生存和繁衍有用的信息阻i 。蚁群中的觅食，报警，繁衍，迁 移等行为都无不依赖于个体对种群中所存在信息素的感知能力。长期以来，蚁群 可以完成各种各样的群体任务，修筑复杂精致的蚁穴、发动战争、建造搬运食物 的快速通道，这些复杂任务的执行都是由于蚁群中基于信息素的信息交流才得以 实现。基于这种依赖于信息素的信息共享和任务协作的思想，d o r i g o 于1 9 9 6 年提出蚁群算法最早的基本数学模型，随后d o 刚g o 发表论文“a n tc o l o n y s y s t e m ：ac o o p e r a t i v el e a r n i n ga p p r o a c ht ot h et r 芦e l i n g s a l e s m a np 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 m ，t s p ) 并取得的良好的控制效果。 由d o r i g o 所提出的这类蚁群算法由于具有分布计算、信息正反馈和启发 式搜索的特点，不仅在求解组合优化问题中得到了广泛的应用，而且也被用于连 续时间系统相关问题的优化1 2 5 i 。这种模拟自然界中蚂蚁群体觅食行为的仿生优 化算法采用了正反馈并行自催化机制，具有较强的鲁棒性。优良的分布式计算机 制和易于与其他方法结合等优点，使得蚁群算法在解决许多复杂优化问题方面已 经展现出其优异的性能和巨大的发展潜力。 现今蚁群算法的研究内容已经由最初仅用于解决一维静态优化问题发展到 求解解决多维动态组合优化问题，对其应用性的研究也渗透到人工智能的多个领 域i 矧。在国内外许多学术期刊和重要国际会议上，众多学者近年来对蚁群算法 进行了多方面的著有成效的研究工作。国际著名的顶级学术刊物n a t u i 迮曾 多次对蚁群算法的研究成果进行报道，f u t u r eg e n e r a t i o nc o m p u t e r s y s t e m s 和( ( i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 分别于2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊，在布鲁塞尔每两年召开一次的蚁 群算法国际研讨会进一步促进了这一智能计算领域的学术交流。作为交叉学科中 一个非常活跃的前沿性问题，目前题蚁群算法已成为国际智能计算领域中备受关 注的研究热点和焦点所在i 2 7 - 捌。 浙江理：【大学硕士学位论文 论文的主要工作和结构 本文主要对群体智能中的蚁群算法原理及其数学模型做了一些有益的探讨 和研究，分析了蚁群算法的在实际应用中存在的某些局限性，并针对这种局限性 提出了改进，随后本文将贪婪算法的思想引入蚁群算法，根据贪婪算法获得的结 果来逐步校正蚁群算法获取最优解的过程，取得了比较好的控制效果。为了进一 步探讨蚁群中的智能性的改进，本文还提出了一种改进的最小距离均衡系数算 法。在本文的最后部分，本文构建了一个实验性的网络实验平台，使得蚁群算法 实施可以放入浏览器中执行，起到了比较良好的效果。 本文的基本框架共分为三大部分：1 ) 蚁群算法的基本原理和应用；2 ) 蚁群 算法的研究和改进；3 ) 蚁群算法的网络演示性实验平台设计。 第一部分，本文首先介绍蚁群算法的起源，研究了蚁群算法的基本原理，描 述了经典的旅行商问题的提出和旅行商基本概念，引用并分析了蚁群算法的基本 数学模型，对蚁群算法理论的提出和发展过程做了简要的介绍，并概述了蚁群算 法的当前应用的主要领域。 第二部分，本文将蚁群算法应用于实际，针对一类蚁群中个体不完全能控， 在运输和转移的过程中随时可能发生停止或停滞的情况，在确保整个交通运输系 统安全的前提下，提出了一种双重约束下的蚁群算法。这种双重约束下的蚁群算 法在整个交通运输网络中引入网络虚断的概念，通过修改网络间两类不同类型的 非可达节点之间距离的方法对网络节点间的连接关系进行矫正，比较有效的解决 了此类问题并获取了完全符合安全性要求的系统最优解。随后针对蚁群算法中所 易于存在的收敛性和稳定性较差，获取最优解的质量不高的问题，本文将贪婪算 法的思想带入蚁群算法的应用中。根据贪婪算法中局部最优的思想，本文提出了 一种基于最小距离均衡系数的负反馈蚁群算法，将最小距离均衡系数所得出系统 最优策略作为一种反向的抑制因素附加到蚁群算法的求解过程中，进而提高了改 进后的混合型蚁群算法算法所能获取最优解的质量。在该部分最后一节，本文针 对最小距离均衡系数算法中局部最优的特性过强所导致的整个算法所能获取最 优解的质量较差的问题，提出了节点间距离预估判断的思想，扩大了最小距离均 衡系数算法运算过程中每一步所能利用到的全局性信息的规模，进而由此提出了 一种改进的最小距离均衡系数算法，提升了最小距离均衡系数算法的在求取最优 6 浙江理工大学硕+ 学位论文 解过程中整体性能。 第三部分，本文设计并实现了一个基于浏览器可用于蚁群算法演示和教学的 网络实验环境。该部分介绍了开发过程所涉及到相关技术，对整个系统的可行性 进行了分析，描述了系统中数据传输和运算的基本流程、提供了整个系统的功能 框图和软件模块结构图，建立客户端和服务器之间的通信和数据交换的连接，并 最终按照需求分析实现并完成了整个系统的构建。 论文的具体组织结构如下： 第一章：绪论 第二章：蚁群算法的基本原理 第三章：改进的蚁群算法研究 第四章：软件平台系统设计 第五章：总结 浙江理工大学硕十学位论文 第2 章蚁群算法的基本原理 本章概述了自然界蚁群中的高度智能性的体现及其运作的具体机理，介绍了 由d e n e u b o u r g 所设计的双桥实验的内容，并由此描述了蚁群中的群体智能 实施的整个过程。在此基础上介绍了旅行商问题的提出和d o g o 所建立的蚁 群算法的数学模型，详细阐述了蚁群算法在旅行商问题的求解过程中运算的整个 流程。在本章的最后部分介绍了蚁群算法的发展历程和近年来的研究现状。 2 1 蚁群中的智能性 在自然界不断进化和竞争的过程中，蚁群必须搜寻到足够的食物以确保整个 种群的生存和繁衍。由于既没有视觉辅助也没有类似蝙蝠的超声波定位系统，蚁 群内部通讯和信息交流只能依靠触觉来完成。此外，蚂蚁触觉的感知范围也相当 有限，对于可能存在于未知空间任意一点的食物的相关信息，每只蚂蚁在从巢穴 出发之前都一无所知。基于以上的这些原因，每只蚂蚁似乎都只能基于一种完全 随机的策略进行漫无目的的搜寻，可以想见，这种搜索方式将是相当费时和低效 的。但是通过试验可以观察到：尽管单只蚂蚁的在搜寻食物过程中的能力是微乎 其微的，但是蚁群却总是可以及时有效的发现食物所在的位置，并且最终使得从 巢穴出发觅食的蚂蚁都遵循最优路径往返于食物和巢穴之间进行搬运工作。 研究表明，蚁群中的这种高效的智能性得以体现的主要原因在于蚁群个体问 的信息共享和任务协作，而这种共享和协作的实现所依赖的则是被称为信息素更 新和传播的机制。在觅食过程中，每只蚂蚁都会在它所经过道路上留下一定数量 的被称为“信息素”的物质，信息素的浓度和路径的长度成反比，路径越长，则 信息素的浓度越低。同一种群的蚂蚁可以感知在二维空间的不同路径上所遗留信 息素的浓度的差异。在感知到这种信息素浓度的差异后，每只蚂蚁都倾向于朝着 信息素高的空间位置行进，在这种正反馈的作用下，越来越多的蚂蚁聚集到那些 距离比较短的路径上，从而使得整个蚁群可以快速的求出搬运食物的最优路径， 即整个蚁群系统完成觅食活动所需的最优解1 2 9 l 。 为了论证这种信息素传播理论的正确性，d e n e u b o u r g 及其同事设计了 著名的双桥实验( d o u b l eb r i d g ee x p e r i m e n t s ) ，如图2 1 所示。在蚁穴 8 浙江理： 大学硕士学位论文 和食物源中存在两条通道，标记上下两条通道的长度分别为t 和4 ( ：乃= 1 ：2 ) ， 蚂蚁从位于节点1 处蚁穴开始搜寻位于节点2 的食物源。在试验的起始阶段，蚂 蚁随机的选择两条道路中的一条通行，此时对于蚁群中的蚂蚁而言，较短的通道 ，并没有体现出比较长的通道更高的优先级。但是在随后的路径选择的过程中， 由于选择了较短的通道，。的蚂蚁可以比另一条较长的通道上的蚂蚁更快的抵达 食物源并折返回到巢穴，从而使得在同样的时间间隔内较短的通道z 。相比较长的 通道4 可以累积起更多的信息素。这种信息素浓度的差异使得蚁群中越来越多蚂 蚁倾向于较短的通道z ，来抵达食物源，与此相对应，越来越少的蚂蚁选择较长的 通道，这使得两条通道上信息素浓度的对比反差越来越大，进而最终使得所有 的蚂蚁都选择了较短的通道，。i 洲。 图2 1 双桥买验( d o u b l eb r i d g ee x p e r i m e n t s ) d e n e u b o u r g 使用以下数学模型来解释双桥实验的结果： 若蚁群中有1 0 只蚂蚁从巢穴触发寻找食物，每只蚂蚁的爬行速度均相同， 设其速度为单位1 ，同时对应的设两条路径的单位长度为：乃= 2 ，= 1 。1 0 只蚂 蚁在节点1 处面临两条分叉的道路c 和的选择，由于此时尚未有蚂蚁通过路径 或者，对蚁群中的任意只蚂蚁而言，和这两条路径上的信息素浓度不存 在数量上的差别，因此蚁群中蚂蚁按照相同的概率来选择了这两条道路。1 0 只 蚂蚁此时分为两组，5 只蚂蚁作为第一组选择较长的路径乃通行，另外5 只蚂蚁 作为第二组选择较短的路径通行。在该时刻对每只蚂蚁而言，较长的路径和 o 浙江理工大学硕十学位论文 较长的路径t 具有同样的优先权，不存在任何的差别。 此后经过一单位时间，经由较短的路径，。的第一组5 只蚂蚁抵达节点2 处， 发现食物并开始折返以便搬运食物回到巢穴。在这一个单位时间的过程中，第一 组的5 只蚂蚁在，。的全路段上完成了信息素的撒播。对比此时选择了较长的路径 4 上的第二组蚂蚁，由于乃长度是的2 倍，第二组的5 只蚂蚁尚未抵达节点2 处，整个厶的路径只走完了一半。第二组