中欧体育第２６卷第１期 重庆邮电大学学报（自然科学版） Ｖｏｌ．２６Ｎｏ．１ ２０１４年２月 ＪｏｕｒｎａｌｏｆＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） Ｆｅｂ．２０１４ ＤＯＩ：１０．３９７９／ｊ．ｉｓｓｎ．１６７３８２５Ｘ．２０１４．０１．０１７ 基于网络服务模式的动态路径规划蚁群算法 夏英，李芳芳 （重庆邮电大学 空间信息系统研究所，重庆４０００６５） 摘要：随着云计算、移动互联网等ＩＴ技术的发展，通过网络提供动态路径规划服务能够进一步改善人们的出行 质量。网络服务模式下的动态路径规划要求系统能够同时为多用户提供最优路径。在多态蚁群算法基础上，借鉴 最大最小蚂蚁系统及自然界优胜劣汰思想，考虑共享侦察蚁群得到的初始道路信息素，提出两阶段蚁群算法。实 验结果表明，两阶段蚁群算法不仅在收敛速度上有所提高，且适应网络服务模式下的多用户实时导航需求。 关键词：网络服务模式；路径规划；蚁群算法；信息素 中图分类号：ＴＰ３０１文献标识码：Ａ 文章编号：１６７３８２５Ｘ（２０１４）０１００９８０６ Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｆｏｒｄｙｎａｍｉｃｐａｔｈｐｌａｎｎｉｎｇｂａｓｅｄ ｏｎｎｅｔｗｏｒｋｓｅｒｖｉｃｅｍｏｄｅ ＸＩＡＹｉｎｇ，ＬＩＦａｎｇｆａｎｇ （ＲｅｓｅａｒｃｈＣｅｎｔｅｒｏｆＳｐａｔｉａｌＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍ，ＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ４０００６５，Ｐ．Ｒ．Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＡｌｏｎｇｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｔｈｅＩＴｔｅｃｈｎｏｌｏｇｉｅｓｓｕｃｈａｓｃｌｏｕｄｃｏｍｐｕｔｉｎｇａｎｄｍｏｂｉｌｅＩｎｔｅｒｎｅｔ，ｐｅｏｐｌｅ’ｓｊｏｕｒ ｎｅｙｑｕａｌｉｔｙｃａｎｂｅｉｍｐｒｏｖｅｄｂｙｐｒｏｖｉｄｉｎｇｔｈｅｎｅｔｗｏｒｋｂａｓｅｄｄｙｎａｍｉｃｐａｔｈｐｌａｎｎｉｎｇｓｅｒｖｉｃｅ．Ｄｙｎａｍｉｃｐａｔｈｐｌａｎｎｉｎｇｂａｓｅｄ ｏｎｔｈｅｎｅｔｗｏｒｋｓｅｒｖｉｃｅｍｏｄｅｓｈｏｕｌｄｂｅａｂｌｅｔｏｐｒｏｖｉｄｅｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｆｏｒｍｕｌｔｉｐｌｅｕｓｅｒｓｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ａｔｗｏｓｔａｇｅａｎｔ ａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｉｔｉｓｂａｓｅｄｏｎｐｏｌｙｍｏｒｐｈｉｃａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｒｅｆｅｒｓｔｏｔｈｅｍａｘｍｉｎａｎｔｓｙｓｔｅｍａｎｄ ｔｈｅｓｕｒｖｉｖａｌｏｆｔｈｅｆｉｔｔｅｓｔｉｄｅｏｌｏｇｙ，ａｎｄｃｏｎｓｉｄｅｒｓｓｈａｒｉｎｇｏｆｔｈｅｉｎｉｔｉａｌｐａｔｈｐｈｅｒｏｍｏｎｅｗｈｉｃｈｉｓｇｅｎｅｒａｔｅｄｂｙｔｈｅｒｅｃｏｎｎａｉｓ ｓａｎｃｅａｎｔｃｏｌｏｎｙ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｔｗｏｓｔａｇｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｓｔｈｅｓｐｅｅｄｏｆｃｏｎｖｅｒｇｅｎｃｅ．Ｉｔｉｓ ａｄａｐｔｅｄｔｏｔｈｅｃｏｎｃｕｒｒｅｎｔｒｅｑｕｉｒｅｍｅｎｔｓｏｆｒｅａｌｔｉｍｅｎａｖｉｇａｔｉｏｎｉｎｎｅｔｗｏｒｋｓｅｒｖｉｃｅｍｏｄｅｌ． Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｓｅｒｖｉｃｅｍｏｄｅｌ；ｐａｔｈｐｌａｎｎｉｎｇ；ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；ｐｈｅｒｏｍｏｎｅ 据用户发出的导航请求，在服务器端进行最优路径 ０引言 规划操作，并通过无线网络将导航信息实时发布给 在城市建设和发展的过程中，路网日益复杂且 用户。与传统的导航相比，网络服务模式下的路径 规模不断扩大，城市交通问题日趋严重。智能交通 规划无需手持终端存储导航地图等数据，也无需进 系统（ｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍｓ，ＩＴＳ）实现了道 行复杂的计算。网络环境下的动态路径规划服务需 路利用效率最大化，大幅度提高路网的通行能力并 要结合实时交通数据，同时支持多用户访问，这对传 改善人们的出行质量。随着智能手机等移动终端设 统的面向个人用户的路径规划方法提出了挑战。 备的日益普及，以及云计算、移动互联网等技术的不 ［１］ 蚁群算法是一种模拟进化算法 ，具有分布式计 断发展，人们对网络环境下的动态路径规划服务提 算、信息正反馈和启发式搜索等特征，易于与其他方 出了需求。网络服务模式下的路径规划服务中心根 法相结合，在组合优化方面得到了广泛的应用。传统 收稿日期：２０１２１２３０修订日期：２０１３０２０９通讯作者：李芳芳ｌｆｆｙｙｘ＠１６３．ｃｏｍ 基金项目：重庆市自然科学基金（ｃｓｔｃ２０１２ｊｊＡ４００１４）；重庆邮电大学博士启动基金（Ａ２０１２３４） ＦｏｕｎｄａｔｉｏｎＩｔｅｍｓ：ＴｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎＰｒｏｊｅｃｔｏｆＣｈｏｎｇｑｉｎｇＣＳＴＣ（ｃｓｔｃ２０１２ｊｊＡ４００１４）；ＴｈｅＳｃｉｅｎｔｉｆｉｃａｎｄＴｅｃｈｎｏｌｏｇｉｃａｌ ＦｏｕｎｄａｔｉｏｎｏｆＣｈｏｎｇｑｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ（Ａ２０１２３４） 第１期 夏英，等：基于网络服务模式的动态路径规划蚁群算法 ·９９· 的蚁群算法存在易早熟、陷入局部最优解等问题。针 对这些问题，国内外学者们对蚁群算法提出了多种改 ［２］ 进。例如，德国学者ＳｔｕｔｚｌｅＴ等 提出“最大最小蚂 蚁系统”（ＭＡＸＭＩＮａｎｔｓｙｓｔｅｍ，ＭＭＡＳ），通过限制路 径上的信息素来克服停滞问题，并通过调整每一代中 最好的蚂蚁个体所走的路径上的信息来加快收敛速 ［３］ 度。吴庆洪等 从遗传算法中得到启发，在蚁群算法 ［４］ 中采用了逆转变异机制。徐精明等 对蚁群进行分 工，提出了一种多态蚁群算法。在蚁群算法基础上的 ［５］ 图２蚂蚁最终选择的路径 改进还包括基于信息素扩散的蚁群算法 ，基于ＧＰＵ Ｆｉｇ．２Ｆｉｎａｌｒｏｕｔｅａｎｔｓｃｈｏｏｓｅ ［６］ 的共享信息素矩阵多蚁群算法 等。 α β （ｔ） （ｔ） τ η ｉｊ ｉｊ ，ｊ ｔａｂｕ 这些算法应用到路径规划问题中时，大多只是针 ｋ α β ｋ （ｔ） （ｔ） Ｐ（ｔ）＝ ∑ τ η ｉｊ ｓ ｔａｂｕ ｉｓ ｉｓ 对单个用户需求，很少考虑多用户同时请求服务时如 {０， ｋ 否则 何共享资源、提高计算效率。考虑到网络服务模式下 的路径规划服务是面向多用户的，本文在多态蚁群算 （１） ｋ （１）式中：Ｐ（ｔ）是ｔ时刻位于节点 ｉ的第ｋ只蚂蚁 ｊ 法的基础上，中欧体育提出一种多用户共享信息素的两阶段蚁 ｉ 选择下一个节点ｊ的概率； （ｔ）为ｔ时刻边（ｉ，ｊ）上 τ 群算法，以此提高网络模式下的路径规划效率。 ｉｊ 的信息素强度； （ｔ）表示ｔ时刻边（ｉ，ｊ）上的启发信 η ｉｊ １相关研究 息，一般情况下 （ｔ）＝１／ｄ，ｄ表示路网中两个节 η ｉｊ ｉｊ ｉｊ 点之间的距离；和 是信息素和启发信息对蚂蚁 α β １．１蚁群算法基本原理 在选择下个节点的影响因子；禁忌表 ｔａｂｕ用来保 ｋ 自然界中的蚂蚁，能找到食物源到巢穴间的最短 存蚂蚁ｋ已经走过的节点的集合，目的是为了避免 路径，依靠的是其自身分泌的一种具有挥发性的物质 蚂蚁走回头路，中欧体育保证路径最优。 ［７］ （信息素） 。蚂蚁在走过的路径上留下信息素，并 道路上的信息素随着时间的推移会有一定量的 能识别信息素且有向其浓度高的方向前进的特性。 挥发，假设所有蚂蚁经过ｎ个时刻完成了一次循环， 在食物源和蚁巢之间，假设所有蚂蚁的速度一样（如 各路径上的信息素量根据（２）式做调整。 图１所示），在相同的时间内蚂蚁走过较短路径的次 （ｔ＋ｎ）＝ × （ｔ）＋ ， （０，１）（２） τ ρ τ Δτρ∈ 数较多，释放的信息素相对来说也较多，更多蚂蚁选 ｉｊ ｉｊ ｉｊ ｍ 择较短路径的可能性也较大，路径上的信息素进而也 ＝ ｋ （３） Δτ ∑Δτ ｉｊ ｉｊ ｋ＝１ 就更多。在这种正反馈机制下，从蚁巢到食物源的最 （２）式和（３）式中：参数 表示信息素的残留程度； ρ 短路径被逐渐的选择出来，如图２所示。 Δτ表示本次循环中路径（ｉ，ｊ）上的信息量的增量； ｉｊ ｋ表示第ｋ只蚂蚁在本次循环中留在路径（ｉ，ｊ）上 τ ｉｊ 的信息量。 １．２网络服务模式下的动态导航 在网络服务模式下的动态路径规划服务中，由 服务中心通过统一的数据接口接入、存储多源异构 交通数据，并通过数据融合技术对接入的实时路况 交通数据进行处理，从而获取城市路网的真实交通 流状态参数信息；服务中心作为信息的存储、处理中 图１蚂蚁在有障碍物情形下的运动状态 枢，根据用户发出的导航请求，进行最优路径规划操 Ｆｉｇ．１Ａｎｔｓ’ｍｏｔｉｏｎｓｔａｔｅｉｎｃａｓｅｏｆｏｂｓｔａｃｌｅ 作，并通过无线网络将导航信息实时发布给用户。 以求解旅行商问题（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ， 用户只需有一个能够接入网络的手持终端即可请求 ＴＳＰ）为例来叙述基本的蚁群算法模型。 该服务。随着云计算、物联网等技术的快速发展，网 ·１００· 重 庆 邮 电大学学报（自然科学版）第２６卷 络服务模式下的动态导航成为可能。 用户共享信息素的路径规划算法—两阶段蚁群算 ２基于网络服务模式的动态路径规划 法。该算法主要包括侦察阶段和搜索阶段，用户可 以共享侦察阶段得到的道路信息素，减小了服务器 算法 的计算量。 ２．１多态蚁群算法的思想 在侦察阶段融入动态交通信息，侦察蚁群侦察 ［４］ 道路上的交通状况，结合当前道路的饱和度信息，用 多态蚁群算法 是徐精明等在基本蚁群算法 的基础上，按照蚂蚁分工不同，把蚁群分成侦察蚁群 当前道路上的平均车速ｖ来表示，中欧体育并用侦察素来记 和搜索蚁群。每种蚁群分泌不同的信息素，侦察蚁 录侦察结果，根据侦察结果初始化道路信息素。为 群的任务是每个侦察蚁以当前所在的节点为中心对 防止某些道路上的信息素过大或者过小，导致算法 周围近邻节点做局部侦察，并用侦察素来记录侦察 易陷入局部最优收敛，把道路上的信息素范围限制 在［ ， ］。该阶段初始化的路网信息素矩阵可 ζ ζ 结果，为搜索蚁到该节点在选择下个节点的时候提 ｍｉｎ ｍａｘ 供辅助信息；搜索蚁群的任务是做全局搜索，每到一 以供在同一路网上的多个用户在搜索阶段共同 个节点，根据侦察蚁侦察出来的结果，来选择下一个 使用。 节点，直到达到目的地。多态蚁群算法将局部侦察 侦察阶段算法描述如下。 算法：Ｉｎｉｔｉａｌｉｚａｔｉｏｎｐｈｅｒｏｍｏｎｅ（Ｓｐｅｅｄ［ｎ］［ｎ］，＆［ｎ］ 与全局搜索相结合，缩小搜索范围从而提高算法的 τ 收敛速度。 ［ｎ］） 输入：Ｓｐｅｅｄ［ｎ］［ｎ］／ 当前道路网中，ｎ对节点之 在规模为ｎ个节点的路网中，将ｎ个侦察蚁分 间的车辆平均行驶速度 ／ 别放在ｎ个节点上，每个侦察蚁以所在节点为中心， 输出：［ｎ］［ｎ］／ 初始化路网信息素 ／ 侦察其他ｎ－１个节点，Ｓ为一个 ｎ×ｎ矩阵，Ｓ［ｉ］ τ ［ｊ］元素用于存放第ｉ个侦察蚁侦得到的节点ｉ到节 处理步骤： 点ｊ个节点的侦察结果。 Ｂｅｇｉｎ ， ，ＭＡＸＰＣ； ζ ζ ｄ／ｄ， 节点ｊ在ｉ的ＭＡＸＰＣ内 ｍｉｎ ｍａｘ Ｓ［ｉ］［ｊ］＝{ ｉｊ ｉｊ （４） ／ 设置每条道路上信息素范围；ＭＡＸＰＣ最大 ０， 否则 可选节点个数； ／ （４）式中：ｄ表示以ｉ为中心，到其他ｎ－１个节点的 ｉｊ 最小距离；ｄ为ｉ到ｊ的实际距离；ＭＡＸＰＣ是对不同 ｆｏｒ（ｉ＝１；ｉ＜ｎ；ｉ＋＋）ｄｏ｛ ｉｊ ［８］ 把侦察蚁ｉ放在道路节点ｉ上； 路网规模下最大可选节点所作的一个统计值 。 在蚂蚁选择下个要走的节点时，对路网中每个节点 ｝ 而言，都从离它最近的ＭＡＸＰＣ个节点中选择一个 ｆｏｒ（ｉ＝１；ｉ＜ｎ；ｉ＋＋）ｄｏ｛ 节点做为近邻节点，而不是从剩下的所有节点中任 ｆｏｒ（ｊ＝１；ｊ＜ｎ；ｊ＋＋）ｄｏ｛ ｆｏｒｅａｃｈｊ ｉ的近邻节点ｄｏ｛ 意选择一个，这样将原来的解空间由ｎ！减小到 ∈ ＭＡＸＰＣ ［９］ 侦察蚁ｉ侦察所在节点及周围近邻节点ｊ ｎ ，加快寻优速度 。 根据侦察结果，对初始时刻路网中各条路径上 交通状况 Ｓｐｅｅｄ［ｉ］［ｊ］得出侦察素，并记 的信息素量 （０）赋值。 录侦察结果存入 Ｓ［ｉ］［ｊ］，根据侦察结果 τ ｉｊ Ｃ×Ｓ［ｉ］［ｊ］， 若Ｓ［ｉ］［ｊ］ ０ 得出道路信息素Ｐ； ≠ ｉｊ τ（０）＝ ～ （５） ｉｊ ｉｆ（ ＜Ｐ＜ ） { ζ ζ Ｃ×ｄ／ｄ， 否则 ｍｉｎ ｉｊ ｍａｘ ｉｊ ｉｊ ［ｉ］［ｊ］＝Ｐ； τ ～ ｉｊ （５）式中：Ｃ为一个常数；ｄ为ｉ到其他ｎ－１个节点 ｉｊ ｅｌｓｅｉｆ（ ＜Ｐ） ζ ｍａｘ ｉｊ 的最大距离。搜索蚁群在搜索过程中，搜索蚁每到 ［ｉ］［ｊ］＝ ； τ ζ ｍａｘ 一个节点，结合侦察素，只需在较小范围内搜索，大 ｅｌｓｅ ［ｉ］［ｊ］＝ ； τ ζ ｍｉｎ 大减小了搜索范围。 ｝ ２．２两阶段蚁群算法 ｝ 针对网络服务模式下的动态路径规划是面向多 ｝ 用户这一特点，在多态蚁群算法基础上提出一种多 Ｒｅｔｕｒｎ ［ｎ］［ｎ］； τ 第１期 夏英，等：基于网络服务模式的动态路径规划蚁群算法 ·１０１· Ｅｎｄ ｝ ［１０］ 为加快算法收敛速度，受细菌觅食算法 启 ｝ 发，引入优胜劣汰机制。在搜索蚁群搜索最优路径 当ｍ只蚂蚁完成一次搜索，记录本次搜索的最 过程中，设置蚂蚁在单个搜索过程中所允许走过的 佳路径节点序列Ｌｋ和路径长度ＬｋＬｅｎｇｔｈ； 最大步长ＳＴＥＰ ，当蚂蚁在一次搜索过程中，走过 ｉｆ（ＬｋＬｅｎｇｔｈ＜Ｂｅｓｔｌｅｎｇｔｈ） ｍａｘ 的步长大于ＳＴＥＰ 仍没有到达目标节点，则被淘 ｛ ｍａｘ 汰；为维持搜索蚁群数量，当所有搜索蚂蚁完成一次 Ｂｅｓｔｌｉｓｔ＝Ｌｋ； 搜索后，恢复搜索蚁群总数量，进入下一轮搜索。这 Ｂｅｓｔｌｅｎｇｔｈ＝ＬｋＬｅｎｇｔｈ； 样在一定程度上减少了在蚂蚁陷入局部搜索时的时 ｝ ［１１］ 更新道路信息素； 间开销 。 重置禁忌表ｔａｂｕ空； 搜索阶段算法描述如下。 ｋ 算法：ＳｅａｒｃｈＢｅｓｔｐａｔｈ（Ｓ，Ｄ，＆ＬｉｎｋｌｉｓｔＢｅｓｔｌｉｓｔ） Ｎｃ＋＋； 输入：起点Ｓ和终点Ｄ ｝ 输出：起点Ｓ到终点 Ｄ的一条最优路径 Ｂｅｓｔｌｉｓｔ（节 ｒｅｔｕｒｎＢｅｓｔｌｉｓｔ； 点序列） Ｅｎｄ 处理步骤： 从算法时间复杂度的角度来分析，两阶段蚁群 Ｂｅｇｉｎ 算法主要包含侦察阶段和搜索阶段。侦察阶段只与 初始化 ｍ，Ｔｍａｘ，Ｔｍｉｎ，ＳＴＥＰｍａｘ，ＮＣ，Ｂｅｓｔｌｅ 路网节点数和最大可选节点数有关，该阶段的时间 ｎｇｔｈ，Ｂｅｓｔｌｉｓｔ； 复杂度为Ｏ（ＭＡＸＰＣ×ｎ×ｎ），其中ｎ表示路网节点 ／ ｍ为搜索蚂蚁个数，ｍａｘ，Ｔｍｉｎ每条道路上 个数，ＭＡＸＰＣ表示路网最大可选节点数；搜索阶段 Τ 信息素范围，ＳＴＥＰｍａｘ在一次循环中每只蚂蚁 与搜索蚁个数ｍ，最大迭代次数ＮＣ，一次循环中每 只蚂蚁允许走的最大步长ＳＴＥＰ ，以及最大可选节 允许走的最大步长，ＮＣ为最大迭代次数，Ｂｅｓｔ ｍａｘ ｌｅｎｇｔｈ记录最优路径长度，初始化为无穷大， 点数有关，该阶段的复杂度为 Ｏ（ＮＣ×ＭＡＸＰＣ× ｍ×ＳＴＥＰ ）。多态蚁群算法的时间复杂度为 Ｂｅｓｔｌｉｓｔ为最优路径的节点序列，初始化为空 ｍａｘ Ｏ（ＮＣ×ＭＡＸＰＣ×ｍ×ｎ）。通常情况下 ＳＴＥＰ 小 ／ ｍａｘ 于ｎ，两阶段蚁群算法在时间复杂度上优于多态蚁 Ｔ［ｎ］［ｎ］＝［ｎ］［ｎ］；／ 侦察阶段得到的道路 τ 群算法。 网初始信息素矩阵 ［ｎ］［ｎ］ ／ τ ｗｈｉｌｅ（Ｎｃ＜ＮＣ｜｜未求出最优解） ３实验结果及分析 ／ 算法终止条件为达到最大迭代次数 ＮＣ或 为验证两阶段蚁群算法的有效性以及对网络服 若干次迭代中求得的解无明显改进 ／ 务模式的适应性，分别用２组实验与多态蚁群算法 ｛ 进行对比分析。实验环境为 Ｉｎｔｅｌ（Ｒ）ＤｕａｌＣｏｒｅ ｆｏｒ（ｋ＝１；ｋ＜ｍ；ｋ＋＋） ＣＰＵＥ５３００＠ ２．６０ＧＨｚ，２ＧＢｙｔｅ内存，操作系统为 ｛把蚂蚁 ｋ放在起始位置 Ｓ上，并把起始 ＷｉｎｄｏｗｓＸＰ。 点Ｓ放入蚂蚁ｋ对应的禁忌表ｔａｂｕ中； ｋ 实验１对比２个算法的计算效率。 ｗｈｉｌｅ（ｊ不是目标节点｜｜ｔ＜ＳＴＥＰｍａｘ） 在Ｍａｔｌａｂ平台下做仿真，数据集选取 ＴＳＰＬＩＢ ／ 节点ｊ表示当前蚂蚁所在节点 ／ ［１２］ 标准库 中的数据Ｅｉｌ５１，算法运行２０次并记录统 ｛ 计结果，对比两阶段蚁群算法与多态蚁群算法在求 根据Ｔ［ｎ］［ｎ］计算节点ｊ到它可选节点的 解 ＴＳＰ问题中的计算效率。统计结果如表１所示。 概率； 由表 １可以看出，获得最优结果质量相同情况 蚂蚁ｋ根据概率选择下一个节点； 下，两阶段蚁群算法的平均运行时间低于多态蚁群 把ｊ加入蚂蚁ｋ对应的禁忌表ｔａｂｕ； ｋ 算法。 ｔ＋＋； ·１０２· 重 庆 邮 电大学学报（自然科学版）第２６卷 表１统计结果分析 质量相同情况下的用户平均执行时间。 Ｔａｂ．１Ｓｔａｔｉｓｔｉｃａｌｒｅｓｕｌｔｓａｎａｌｙｓｉｓ 表２和表３分别是与实验路网相对应的路段表 实例Ｅｉｌ５１ 多态蚁群算法 两阶段蚁群算法 和结点表。表２中ＩＤ表示道路的唯一标识，Ｆ 和 ｎｏｄｅ 最优解 ４２６ ４２６ Ｔ 分表表示路段首尾结点，Ｌｅｎｇｔｈ表示路段长度， ｎｏｄｅ 最差解 ４３６ ４３１ Ｎａｍｅ为路段的名称。表３中ＩＤ表示结点的唯一标 平均结果 ４３１．３３ ４２７．９６ 识，Ｌａｔ和 Ｌｏｎ分别表示该结点的经度和纬度， 平均运行时间／ｓ ２．２ １．６ Ｌｉｎｋ１，Ｌｉｎｋ２，Ｌｉｎｋ３，Ｌｉｎｋ４分别表示与该结点相关联 的结点ＩＤ。 实验２验证算法在网络服务模式下的有效性。 表２路段表 为验证两阶段蚁群算法在网络服务模式下的有 Ｔａｂ．２Ｒｏｄｅｄａｔａ 效性，本文选用上海市路网和交通实际数据。路网 ＩＤ Ｆ Ｔ Ｌｅｎｇｔｈ Ｎａｍｅ 包含２４０个结点和３５２条路段，使用Ｃ＃语言在Ｖｉｓ ｎｏｄｅ ｎｏｄｅ ０２７ ６３７７０００１４ ７７．４７３ 旅顺路 ｕａｌＳｔｕｄｉｏ２０１０环境下进行实验，模拟多个用户请求 ６３７７００００２ ６３７７０００１４ ６３７７０００２８ １４７．４７３ 东大名路 导航服务。算法参数设置为：侦察蚁 ｎ＝２４０，搜索 ６３７７００００３ ６３００００１２９ ６３７７０００４４ ２１４．００８ 九龙路 蚁ｍ＝８０，信息素挥发因子 ＝０．３，参数 ＝１，＝ ρ α β ３，信息素总量Ｑ＝１００，最大迭代次数ＮＣ＝２００。比 较两阶段蚁群算法和多态蚁群算法在求得的最优解 表３结点表 Ｔａｂ．３Ｎｏｄｅｄａｔａ ＩＤ Ｌａｔ Ｌｏｎ Ｌｉｎｋ１ Ｌｉｎｋ２ Ｌｉｎｋ３ Ｌｉｎｋ４ ６３７７０００１４ １２１．４８６６４０ ３１．２４９８９０ ６３７７００００２ ６３７７００００１ ６３７７００２０６ － ６３７７０００２８ １２１．５１３９６０ ３１．２６７３００ ６３７７００１１９ ６３７７００１４３ ６３７７００１３５ － ６３７７０００４４ １２１．４９１８０２ ３１．２４９９１０ ６３７１０００８７ ６３７１０００８８ ６３７１０００８９ ６３７１０００９４ 实验中道路信息素初始值根据道路长度以及交 从图３可以看出，在首次为用户计算最短路径的 通流量进行初始化。两阶段蚁群算法在搜索阶段共 时候，两阶段蚁群算法与多态蚁群算法相比，在搜索 享了侦察阶段得到初始化信息素，对同一路网上的 效率上有提高，此时是因为两阶段蚁群算法自身在搜 信息素只用执行一次初始化，而多态蚁群算法在计 索效率上的优势；随着用户数量的增多，两阶段蚁群 算最优路径时候，用户数量决定信息素的初始化次 算法相对多态蚁群算法，在执行效率上的优势明显。 数。实验结果如图３所示。 这是因为两阶段蚁群算法在其他用户搜索最优路径 时，不需要再次进行道路信息素初始化，而多态蚁群 算法对每个用户而言仍需要初始化道路信息素。 ４结论 针对网络服务模式下面向多用户的动态路径规 划问题，在多态蚁群算法的基础上，提出两阶段蚁群 算法。在为用户计算最优路径的时候共享计算资 源，减少服务器端负载；在蚂蚁完成一次搜索的过程 中，借鉴了细菌觅食算法，引入优胜劣汰机制，提高 了算法计算效率。实验表明，两阶段蚁群算法不仅 在计算效率上有所提高，且在网络服务模式下表现 出明显的优势。 图３平均执行时间 在动态交通状况方面，目前仅仅考虑了动态路 Ｆｉｇ．３Ａｖｅｒａｇｅｅｘｅｃｕｔｉｏｎｔｉｍｅ 第１期 夏英，等：基于网络服务模式的动态路径规划蚁群算法 ·１０３· 网中道路的平均车速以及道路长度这２个因素，下 ［８］全惠云，文高进．求解ＴＳＰ的子空间遗传算法［Ｊ］．数 一步研究中将考虑加入用户个人的偏好等因素。 学理论与应用，２００２，２２（１）：３６３９． ＱＵＡＮＨｕｉｙｕｎ，ＷＥＮＧａｏｊｉｎ．Ｓｕｂｓｐａｃｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ 参考文献： ｆｏｒＴＳＰ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌｔｈｅｏｒｙａｎｄａｐｐｌｉｃａｔｉｏｎ，２００２， ２２（１）：３６３９． ［１］ＤＯＲＩＧＯＭ，ＭＡＮＩＥＺＺＯＶ，ＣＯＬＯＭＩＡ．ＴｈｅＡｎｔＳｙｓ ［９］张春艳，刘清林，孟珂．基于蚁群优化算法的云计算任 ｔｅｍ：Ｏｐｔｉｍｉｚａｔｉｏｎｂｙａｃｏｌｏｎｙｏｆｃｏｏｐｅｒａｔｉｎｇａｇｅｎｔｓ［Ｊ］． 务分配［Ｊ］．计算机应用，２０１２，３２（５）：１４１８１４２０． ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＳｙｓｔｅｍｓ，ＭａｎａｎｄＣｙｂｅｒｎｅｔｉｃｓ，中欧体育 ＺＨＡＮＧＣｈｕｎｙａｎ，ＬＩＵＱｉｎｇｌｉｎ，ＭＥＮＧＫｅ．Ｔａｓｋａｌｌｏｃａ ＰａｒｔＢ，１９９６，２６（１）：２９４１． ｔｉｏｎｂａｓｅｄｏｎａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｉｎｃｌｏｕｄｃｏｍｐｕｔｉｎｇ ［２］ＳＴＵＴＺＬＥＴ，ＨＯＯＳＨＨ．ＭＡＸＭＩＮａｎｔｓｙｓｔｅｍａｎｄｌｏｃａｌ ［Ｊ］．ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ，２０１２，３２（５）：１４１８１４２０． ｓｅａｒｃｈｆｏｒｔｈｅｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍ［Ｃ］／／Ｉｎ： ［１０］周雅兰．觅食优化算法的研究与应用［Ｊ］．计算机工 ＩＥＥＥＩｎｔ’ｌＣｏｎｆ．ｏｎＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ．Ｉｎｄｉａｎ 程与应用，２０１０，４６（２０）：１６２１． ａｐｏｌｉｓ：ＩＥＥＥＰｒｅｓｓ，１９９７：３０９３１４． ＺＨＯＵＹａｌａｎ．Ｒｅｓｅａｒｃｈａｎｄａｐｐｌｉｃａｔｉｏｎｏｎｂａｃｔｅｒｉａｆｏｒａ ［３］吴庆洪，张纪会．具有变异特征的蚁群算法［Ｊ］．计算 ｇｉｎｇｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ ［Ｊ］．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ 机研究与发展，１９９９，中欧体育３６（１０）：１２４０１２４５． ａｎｄＡｐｐｌｉｃａｔｉｏｎ，２０１０，４６（２０）：１６２１． ＷＵＱｉｎｇｈｏｎｇ，ＺＨＡＮＧＪｉｈｕｉ．ＡＮａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ ［１１］黄翰，郝志峰，吴春国，等，蚁群算法的收敛速度分析 ｗｉｔｈＭｕｔａｔｉｏｎＦｅａｔｕｒｅｓ［Ｊ］．ＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅ ［Ｊ］．计算机学报，２００７，３０（８）：１３４５１３５３． ｖｅｌｏｐｍｅｎｔ，１９９９，３６（１０）：１２４０１２４５． ＨＵＡＮＧＨａｎ，ＨＡＯＺｈｉｆｅｎｇ，ＷＵＣｈｕｎｇｕｏ，ｅｔａｌ．Ｔｈｅ ［４］徐精明，曹先彬，王煦法．多态蚁群算法［Ｊ］．中国科学 ＣｏｎｖｅｒｇｅｎｃｅＳｐｅｅｄｏｆＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｃｈｉ 技术大学学报，２００５，３５（１）：５９６５． ｎｅｓｅＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒｓ，２００７，３０（８）：１３４５１３５３． ＸＵＪｉｎｇｍｉｎｇ，ＣＡＯＸｉａｎｂｉｎ，ＷＡＮＧＸｕｆａ．Ｐｏｌｙｍｏｒｐｈｉｃ ［１２］ＵｎｉｖｅｒｓｉｔａｔＨｅｉｄｅｌｂｅｒｇ．Ａｌｉｂｒａｒｙｏｆｓａｍｐｌｅｉｎｓｔａｎｃｅｓｆｏｒ ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ ［Ｊ］．ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄ ｔｈｅＴＳＰａｎｄｒｅｌａｔｅｄｐｒｏｂｌｅｍｓ［ＥＢ／ＯＬ］．（２００８０７２６） ＴｅｃｈｎｏｌｏｇｙｏｆＣｈｉｎａ，２００５，３５（１）：５９６５． ［２０１２０４２５］．ｈｔｔｐ：／／ｗｗｗ．ｉｗｒ．ｕｎｉｈｅｉｄｅｌｂｅｒｇ．ｄｅ／ ［５］黄国锐，曹先彬，王煦法．基于信息素扩散的蚁群算法 ｇｒｏｕｐｓ／ｃｏｍｏｐｔ／ｓｏｆｔｗａｒｅ／ＴＳＰＬＩＢ９５／． ［Ｊ］．电子学报，２００４，３２（５）：８６５８６８． ＨＵＡＮＧＧｕｏｒｕｉ，ＣＡＯＸｉａｎｂｉｎ，ＷＡＮＧＸｕｆａ．ＡｎＡＮＴ 作者简介： ＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＰｈｅｒｏｍｏｎｅＤｉｆ 夏英（１９７２），女，四川人，教授，主要研 ｆｕｓｉｏｎ［Ｊ］．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＥｌｅｃｔｒｏｎｉｃｓ，２００４：３２（５） 究方向为数据库与数据挖掘、移动定位与 ８６５８６８． 位置服务、云计算等。Ｅｍａｉｌ：ｘｉａｙｉｎｇ＠ ［６］白洪涛，欧阳丹彤，李熙铭，等．基于ＧＰＵ的共享信息 ｃｑｕｐｔ．ｅｄｕ．ｃｎ。 素矩阵多蚁群算法［Ｊ］．吉林大学学报，２０１１，４１（６）： １６７８１６８３． ＢＡＩＨｏｎｇｔａｏ，ＯＵＹＡＮＧＤａｎｔｏｎｇ，ＬＩＸｉｍｉｎｇ，ｅｔａｌ． Ｍｕｌｔｉｐｌｅａｎｔｃｏｌｏｎｉｅｓｓｈａｒｉｎｇｃｏｍｍｏｎｐｈｅｒｏｍｏｎｅｍａｔｒｉｘ 李芳芳（１９８６），女，河南人，硕士研究生， ｂａｓｅｄｏｎＣＰＵ［Ｊ］．ＪｏｕｒｎａｌｏｆＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，２０１１，４１ 主要研究方向为空间信息处理
GB T 32610-2016_日常防护型口罩技术规范_高清版_可检索.pdf