（计算机应用技术专业论文）改进蚁群算法及其在公交线网优化中的应用.pdf

论文摘要 随着我国社会的快速发展，居民出行量成倍增长，城市交通越来越拥挤，大 力发展公共交通，提高公共交通在整个居民出行中的分担率是改善城市交通问题 的一个有效手段。其中，公交线网布局优化能在城市现有的道路交通系统和公交 运力的基础上，通过线网优化、合理布局，最大程度发挥城市公共交通自身潜力， 提高交通资源利用效率，是一项投资少、见效快、易于实施的有效措施。蚁群算 法是一种新型启发式智能算法，在解决组合优化问题方面表现出很好的性能，而 公交线网优化是一个典型的非线性组合优化问题，本论文尝试将蚁群算法运用于 求解公交线网优化，主要研究工作如下： 本文首先介了绍蚁群算法和公交线网优化的基本内容，然后对现有蚁群算法 的改进方法进行了分析，对蚁群算法容易陷入停滞和算法参数难以设置这两个问 题，本文创新性提出了停滞计数器概念来判断算法所处阶段，依据不同阶段对算 法新发现的更优路径进行不同程度的信息素额外增强，以加强蚂蚁对偶然出现的 更优路径的学习；同时提出了依据算法所处的不同阶段对参数的动态设置方法， 以达到算法探索与开发的平衡。通过程序实现与基本m m a s 算法比较，应用本 文所提出的方法在求解质量、收敛速度都有很好的改进，证明本文改进方法的有 效性。 最后综合分析线网布局优化目标、约束条件，提出以单位时间动态直达客流 量最大为目标，并建立了优化数学模型。同时结合线网优化具体问题模型对改进 蚁群算法做了进一步的改进，创新性提出每个城市节点的候选列表和对死亡蚂蚁 的惩罚机制，并通过改进蚁群算法求解，证明本文方法能在综合考虑乘客出行心 理、客流直达率、线路非直线系数、路线重复系数等约束条件下，使单位时间的 直达客流量最大，线路设置更为科学。 关键词：蚁群算法， 算法改进，公交线网优化，优化仿真 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fo u rs o c i e t y ，t h ea m o u n to fr e s i d e n t t r i p si sm u l t i p l i n g ，w h i c hl e a d st ou r b a nt r a f f i cc o n g e s t i o n a ne f f e c t i v e w a yo fs o l v i n g t h i sp r o b l e mi st od e v e l o pu r b a np u b l i ct r a n s p o r t v i g o r o u s l y ，a n dt oi m p r o v ei t sc o n t r i b u t i o nr a t ei nt h ew h o l ea m o u n to f p e o p l et r a v e li n g u r b a nt r a n s i tn 。e t w o r ko p t i m i z a t i o n ( u t n o ) c a nm a x i m i z e t h ep o t e n t i a lo fu r b a np u b l i ct r a n s p o r t s y s t e mb y1 i n eo p t i m i z a t i o na n d r a t i o n a ld i s t r i b u t i o nb a s e do nt h ee x i s t i n gc i t yt r a n s p o r t a t i o ns y s t e m a n dp u b l i ct r a n s p o r t a t i o nc a p a c i t y i ti sa ne f f e c t i v em e a s u r ew h i c hn e e d s s m a l la d d i t i o n a li n v e s t m e n tb u tl e a d st of a s ti m p r o v e m e n t ，a l s o ，i ti sa n e a s yw a yt ob ei m p l e m e n t e d a n tc o l o n ya l g o r i t h m ( a c a ) i san e wh e u r i s t i c a l g o r i t h mw h i c hh a sm a d eg r e a te f f e c t i v ep r o g r e s s i nas e r i e s o fh a r d 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 m s ，w h i l et h eu r b a nt r a n s i tn e t w o r k o p t i m i z a t i o ni sat y p i c a ln o n l i n e a rc 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 m ， s oi nt h i sp a p e r ，a n tc o l o n ya l g o r i t h mw i1 1b ea p p l i e dt os o l v et h ep r o b l e m o fu r b a nt r a n s i tn e t w o r ko p t i m i z a t i o n t h em a j o rc o n t e n t so ft h er e s e a r c h p r e s e n t e di nt h i sp a p e ra r ea sf o l l o w i n g ： f i r s to fa l l ，t h i sp a p e ri n t r o d u c e st h eb a s i cc o n t e n t so fa n tc o l o n y a l g o r i t h ma n du r b a nt r a n s i t n e t w o r ko p t i m i z a t i o n t h e n ，t h i sp a p e r p r e s e n t st h et w o1 i m i t a t i o n so fa c aw h i c hc a nn o tb ew e l ls o l v e db yt h e e x i s t i n gs t u d yo fa l g o r i t h m ，i n c l u d i n gt h ep r o b l e mo fa c at h a ti se a s y t of a l l i n t os t a g n a t i o na n dt h ep r o b l e mo fa l g o r i t h mp a r a m e t e r st h a ti s d if f i c u l tt ob es e tu p i no r d e rt os o l v et h e s ep r o b l e m s ，t h i sp a p e rp u t s f o r w a r dt h ei n n o v a t i v ec o n c e p to fs t a g n a t i o nc o u n t e rw h o s ef u n c t i o ni s t oj u d g et h es t a g eo fa l g o r i t h m a c c o r d i n gt ot h ed i f f e r e n ts t a g e so f a l g o r i t h m ，t h ei m p r o v e da c aw i l lc a r r yo u t s o m ea d d i t i o n a lp h e r o m o n e u p d a t eo ft h en e w l yd i s c o v e r e db e t t e rp a t h ，s oa st oe n h a n c et h el e a r n i n g t ot h ea n t s o c c a s i o n a lf i n d i n g so f m u c hm o r ee x c e l l e n tp a t h s f u r t h e r m o r e ，t h i sp a p e rp r e s e n t sad y n a m i cp a r a m e t e r ss e t t i n gm e t h o d b a s e do nt h ed i f f e r e n ts t a g e so fa l g o r i t h m ，i no r d e rt oa c h i e v eab a l a n c e b e t w e e ne x p l o r a t i o na n de x p l o i t a t i o n a tl a s t ，w i t han u m e r i c a lt e s t ， c o m p a r e dw i t ht h eb a s i cm m a s ，t h es o l u t i o nq u a l it ya n dc o n v e r g e n c es p e e d o ft h ei m p r o v e da l g o r i t h ma p p li e dt h ea b o v e m e n t i o n e dm e t h o d sh a v eb e e n i m p r o v e ds i g n i f i c a n t l y t h ee f f e c t i v e n e s so f t h ei m p r o v e da c ap r o p o s e d i nt h i sp a p e ri sv e r i f i e d f i n a l l y ，w i t ht h ec o m p r e h e n s i v ea n a l y s i so ft h eg o a l sa n d c o n s t r a i n t s o ft h eu r b a nt r a n s i tn e t w o r ko p t i m i z a t i o np r o b l e m ，t h i sp a p e rp r o p o s e s m i n i m u mt r a n s f e r sa n dm a x m u md y n a m i c a l l yd i r e c tt r a v e l e rf l o wp e ru n i t t i m ea st h et a r g e t ，a n de s t a b l i s h si t sm a t h e m a t i c a lm o d e l a n dt h i sp a p e r m a k e saf u r t h e ri m p r o v e m e n tt ot h ei m p r o v e da l g o r it h mb yp u t t i n gf o r w a r d i n n o v a t i v ec a n d i d a t el i s to fc i t yn o d e sa n dm e c h a n i s mo fd e a t ha n t s p e n a l t ya d a p t i n gt ot h es p e c i f i cp r o b l e mo fu t n o t h e nt h i sp a p e ru s e st h e i m p r o v e da c at or e s o l v et h eu t n op r o b l e m t h ei m p r o v e da l g o r i t h mp r e s e n t e d i nt h i sp a p e rh a sa c h i e v e dg o o dr e s u l t si nt h er a t eo fd i r e c tt r a v e l e r f l o w ，n o n l i n e a rc o e f f i c i e n ta n dl i n er e p e t i t i o nf a c t o r i tm a k e sd i r e c t t r a v e l e rf l o wp e ru n i tt i m em u c hl a r g e ra n dt r a n s i tn e t w o r kc o n f i g u r a t i o n m o r es c i e n t i f i c k e yw o r d s ：a n tc o l o n ya l g o r i t h m ， n e t w o r ko p t i m i z a t i o n ，a l g o r i t h m a lg o rit h mi m p r o v e m e n t ，u r b a nt r a n sit s i m u l a t i o n 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果。据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：望l 盘 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进 行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 学位论文作者签名：学、加 日期：丛! j ! ：山丝 导师签名：弓红 华东师范大学硕十学位论文改进蚁群算法及其在公交线网优化中的应用 1 1 引言 第一章绪论 改革开放以来，随着我国社会的快速发展，城镇化进程不断加快，城市经济 社会文化活动空前繁荣，居民出行量成倍增加，随之而来是道路负荷只益加重、 交通拥挤、事故频发、城市的环境污染加重，严重影响城市发展和人民群众生活 水平的提高，给人们的生活和工作带了诸多不便，是我国城市面临的及其严重的 “城市病 之一，已经成为制约社会、城市可持续发展的瓶颈。 1 2 优先发展城市公共交通的必要性 造成上述城市道路不通畅、居民出行不便的主要原因有： 1 近年来我国各城市家庭轿车等机动车数量急剧剧增，这是导致交通堵塞、 环境污染最主要的原因，而我国的道路建设也不容乐观，目前我国城市道路基础 建设缓慢，新增道路量跟不上飞速增长的机动车增长量和交通需求量，虽然2 0 世纪9 0 年代人均道路面积由2 8 m 2 上升到6 6 m 2 ，涨幅较快，但仍跟不上城市交 通量年近2 0 的增长速度【l l 。特别是我国一些城市经由老城区扩建，原有城市规 划的道路宽度根本不能满足现有的机动车数量，直接导致了道路的拥挤不堪。 2 由于我国现在城市经济水平比较低，交通工具种类繁多，居民根据自身 的需求需用不同的交通工具出行，导致了不同性能和不同功能的交通流在同一道 路路面上混合行驶，相互干扰，特别是机动车受到自行车等非机动车的干扰，行 驶速率非常缓慢，城市道路利用率降低，导致交通问题的进一步恶化。 3 交通发展政策不合理、管理规划不到位、道路路面优先通行权设置不明 确导致了交通结构设置不合理。根据2 0 0 1 年对我国十大城市居民出行调查资料 分析【2 j ，国内交通结构极不合理，在全部出行方式中，自行车占5 0 6 0 ，步行 占3 0 ，其他非公交机动车1 0 左右，而公共交通方式仅占5 一1 0 。不同的出 行方式对道路面积的需求是不一样的，公共交通出行方式道路利用率最高，人均 出行面积仅为1 m z ，非公交机动车人均占路面积为l o 1 5 m 2 ，自行车人均出行为 3 - 4 m 2 。道路利用率最高的公交系统没有得到充分发挥，而道路利用率较低的自 行车却成为交通的主要方式，造成交通运输效率低下。 华东师范人学硕1 ：学位论文 改进蚁群算法及其在公交线网优化中的应用 解决交通问题，仅仅依靠大规模的道路交通工程只能治标不治本，在机动车 数量的持续上涨以及可扩充道路特别是原有老城区道路扩建资源十分有限的现 状下，改善城市交通的出路剁3 】：在继续加强交通设施建设的同时，优先发展城 市公共交通，引导居民出行首选公共交通方式，提高交通资源利用效率，提高公 共交通分担率，以此作为交通政策的核心，并采取有力措施加以实施。 城市公共交通主要包括常规地面公共交通，城市地铁、轻轨等轨道交通和 b r t ( 快速交通) 。目前我国公共交通的主题依然是常规地面公共汽车交通( 简 称常规公交) ，本文的研究也是基于常规公交的线网优化。 1 3 公交线网优化概述 “公交优先 于二十世纪六十年代起源于巴黎，很快就被饱受交通拥挤之苦 的欧美等发达国家所接受，并逐步发展完善，目前在我国的许多城市也达成共识， 并取得逐步实施。在我国各省市大力发展城市公共交通的大背景下，交通状况得 的极大改善，但是随着城市公交需求迅速增长，城市公共交通也遇到了一些瓶颈： 1 城市公共交通的分担率一直处于较低水平。据调查，在我国6 6 0 多个城 市居民的出行结构中，为数众多的5 0 万人口以下的中等城市和小城市，居民公 交出行的比重则普遍不足5 ，5 0 万人口以上大城市居民公交出行的比例大多数 只在1 0 左右，只有少数城市在2 0 左右，像北京、上海、南京等几个中国最 大的城市的平均公共交通分担率才为2 2 。建设部要求特大城市公共交通在城市 总城中的比率达到3 0 以上，大中城市的公交分担率要在2 0 以上，由此可见 目前我国城市公共交通的建设发展离建设部的要求还有很大的差距。分析原因除 了跟政策、观念习惯和经济水平等有些影n l h 彤, l - ，最主要的还是公交本身存在的问 题，如公交服务水平较低、线路设置不科学等。 2 公交线路设置不科学。现有城市特别是中小型城市在设计公共交通布局 时，调研不够深入导致规划不到位，导致城市公共交通线路分布不平衡，部分居 民区、商务区有多条班线经过，公共交通提供量远大于需求量，造成部分公交车 装载率低，浪费资源，而一些小区、郊区的公交覆盖率低、班次少，还存在很多 盲点，导致居民乘车不便，“乘车难”、“出行难”问题严重，居民只能选择家庭 轿车、摩托车、自行车出行。同时由于城市的变迁发展，人口转移导致了交通流 的转移，原有的公交规划已不适应的现在交通流向，原来的交通线网布局已不适 应现在的居民出行需求，需进行线网布局优化改进。 2 华东师范大学硕十学位论文改进蚁群算法及j e 在公交线网优化中的心用 3 公共交通服务水平差。从表1 1 我们可以看出各地区因经济水平和城市 形态方面的原因，公共交通水平差异比较大，不过总体上服务水平是比较低下的， 竞争优势不明显。典型问题有短途乘坐公共交通时间效率低下，以自行车需要 2 0 3 0 的路程两地出行为例，由于候车时间偏久，以及公交车运行速度偏慢，乘 坐公共汽车也可能需要3 0 分钟；长途乘坐公共汽车换乘不便，以家庭轿车出行 3 0 分钟两地出行为例，一般公交直达性比较低，有可能要经过1 或多次换乘， 这样子一来，浪费在候车和换乘的时间非常多，出行效率低下；公交调度不科学， 高峰时段客运量大，特别是上下班高峰时候公交车拥挤不堪，严重影响了乘车的 舒适度，而低峰时段的公交车装载率过低，个别车甚至空载行驶。 表1 1 我国城市公共汽电车的一般服务水平【4 】 序号指标名称2 0 个城市情况统计 1 运送速度( k m h ) 1 l 2 4 2 行车准点率* 1 0 0 7 9 9 2 3 平均站距( m ) 5 0 0 - - 9 0 0 4 换乘率* 1 0 0 2 2 8 8 5 换乘距离( m ) 7 0 5 0 0 6 高峰满载率* 1 0 0 8 0 1 1 5 7 全日满载率* 1 0 0 3 6 8 1 8 乘客候车时间( m i n ) 3 2 0 9 完好车率* 1 0 0 8 8 9 5 1 0 居民公共交通乘用率次“人母年) 12 0 - - 7 6 0 从上面我们可以得出城市居民的出行与公共交通事业发展滞后的矛盾突出， 因此有必要加强改善城市公共公交系统，充分发挥公共交通优势，提高公共客运 效率，增大载客容量，改善服务水平，提高公共交通在整个交通出行中的分担率， 用有限的道路面积解决尽可能多的出行，最大可能的减轻交通压力。公交系统能 否充分发挥自身优势，在可能的资金、资源条件下，做好城市交通系统的建设、 布局和运营，从整体上做出最佳安排，这要依靠于系统工程和计算机来完成复杂 的城市道路规划、公交线网优化、公交车辆调度优化，交通环境改善等。其中， 公交线网优化是一项投资少、见效快、易于实施的有效措施。 公交线网优化是运用现代化的交通规划理论、运筹学、现代计算技术、人工 智能等，在城市原有交通道路系统和公共交通运力的基础上，通过对城市公共交 3 华东师范大学硕t = 学位论文改进蚁群算法及j e 在公交线网优化中的心用 通道路线网合理布局，对现有的公交运力进行优化组合，一方面可以在有限的资 源条件下，充分发挥公交自身的潜能，提高公交运营效率减轻城市道路系统的交 通压力，发挥城市用地的最大效能和交通系统的最大效益；另一方面，公交线网 优化能充分利用公交运输能力，使交通均衡分布，方便居民出行，节约整个社会 的公共交通出行费用，对提高整个城市的交通效率具有重要意义。 1 4 公交线网优化国内外研究现状 国外关注线网优化的研究比较早，公交线网优化大研究发展大致经历三个阶 段【5 】。在6 0 年代初，由于科技发展水平和投资条件的限制，再加上当时公交线 路并不复杂，公交线路规划设置比较简单，公交线网的布局优化采用专家定线的 方式，即在公交线网布设中，采用某权威机构或者专家意见进行布局，这种方法 只定义了布设公交线网应该遵循的原则，多数为线网功能特性的叙述，很少使用 量化的分析。从6 0 年代到8 0 年代，随着工程学和系统工程学科的迅速发展，公 交线网的规划引入系统工程学和运筹学相关理论，在既定的目标函数下，符合一 定得约束条件下，进行线网的优化布设。同时，数学寻优方法开始运用于线网优 化中，该方法将公交线网结构抽象为简单几何形状，在对出行供需关系分析的基 础上，建立数学模型求解来确定最优的公交线路，一般该方法适用于简单的路网。 8 0 年代至今，f e m a n d e z 掣6 】采用组合数学方法，模拟决策者决策过程建立了大 容量公交站点布局和设计专家系统；s u l l i v a n 等【7 】利用流行的桌面g i s 对生成等 时线地图的可行性进行分析，提供了公交最佳路径选择的分析方法。 国内对公交线网优化理论的研究起步比较晚，开始于8 0 年代，主要集中在 寻优模型的建立和已有模型算法的改进。主要有吴稼豪【8 】、夏伟副9 】比较全面的 叙述了有关城市公共交通网络优化问题的模型和方法；王志栋 1o 】提出了以乘客 总出行时间最小、客流直达率最高、线网覆盖率最高、线路重复系数最低、公交 经济效益最高为目标，公交网络优化模型，不过这种模型是无法求解的，最终转 化为单一目标的求解。王炜【4 】提出了以直达客流量最大为目标的公交网络逐条布 设方法，采用“指派问题”( a s s i g n m e n tp r o b l e m ) 法求解。对线路走向优化，以乘 客总出乘行时间最短为目标，采用最短路法求解。其主要优点是线路优化程序少， 并结合部分指标的修正计算( 包括线路长度修正、双向端点配对修正、避免自相 配对修正、一区( 点) 设多站修正等综合进行求解。其主要缺点是算法模型中的试 算工作量较大，并且约束条件数量少，使其对优化效果有一定影响。 4 华东师范人学硕 ：学位论文改进蚁群算法及其在公交线网优化中的应用 同时随着计算机技术和人工智能算法的兴起，基于启发式的人工智能算法在 应用于组合优化问题取得了很好的效果，学者尝试着将人工智能算法引入公交优 化中，并取得了不错的效果。如p a t n a i k 等【l l 】等提出了运用遗传算法设计公交线 网。该模型以公交乘客出行费用和运营费用总和最小为目标，首先生成线路各选 集，然后通过遗传算法进行优选；b a a j 和m a h m a s s a n i 【1 2 】建立了一套基于人工智 能的线网优化解决方案，刘好德掣b 】改进遗传算法，在遗传算法中引入模拟退 火拉伸思想，并研究了其在公交线路优选过程中应用的基本方法：邬开俊、郑丽 英等【1 4 】引入图论中的支撑树来表示问题的解，以乘客公交总出行时间最短与公 交运营投入最小为目标建立数学模型求解最优路径；胡启洲等【l5 】在定义时间、 空间、环境、能源等思维消耗概念的基础上，从点、线、面3 个方面对进行研究， 利用函数建立公交线网优化的多目标现行规划模型并求解。蚁群算法是一种新型 启发式智能算法，在解决组合优化问题方面表现出很好的性能，而公交线网优化 是一个典型的非线性组合优化问题，本论文尝试将蚁群算法运用于求解公交线网 优化。 1 5 论文主要内容及创新处 本文的主要内容包括：一、介绍了蚁群算法及现有的改进方法，针对蚁群算 法容易陷入停滞和算法参数难以设置这两个问题，本文提出了改进方法，并通过 与最大最小m m a s 算法比较得出了本文改进算法在性能上的提高。二、介绍了 城市公交线网优化问题，本文提出了以单位时间动态直达客流量最大为目标，并 建立数学模型，利用本文改进的蚁群算法进行单条线路布设的优化求解后，对乘 客出行o d 表和复线系数进行调整，求出了整个区域的公交线网布局。 本文主要创新之处有：一、在分析现有改进方法的基础上，本文创新性地提 出了停滞计数器概念，利用停滞计数器判断算法所处的探索或者开发阶段，对蚂 蚁新开发的更优路径进行额外的不同程度的信息素加强以及对算法参数进行动 态调整，改进了现有的蚁群算法。二、创新性引入每个城市节点的候选列表和对 死亡蚂蚁的惩罚机制，以及给出了一种动态启发式信息的设置方法，加强了蚂蚁 在路径选择中的偏向性，提高算法收敛速度。三、本文提出了单位时间动态直达 客流量最大为目标，并求出了单条线网布局，同时现有文献只给出了单条线路的 优化布局方法，本文在考虑乘客出行o d 表修正和复线系数修正，改变已设置公 交线路的路段之问的出行时间，算法直接求出了了整个区域的公交线网布局。 5 华东师范人学硕七学位论文 改进蚁群算法及j e 订：公交线网优化中的应用 1 6 论文组织结构 论文主要章节安排如下： 第一章介绍了本论文的选题背景和公共交通线网优化的概念以及研究意 义。 第二章介绍基本蚁群算法概念，结合旅行商问题给出蚁群算法的基本求解 模型，并对算法中参数的设置及其对算法性能的影响做了初步的分析说明。 第三章对城市公共交通线网规划做简要介绍，并引出了公交线网优化的目 标、约束条件，分析了3 种不同的常规公交线网布局求解方法，并运用“逐条布 设，优化成网”方法，结合具体问题给出了常规最短路径线网规划求解实现过程。 第四章分析了蚁群算法存在的一些不足，以及现有的改进蚁群算法的介 绍，提出了本文的改进方法。并通过对t s p 标准数据库中3 0 城市和1 0 0 城市测 试数据进行实验测试，给出了本文改进算法与基本的m m a s 算法性能相比较。 第五章结合第三章的具体线网规划问题，综合分析线网布局优化目标、约 束条件，提出以单位时间动态直达客流量最大为目标，建立了优化数学模型。同 时结合线网优化具体问题模型对第四章改进蚁群算法做了进一步的改进，求出了 单条线网的优化布局。最后在综合考虑乘客出行o d 表的修正和复线系数、已有 公交线路路段的出行时间修正后，求解出整个区域的公交线路布设。 第六章总结本文所做的研究工作，并指出了研究中存在的问题以及今后的 研究方向。 6 华东师范大学硕七学位论文改进蚁群算法及其n ：公交线网优化中的鹰用 2 1 引言 第二章蚁群算法基础 蚁群算法( a n ts y s t e ma l g o r i t h m ) ，是受真实蚂蚁觅食行为的启发下，由意 大利学者m a r c od o r i g o 等于1 9 9 1 年提出的一种新型的元启发式算法，在当时的 学术界并没有引起多大关注，直到1 9 9 6 年d o r i g o 在 i e e et r a n s a c t i o n so n s y s t e m s ，m a n ，a n dc y b e r n e t i c s - p a r tb 上发表了“a n ts y s t e m ：o p t i m i z a t i o nb ya c o l o n yo f c o o p e r a t i n ga g e n t s i t 6 j ，在该文章里进一步系统阐述了蚁群算法的基本 原理和数学模型，将蚁群算法和其它仿生算法( 禁忌搜索算法、模拟退火算法、 遗传算法等) 进行仿真比较，说明了该算法的高效性。蚁群算法首先应用于解决 著名的旅行商问题【1 7 j ( 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 ) 并获得很好的性能，随 后引起广大学者关注，对算法进行各种改进并应用于更多工程领域，典型代表应 用有网络路由【1 8 】【1 9 】、组合优化【2 0 】【2 1 】【2 2 】、数据挖掘等。该算法具有信息正反馈 机制、鲁棒性、协同工作机制以及易于和其他启发式算法结合等优点。 2 2 自然蚂蚁与人工蚂蚁 自然界中蚂蚁个体非常简单，但是由简体个体组成的蚁群却表现出很高的组 织性，当一只蚂蚁找到食物以后，其它的蚂蚁都会被吸引过来，发现该食物源， 同时在蚂蚁来回搬运食物的时候，会有新的蚂蚁开辟比原来更短的道路，更多的 蚂蚁被吸引到这条新丌发的路径上来。最后，经过一段时间，蚁群可能会找到一 条从蚁巢到食物的最短路径，不仅如此，当环境变化时，蚁群能够很快的寻找到 一条新的最短路径，小小的蚂蚁依靠什么来寻找到最短路径呢? 生物学家的研究 表明，蚁群中个体之间以及个体与环境之间的信息传递大部分是借助一种特殊的 化学物质一信息素( p h e r o m o n e ) 来实现的。当蚂蚁离丌食物源走向巢穴时，或 者从巢穴出发到食物源时，都会在所经过的地面上释放信息素，从而形成了一条 含有信息素的路径。当其他的蚂蚁经过的时候，感知到环境中的信息素，将会被 吸引过来寻找食物，同时也有一些蚂蚁会另辟蹊径找到一条更短的路径，从而释 放更多的信息素，慢慢地会有更多的蚂蚁以更高的概率选择这条新的信息素浓度 高的路径来寻找食物。 其实蚂蚁之间并没有直接的交流，每只蚂蚁都只和环境进行交互，蚂蚁选择 7 华东师范火学硕上学位论文 信息素浓度高的路径移动，同时移动过程中释放新的信息素，通过信息素这个纽 带把所有蚂蚁都联系起来了。d e n e u b o u r g 等设计和完成的双桥实验【2 4 】( 如图2 1 所示) 可以很好的说明蚁群寻找食物的行为策略，两条路都通向食物，开始的时 候两条分支上都不存在信息素，因此蚂蚁选择两条分支的概率是一样的( 或者是 因为随即波动，选择较长的路径上的蚂蚁多一些，这不影响实验结果) ，当蚂蚁 沿着一条路径到达食物后马上返回，如此反复，这样子，在较短路径上蚂蚁来回 所用的时间比较短，意味着在同等时间内走过较短路径的蚂蚁数目较多，在较短 路径释放的信息素也比较多，更多的蚂蚁会选择这条路，实验结果表明蚁群最终 会选择这条从食物到巢穴最短的路径。 图2 - 1 双桥实验模拟图 通过上面的分析，我们不难发现蚁群所具有的解决复杂问题的智能行为和自 组织性完全依靠它的简单行为规则，这些规则综合起来具有一下两个方面的特 征：正反馈性和多样性，这正是蚁群算法的来源。多样性保证了蚂蚁在觅食的时 候不至于停滞在一条局部最优路径上，能有更多的机会探索新的路径；正反馈机 制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造 能力，而正反馈是一种学习强化能力。 人工蚂蚁是由自然蚂蚁行为特征的一种抽象，也需要通过信息素来进行间接 通讯，通过协作以群体的方式才能完成一个目标，人工蚁群也同样具有正反馈性 和多样性。但是如果完全依照现实蚂蚁行为机制来设计蚁群算法，实验表明算法 需要很多的时间才会收敛，而且可能会收敛于一些局部最优解，所以人工蚂蚁需 要添加一些额外的特性，主要包括一下几个方面：a 人工蚂蚁具有记忆存储能力， 这样人工蚂蚁就可以消除环路的产生，同时也可以对生成解的质量进行评估，根 据解的质量来决定释放信息素的浓度。b 人工蚂蚁的移动走向不仅仅依据信息素 浓度来确定，还受具体空间特征的启发，如相连路径的距离。c 人工蚂蚁释放信 华东师范人学硕上学位论文改进蚁群算法及其在公交线网优化中的应用 息素的时间视情况而定，真实蚂蚁是在移动的同时释放信息素，而人工蚂蚁可以 选择移动过程中更新信息素，也可以选择在建立一个可行解的时候释放信息素。 d 人工蚂蚁处于一个离散的时间点上，我们只考虑某个离散时间点上蚂蚁处于图 中的哪个节点的状态，而不考虑节点之间的移动过程，而现实世界中的蚂蚁处于 一个连续的时间维中。e 信息素的蒸发，虽然在真实蚂蚁群体中，信息素也随 着时间的推移而蒸发，但是真实蚂蚁的信息素蒸发对于蚁群寻找最优路径并不重 要，相反，因为人工蚁群所要解决的问题要复杂得多，蒸发机制可以让蚁群忘记 过去的劣质选择，使蚁群对已学到的问题结构不断进行改进，显得非常重要。 2 3 蚁群算法基本模型 蚁群算法主要用来解决组合优化问题，能用图来表示的最短路径问题。在求 解不同性质问题的时候，蚁群算法的模型也有所不同，但主要思想都是依据问题 性质构建图，把问题描述成可以被人工蚂蚁用来构建解的表达方式，依据所构建 的图结合具体问题性质定义约束条件、信息素和启发式信息，随后生成一定数量 蚂蚁的蚁群，每只蚂蚁按照一定的规则通过搜索路径建立可行解或者可行解的一 部分。刚丌始时，每只蚂蚁都被随机分配到图的一个初始节点上，蚂蚁从初始节 点出发，按照路径上信息素的浓度和问题特征的启发式信息，以某种概率策略选 择下一个移动的点，直到建立一个可行解或者不符合约束条件而消亡，每只蚂蚁 根据所求解的质量优劣程度，在所经过的路径状态上释放与解的质量成正比的信 息素，之后进入下一个循环，蚂蚁根据路径上新的信息素浓度来搜索路径，直到 找到全局最优解，或者满足一定的条件后退出算法，取得满意解。下面以n 个城 市的旅行商问题( t s p ) 为例来说明蚂蚁算法【1 7 】( a n ts y s t e m ) ，它是第一个蚁群 算法模型，也是其它蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ) 模型的原型。 2 3 1t s p 问题描述 t s p 问题指一群旅行商从一个城市出发丌始访问其它所有的城市，每个城市 能够被访问且仅能够被访问一次，最后回到原先的城市，目标是要找到一条路程 最短的旅行线路。虽然旅行商问题描述非常简单，但是这类问题的求解却非常困 难，由于该问题可能的备选路径随着城市的数目n 的增大成指数级增长，例如一 个1 0 城市的t s p 问题求解有3 6 2 8 8 0 ( = ( 1 0 1 ) ! ) 条路径，而一个中等规模的问题如 1 0 0 个城市的旅行商问题，就有约9 3 3 2 6 e + 1 5 5 种可能的路径，现有计算机己不 9 华东师范人学硕j 二学位论文改进蚁群算法及】在公交线嘲优化中的应用 可能精确求解了，所以人们求助于人工智能算法，希望能够在一个可以接受的时 间内得到一个满意的接近最优的解，蚁群算法就是其中之一。t s p 问题可以用一 个带权完全图g = ( c ，l ) 来表示，其中c 是n = l c l 个城市节点的集合，l 是完全连 接这些城市的边的集合，t s p 问题的本质是在一个n 个节点的完全图上找到一条 路径最短的哈密尔顿( h a m i l t o n ) 回路，是一个典型的n p 一难问题。 2 3 2 蚂蚁算法( a s ) 求解t s p 问题模型0 2 5 i 1 构建图 使用蚁群算法求解组合优化问题时，我们考虑的第一个问题就是构建图的定 义，多数情况下，人工蚂蚁所使用的构建性启发式决定了可选用的图的模式，结 合问题性质我们选择最自然的图的构建放方法。t s p 问题中，构建的带权完全图 g = ( c ，l ) 与问题的描述是一致的，c = c l ，c 2 ， 代表了所有城市的节点， l = 乞i c , ，c j c 代表了城市之间所有的路线，且每一条路线都有一个权值，代 表城市i 到城市j 之间的距离以( i j = l ，2 n ) 。在现实情况中，可能不存在每两 个城市之间都有直达的路线，这只需要设置这些城市之间的路径足够大的权值， 保证他们不会被选中出现在任何优化的解中。t s p 问题的解可以用城市节点序号 的一个排列来表示，这个排列是环状的，所以解中城市的绝对位置是没有关系， 最主要的城市之间的相对位置，即旅行商不管从哪个城市出发，所需旅行的路程 是一致的。 2 定义约束条件 约束条件是蚁群算法求解过程中，结合具体问题，需要满足的一些情况，是 防止人工蚂蚁的状态突破了约束条件，构建出无效的没有实际意义的解，降低了 蚂蚁构建解的效率。实现约束的方法有两种，一种是在人工蚂蚁构建解的过程中 在约束条件范围内选择下一个移动的点，另一种是当人工蚂蚁完成一次接的构建 之后，用一个函数来判断解是否符合约束条件。t s p 问题中的唯一的约束条件是 旅行商必须访问所有的城市节点，且每个节点只能够被访问一次，算法实现中引 入禁忌表t a b u 。用来记录第k 只蚂蚁在本次路径搜索中已经探索过的城市来解 决。 3 定义信息素、启发式信息素 信息素、启发式信息素的定义对于蚁群求解性能的影响是非常大的，幸好对 于很多问题来说，结合问题性质直观定义信息素都能取得很好的效果。t s p 问题 l o 华东师范大学硕 ：学位论文 改进蚁群算法及j 在公交线嗍优化中的应用 中信息素浓度r u ( t ) 表示t 时刻访问完城市i 后直接访问城市j 的期望值。启发式 信息是利用求解问题已有的具体知识来引导蚂蚁的求解，表示蚂蚁在图中的一个 节点访问另一个节点的期望值，t s p 中启发式信息值7 7 ：f ，与城市i 到城市j 的路径 距离相关，距离越短期望值越大，一般取反比关系，比较直接的做法是取 q u2 小uo 。 4 解的构建 解的构建过程对于不同问题是相似的，都是随机产生一群人工蚂蚁，每只蚂 蚁根据信息素和启发式信息来动态的选择下一个访问的节点，直到构建出一个可 行解。t s p 问题的求解过程如下：算法开始时，将m 只蚂蚁随机分配到不同的 城市节点上，将这个城市节点加入到每只蚂蚁k 的禁忌表t a b u 。中，对每条路径 上的信息素赋初值乃( o ) 。蚂蚁k 依据信息素r j ( t ) 和启发式信息通过概率策略 选择下一个要访问的城市，概率规则如下： p k v o o 一 ：耘，萑f 口6 “尼 。2 。， p ：表示本次迭代中，k 蚂蚁由i 城市转移到j 城市的概率，信息素启发式因子口、 期望启发式因子是两个参数，它们分别决定算法中信息素和启发式信息的相对 影响力。每经过一次迭代，蚂蚁就向可行解中添加这次访问的城市，同时修改禁 忌表。当所有城市的被蚂蚁k 访问过之后，蚂蚁k 解的构建结束。 5 信息素更新 d o r i g o 给出了3 种不同信息素更新的策略【2 6 】，分别称为蚂蚁罔( a n t - c y c l e ) 、 蚂蚁密度( a n t d e n s i t y ) 和蚂蚁数量( a n t - q u a n t i t y ) ，更新策略如下所示： 在a n t q u a n t i t y 中， 在a n t d e n s i t y 中， 苟黧如黝( i ，j ) 栅细k 苟= 侄嚣趴i ，j ) 在路径十上 ( 2 2 ) ( 2 3 ) 其中呓为本次迭代中第k 只蚂蚁向他所经过的路径上释放的信息素量，q 为常 数，表示信息素浓度，一定程度上影响算法的收敛速度，吒表示城市i 到城市 j 的距离，严表示本次迭代中第k 只蚂蚁所构建的路径。这两种算法信息素的更 新与蚂蚁所求解路径的优劣无关，且蚂蚁从一个城市移动到另一个城市后立即更 华东师范人学硕j 二学位论文改进蚁群算法及j 在公交线嗍优化中的应用 新信息素，已被证明性能优劣而淘汰。我们现在所使用的策略都是蚂蚁圈策略， 在该策略中只有当所有蚂蚁都构建完可行解，各路径上的信息素才会被更新。首 先，所有边上的信息素都会按一定比率减小，然后在个蚂蚁所构建解的路径上增 加信息素。信息素的更新根据式2 4 执行， l ，卜( 1 一p ) f ，v ( f ，) l ( 2 4 ) 其中p ( o p 1 ) 表示信息素的蒸发率，参数p 的作用是避免信息素的无限积累， 同时使算法忘记蚂蚁之前找到的较差的路径，使蚂蚁具有更多的创新性。信息素 蒸发之后，所有蚂蚁都在它们经过的路径上释放信息素： 卜巧+ 磊l 哆，v ( ，) 三 ( 2 5 ) 在a n t c y c l e 中，书： q 气，如果边“，j ) 在路径t k 上 ( 2 6 ) lo ，否则 厶表示蚂蚁看在本次