（计算数学专业论文）基于中心定位的蚁群算法及其在交通选路中的应用.pdf

武汉理i ：人学硕十学侮论文 摘要 需求工程对复杂系统的软件工程的基础研究是科技部于2 0 0 7 年批准 的国家重点基础研究项目( 即9 7 3 项目) 。该项目选取城市交通领域的问题作为 问题研究的载体，而城市交通选路问题又是其中一个重要研究内容。应用蚁群 算法解决该问题是本文研究的主要内容。 蚁群算法是一种新生算法，从产生伊始就用于解决旅行商( t s p ) 问题。 该算法具有结构简单、易于实现、正反馈性和本质的并行性等优点。本文将基 本蚁群算法加以改进，有效发挥了蚁群算法的特性，为交通选路问题的解决提 供了一种方案。 本文首先介绍了课题的研究背景和意义，阐述了城市交通选路问题的研究 现状，详细介绍了基本蚁群算法，并在此基础上提出了一种改进算法：基于中 心定位的蚁群算法，并在相同的实验环境下分别用两种算法进行仿真实验，结 果验证了改进算法寻找最优解的速度明显比原基本算法快，且更接近于理论上 的最优值，最后将基于中心定位的蚁群算法应用于交通选路问题中。具体内容 如下： ( 1 ) 介绍了基本蚁群算法的基本原理，以旅行商问题为背景建立数学模型， 总结了算法的具体步骤，从时间复杂度和空间复杂度两方面分析了算法的复杂 度，论证了算法的收敛性。 ( 2 ) 在基本蚁群算法的基础上对其进行改进，提出基于中心定位的蚁群算 法，以旅行商问题为背景建立了新的数学模型，同样总结了改进算法的具体实 现步骤，分析了改进算法的复杂度，并论证了其收敛性。 ( 3 ) 利用t s p l i b 网站上公布的t s p 数据，对基本蚁群算法和基于中心 定位的蚁群算法在相同的实验条件下进行仿真实验，并对实验结果做了对比分 析，验证了基于中心定位的蚁群算法的优越性。 ( 4 ) 以交通选路问题为例建立数学模型，设计了解决交通选路问题的实现 步骤，将基于中心定位的蚁群算法应用在交通选路问题中。 ( 5 ) 基于真实交通数据，建立初步的交通选路系统，基本满足了交通选路 问题的需求。 本文的最后从四个方面对全文进行了总结，并对今后的工作进行了展望。 关键词：蚁群算法，交通选路，中心定位，信息素，旅行商问题 武汉理i ：人学颂十学位论文 a b s t r a c t m i n i s t r yo fs c i e n c ea n dt e c h n o l o g yf o u n d e dn a t i o nf o c u s r e s e a r c hp r o j e c t ( 9 7 3 ) ： o i lr e q u i r e m e n te n g i n e e r i n g - b a s i cr e s e a r c ho ns o f t w a r ee n g i n e e r i n gf o rc o m p l e x s y s t e m s i tt a k e st h et r a f f i cd o m a i na st h ev e c t o ro f t h er e s e a r c h ，t ot h ep u b l i c ；t h e m o s ti m p o r t a n tt h i n g sa r et r a v e la n dt h et r a f f i ci n f o r m a t i o na b o u tt h i s a ni m p o r t a n t p r o b l e mw o r t hb e i n gp a i dm o r ea t t e n t i o ni st r a f f i cr o u t i n g u s i n gt h ea n tc o l o n y a l g o r i t h mt os o l v e t h e s ep r o b l e m si sa na s p e c to f t h er e s e a r c hn o w a d a y s a n tc o l o n ya l g o r i t h mi san e wa l g o r i t h mt h a tw a su s e dt os o l v et r a v e l i n g s a l e s m e np r o b l e mf r o mi t sb o r n i th a sm a n ya d v e n t u r e ss u c ha ss i m p l es t r u c t u r e ， e a s y - t o a c h i e v e ，p o s i t i v ef e e d b a c k ，t h en a t u r eo fp a r a l l e l i s ma n ds oo n t h e r e s e a r c h a b o u ti th a sb e e nc o n t i n u e dd e e pa n dm a t u r e i ft h et r a f f i cr o u t i n gp r o b l e mc a nb e s o l v e dp e r f e c t l y , t h ep r o j e c tw o u l db ei m p r o v e di ns o m ed i s t a n c e w ew i l li m p r o v e t h eb a s i ca l g o r i t h ma n di n t r o d u c et h ei m p r o v e da l g o r i t h mi n t ot h ep r o je c t ，w i t ht h e h o p et h a ti tw i l lo f f e ras o l u t i o no nt r a 衔cr o u t i n g i nt h i sp a p e r , w eh a v ei n t r o d u c e di t sb a c k g r o u n da n dm e a n i n g ，t a l k e da b o u ti t s r e s e a r c hs i t u a t i o n ，d e s c r i b e dt h eb a s i ca n tc o l o n ya l g o r i t h m ，a n dt h e na c h i e v e da l l i m p r o v e da l g o r i t h m ：c e n t e rb a s e da n tc o l o n ya l g o r i t h m t h e d e t a i lc o n t e n t sa s f o l l o w s ： ( 1 ) i n t r o d u c i n gt h ep r i n c i p l e so ft h eb a s i ca n tc o l o n ya l g o r i t h m ，m a k i n ga m a t h e m a t i c sm o d e lw i t ht h et r a v e l i n gs a l e s m e np r o b l e m ，o b t a i n i n gt h er e a l i z a t i o n s t e p s ，a n a l y z i n g t h ec o m p l e x i t yf r o mt i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y , p r o v i n gi t sc o n v e r g e n c e ( 2 ) m a k i n gs o m ei m p r o v e m e n t so nt h eb a s i ca n tc o l o n ya l g o r i t h m ，g e t t i n gt h e c e n t e rb a s e da n tc o l o n ya l g o r i t h m ，m a k i n gam a t h e m a t i c sm o d e lw i t ht h et r a v e l i n g s a l e s m e np r o b l e m ，o b t a i n i n gt h er e a l i z a t i o ns t e p s ，a n a l y z i n gt h ec o m p l e x i t yo ft h e i m p r o v e da l g o r i t h m ，p r o v i n gi t sc o n v e r g e n c e ( 3 ) d o i n gs i m u l a t i o ne x p e r i m e n t so nt h et w oa l g o r i t h m sa tt h es a m es i t u a t i o n b vt h et s pd a t ao nt h et s p l i bn e t ，a n dm a k i n gs o m ec o n t r a s ta n a l y s i so nt h e r e s u l t s ，p r o v i n gt h ea d v e n t u r e so f t h ec e n t e rb a s e da n tc o l o n ya l g o r i t h m ( 4 ) m a k i n gam a t h e m a t i c sm o d e lw i t ht h et r a f f i cr o u t i n gp r o b l e m ，d e s i g n i n g t h es t e p so fs o l v i n gt h et r a f f i cr o u t i n gp r o b l e m a p p r o a c ht h ec e n t e rb a s i ca n tc o l o n y a l g o r i t h mo nt h et r a f f i cr o u t i n gp r o b l e m ( 5 ) f o u n d i n gas i m p l et r a f f i cr o u t i n gs y s t e mw i t hr e a lt r a f f i cd a t a ，a sak i n do f 武汉理i ：大学硕十学位论文 s e r v i c e ，i tc a nm e e tt h en e e do ft h et r a f f i cr o u t i n gp r o b l e m a tt h ee n do ft h i sp a p e r , w em a k eas u m m a r yi nf o u ra s p e c t s ，a n dm a k es o m e p r o s p e c t sa b o u tt h ef u t u r ew o r k k e y w o r d s ：a n tc o l o n ya l g o r i t h m ，t r a f f i cr o u t i n g ，c e n t e rb a s e d ，p h e r o m o n e ，t r a v e l i n g s a l e s m e np r o b l e m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研穷所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盒蝉导师签名： 日期：巡墨：! ! ：! ! 武汉理i ：人学硕十学位论文 1 1 研究背景及意义 第1 章绪论 软件是信息系统的核心，软件产业是信息产业的核心。软件与信息服务业 已经成为世界各国争夺科技制高点的关键领域，是国家安全的重要保障及国家 综合实力的主要体现。软件产业的发展，对于充分发挥我国的人力资源优势， 促进经济结构调整，推进经济增长方式转变具有不可替代的作用，提升软件产 业核心竞争力是经济发展的战略需求。 需求问题是软件工程中的传统问题，长期困扰着软件工程。研究表明，需 求引发的问题在软件工程中占据着越来越大的比重。大众用户对软件服务的定 制需求既有共性的一面，也有个性化的一面。随着软件服务的同益丰富和深化， 在基本满足用户共性需求的情况下，服务的个性化就成为竞争优势的关键。软 件的规模化定制生产方式是：对共性需求，一般要充分利用共同的领域知识， 提供通用化的解决方案和服务资源。对个性化需求，则需要在共性的基础上实 施差异性定制，即将共性的需求和个性化的需求进行协同整合，形成软件系统 的整体需求，实现以规模化的成本和速度满足的个性化和多元化的大众需求。 从当前现状来看，需求牵引和服务资源作为实现软件规模化定制的两个基 本要素，后者在客观上得到了更大的发展，而需求牵引的发展则无论从方法论 研究、产业支撑技术、抑或是国家的政策性资助现状，都略显滞后，两者之问 呈现出失衡的态势，从而使得需求工程正同益成为网络化软件发展的瓶颈。在 软件的网络化和服务化发展趋势已经十分明显的背景下，需求工程已经成为软 件工程研究的前沿热点。因此，为了促进网络时代的软件工程发展，研究网络 时代软件需求工程的理论、方法和产业支撑技术，具有重要的科学意义和迫切 的产业发展意义。 国家十分重视需求工程的基础理论研究，科技部于2 0 0 7 年设立了国家重 点基础研究项目( 即9 7 3 项目) ：需求工程对复杂系统的软件工程的基础研 究。该项目选取城市交通领域的问题作为科学问题研究的载体，并安排了相关 的研究课题。课题的主要任务是针对城市交通领域，利用武汉大学针对需求工 程提出的r g p s 元模型的理论和方法，描述与城市交通相关问题的需求，并建 立相应的领域模型，最终构建面向大众的城市交通按需回答原型系统。城市交 通是由道路、铁路、水路、空路、管路等各种交通运输系统、多种职能管理部 门以及多种信息发布平台构成的复杂系统，其功能是完成城市内部和外部客与 武汉理i ：人学硕+ 学位论文 货的往来、传递和输送，是促进城市经济和社会持续发展的基础条件，也是增 强城市综合竞争力和提高市民生活质量的重要因素。对于大众来说，最关注的 城市交通问题包括出行和与出行相关的交通信息，其中城市交通选路问题的研 究就是一个非常值得关注的重要问题。应用蚁群算法解决相关问题是当前研究 的一个方面。 蚁群算法是一种新生算法，从产生伊始就用于解决t s p 问题。蚁群算法具 有结构简单、易于实现、正反馈性和本质的并行性等优点，其研究也不断深入 和成熟。目前人们对蚁群算法的研究已经由当初单一的t s p 领域渗透到了多个 应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离 散域范围内研究逐渐拓展到连续域范围内的研究，使得蚁群算法在求解二次分 配、j o b s h o p 问题、图着色问题、车辆调度、集成电路设计以及通信网络负载 问题的处理中都取得了较好的结果，特别是在解决n p h a r d 问题时往往能取得 令人满意的结果。目前作为一种新兴的仿生优化算法，蚁群算法展现出了勃勃 生机，已经成为可以与遗传算法相媲美的仿生优化算法。 我们承担的9 7 3 项目课题六验证示范服务大众的按需回答原型系统” 构建的平台中涉及交通网络路径选择的案例，如果能把交通选路问题完善解决， 将在一定程度上推动项目的进展。我们将基本蚁群算法加以改进，并应用于项 目中，希望有效发挥蚁群算法特性，为交通选路问题提供一种解决方案。 1 2 课题相关的研究现状 2 0 0 7 年3 月2 8 日，世界经济论坛、i n s e n d 和世界银行( w o r l de c o n o m i c f o r u m ) 公布了全球信息技术报告2 0 0 6 2 0 0 7 ，在对1 2 2 个国家的网络普及 度和i t 业发展的信息化综合指数的排名中，中国连续第二次下滑，从2 0 0 4 年 的第4 1 名，跌至2 0 0 5 年的第5 0 名，再跌至2 0 0 6 年的第5 9 名，这说明我国的 整体信息实力不容乐观12 0 0 5 年，纽约时报的专栏作家托马斯弗里德曼在 世界是平的一书中认为：“世界开始从垂直的价值创造模式( 命令和控制) 向同益水平化的价值创造模式( 联系和合作) 转变”。一项对3 5 0 家美国公司承 担的8 0 0 0 多个项目进行的调查显示，三分之一的项目未能完成，在完成的项目 中有一半的项目只是部分成功，即只完成了部分功能、超出预算、严重延期。 对于这些项目失败的原因，项目管理人员认为糟糕的需求是问题的主要来源。 更具体的讲，缺乏用户参与( 1 3 ) ，需求不完备( 1 2 ) ，变更需求( 1 1 ) ， 不切实际的期望( 6 ) ，目标不清晰( 5 ) 。在欧洲范围内，对1 7 个国家的 3 8 0 0 多个组织的调查表明了类似的结果。大多数可以感知的软件问题发生在需 求规约( 5 0 ) 和需求管理( 5 0 ) 阶段。 2 武汉理i ：人学硕十学位论文 2 0 0 7 年1 月的中国互联网络发展状况调查结果显示，目前中国互联网 用户数量已经达到1 3 7 亿人，除了浏览新闻、搜索引擎、收发邮件三大最常用 的基础网络服务外，电子杂志、网络教育、网络销售、网络电话、网络金融等 服务实现了从无到有，并快速上升。传统面向固定领域的方法和工具难以满足 高效率和高用户满意度的网络化软件生产。 国家十分重视需求工程的基础理论研究，科技部于2 0 0 7 年设立了国家重点 基础研究项目( 即9 7 3 项目) ：需求工程对复杂系统的软件工程的基础研究， 该项目选取城市交通领域的问题作为科学问题研究的载体。对于大众最关注的 城市交通问题，主要包括出行和与出行相关的交通信息。就北京来说，北京常 住人口1 4 9 3 万，流动人口3 6 0 万，机动车保有量已达到2 4 5 万辆，其中私人小 汽车1 6 0 力- 辆。公共交通出行只占2 6 5 ，自行车出行占3 2 ，其余的4 0 多为小汽车、公务车和出租车。由此可以看出，北京大众出行面临的形势相当 不利，因此，如何选择出行道路是大众出行最关心的问题，合理解决交通选路 问题意义重大。早在1 9 9 3 年，m i s h c h e n k o 就已将蚁群算法应用至交通领域f 1 1 ， 并取得了较好的结果。 受自然界中真实蚁群集体行为的启发，1 9 9 1 年，由意大利科学家m d o r i g o 等人系统地提出这种基于蚂蚁种群的新型优化算法f 引，并成功地用于求解t s p 问题。同年，d o b o s i e w i c z 、w l o d e k 、g b u r z y n s k i 等人也公交网络【3 j 进行了研究。 自1 9 9 6 年起，蚁群算法引起了世界各国学者的广泛关注，越来越多的研究人员 正在从事这方面的工作，我国最早研究蚁群算法的是东北大学张纪会博士和徐 心和教授【4 】。从当前可以查阅的文献情况来看，研究和应用蚁群算法的学者主 要集中在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国在这一 两年内也开始启动对蚁群算法的研究。国内于1 9 9 8 年末才丌始有少量公开报道 和研究成果。 蚁群算法从1 9 9 1 年提出以来，得到了迅速的发展和广泛的应用，但由于蚁 群算法还是一个比较年轻的算法，其发展相对来说还不算太成熟，所以难免存 在这样那样的缺点，如：当问题规模变大时，算法效率下降的很快，需要较长 的搜索时间，容易出现停滞现象等。针对这些缺点，很多学者进行了大量的研 究，提出了切实可行的改进方法。 1 9 9 2 年，d o r i g o 对优化问题【5 】做了相应研究。1 9 9 6 年，d o r i g o 、m a n i e z z o 、 c o l o m i 等对蚁群算法做了新的改进【6 1 。c a m b a r d e l l a 和d o r i g o 又提出一种修 诈的蚁群算测7 1 。t h o m a ss t u t z l e 等人于1 9 9 7 年提出了m a x m 烈蚁群系统。 ( m m a s ) i 引，至今仍是解决t s p 和q a p 等离散优化问题的较好模型之一。 1 9 9 8 年，d o r i g o 发表了复杂组合优化问题从自然界得到的启发，进一步阐述了 武汉理i ：人学颂十学何论文 蚁群算法的思想【9 1 。1 9 9 9 年，d o r i g o 和c a m b a r d e l l a 将蚁群算法引入二次分配 问题( q h p ) 们，b u l l n h e i m e r 、h a r t l 和s t r a u s s 把蚁群算法改进之后应用在 车辆路径问题( v l 廿) i l lj 。2 0 0 0 年，d o r i g o 对蚁群算法做了新的改进【1 2 l 。g u o a h r 论述了基于图论的蚁群系统和它的收敛性1 1 3 】，b o n a b e a u 、d o r i g o 和t h e r a u l a z 发表了从群居昆虫行为获得的对优化问题的灵感l m 】，m e r k l e 和m i d d e n d o r f 提 出了一种新的信息素更新规则【15 1 ，s t u t z z l e 和h o o s 对m a x m i n 蚁群算法 做出改进【l 引。2 0 0 1 年，c o r d o n e 和m a f f i o l i 将蚁群算法的局部搜索应用到无 线电通信网络的设计l l7 1 。a b b a s p o u r 、s c h u l i n 、g e n u c h t e n 等将蚁群算法应用到 参数评估【l 引。2 0 0 2 年，s a l i m aq 、m o h a m e d 、c a t h e r i n e 等将蚁群算法应用至 马尔科夫随机问题【】9 1 。j o h na s a u t e r 、r o b e r tm a t t h e w s 等研究了信息素路径规 划机制【2 们。g u t j a h r 论述了蚁群算法保证最优解的收敛性【2 1 】，m i d d e n d o r f 、 r e i s c h l e 和s c h m e c k 提出了多种群的蚁群算法( 2 2 t d o r i g o 将蚁群优化应用到随 机梯度下降问题【2 3 1 。r y a n 、r i c h a r d 等将蚁群算法用于网络中的动态波长路由 问题1 2 4 j 。g u n t s c hm ，m i d d e n d o r f m ，s c h e u e r m a n n 将蚁群优化进行了改进并加以 应用【2 5 1 。c o e l l oc a c ，g u t i e r r e zr l z ，g a r c i a 等将蚁群系统应用于组合逻辑的原 子设计1 2 引。2 0 0 3 年，c h u 、r o d d i c k 和p a n 提出了并行的蚁群系纠2 7j 。2 0 0 4 年，s c h e u e r m a n n 和c u n t s c h 提出了一种新的蚁群优化方法f 2 引。2 0 0 5 年， e l l a b i b 、b a s i r 和c a l a m a i 提出不同的信息传输策略进而改进蚁群算法【2 9 1 。2 0 0 6 年，c a r o l i n eg a g n e 、m a r cg r a v e l 和w i l s o nl p r i c e 等人蚁群优化算法应用于实 时汽车排序问题【3 0 1 。2 0 0 7 年，o l i v e rk o r b 和t h o m a ss t u t z l e 等人将蚁群算法应 用于生物领域：弹性蛋白配体对接【3 1 1 。高为民等将蚂蚁算法应用于公交网络最 短路径问题1 3 2 1 。2 0 0 8 年，k r z y s z t o fs o c h a 和m a r c od o r i g o 将蚁群优化算法应用 于连续域【33 1 。上海交大的万福赞和山东师范大学的杨海分别在自己的硕士毕业 论文中将蚁群算法应用于i t 项目进度管理【3 4 】和智能交通【3 5 1 中。 蚁群算法是一种新生算法【3 6 1 ，虽然对于它的研究才刚刚起步，但其在众多 领域中已展现出它的特点和魅力，它具有很强的鲁棒性和通用性，对蚁群算法 模型稍加修改，就可以应用于其他问题。又是一种基于种群的进化算法，具有 并行性，易于并行实现。它很容易与多种启发式算法结合，以改善算法的性能。 从提出到现在，仅短短十余年的时问，但其在离散型组合优化问题【3 7 】1 3 8 l 和其他 优化组合问题【3 9 】1 4 0 】【4 1 】中，表现得很突出，所以引起人们的关注。作为一种新生 算法，蚁群算法也存在一些有待解决的问题，比如蚁群算法本身是一种概率算 法，但目前有关合理选择蚂蚁数量以及算法运行时问数学分析的概述仍然很少。 虽然蚁群算法经过优化后收敛速度得到了一定的提高，但对于高组合优化问题 并不是很理想。蚁群算法的并行性为提高算法的收敛性【4 2 】提供了可能性，尽管 4 武汉理i ：人学硕十学位论文 不少学者在算法的并行方面做了不少工作，但比起其他启发式算法如遗传算法 【4 3 】m l 还是远远不够的，如：在大家最常用的谷歌搜索引擎中输入蚁群算法，会 出现5 8 6 0 0 项查询结果。而输入遗传算法，会出现8 3 1 0 0 0 项查询结果。在百度 搜索引擎中输入蚁群算法，出现9 8 9 0 0 项查询结果，而输入遗传算法，出现 2 2 4 0 0 0 0 项查询结果。尽管蚁群算法在众多领域得到了推广应用，但其中大多 仅仅是对蚁群算法在该领域应用的一个简单的仿真实验和思想的引入。对这些 问题做进一步的研究将会促进蚁群算法的理论和应用的发展，蚁群算法也将在 智能设计领域有更大的发展前景。 总之，蚁群算法作为一种新的并且很有前途的研究领域，处于人工生命与 运筹学的交叉位置。随着对其研究的不断深入，其应用将更加广泛，相应的理 论基础也会更加完善。 1 3 本文的主要内容 本文首先详细介绍了基本蚁群算法，然后在此基础上针对基本蚁群算法搜 索时问长、易出现停滞现象等缺陷提出一种改进算法：基于中心定位的蚁群算 法，并在相同的实验环境下分别两种算法进行仿真实验，结果验证了改进算法 寻找最优解的速度明显比原基本算法快，而且更接近于理论上的最优值，最后 将基于中心定位的蚁群算法应用于交通选路问题中。具体内容如下： ( 1 ) 从蚁群算法的产生及发展和基本原理到以旅行商问题为背景建立数 学模型，再到算法的具体步骤，详细介绍了基本蚁群算法。 ( 2 ) 提出并介绍了基于中心定位的蚁群算法。 ( 3 ) 仿真实验和结果分析。 ( 4 ) 基于中心定位的蚁群算法在交通选路问题中的应用。 ( 5 ) 建立初步的交通选路系统。 1 4 本文研究方法及成果 ( 1 ) 研究方法、方案和技术路线 通过对基本蚁群算法的研究，提出改进的蚁群算法，即基于中心定位的蚁 群算法。利用t s p l i b 网站上公布的t s p 数据，对算法进行仿真实验验证。将算 法应用于旅行商问题，并进行分析。基于真实交通数据，将改进算法应用于交 通选路实际问题以验证算法的效果，为指导实际交通选路问题或其他相近的问 题提供借鉴。 ( 2 ) 主要成果和创新 武汉理l ：人学硕十。学位论文 提出改进后的基于中心定位的蚁群算法。 将基于中心定位的蚁群算法引入交通领域，指导实时交通选路。 以北京市电子地图和少量公交站点的真实经纬度数据，建立了初步的交通 选路系统。 1 5 本文的组织结构 本文结构安排如下： 第一章是绪论部分。 第二章介绍了基本蚁群算法。首先介绍了蚁群算法的产生及其发展，重点 介绍了基本蚁群算法的三个重要特征：分布式计算、自组织、正反馈。第二节 模拟真实蚁群觅食行为介绍了蚁群算法的基本原理。第三节介绍了从自然蚂蚁 到人工蚂蚁的转化，并以旅行商问题为背景建立数学模型。第四节蚁群算法的 具体实现步骤。第五节从时间复杂度和空间复杂度两方面分析了基本蚁群算法 的复杂度。第六节分析了基本蚁群算法在最短路径选择问题上的收敛性，并通 过三个定理证明了算法的收敛性。 第三章在对基本蚁群算法深入研究的基础上对其进行改进，提出了一种基 于中心定位的蚁群算法。在第一节引入了中心定位因子。第二节同样以旅行商 问题为北京详细介绍了改进后的算法的建模过程。第三节介绍了基于中心定位 的蚁群算法的具体实现步骤。第四节作为跟基本蚁群算法的对比，从时间复杂 度和空间复杂度两方面分析了改进算法的复杂度。第五节简单说明了基于中心 定位的蚁群算法的收敛性。第六节分别对基本蚁群算法和改进后的算法做了仿 真实验。首先介绍了仿真实验的环境，接着介绍了4 个重要参数的设置，然后 在参数确定的基础上实现实验并对结果做了深入的分析。 第四章将基于中心定位的蚁群算法应用于交通选路问题中。第一节从9 7 3 项目所涉及的关于r g p s 模型的概念过渡到交通选路问题。第二节对交通选路 问题建立模型。第三节主要描述了基于中心定位的蚁群算法解决交通选路问题 的具体步骤。第四节进行了仿真实验，首先对实验进行了分析，然后根据实验 分析建立了初步的交通选路系统。 第五章从基本蚁群算法、基于中心定位的蚁群算法、两种算法的比较、在 交通选路问题中的应用四个方面对全文做了总结，并对今后的工作进行了展望。 6 武汉理i ：人学硕十学何论文 第2 章基本蚁群算法 2 1 基本蚁群算法介绍 生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起 来没有集中的指挥，但他们却能协同工作，集中食物，建起坚固漂亮的蚁穴并 抚养后代，依靠群体能力发挥出超出个体的智能。 很早人们就知道模仿生物的一些特性，来更好地为人类服务。于是，出现 了很多智能算法，比如遗传算法、进化策略算法、模拟退火算法、禁忌搜索算 法等。这些算法由于能较好地解决实际问题而得到了迅速发展和广泛应用。近 几年，在优化算法领域，一种新的仿生优化算法进入了人们的视野蚁群算 法( a n tc o l o n y a l g o r i t h m ) ，也称为蚁群系统( a n ts y s t e m ，a s ) 。 蚁群算法是2 0 世纪9 0 年代由意大利学者d o r i g o 等人根据蚂蚁群体的觅食 行为提出的一种新型的模拟进化算法。蚁群算法具有结构简单、易于实现、正 反馈性和本质的并行性等优点，现已被应用于求解旅行商问题、二次分配问题、 顺序排列问题、广义分配问题、多重背包问题、网络路由问题等多种n p h a r d 问题。但是基本蚁群算法也存在着易陷入局部最优解和收敛慢等方面的不足。 蚁群算法具有三个最重要的特征【4 5 】：分布式计算、自组织、正反馈。 ( 1 ) 分布式计算 所谓分布式计算是一门利用互联网上的计算机的中央处理器的闲置处理能 力来解决大型计算问题的计算机科学，它研究如何把一个需要非常巨大的计算 能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进 行处理，最后把这些计算结果综合起来得到最终的结果。 仔细分析可以发现，自然界中的真实蚁群行为出现了分布式。当蚁群需要 完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任 务的完成不会由于某些个体的缺陷而受到影响。蚁群算法作为对蚁群觅食行为 的抽象，也体现了群体行为的分布式特征。每只人工蚂蚁在问题空间的多个点 同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无 法成功获得解而受到影响。 具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加 现实的意义。因为所有的仿生优化算法均可看作按照一定规则在问题解空间搜 索最优解的过程，所以搜索点的初始选取就直接关系到算法求解结果的优劣和 算法寻优的效率。当求解许多复杂问题时，从一点出发的搜索受到局部特征的 限制，可能得不到所求问题的满意解。而基本蚁群算法则可看作是一个分布式 7 武汉理i ：人学硕十学何论文 的多智能体系统，它在问题空间的多点同时独立地进行解搜索，不仅使得算法 具有较强的全局搜索能力，也增加了算法的可靠性。 ( 2 ) 自组织 基本蚁群算法的另一个重要特征是自组织，这也是遗传算法、人工神经网 络、微粒群算法、人工免疫算法、人工鱼群算法等仿生优化算法的共有特征。 自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组织行 为分为自组织和他组织两大类。其根本区别在于组织力或组织指令是来自于系 统内部还是来自于系统外部，前者称为自组织，而后者即称为他组织。如果系 统在获得时间的、空问的或者功能的结构过程中，没有外界的特定干预，则称 该系统是自组织的。 最典型的自组织就是生物体，在生物学上有一个观点，即类似蚂蚁、蜜蜂 这样的昆虫，由于个体作用简单，而个体之问的协作作用特别明显，因而可把 它们当作一个整体来研究，甚至把它们看作一个独立的生物体。在这样的群落 中，生物个体相互作用，协同完成某项群体工作，自然体现出很强的自组织特 性。从抽象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程( 即 系统从无序到有序的进化过程) 。基本蚁群算法体现了这一过程，以蚁群优化为 例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演 化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序 到有序的自组织进化。 自组织大大增强了算法的鲁棒性，传统的算法都是针对某一具体问题而设 计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他 问题。而自组织的蚁群算法不需要对待求解问题的所有方面都有所认识，因而 教容易应用到一类问题中。 ( 3 ) 正反馈 反馈是控制论中的重要概念，它代表信息输入对输出的反作用。在系统学 上认为，反馈就是把系统现在的行为作为影响系统未来行为的原因。反馈分为 正反馈和负反馈两种，前者指的是以现在的行为去加强未来的行为，而后者则 是以现在的行为去削弱未来的行为。由自然界中真实蚂蚁的觅食行为可见，蚂 蚁能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的 堆积却是一个f 反馈的过程。对于基本蚁群算法而言，初始时在环境中存在完 全相同的信息量，给系统一个微小的扰动，使得各个边上的信息量大小不同， 蚂蚁构造的解就存在了优劣。算法采用的反馈方式是在较优解经过的路径留下 更多的信息素，更多的信息素又吸引了更多的蚂蚁，这个证反馈的过程使得初 始值不断地扩大，同时又引导整个系统向着最优解的方向进化。 8 武汉理r 人学硕 学位论文 单一的j 下反馈或者负反馈存在于线性系统之中，是无法实现系统的自我组 织的。白组织系统通过j 下反馈和负反馈的结合，以实现系统的自我创造和自我 更新。基本蚁群算法中同样隐含着负反馈机制，它体现于蚁群算法在构造问题 解的过程中用到了概率搜索技术，通过该技术增加了生成解的随机性。随机性 的影响就在于接受了解在一定程度上的退化，另一方面又使得搜索范围得以在 一段时间内保持足够大。这样正反馈缩小搜索范围，保证算法朝着最优解的方 向进化。而负反馈保持搜索范围，避免算法过早收敛于不好的结果。恰恰是在 正反馈和负反馈共同作用的影响下，基本蚁群算法得以自组织地进化，从而得 到问题在一定程度上的满意解。值得一提的是，在已经公开发表的大部分论文 中，对于基本蚁群算法所隐含的负反馈机理没有提及，但这并不影响对基本蚁 群算法本质特性的理解以及对基本蚁群算法的改进和广泛应用。 2 2 基本蚁群算法原理 根据仿生学家的长期研究发现：蚂蚁虽没有视觉，但运动时会通过在路径 上释放出一种特殊的分泌物信息素来寻找路径。当他们碰到一个还没有走 过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的信息 素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路 口的时候，选择信息量较大路径的概率相对较大。这样便形成了一个正反馈机 制。虽优路径上的信息量越来越太，而其他路径上的信息量却会随着时间的流 逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变 化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快地重新找到虽优路 径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息 索的作用使整个蚁群行为具有非常高的自组织性，蚂蚁之间交换着路径信息， 最终通过蚁群的集体自催化行为找出最优路径。这里用如图2 1 所示的形象图 例来进一步说明蚁群的搜索原理。 rr d = 1d = i ab c d 一- 3 03 0 d = 05d o5 f ( 4 ) 图 f ( 坼 2 - 1 自然界中的蚂蚁觅食模拟 武汉理i ：人学硕十学何论文 图2 1 中，设a 点是蚁巢，d 点是食物源，e f 为一障碍物。由于障碍物 的存在，蚂蚁只能由a 经e 或f 到达d ，或由d 到达彳，各点之间的距离如图 2 一l ( a ) 所示。假设每个时间单位有3 0 只蚂蚁由a 到达d 点，有3 0 只蚂蚁由d 到达么点，蚂蚁过后留下的信息量为l 。为了方便起见，设物质停留时间为1 。 在初始时刻，由于路径b e 、f c 、b e 、e c 上均无信息存在，位于a 和d 的 蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择b f 、 f c 、b e 、e c ，如图2 1 ( b ) 所示。经过一个时间单位后，在路径肼1 c 上的 信息量是路经b e c 上信息量的2 倍。又经过一段时间，将有2 0 只蚂蚁由b 、f 和c 点到达d ，如图2 1 ( c ) 所示。随着时间的推移，蚂蚁将会以越来越大的 概率选择路径艿形，最终将会完全选择路径召粥，从而找到蚁巢到食物源的 最短路径。 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的， 该算法基于如下基本假设： ( 1 ) 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局 部环境做出反应，也只对其周围的局部环境产生影响。 ( 2 ) 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁 的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。 ( 3 ) 在个体水平上，每只蚂蚁仅根据环境做出独立选择。在群体水平上， 单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适 应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构， 路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择。时间越长，信 息量会越小。在协作阶段候选解之间通过信息交流，以期望产生新能更好的解。 2 3 基本蚁群算法模型 2 3 1 自然蚂蚁到人工蚂蚁 蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很 多观点都来源于真实蚁群。在从真实蚁群行为获得启发而构造蚁群算法的过程 中，人工蚂蚁还具备了真实蚂蚁所不具有的一些特性。 由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上 的应用，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进 行完全再现。抽象的目的就是为了能够更加有效地刻画出真实蚁群中能够为算 1 0 武汉理i ：人学硕十学位论文 法所借鉴的机理，同时摒弃与建立算法模型无关的因素。这样抽象出来的人工 蚂蚁可以看作是一个简单的智能体，能够完成所求问题简单解的构造过程，也 能通过一种通信手段相互影响。 自然界中的真实蚂蚁存在于一个三维的环境中，而问题空间的求解一般是 在平面内进行的，因此需要将蚂蚁觅食的三维空间抽象为一个平面。因为蚂蚁 觅食所走的路径本来就存在于一个二维空间上，另外一个问题是真实蚂蚁是在 一个连续的二维平面中行走的，而我们无法用计算机直接来完整的描述一个连 续的平面，人工蚂蚁可在抽象出来的点上自由运动。这个抽象过程的可行性在 于，尽管蚂蚁是在连续平面行动，但其行动经过的总是离散点，因此抽象过程 只是提高了平面点离散分布的粒度，与其觅食行为的本身机理没有任何冲突。 真实蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方 向，而人工蚂蚁是在平面的节点上运动的，因此可把觅食过程抽象称算法中解 的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点，人工蚂蚁 感知连接该节点于相邻节点分别表示蚂蚁的巢穴( 初始节点) 和食物源( 目标 节点) ，人工蚂蚁从初始节点按照一定状态转移概率选择下一节点，依此类推， 最终选择行走到目标节点，这样便得到了所求问题的一个可行解。 自然界中的蚂蚁总是在所经过路径上连续不断地留下信息素，而信息素也 会随着时间的推移而连续不断地挥发。由于计算机处理的事件只能是离散事件， 所以必须使信息素的挥发离散发生。通常的做法是，当蚂蚁完成从某一节点到 下一节点的移动后，即经过一个时间单位之后，进行一次信息素的挥发，而这 种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理是完全相符的。 以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组 织性，但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。 而实际应用时对算法运行时间的要求也是必不可少的，因此在决定蚂蚁行走方 向的状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，根据 所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大地增加 了算法的时间有效性，从而