蚁群优化算法在求解最短路径问题中的研究与应用.pdf

摘要 摘要 j i l l l1j j l l l f l j li ii i iji i i i ir1111i i j j j l l l i j i i y 2114 0 7 4 最短路径问题一直是交通工程学 计算机科学 城市规划等学科的研究热点 研究最短路径问题具有重要的意义和实用价值 在求解此问题时 传统的最短路 径算法有d i j k s t r a 算法 动态规划算法 启发性的搜索算法有模拟退火算法 遗 传算法 蚁群算法等 蚁群算法作为仿生优化算法 它的全局搜索 工f 反馈 鲁棒性 易与其他仿 生优化算法结合 分布式计算等特点 体现出了求解复杂优化问题的优越性 吸 引了越来越多人的研究 从一开始被运用在解决旅行商问题到图着色问题 车辆 调度问题 再后来应用在动态组合优化问题如通讯网络路由问题等等 蚁群算法 已经广泛应用到各个其他领域中 许多学者通过研究基本蚁群算法 针对它的收 敛速度慢和早熟缺点 提出了很多改进的蚁群优化算法 如蚁群系统 带精英策 略的蚁群算法 多态蚁群算法 基于免疫的蚁群算法 自适应蚁群算法等 本文首先系统地论述了基本的蚁群算法 介绍了几种常见的蚁群优化算法 并对蚁群系统进行了深入的分析 然后针对蚁群算法在求解交通网络两点之间最 短路径问题时存在收敛速度慢和容易出现搜索停滞现象等缺点 为提高搜索效率 和质量 提出了一种改进的蚁群算法 改进如下 1 通过在初始化信息素时加入方向引导因素 减少了劣质解 提高了解 空间的质量 2 设计了一个动态因子 使其自适应平滑地更新迭代最优解路径信息 素 很好地利用了较优的解 提高了搜索比较好的解空间能力 有效 地避免算法求解出现早熟 仿真实验结果表明 不但算法在收敛速度有大幅度地提高 而且在避免易于 陷入局部最优解方面取得了很好的效果 该改进算法是有效的 可行的 最后把 改进的蚁群优化算法应用到g i s 交通网络最短路径问题中 提高了搜索到全局最 优解的速度 关键词 蚁群算法 最短路径 信息素 智能交通 g i g 蚁群优化算法在求解最短路径问题中的研究与应用 a bs t r a c t t h es h o r t e s tp a t hp r o b l e m h a sa l w a y sb e e nt h er e s e a r c hf o c u so ft h et r a f f i c e n g i n e e r i n g c o m p u t e rs c i e n c e a n du r b a np l a n n i n g s t u d yo ft h e s h o r t e s t p a t h p r o b l e mh a v eg r e a ts i g n i f i c a n c ea n dp r a c t i c a l v a l u e i ns o l v i n gt h i sp r o b l e m t h e t r a d i t i o n a ls h o r t e s tp a t ha l g o r i t h m sa r ed i j k s t r aa l g o r i t h m d y n a m i cp r o g r a m m i n g a l g o r i t h m a n d t h eh e u r i s t i cs e a r c ha l g o r i t h m s a r es i m u l a t e da n n e a l i n ga l g o r i t h m g e n e t i ca l g o r i t h m a n tc o l o n ya l g o r i t h m a n tc o l o n ya l g o r i t h mw a sf i r s tp r o p o s e db ym d o r i g oi n19 91 a sb i o n i c o p t i m i z m i o na l g o r i t h m t h eg l o b a ls e a r c h t h ep o s i t i v ef e e d b a c k r o b u s t n e s s a n d c o m b i n e dw i t ho t h e rb i o n i co p t i m i z a t i o na l g o r i t h me a s i l y d i s t r i b u t e dc o m p u t i n g r e f l e c t st h es u p e r i o r i t yo fs o l v i n gc o m p l e xo p t i m i z a t i o np r o b l e m s p r o m o t i n g m o r ea n dm o r es t u d y f r o mt h eb e g i n n i n gi ti su s e dt os o l v et h et r a v e l i n gs a l e s m a n p r o b l e mt ot h eg r a p hc o l o r i n gp r o b l e m v e h i c l es c h e d u l i n gp r o b l e m a n dt h e nl a t e r u s e di nd y n a m i cc 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 ss u c ha sc o m m u n i c a t i o n n e t w o r kr o u t i n gp r o b l e m s a n tc o l o n ya l g o r i t h mh a sb e e ns u c c e s s i v e l ya p p l i e dt o v a r i o u so t h e ra r e a s m a n ys c h o l a r st h r o u g ht h es t u d yo fb a s i ca n tc o l o n ya l g o r i t h mf o r i t ss l o wc o n v e r g e n c ea n dp r e m a t u r es h o r t c o m i n g s p r o p o s e dm a n yi m p r o v e da n t c o l o n yo p t i m i z a t i o na l g o r i t h m s s u c ha sa n tc o l o n ys y s t e m a n tc o l o n ya l g o r i t h m w i t he l i t i s ts t r a t e g y 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 a n tc o l o n ya l g o r i t h mb a s e do n i m m u n i t y a d a p t i v ea n tc o l o n ya l g o r i t h m t h ea r t i c l ef i r s td i s c u s s e sab a s i ca n tc o l o n ya l g o r i t h m i n t r o d u c e ss e v e r a l c o m m o na n tc o l o n yo p t i m i z m i o na l g o r i t h m s a n dd e e p l ya n a l y s i sa n tc o l o n ys y s t e m t h e nc o n s i d e r i n gt h ea n tc o l o n ya l g o r i t h mi ns o l v i n gt h es h o r t e s tp a t hb e t w e e nt w o p o i n t so ft r a n s p o r tn e t w o r kh a st h es h o r t c o m i n g ss u c ha ss l o wc o n v e r g e n c ea n db e p r o n et os t a g n a t i o np h e n o m e n o n t h ea u t h o r sp r o v i d e sai m p r o v e da n ta l g o r i t h m t h e i m p r o v e m e n t si n c l u d e i ta d d st h eh e u f i s t i cd i r e c t i o ni n f o r m a t i o n r e d u c e st h ei n f e r i o r s o l u t i o n i m p r o v e st h eq u a l i t yo fs o l u t i o n 2 d e s i g n sad y n a m i cf a c t o r t oa d a p t i v e l ya d j u s tt h e r e n e w a lo f a b s t r a c t p h e r o m o n eo nt h eo p t i m a ls o l u t i o n w h i c h i sm o r ec o n d u c i v et o o p t i m a lp a t h i m p r o v et h ec a p a b i l i t yo fg l o b a ls e a r c h a v o i dt h a tt h e a l g o r i t h ma p p e a r sp r e m a t u r e t h er e s u l t so fe x p e r i m e n ts h o wt h a tt h ei m p r o v e da l g o r i t h me n h a n c e st h e c o n v e r g e n c el a r g e l ya n de f f e c t i v e l ya v o i d sg e t t i n gi n t o l o c a lo p t i m a le a s i l ya n di t p r o v et h ev a l i d i t y o ft h ei m p r o v e da l g o r i t h m f i n a l l y a ni m p r o v e da n tc o l o n y o p t i m i z a t i o na l g o r i t h mi sa p p l i e dt ot h eg i st r a n s p o r t a t i o nn e t w o r ks h o r t e s tp a t h p r o b l e m t oi m p r o v et h es p e e do ft h es e a r c ht ot h eg l o b a lo p t i m u ms o l u t i o n k e y w o r d s a n t c o l o n y a l g o r i t h m s h o r t e s t p a t h p h e r o m o n e i n t e l l i g e n t t r a n s p o r t a t i o n g i s 第一章绪论 第一章绪论 1 1 选题背景及意义 现在的城市已经进入 数字城市n h 数字城市 是对城市发展的另一 种认识 数字化认识物质城市及其现象 用数字化的形式来分析 研究城市的人 流 物流 交通流 信息流 使其能够协调顺利的进行 而地理信息系统即g i s 是实现数字城市的一个重要的支撑技术 以空间地理位置为基础 综合各种信息 而成的系统 地理信息系统一般用空间特征数据和属性特征数据来表示现实世界 空间的实体对象的 空间特征包括各个实体的空间位置 以及实体之间的关系等 如 经纬度 是否相邻等 而属性特征包括实体的各个特征 如颜色 道路长度 面积等 在地理信息平台上以空间作为坐标 以物质城市的交通 经济 文化 科技等各行业作为属性信息以时间的序列展示出来 把空间特征数据和属性特征 数据综合成为一个相互联系的对象 以全新的面貌展现在人们的面前 使我们对 城市的规划 交通 电力等各个领域有了更为直观感性的认识 更好的规划 建 设 管理城市的发展 我们只需要坐在一个电脑面前 就可以全面认识城市 规 划设计城市布局 配置资源 使城市得到更有效的调控 改善和可持续的发展 g i s g e o g r a p h i ci n f o r m a t i o ns y s t e m 郾 是在地理空间数据库的基础上 以 计算机软硬件为支持 运用现代工程技术和计算机科学的理论 对地理空间数据 以及数据之间的关系属性进行深入地研究分析 给相关地理人员或者管理人员提 供参考决策的技术系统 简单的说 g i s 是以计算机编程为平台 综合研究 空 间分析具有空间实体位置坐标及其属性的一种技术系统 随着g i s 技术的不断 深入研究和应用发展 g i s 目前已经被大量地渗透到城市规划 交通运输 电力 设施 社会经济等几乎所有领域 伴随着我国经济的迅速发展 人们的生活越来越富裕 对生活质量要求越来 越高 城市的道路建设也越来越好 但是目前车辆的增长速度远远超过了道路网 络的扩展速度 出现了道路很复杂并且常常拥挤堵塞情况 这不仅影响了交通运 输的运输效率 而且会直接影响人们的生活 阻碍了城市的发展建设 为了解决 交通问题 必须依靠现在科学技术 选择合理的道路选择机制 更有效的提供道 路实时信息 指导人们选择最短的出行路径 将无序的交通出行变得有序 减少 蚁群优化算法在求解最短路径问题中的研究与应片j 出行的盲目性 避免高峰路段 提高城市道路交通的运输效率 对于研究道路交通网络中的最短路径问题的研究 很多学者提出许多有效的 方法 在现代科学技术的不断发展基础上 智能交通系统这个名词自从出现后就 一直受越来越多人的关注 它将计算机技术 网络技术和智能软件技术等综合运 用在一起 应用在交通网络中 为人们提供最佳的出现路线 有效地缓解了目f j 道路拥塞问题 保障了交通网络的运行效率 最短路径问题是智能交通系统的重 要的研究课题 其中近年来的热点是利用地理信息系统 g i s 技术来解决最短路 径问题 4 5 j 以数字化的形式 存储在电子地图上 地图上的道路名 道路位置 道路拓 扑结构 完全反映实际的道路状况 智能交通系统可以指导车辆驾驶人 按照他 的意愿 根据某个因素或者多个因素 选择一条从起始点到目的地之间的最短路 径 驾驶员就可以按照给出的路径很快的到达目的地 少走一些不必要的弯路 这对一个不熟悉道路状况 对城市很陌生的驾驶人来说 更加的迫切有效 将 g i s 技术应用在 数字城市 中 已经成为建设城市的一个强有力的工具 具有 划时代的意义 1 2 最短路径问题 最短路径问题一直是图论中的一个传统的算法问题 目的在于寻找图中任 意两个节点之间的最短路径 城市道路交通网络中的最短路径问题不仅仅是静态 道路中最短的路径 还有动态的最短路径 包括时间 费用最短 道路中可能绕 过临时障碍物 道路阻塞拥挤 道路的权值等等因素 动态计算出当前最佳路径 寻找出从起点到终点的一个或多个方面因素的费用总和最小的路径 1 2 1 最短路径问题定义 设p s e 是加权图g 中的从s 到e 的路径 则该路径上的边权值之和称为 路径的权值 记为w p 而从s 到v 的最短路径则为w p 值最小者的路径 p 母 s e 根据起始节点 目的点的个数 最短路径的条数 以及道路的弧段长 度 道路的权重 道路是否畅通以及是否含环等特殊因素可以把最短路径问题划 分为几种不同的类型 如图1 1 所示 第一章绪论 图1 1 不同的最短路径问题的类型 1 2 2 最短路径问题研究方法 最短路径问题一直是交通运输 计算机科学 物流学等学科的热门研究课题 研究最短路径问题具有重要的意义和实用价值 在求解此问题时 传统的最短路 径算法有d i j k s t r a 算法 6 1 动念规划算法 启发性的搜索算法有a 宰算法 7 1 模拟 退火算法 遗传算法 蚁群算法 6 1 几种仿生优化算法结合的算法等 它们自 从出现之后 受到各领域的广泛关注 也产生许多相对应的改进算法 并且在实 际中获得了应用 1 2 3 最短路径问题求解方法 1 d i j k s t r a 算法 d i j k s t r a 算法是传统的求解单源最短路径算法 已经得到较完善的发展与应 用 是从起始节点开始寻找其他节点到该节点的最短距离 设置节点集合s 和v 初始化时 s 中仅有开始节点 然后不断选择v s 中 的一个节点u 搜索从开始节点到u 中间只经过集合s 中节点的路径 并用d i s t 记录从起始节点到u 中的最短路径和路径长度 一旦u 恰好就是目的节点时 输 3 蚁群优化算法在求解最短路径问题中的研究与应用 出这时的最短路径和路径长度 算法终止 d i j k s t r a 算法本质上是贪婪算法 在所有方向上都搜索 以开始节点层层向 外扩展 直至扩到目的节点为止 而在过程中有意图地向目的节点位置靠拢 搜 索到的路径一定是实在的最短路径 但是其时间复杂度为0 n 3 节点越多 搜 索的开销成倍增加 效率很低 对于庞大的g i s 数据时 几乎是不可能的事 2 a 木算法 a 宰算法是一种经典的启发式搜索方法 通过估价函数来评估路径的长短 f i m g m h m 其中 f m 是算法的估价函数 它的大小表示路径的估价值 g m 是个确定 值 代表从起始节点到节点m 的实际所需要的代价 而h m 是表示从节点m 到 终点的最好的估价的所需要的代价 算法的关键在于估计函数h m 的设计好坏 h m 总是小于或者等于当前节点m 到终点的实际距离 搜索的效率越好 估价 值就越逼近或者等于实际最短路径值 3 模拟退火算法 模拟退火算法是在给定的一个初始温度条件下 随着算法的进行 温度参数 不断的下降 运用概率的跳出特点 在解空间中随机的寻找较优解 而最终这个 解会趋向于全局最优解 它的一个优点是在局部最优解情况下 有概率性地跳出 并收敛于全局最优解 不仅可以进行局部搜索 还可以一定概率跳出避免陷入局 部最优解中m 4 遗传算法 遗传算法 g a 是在1 9 7 5 年由j o h nh o l l a n d 教授在一书中首先提出的 是模 拟生物界中自然选择和遗传机制的一种仿生优化算法n 引 该算法将优化问题来模 拟自然界中生物的进化过程 通过大自然中生物不断进化和淘汰机制 来达到寻 优的目的 被广泛应用于n p 问题和多目标优化问题 g a 算法的主要思想是随机 产生解空间编码 通过一个适应度函数来引导进化 对编码进行选择交叉变异操 作 使较高适应度值的个体以较大的概率复制交叉变异生成新的下一代 最终通 过代代选择繁殖 步步逼近最优解 5 蚁群算法 蚁群算法是一种基于蚂蚁群体的模拟进化算法 1 9 是对自然界中真实蚁群行 4 第一章绪论 为的一种模拟 通过对蚂蚁觅食行为的研究启发而提出的 蚂蚁在它所经过的路 径下留下彼此可以识别进行信息传递的物质 这种物质叫信息素 蚂蚁在选择下 一个步时总是趋向于选择走信息素浓度较高的路径 因此 尽管单个蚂蚁是无规 律的 但是大量蚂蚁之间经过适应与协作组成的群体的活动表现出来的一种信息 正反馈现象 相对比较短的路径 蚂蚁经过的次数就相对较多 该路径上的信息 素浓度就会相对比路径较长的大 以后的蚂蚁选择该条路径的概率就会相对较 大 从而促进该条路径的蚂蚁继续增多和信息素的继续变大 根据蚂蚁的正反馈 作用 最终蚂蚁通过个体之间的这种信息交流 搜索到一条最短路径 在众多求解最短路径算法中 蚁群算法 l 表现的发现较好解的能力和相对较 好的性能 作为一种仿生优化算法 它具有很好的鲁棒性 计算的并行性 易于 其他仿生优化算法互补结合以及正反馈机制等优点 但容易出现停滞早熟现象和 计算收敛时间比较慢等缺点 自1 9 9 1 年d o f i g o 学者等人提出蚁群算法后 国内 外学者通过对蚁群算法的深入研究 相继改进了蚁群算法 国外的有如精英蚂蚁 系统 排序蚁群算法 最大最小蚂蚁系统 蚁群系统 a c s 等 8 6 1 尽管国内 对蚁群算法的研究相对较晚 但是也有不少改进优化算法的提出 在蚁群算法改 进方面 有如变异的蚁群算法 自适应蚁群算法 奖惩蚁群算法 还有与其他仿 生优化算法结合的算法如遗传蚁群算法 免疫蚁群算法等 蚁群算法从一开始求 解t s p 问题 一直被不断的深入研究与应用 已经被应用在各个领域 如交通 旅游问题 通讯网络中的路由问题 负载平衡问题 车辆调度等问题 蚁群算法 的应用可归纳为两类 一类是应用于静态组合优化问题的求解 如t s p 问题 另一 类是应用于动态组合优化问题的求解 如网络路由问题 路径分析是g i s 中重要的功能之一 在当今社会寻到最短路径 实现路径最 短 运输成本最低等变得非常迫切 在庞大的g i s 数据中 启发性寻址算法越来 越占优势 而蚁群算法是其中的全局性算法之一 基本蚁群算法计算速度慢 容 易陷入局部最优解 因此研究改进蚁群算法 加快收敛到全局最优解 减少局部 最优解已经变得必要 1 3 论文研究工作及结构安排 本文回顾了基本的蚁群算法的理论 详细分析了蚁群系统的实验参数对实验 5 蚁群优化算法在求解最短路径问题中的研究与席用 结果的影响 介绍了几种典型的改进蚁群算法 重点是对蚁群系统进行改进 初 始化信息素浓度时加入了方向引导 而不像其他算法中初始化时每个节点信息素 浓度都为一个常数 使蚂蚁在选择下一节点时 越趋向于终点的节点 蚂蚁选择 该节点的概率相对较大点 在全局信息素更新上引入了s i g m i o d 函数作为动态因 子o r 自适应平滑地调节每次迭代最优解对路径的信息素更新的比重 最优解越 短的信息素加成的越多 反之较长的加成的较少 仿真结果表明 它与a c s 相 比 有较好的寻优能力和收敛能力 最后将本文改进的蚁群优化算法应用于g i s 系统中 本文主要研究工作及安排如下 第一章 绪论 主要阐述 数字城市 概念以及用g i s 技术来解决最短路径问题的重要性 描述了交通网络最短路径问题定义 介绍了目前求解最短路径问题的研究现状并 简介了本文所要做的工作 第二章 蚁群优化算法 首先详细系统地论述了基本蚁群算法 包括基本原理 应用和优缺点 并针 对基本蚁群算法存在收敛速度比较慢 容易陷入局部最优解问题的缺点 介绍了 当前几种比较典型的改进蚁群优化算法 求解性能上得到一定程度上的改善 第三章 蚁群系统求解无向图最短路径问题 系统地论述了蚁群系统求解无向图最短路径问题 对蚁群系统的几个主要参 数进行了实验性分析 并推算实际较优参数的设置 第四章 改进的蚁群优化算法求解无向图最短路径 详细论述了本文的改进蚁群优化算法 初始化信息素时加入方向引导和全局 信息素更新时引入动态因子 并通过实验仿真 和蚁群系统以及目前其他论文算 法进行了比较 结果有效地验证了改进性 第五章 改进的蚁群优化算法求解g i s 交通网络最短路径问题 描述7 g i s 概念发展现状 模型和最短路径平台的建立 应用改进的蚁群优 化算法求解实际的g i s 地图交通网络最短路径问题中 第六章 结论与展望 总结了本文对蚁群算法 本文改进的算法以及其在g i s 中的应用研究进行了 总结 实验结果表明 改进的蚁群优化算法提高了解空间质量 很好的利用了较 6 第一章绪论 优解 有效的避免陷入局部最优解 提高了收敛到全局最优解的速度 但是对蚁 群算法的尚需要更深入的研究 介绍了下一步的工作 7 蚁群优化算法在求解最短路径问题中的研究与应用 2 1 蚁群算法 第二章蚁群优化算法 2 1 1 蚁群算法的基本原理 根据仿生学家的研究结果表明 单只蚂蚁不能找到从巢穴到食物源的最短路 径 4 引 而大量蚂蚁之间通过相互适应与协作组成的群体则可以 蚂蚁是没有视 觉的 但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质 叫信息 素1 4 引 来相互传递信息 达到协作的 蚂蚁在搜索食物源的过程中 在所经过 的路径上留下信息素 同时又可以感知并根据信息素的浓度来选择下一条路径 一条路径上的浓度越浓 蚂蚁选择该条路径的概率越大 并留下信息素使这条路 径上的浓度加强 这样会有更多的蚂蚁选择次路径 相反 信息素浓度少的路径 蚂蚁选择的概率小 该路径随着时间的推移信息素逐渐挥发 而导致以后蚂蚁选 择的可能性更小 最终蚂蚁找出了最优路径 2 0 2 3 同时当运动的路径出现障碍物 时 蚂蚁可以很快的适应环境的变化 绕过障碍物重新找到最优路径 蚂蚁就是 通过群体问相互交换信息 自催化行为来实现正反馈过程找到当前最短路径的 自然界的觅食行为可以通过下图来模拟 并且说明了蚁群群体的搜索原理 1 2 8 图2 1 蚂蚁从巢穴到食物源的搜索过程 第二章蚁群优化算法 如图2 1 a 是食物源 f 是巢穴 a b b d d e e f 长度都为1 b c c e 长度为2 假设蚂蚁爬行速度为1 一个时间单位蚂蚁在经过的路径上残留信 息素为l 所有的路径上的信息素浓度一开始都初始化为o 当t 0 时 在巢穴f 处放置4 0 只蚂蚁 它们开始寻找食物源a 当t l 时 它们都到达e 处 有两侧道路可以选择 因为c e 年i d e 上没有信息素 所以它们选择左侧道路或右侧道路的概率是一样的 2 0 只蚂蚁走左侧 2 0 只走右 侧 当t 4 时 选择了b d e 路径的蚂蚁到达食物源 并立即返回 而此时选择了b c e 路径的蚂蚁正在b c 中点处 当t 5 时 正在返回的蚂蚁和正赶往食物源的蚂蚁j 下好在b 处相遇 此时b c 和b d 路径上的信息素浓度是一样的 所以返回的2 0 只蚂蚁中 有1 0 只将选择b d 1 0 只选择路径b c 当t 7 时 有2 0 只蚂蚁在b 处 因为b c 和b d 路径上的信息素一样 所以将有1 0 只选择b c 1 0 只选择b d 另外此时有l o 只蚂蚁在c 处 1 0 蚂蚁在e 处 当t 8 时 在巢穴上的有1 0 只蚂蚁 同时c e 的中点处 b c 的中点处和d 点上也 各有1 0 只蚂蚁 当t 9 时 已返回巢穴的l o 只蚂蚁到达e 处 此时 c e 上的信息素浓度是3 0 而d e 上是4 0 因此将有较多的蚂蚁选择右侧道路d e 从而增强了该路径上的信息 素 使得d e 上的信息素浓度 f c e 的差值变大 直接导致后来的蚂蚁选择d e 的概率 更大 进而又促进它们的信息素浓度差异越来越大 越来越多的蚂蚁选择路径d e 从而最终的结果是所有蚂蚁选择了路径d e 找到了最短路径a b d e f 蚂蚁通过群 体间的协作来寻找食物源的行为过程表现出正反馈现象 一条路径上蚂蚁经过的 越多 留下的信息素也就越多 后来的蚂蚁选择该条路径的概率也就越大 从而 又促进了该条路径的信息素浓度 最终蚂蚁找到了最短的路径 受到蚂蚁觅食行为的启发 d o r i g om 提出了蚁群算法 该算法是一种仿生优 化随机算法 是基于蚂蚁群体之间的信息交流进化过程 最终找到了一条最优解 它包括了两个方面 适应阶段和协作阶段 在适应阶段 各候选解按照路径上的 信息素浓度来不断调整自身的结构 某条路径上蚂蚁经过的总次数数目越多 路 径的信息素也就越多 这样以后的蚂蚁在选择下一节点时选择该路径的可能性相 蚁群优化算法在求解最短路径问题中的研究与应用 对来说就会越大 相反 某条路径上蚂蚁经过的次数越少 路径上的信息素越少 蚂蚁选择该路径的可能性就越小 随着信息素的挥发机制 信息素变得更少 在 协作阶段 候选解之间经过信息交流与互换 以期望在解空间中搜索到更好的解 蚁群算法对搜索的空间的了解具有记忆性 一次遍历过程中同一只蚂蚁对已经搜 索过的路径下次搜索时是不会选择的 是通过利用禁忌表来模拟的 蚂蚁在经过 的路径上释放信息素 用数字信息量来记录下来 较短的路径上的数字信息量会 相对较多 从而蚂蚁选择该路径的概率较大 从而更加促进了该条路径上的数字 信息量的积累 通过正反馈作用 全局最优解上的路径的数字信息量会越来越多 与其他路径上的差异会越来越大 最终所以蚂蚁集中选择该路径 2 1 2 蚁群算法的数学模型 t s p 是蚁群算法求解经典的组合优化问题 2 4 之5 1 下面以t s p 为例来说明 删 设有m 个蚂蚁 n 个城市 用变量z 疋 户1 2 n 表示城市节点f 和城市节蔚 之间的弧段长 r j t 表示在某时刻t 时 城市f 和城莉两个节点之间弧段的信息素 浓度 来模拟实际蚂蚁的分泌 一开始我们假定所有路径上的信息素浓度都相等 并设为r u 0 c o c o 为常数 蚂蚁k 1 2 m 在搜索遍历过程中 根据路 径上的信息素浓度来选择下一步 禁忌表t a b u k 记录蚂蚁k 经过的路径记录 信息 启发式因子口 反映了路径上的信息素对蚂蚁选择作用强度 其值相对来说较大 蚂蚁选择信息素浓度相对较高的路径的概率就会较大 随机性相对较小 口表示 期望启发式因子 表明启发信息对蚂蚁选择下一步时的影响程度 其值越大 蚂 蚁相当于在做贪心规则 信息素浓度乃和启发函数 l 乃 蚂蚁根据如 下转移规则选择下一节点 咖 e 罴 t r l f 洲州毗 2 1 已 m 胁 r f 7 0 仨a l l o w e d 女 其中 a l l o w e d k o 1 n 1 卜一t a b u k 表示蚂蚁在选择一个城市时可 以选择的城市集合 为了避免道路信息素的过渡积累 导致启发信息作用的弱化 每当蚂蚁k o l o 第二章蚁群优化算法 l m 行进 步或者完成所有城市的遍历 一次循环遍历 后 要对它行进的 这次路径上的信息素进行一次更新 其表达式为 2 2 式 弓 f 功 1 一力木弓o 巧 2 2 f 多 k i 2 3 其中p 0 p g a m 籼f d d l a n 瑚l l dm da s a 趟 1 9 势 l t e t m a n e d o e m e ra n dh 一l舢 列络路由 s c b o o e d e r w e a d 髓虹1 9 9 6 1 9 9 7 1 甜嘲d i c a m 酬d o 伽 1 9 9 7 1 9 9 8 r o u t i n g s l m 柚d s 哺1 9 鳟 另外蚁群算法还可以很好的与其他仿生优化算法结合 达到优势互补 最 早的是集成蚁群算法和遗传算法的融合算法 2 9 l 遗传算法尽管具有快速全局搜 索能力 但是没有很好的利用系统的正反馈信息 很多较好的解缺失掉了 求解 效率低 而蚁群算法具有很好的鲁棒性 并行计算能力 正反馈和发现较好解的 能力 但是算法初期的路径上的信息素浓度极度贫乏 信息素浓度差别不大 导 致蚂蚁选择路径时的随机性很大 收敛速度慢 两者的结合既可以很好的利用遗 传算法产生解空间编码的快速性 随机性来形成问题的初始化信息素分布 又利 用到蚁群算法的正反馈机制 并行性 发现较优解能力强等优点 还有蚁群算法 和人工免疫算法的融合 蚁群算法和人工鱼群算法的融合等等 蚁群优化算法在求解最短路径问题中的研究与应用 2 1 5 蚁群算法的优缺点 蚁群算法是模拟自然界中蚂蚁觅食行为的随机搜索算法 3 0 具有正反馈作 用 通过一群蚂蚁之问的信息交流和传递 最终找到最优解 蚁群算法具有的优 点如下 1 鲁棒性性很好 对蚁群算法的模型进行的稍微的修改 就可以求解很多 不同类型的问题 2 并行性计算能力 蚁群算法是一种基于群体的随机搜索算法 具有并行 计算的能力 在求解大规模问题时 可以很明显的减少算法的计算时间 3 具有正反馈机制 某条路径上的信息素浓度高 蚂蚁选择该路径的概率 就大 进而经过此条路径上的蚂蚁数目就多 促使该条路径上的信息素浓度不断 的增加 路径上的信息一开始极度贫乏 由于正反馈作用 一段时间后 较短的 路径上的信息素相对较多 最终蚂蚁集中在最优解的路径上 4 易于与其它方法结合 蚁群算法很容易和很多不同的启发式算法结合 达到算法间的优势互补 提高算法的求解效率和求解能力 大量研究表明蚁群算法有很好的搜索到较优解的能力和较好的算法性能 算 法的进化过程中利用到了正反馈机制 提高了对蚂蚁每次搜索解的利用 并且具 有计算的并行性 蚂蚁通过群体之间的进行信息交流 相互适应与协作 很快收 敛于解空间的较优解的路径上 不断地探索解空间 减少了收敛到局部最优解的 可能性 尽管蚁群算法有很多优点 但是也有一些缺点 如 1 与其他算法相比 该算法收敛速度慢 搜索需要一段较长的时间 4 从蚁群 算法的复杂度可以反映出来 尽管现在计算机的性能和算法的计算并行性 对求解问题有所缓解 但是如果求解大规模的组合优化问题时 由于蚂蚁个 体搜索的随机性 尽管通过群体问的适应与协作 彼此之间进行信息的交流 与传递 最后蚂蚁趋向于选择全局最优解的路径 但是由于初期的信息素浓 度极度贫乏 路径之间的信息素差异区别不够明显 蚂蚁有很大可能根据启 发信息来选择下 步 甚至蚂蚁选择的路径是较差路径 这给后来的蚂蚁起 了误导作用 更加延迟了收敛时间 所以很难在较短的时间内 蚂蚁从大量 的解空间中找出 条较优的路径 不过通过蚂蚁间的j 下反馈作用 路径上的 1 4 第二章蚁群优化算法 信息素差异才慢慢变大 最终蚂蚁找出了全局最优解 2 算法容易出现搜索停滞现象 即算法进行到一定程度后 所有蚂蚁都集中走 同一条路径 不能进行新路径的搜索 不能发现更好的解 算法收敛到局部 最优解而非全局最优解 3 蚁群算法研究起步比较晚 数学基础不够坚实 还需要进一步的研究 由蚁群算法的介绍可知 蚂蚁的状态转移规则是按照路径上的信息素浓度和 城市之间的距离来计算的 蚂蚁总是趋向于走信息素浓度最强的路径 该路径和 实际上的最短路径比较接近但不相同是有一定概率出现的 这和搜索的初始阶段 有一定的关系的 在蚂蚁搜索的起始阶段 路径上的信息素分布差异不大 特别 是第一循环遍历 蚂蚁主要靠城市之间的距离这一启发信息来决定转移方向的 蚂蚁在这条路径上留下的信息素不一定真正反映在实际上的全局最优路径 而有 可能是和全局最优解上的路径差异很大 这会给后来的蚂蚁起了误导作用 通过 正反馈作用 该路径得到信息素的一定程度的加强 阻碍了蚂蚁选择更好的解 甚至有可能导致算法出现早熟停滞 不能产生全局最优解 国内外的许多学者对 以上问题进行了研究 并提出了改进算法 主要是通过尝试对算法的基本规则 参数的动态调整 与其他启发式算法的结合 来提高算法的发现较优解的能力和 收敛速度 2 2 精英蚂蚁系统 精英蚂蚁系统1 1 9 的蚁群算法的比较早的改进 为了突出当前的最优解在蚂 蚁搜索路径时的分量 对下次迭代搜索的蚂蚁产生更多的吸引力 在每次迭代都 要给予目前为止的当前最优解的路径上额外的信息素浓度的加成 某个蚂蚁找出 了这个当前最优解 则这个蚂蚁就叫精英蚂蚁 设从开始到现在为止找出的最优的路径为t b 3 最优路径t 6 3 的长度为l 宰 则每次循环信息素更新按照式2 7 更新 乃 t n 1 一户 木乃 呓4 a t f 幸 2 7 七 1 j 詈 若边i j 是所找出的最优解的一部分 10 否则 蚁群优化算法在求解最短路径问题中的研究与应用 其中盯为一个设定参数 定义权值大小 实验表明 选用一个合适的盯 可以使蚂蚁系统找出更优的解 并且缩短了 收敛周期 但是盯设置过大 对当前最优解的加成过大 蚂蚁选择该条路径的可 能性变得很大 而选择其他路径的概率很小 导致蚂蚁很快收敛早熟 重复地在 同一路径上移动 而不能找到更好的实际存在的解 2 3 基于排序的蚂蚁系统 基本蚂蚁系统和精英蚂蚁系统都有一个缺点 在循环迭代过程中 蚂蚁趋向 于在较优解的路径上 候选解路径上的信息素浓度差异不断减小 导致蚂蚁选择 它们的路径上的概率差异也变得较小 这样使得蚂蚁在行进过程中 不能很快的 集中在全局最优解附近 阻止了发现更优解的进程 甚至最终陷入局部最优解 中 而基于排序的蚂蚁系统改进方法为 当所有蚂蚁完成一次循环后 即一次 迭代后 对蚂蚁进行排序 前仃一1 只蚂蚁和当前最优解才可以释放信息素 对经 过路径进行信息素加成 其他的蚂蚁路径适当的挥发 信息素更新规则按照式 2 8 进行更新 o 1 勺 玎 p 宰乃 苟 乃 2 8 七 l 呓 p 一屉 古 若第k 只蚂蚁经过路径 i j 0 否则 号 若边i j 是所找出的最优解的一部分 0 否则 其中o r 为设定值 k 为蚂蚁的排序号 力为第k 只蚂蚁在所经过路径上的信 息素加成 r 为第k 只蚂蚁的路径长度 l 唪为当前最好的解的长度 选择一个合适的盯值 可以有效地利用蚂蚁中较好的解 同时又对当前最优 解进行额外的加成 使得较优解路径与较差解路径的信息素差异变得越来越大 根据正反馈作用 蚂蚁选择较优解的可能性变大 加快了蚂蚁集中到最优解的速 度 1 6 第二章蚁群优化算法 2 4 蚁群系统 蚁群系统 a c s 是在蚂蚁系统 a s 的基础上进行了三个改进 2 9 1 a c s 采用了不同的状态转移规则 称之为伪随机比例规则 而a s 采用 的是随机比例规则 位于第i 个城市的蚂蚁k 有一定概率会按照先验知识选择它的下一步j 当q q o 时 a r g 碑a x 乃 f i a l l o w c a l 当g q c 时 蚂蚁根据概率转移公式b f 选择下一城市 弓 f 水砒w 以 a 舭哦乃 f 芦 f o j 正a l l o w e d k 其中g d 为给定参数 0 q o 吼时 蚂蚁以 1 一q o 的概率有偏向性的探索各条边 和a s 中的规则一样选择下一步城市 2 全局更新规则只更新当f j 最优解路径上的信息素浓度 而在a s 中全局 更新规则对一次循环中的所有蚂蚁经过的路径进行信息素更新 减少了信息素浓 度差异的变化 降低了搜索到最优解的速度 而在a c s 中 由于每次循环只对当 前最优解的路径进行信息素更新加成 突出了最优解的分量 促进了蚂蚁倾向选 择最优解路径的边 加快了搜索到最优解的速度 全局更新规则公式为 f u 1 一 f fu 嵋 亡 边 i 堋于全局最优解 o 否则 其中 为信息素挥发参数 厶 为当前为止的迭代循环最优解的最短的解 3 a c s 采用了局部更新规则 蚂蚁在构造路径的同时进行信息素浓度的 局部更新 而在a s 中 只在每次迭代后 对所有的蚂蚁经过的路径进行全局信 息素浓度更新 局部更新规则公式为 蚁群优化算法在求解最短路径问题中的研究与应用 f 盯 1 一p r 玎 尸f o 其中p r o 为给定参数 当某个蚂蚁经过边 i j 路径后 随即挥发些该边的 信息素浓度 这样就可以使蚂蚁选择其他路径的概率增大 增大了算法的全局搜 索能力 从而增加了选择未经过知边的可能性 一定程度避免了早熟收敛 2 5 最大最小蚂蚁系统 蚁群系统中 只有当前最优解的路径可以进行信息素更新 该路径上的信息 素浓度过高 而促使蚂蚁集中到最优解的附近 收敛速度有了很大的提高 但可 能出现这个最优解并非是实际最优解 蚂蚁搜索很快出现收敛停滞现象 为了有 效的抵消上述影响 最大最小蚂蚁系 z 统 m m a s 被提出来了 2 1 1 把信息素的范围 限制在 j n 内 不在这个范围的将被限制设为 或者 这样可以有 效地避免某条路径的信息素浓度过大或者过小于其他的路径 减少由于正反馈作 用而收敛到局部最优解的可能性 m m a s 经过对基本蚁群算法的研究和分析 提出了四个改进 1 在m m a s 中 每次迭代一次后 有且仅有一只蚂蚁释放信息素 这只 蚂蚁可以是当前迭代最优解或者是该次迭代最优解的蚂蚁 这与a c s 非常相似 而在a s 中 对所有蚂蚁走过的所有路径进行全局信息素浓度更新 更新规则公 式不一样 2 为了解决a c s 中可能某条当前最优解但并非实际最优解的路径上信息 素过大而造成的搜索过早停滞问题 对每条路径上的信息素进行限制在 f i n 内 而在a s 中 对信息素没有任何限制 使得一些路径上的信息素浓度远 远高于其他路径 使得后来的蚂蚁集中在同一条路径上 阻止了蚂蚁寻找新路径 发现更近的解 3 为了增加蚂蚁在第一次循环中对解空间的探索 对每条路径上的信息素 初始化为 4 引入了一种信息素平滑化机制 在算法接近收敛时 对信息素进行差异 调整 有助于更有效的搜索解空间 第二章蚁群优化算法 2 6 自适应蚂蚁系统 基本蚁群算法存在收敛速度慢和易于陷入局部最优解的问题 王颖等人提出 了一种自适应蚂蚁系统 3 l 来提高全局搜索能力和搜索速度 它对基本蚁群算 法进行了引入了两个方面的算法改进 1 保留最优解 在每次迭代一次后 记录下最优解 2 当问题规模相当的大时 由于信息素挥发系数1 p 的存在 每次循环都 会对从未搜索过的路径上的信息素进行更新减少 从而使后来的蚂蚁选择该路径 的概率更加的小 降低了全局搜索能力 而且当l p 的值过大时 路径上的信息 素挥发的很快 从而使信息素的先验经验降低 蚂蚁选择之前搜索过的路径的可 能性变的很大 没有很好的利用算法的正反馈机制 算法寻找到较好解的能力降 低 严重降低了算法的收敛速度 因此 为了提高蚁群算法搜索新路径的能力 和算法的收敛速度 王颖等 人提出了自适应的蚁群算法 在算法的行进过程中 自适应地调整信息素残留系 数p 值 设置p 的初始值4 t 1 当在给定常数n 次迭代中 如果当前最优 解没有明显的变短时 按照以下公式对p 值作适当的调整 f 0 9 5 p t 1 压t 风i 若0 9 5 p t 1 2 成i 否则 这就可以使p 适当的减小 提高了搜索新路径的能力 便于发现更近的最优解 同时p 有最小限制 防止p 过小 而导致先验知识受重视程度过小 降低了全局 收敛速度 2 7 小结 蚁群算法是一种仿生优化随机搜索算法 并被很好的应用到社会各个领域 中 首先在本章的开始 系统阐述了蚁群算法 针对基本蚁群算法存在收敛速度 慢和易于陷入局部最优解 出现早熟停滞现象 提出了一些改