（电工理论与新技术专业论文）基于蚁群算法的最佳路径搜索问题的研究.pdf

t h er e s e a r c ho fs e a r c h i n gt h eb e s tp a t hb a s e do n a n tc o l o n ys y s t e m a b s t r a c t a st h ed e v e l o p i n go ft h es o c i e t ya n dt h ec it i e s ，t r a f f i c p r g b l e m h a st ob es o l v e da ss o o na sp o s s i b l e r o u t eg u i d a n c es y s t e m ( r g s ) i s u s e f u lf o rs o l v i n gt h ep r o b l e m o n eo ft h ec o r ep r o b l e m so fr g si sh o w t os e a r c ht h eb e s t p a t h 。 t h i sp r o j e c tf o c u s e so nt h i sp r o b l e m a n i m p r o v e da l g o r i t h m w h i c hb a s e do na n t c o l o n ya l g o r i t h m a n o v e l s i m u l a t i n ge v o l u t i o n a r ya l g o r i t h m i s s t u d i e di nt h i s s y s t e m a n t c o l o n ya l g o r i t h m i su s e dt o s o l v i n gt h et s p ( t r a v a i l i n gs a l e s m a n p r o b l e mb y s i m u l a t i n g t h em o d eo ft h e f o r a g i n gp r o c e d u r e o ft h et r u e a n t s t h e a l g o r i t h m w h i c hi su s e di nt h i s s y s t e mi m p r o v e s t h ea n t c o l o wa l g o r it h ma n d c a nw o r kv e r yw e 儿i ns e a r c h i n gt h eb e s t p a t ho f ac i t yn e t w o r k t h es y s t e mu s e sv i s u a lc + + 6 0t or e a l i z et h ei m p r o v e da l g o r i t h m t h e b a c k g r o u n d o ft h e s y s t e m i sa r c v i e wg i ss o f t w a r e t h em e d i a l c o m p o n e n t i st h ea c t i v e x e o n t r o l m a p o b j e c t s t h ee x p e r i m e n td a t a is f e t c h e df r o mt h em a po fp u d o n gn e wd i s t r i c t ，s h a n g h a ic i t y i no r d e rt of i n dt h eb e s tp a t hs u c c e s s f u l l y ，t h er e s e a r c ho ft h e s y s t e mf o c u s e so nh o wt oi m p r o v et h ea n tc o l o n ya l g o r i t h mb ya n a l y z i n g t h ec h a r a c t e r so ft h et r a f f i cn e t w o r k s b ya n a l y z i n ga n dc o m p a r i n gt h e r e s u l t so ft h ed i f f e r e n t e x p e r i m e n t s ，t h es y s t e m c h o o s e st h em o s t p r e c i s ep a r a m e t e r st h r o u g h t h e t h e o r yd e d u c i n g t h e nt h e s y s t e m c a n f e t c ht h em a pi n f o r m a t i o nf r o mt h ea r c v i e w b a c k g r o u n db yp r o g r a m m i n g t h e m a p o b j e c t s w h e n t h e i m p r o v e da l g o r i t h mf i n i s h e sc o m p u t i n g ，t h e r e s u l t sa r et r a n s f e r r e dt ot h eb a c k g r o u n da n ds h o w e da t o n c e k e y w o r d s ：t r a f f i cg u i d a n c es y s t e m ，t h eb e s tp a t hs e a r c h i n g ，a n t c 0 1 0 n y a l g o r it h m ，g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，g i s ，a r c v i e w ，m a p o b j e c t s 第一章绪论 第一章绪论 交通运输是人类社会生存与发展的最基本需求之一。近半个世纪以来，随着 全球社会的加速发展，城市的日益扩大和复杂化，以及人们交通观念与需求的变 化，城市交通问题己变得日益突出。交通路径导航系统( r o u t e c u i d a n c e s y s t e m ，简称为r g s ) 就是在这种状况应运而生的一种新的交通管理系统，它 是智能交通系统的一个重要组成部分。 1 1 路径导航系统的结构 所谓路径导航系统，是指一种新的交通管理控制系统，它利用计算机和通 讯技术，帮助驾驶员找到一条从出发地到目的地的最优路径，同时向驾驶员提 供多种形式的路径导航指令和丰富的实时交通信息。使用这种系统后，能有效 防i r 交通堵赛和交通事故的发，减少4 i 辆在道路上的逗留时问，剪最终实现 交通流量谯各条路段上的合理再分配。掘英国交通和公路实验研究室估计，给 第一鼋绪论 司机提供行驶路径信息，可以减少行车时间8 1 2 。此外，应用这种系统，能 帮助对地理环境不熟悉的驾驶员准确、快速的到达目的地。 交通路径导航系统的一般组成结构如图1 1 所示。在图i 1 中主要包括了 四个子系统： 1 1 1 交通流信息采集和处理子系统 如图1 1 所示，交通信息的采集是在路旁设备和交通控制中心完成的。路 旁设备通过传感器获得交通网络流量信息，通过无线传输到交通控制中心，控 制中心滚动式预测网络中各路段和交叉口的交通流量，利用实时动态交通分配 模块和软件进行动态交通分配，为导航提供依据。交通流信息的获得是路径导 航的前提条件，主要涉及到接口技术的研究。 。 1 1 2 车辆定位子系统 车辆定位子系统的功能是确定车辆在路网中的确切位置，其主要研究内容 有： 建立一套差分的理论模型和应用技术，即讨论如何根据基准台所测出的测 差来正确的修正车载台的误差，从而达到准确定位的目的。 设计系统的通信网络，其中包括信号的编码、发射和接收以及信号的调制 和解调等问题。 研究系统的电子地图制作方法以及在光盘上的实现技术。 建立系统的自学习体系，以实现对电子地图进行不断的修正。 建立一套故障自诊断体系，以保证在系统发生故障或信号在传输中出现较 大误差时，也能准确的确定车辆的位置。 1 1 3 交通信息服务子系统 交通信息服务子系统是交通流导航系统的重要组成部分，它可以把主机运 算出来的交通信息( 包括预测的交通信息) 通过各种传播媒介传送给公众。这 些媒介包括有线电视、联网的计算机、收音机、公共场所的电话亭、路边的可 变标示牌和车载的接收装置，使出行者在家中、在路上都可以得到交通导航信 息。 1 1 4 路径优化子系统 路径优化子系统就是路径导航算法，它是交通路径导航系统中不可或缺的 主要组成部分，也是本课题的研究对象。它的作用是依据车辆定位子系统所确 定的车辆在网络中的位置和出行者输入的目的地，结合交通信息采集和处理子 系统传输的路网交通信息，为出行者提供能够避免拥挤、减少延误、快速到达 终点的行车路径。在车载计算机的屏幕上显示出路径或以声音提示。路径导航 算法可以用硬件实现，也可以采用软件，要视具体应用场合而定。一般而言， 动态路径导航系统由以下3 个部分构成：( 1 ) 交通信息( 控制) 中心，信息中心是 动态路径导航系统的主控中心，主要功能是从各种信息源获得实时的交通信 息，进一步处理产生要发布的交通数据；( 2 ) 通信系统，负责完成车辆和交通信 息中心的数据交换；( 3 ) 车载导航单元，车载导航设备主要由计算机、通信设备 和车辆定位设备组成。定位设备为g p s 接收机或信标信号接收机及速度、方向 传感器等其它定位设备。主要功能是接收、贮存和处理交通信息，为驾驶人员 提供良好的人机界面，方便驾驶人员输入信息和获得导航指令。导航指令一般 为3 种方式：文本方式、声音方式和图形方式。 第一章绪论 1 2 动态路径导航系统的分类 按照在车载导航单元还是在交通信息中心计算抽取最佳路径，动态路径导 航系统可以分为2 类：。”l ( 1 ) 中心决定式的动态路径导航系统c d r g s ( c e n t r a l l yd e t e r m i n e d r o u t e g u i d a n c es y s t e m ) ，这类系统又可以细分为：( a ) b - c d r g s ( b r o a d c a s tt y p e c d r g s ) ，即广播类的中心决定式的动态路径导航系统：( b ) i c d r g s ( i n t e r a c t i v et y p ec d r g s ) ，即交互类的中心决定式的动态路径导航系 统。这种系统在信息中心的主机基于实时交通信息进行路径规划，为每一个可 能的0d 对计算最优或准最优路线，然后通过通信网络提供给用户。c d r g s 进 行的路径规划为基于系统整体的多车辆路径规划，有两种方式：( ，a ) 按交通需 求计算，即按照用户提交的0d 计算相应最优路线；( b ) 定周期计算，即按照一 定的周期为所选择的所有0d 对计算最优路线，这类系统的结构框图见图1 2 所示。 夷譬誊通- - 一。，人帆界叭- 鬣嚣 二二z 一 二二二二，一路径规则 2 ，关联弧的编号根据关联弧数量按顺序给出：而对于每条弧段，利用弧结 构可以唯一地确定，有着相同起始点与终止点甚至弧属性值都致的弧段并不 意味着是同一条弧段，因为所有的弧段都可以由弧编号唯一地确定。 ( 2 ) 有一定程度的数据冗余。与采用节点邻接矩阵的表示法相比，数据冗余 程度较低。 ( 3 ) 利用上面的结构，在执行算法时，可以避开大量不必要的判断。在利用 邻接矩阵的表示方法中，即使某对节点不直接连通，也要执行路径最小值判断 ( 因为它认为这是距离为+ 。的特殊连通) 。而在节点一弧段联合结构中，在针对 每个点进行遍历时，可以利用点的关联弧数来控制循环次数，从而提高搜索效 率。 ( 4 ) 除了弧具有多重属性外，节点或网络图都可具有不同属性。如在某些应 用问题中，需要考虑节点是否为阻挡点、站点、或节点处的费用等；又如，有 些图可能由若干子图构成，不同子图内的点、弧具有不同的属性( 如所属子图或 图块编号，是否为割点、悬挂点、伪顶点等) 节点、弧段结构是g i s 表达地图的- 7 十常用数据结构。在该结构中，一幅 图可抽象为“( 节点集合 + ( 弧段集合 ”。对于每条弧段，记录了其起始节点、 终止节点编号，以及弧段权值( 可描述弧段各种属性信息) ；而对于每个属于节 点集的点，其数据项包括：点的地理坐标、关联弧段数、关联弧段的编号，及 节点的属性，如节点是否为阻挡点、节点处的费用、是否为图的割点等。在进 行最短路径分析时，需要考虑图的遍历方法，即从图中某一节点p 出发，访遍 图中其余节点，且使每一个节点仅被访问一次。图的遍历算法是求解连通性问 题、关键路径等算法的基础。通常有两种遍历图的路径：深度优先( d f s ) 和广度 优先( b f s ) 搜索。这两种搜索方法作图的遍历时，其时间复杂度相同，不同之处 仅在于对顶点的访问顺序不同。深度优先搜索是在试探另外一条路径前先试探 完到达每一条路径的可能；而广度优先搜索与此相反，在它进行到下一层之前 将检查f i “层的每一个节点因此，遍历的过程实质上是对每个顶点查找其邻接 点的过程，其耗费的时取决于所采用的存储结构。当采用节点邻接矩阵时， 硷找每个顶点的邻接点所需叫问为0 ( n n ) ，其中1 3 为图的项点数：而当以节 第二章最佳路径搜索的研究现状 点弧段联合结构作为图的存储结构时，找邻接点所需时间为0 ( e ) ，其中e 为 图中的弧数，此时遍历图的时间复杂度为0 ( n + e ) 。 2 3 3 基于流体神经网络的最优路径算法 该算法利用遗传算法为流体神经网络模型设计了在非规范条件应用下的参 数优化方法，拓宽了该模型的适用范围；利用流体神经网络与道路交通网络具 有相似性的特点，将流体神经网络技术引入交通网络的路线优化l e i g 基于连续 h o p f e i l d 网络模型，利用流体在自然流动时总是选择最速下降方向的特性，给 出了一种具有直观流体性质的流体神经网络模型( f l u i d n e u r o n n e t w o r k ，f n n ) ， 它的收敛过程和稳定状态十分明确，无需通过能量函数的极小化来解决优化问 题。 2 3 4 基于模拟退火算法的曲面最短路径算法 该算法通过对路径的节点序列内在关联性的分析，提出了适合曲面最短路 径问题的邻域结构，使整段路径的优化问题能够通过局部调整得以实现。将模 拟退火算法的框架引入路径寻优中，提出了解决曲面最短路径的随机搜索算 法。”1 2 3 5 s l d f ( s m a l l e s t l a b e l d e p 曲f i r s t ) 算法 该算法基于结点标号深度的概念，给出了求解单源点最短路径问题的一个 新算法。其特点是，它具有s h i e r w i t z g e a l l 提出的所谓“锐利”( s h a r p ) 性 质，而且算法的时间复杂性在最坏情况下为0 ( n m ) ，这里n 和m 分别表示有向 图中结点的数目和弧的数目。因此，该算法的实际效率是相当高的。”】 2 3 6 夹角算法 在该算法中，为了选出组成最短路径的路段，采用相对夹角最小的贪婪算 法，即在当前节点处，在与当前节点相交的路段中，取与当前节点到终点的直 线夹角最小的路段，作为组成最短路径的路段集合的一个元素，接着把当前节 点设为选中路段的另一端节点，继续选取相对夹角最小的路段，直至当前节点 为终点。 小结 本章主要介绍了最佳路径搜索的研究现状，包括最佳路径研究的应用方面 ( 如资源分配、连通分析、流分析、选址等) ，经典的最佳路径相关算法，其 它的最佳路径算法( 包括基于层次空间推理的最优路径算法、基于点一弧段联合 结构表示法的最优路径算法、基于流体神经网络的最优路径算法、基于模拟退 火算法的曲面最短路径算、s l d f 算法、夹角算法等) 。 第二章蚁群算法原理及且应用 第三章蚁群算法原理及其应用 路径导航系统中的一个相当重要的问题是：根据用户的需求，如何快速高 效地从交通网中找到最佳路径。在这个问题的研究上，有很多不同的算法。其 中大部分是基于传统的d i j k s t r a 算法。本系统所采用的蚁群算法，则是首次被 应用到此问题的研究上。 3 1 基本蚁群算法的原理 蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发， 而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者 m d o r i g o 等人首先提出。m d o r i g o 等人首次提出该方法时，充分利用了蚁群搜 索食物的过程与著名的旅行商问题( t s p ) 之间的相似性，通过模拟蚂蚁搜索食物 的过程( 即通过个体之间的信息交流与相互协作，最终找到从蚁穴到食物源的最 短路径) 来求解t s p 问题，这种算法被称为“蚁群算法”“。 为了说明蚁群系统的原理，先简要介绍一下蚂蚁搜索食物的具体过程。像 蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁巢到食物源的最短路径，原 因是什么呢? 虽然单个蚂蚁的行为极其简单，但由这样的单个简单的个体所组 成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂 蚁还能够适应环境的变化，如：在蚁群运动路线上突然出现障碍物时，蚂蚁能 够很快地重新找到最优路径，蚁群是如何完成这些复杂任务的昵? 所有这些问 题，很早就激起了生物学家和仿生学家的强烈兴趣，仿生学家经过大量细致观 察研究发现，蚂蚁个体之间是通过一种称之为信息素( p h e r o m o n e ) 的物质进行信 息传递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行 为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能 够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物 质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度 高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正 反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 具体的蚂蚁寻径方式如图3 1 所示。 5 c 5 t = 0 时刻t = 1 时刻 图3 1 蚂蚁寻径方式示意图 蕊蕊 第三章蚁群算法原理及其应用 设a 是巢穴，e 是食物源，h c 为一障隘物。由于障随物存在，蚂蚁只能经 由h 或c 由a 到达e ，或由e 到达a ，各点之间的距离如图3 1 所示。设每个时 间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d 点，蚂蚁过后留下的 信息素为l 。为方便，设该物质停留时间为i 。在初始时刻，由于路径b h 、b c 、 d h 、d c 上均无信息存在，位于b 和e 的蚂蚁可以随机选择路径。从统计的角度 可以认为它们以相同的概率选择b h 、b c 、d h 、d c 。经过一个时间单位后，在路 径b c d 上的信息量是路径b h d 上信息量的二倍。t = l 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会以越来 越大的概率选择路径b c d ，最终完全选择路径b c d 。从而找到由蚁巢到食物源的 最短路径。由此可见，蚂蚁个体之间的信息交换是个正反馈过程 蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组 成的群体的进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协 作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构：在协作阶 段，候选解之间通过信息交流，以期望产生性能更好的解。 3 2 蚁群算法的模型和流程 蚁群算法首先是被m d o r i g o 用来研究t s p 问题。 3 2 1t s p 问题的描述 给定n 个城市的集合 1 ，2 ，r 1 ) 及城市之间环游的花费c ，。( 1 i n ，i j r l ，i j ) 。t s p 问题是指找到一条经过每个城市一次且回到起点的最小花费 的环游。若将每个顶点看成是图上的节点，花费c 。为连接顶点v ，、v 边上的 权，则t s p 问题就是在一个具有n 个节点的完全图上找到一条花费最小的 h a m i i r o n 回路。 3 2 2 蚁群算法的描述 给定一个有n 个城市的t s p 问题，人工蚂蚁的数量为m 。每个人工蚂蚁的 行为符合下列规律”1 ： 1 ) 根据路径上的激素浓度，以相应的概率来选取下一步路径； 2 ) 不再选取自己本次循环已经走过的路径为下步路径。用一个数据结构 ( t a b u l i s t ) “。来控制这一点； 3 ) 当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更 新走过的路径上的信息素浓度。 现用t ，。( t ) 表示在t 时刻，边( i ，j ) 上的信息素浓度。当蚂蚁完成了一次循 环之后，相应边上的信息素浓度为 公式3 一l ： r ( ，+ 1 ) = p f u ( ，) + f 其中p 为一个取值范围在0 到l 之间的常数系数，( 1 一p ) 表示在时间t 到 t + l 之间信息素的挥发。公式3 一l 中的t ，由如下公式确定： 公式3 - 2 ： 变襄息信的自蹭 边在0，i五 ， 之 芝叭 = t 赃虢 蚂0个 k 式象公是由 。值。的邑其崴 公式3 3 f j = o 蜘果第 k 只蚂蚁在时f 口jf 到 k r + i 之间经过边( 7 ，j ) 其中q 是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放的信息 素总量；l 。是第k 个蚂蚁的路径总花费，它等于第k 个蚂蚁经过的各段路径上 所需的花费c 。的总和。如果蚂蚁的路径总花费越高，那么其在单位路径上所释 放的信息素浓度就越低。很显然，蚂蚁不会在其没有经历过的路径上释放信息 素。 公式3 4 定义蚂蚁选择路径( i ，j ) 的概率 公式3 - 4 ： p 1 0 ) = m ) rh p i f je a l l 。w e c 【 嘲k ( f ) r 饥r 0 o t h e r w i s e 其中n 。= i c 。c 。，为经过路径( i ，j ) 所需的花费。和b 两个参数，分别用来控 制信息素和路径长度的相对重要程度。a 1 l o w e d 。是第k 个蚂蚁下一步可以选择 的路径的集合。 3 3 蚁群算法的流程 蚁群算法主要有三种形式，分别是a n t c y c e q u a n t it y 。下面主要介绍的是a n t c y c l e 算法。 在初始化的时候，m 个蚂蚁被放置在不同的城市上，赋予每条边上的信息 素浓度为t 。，( 0 ) 。每个蚂蚁的t a b u i i s t 的第一个元素赋值为它所在的城市。当 蚂蚁们完成了一次完整的寻径过程后，计算t 。，并且更新每条边上的信息 素浓度。然后开始新一轮的循环。当循环的次数达到实现定义好的n c 。、时或者 所有的蚂蚁都选择了同一种路径方式时，整个程序终止。 a n t c y c l e 程序的伪代码如下： 初始化： s e tt = 0 ，n c = o ，每条边上的t ( 0 ) = o ，并且t ，。= o ，放置m 个蚂蚁到n 个城 市上 令s = 1 ，( s 是t a b u l is l 的下标) )0 at 到胃放冯号市 城始m初。的。蚁蛆 m 1个“如0 曲m 第o i j 1扎 1 u 虹 。 叮 睥 r k 第三章蚊群算法原理及其应用 s e ts = s + l f o rk = lt omd o 根据概率p 。来选择下一步应该到达的城市，将第k 个蚂蚁移到城市j ， 并将j 插入到t a b u 。( s ) 中 f o rk = 1 t omd o 计算第k 个蚂蚁的总路径长度l 。，更新找到的最短路径。 f o rk - lt omd o ， 更新边上的信息速度浓度 对每一条边计算t 。( t + 1 ) s e tt = t + l， s e tn c = n c + 1 s e t t 。j = 0 i f ( n c n c 。) a n d ( 不是所有的蚂蚁选择同一条路径) t h e n 清空所有的t a b u l i s t g o t os t e p 2 e l s e 打印出最短路径 终止整个程序 如果程序终止于n c 次循环后，这个算法的复杂度为o ( n c n 2 m ) 。实际 上，第一步的复杂度为o ( n 2 + m ) ，第二步的复杂度为o ，第三步和第四步的 复杂度为o ( n ! m ) ，第五步的复杂度为o ( n ：) ，第六步的复杂度为o ( n m ) 。 实验证明m 一般取值与n 为同一数量级。因此整个算法的复杂度为o ( n c n ) 。 另外，还有两种蚁群算法的变形，分别是a n t d e n s 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 ) 时，浓度为常量q 的信息素被释放在这条边上。对 于a n t q u a n t it y 算法，每当蚂蚁经过边( i ，j ) 时，浓度为q d 。的信息素被释放 在这条边上。 很明显，在a n t d e n s i t y 算法中，蚂蚁释放的信息素浓度与边长度d 。无 关：在a n t q u a n t i t y 算法中，这两者就建立了相关性。也就是说，蚂蚁倾向于 选择下一步较短的路径。 3 4 基于蚁群算法的t s p 问题的研究 蚁群算法在解决t s p 问题中取得了相当的成果。系统先期实验采用的实验 数据是标准t s p 数据库中的0 1 i v e r 3 0 数据样本。 系统采用了上述的三种蚁群算法的形式，进行了相关的实验。考虑的参数 有 o ：信息素浓度的n x , 1 重要性参数，o 0 ： p ：路径费用权值的相对重要性参数，0 0 ： p ：信息素浓度的随时间变化而剩余的比例，o p l ( 1 一p 即为信息素 挥发的比例) ： 第三章蚁群算法原理及其应用 q ：蚂蚁所释放的信息素常量。 取蚂蚁的数目m = 4 0 。事实上，实验结果显示，当m e ( n l o ，n 2 ) ，其值对实 验结果不会产生显著的影响。在测试参数值对结果的影响时，每次只改变其中 的一项参数值，而保持其它的不变。实验重复了l o 次，以消除中间可能会出现 的扰动因素。缺省的参数值为a = l ，0 = 1 ，p = o 9 ，q = 1 0 0 。我们测试的参数范 围是： q 0 ，0 5 ，1 ，5 ， b 0 ，l ，2 ，5 ， p 0 3 ，0 5 ，o 7 ，0 9 ，0 9 9 9 ， q 1 ，1 0 0 ，1 0 0 0 0 。 实验结果见表3 1 。 最佳参数对平均结果最佳结果 a n t - d e n s i t ya = l ，b = 5 ，p = o 9 9 4 2 6 8 8 34 2 4 7 1 0 a n t q u a n t i t y = l ，0 = 5 ，p = o 9 94 2 7 4 3 54 2 6 3 5 9 f a n t - c y c l eq = l ，b = 5 ，p = o 5 4 2 4 3 1 04 2 3 8 1 1 表3 1 三种蚁群算法的比较 从实验结果中可以看出，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 tit y 算法则采用的是局部信息。 3 5 蚁群算法的应用 蚁群算法在解决很多组合问题( c o m b i n a t o r i a lp r o b l e m s ) 上都取得比较理 想的效果。其中有两个比较著名的组合问题，q a p 问题( o u a d r a t i ca s s i g n m e n t p r o b l e m ) 和7 s p 问题( j o b s h o ps c h e d u l i n gp r o b l e m ) ”。作相应调整的蚁群算 法可以比较好地解决这两个组合问题。 另外，将蚁群算法对实际问题的解决也取得一定的进展，如大规模集成电 路中的综合布线以及电信网络中的路由等方面的应用。 3 5 1 大规模集成电路综合布线 详细布线是v l s i 电路物理设计的最后一个步骤，按布线类型主要分为开关 盒布线和通道布线。随着v l s i 电路向深亚微米工艺发展，对布线算法提出了新 的性能( 时延、功耗、串扰、面积) 驱动要求，布线的难度也就日益增大。因 而新的布线系统需要更多的资源和更先进的实现技术，因此并行技术和计算智 能方法的应用也就日显其重要性”。 大规模集成电路中的综合布线可以采用蚁群算法的思想来进行。在枷线过 程中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网a g e n t 根据启 第三章蚁群算法原埋及其应用 发策略，象蚁群一样在开关盒网格上爬行，所经之处便布上一条金属线，历经 一个线网的所有引脚之后，线网便布通了。 在布线系统中每台计算机上部有n 个线网a g e n t 并发地运行，每个线网 a g e n t 负责布通开关盒中的一个线网，当n 个线网a g e n t 都布通自己的线网 时，开关盒布线就成功了。线网a g e n t 采用了仿生的蚁群算法。一个线网a g e n t 可以看作为一个智能蚁群，蚁群根据目前布线区域的状态和线网中各引脚的拓 扑结构来决定自己的前进方向，并且在适当的时候派遣一个蚂蚁迅速前进到某 个引脚，最后该线网中所有引脚上都有一个蚂蚁，爸引脚就互连起来了。线网 a g e n t 的行为会直接影响开关盒布线质量。每个线网a g e n t 布通自己线网或有 引脚无法连结时，停止布线，然后向自己所在机器上的开关盒a g e n t 报告布线 结果。 在布线过程中，各线网a g e n t 到达一个新的位置后，首先搜集目标和路径 情况的信息，以作选择行进策略的依据。这些检测信息包括： 1 正前方和左、右两侧有无本线网的引脚； 2 左前方和右前方有无属于本线网的引脚，如有，有多少个； 3 在线网a g e n t 当前位置与本线网的某个引脚相当靠近时，就要作该目标 的可到达性检测，即路况检测。 给定一个开关盒布线问题，问题的计算量是固定不变的，主要由算法的迭 代次数决定，而迭代次数由a g e n t s 的智能和开关盒问题本身的性质确定。蚁群 算法本身的并行性，使之比较适合于解决布线问题。 3 5 2 电信网络路由 电信网络管理关键技术之一是通信网路由优化技术 如动态选路策略) 。 我国的电信网络规模庞大、结构复杂、更有各种约束条件。如果采用传统的优 化算法和集中控制的方式来实现通信网的动态路由优化，就需要巨大的计算 量，并大大增加网络信令系统的负担：而且还会降低系统的可靠性增加网络运 营的成本。因此，需要研制开发一种先进的智能优化算法、采用分散控制、低 成本高效率地实现电信网的动态路由优化“4 “”1 。 电信网络中的路由是通过路由表进行的。在每个节点的路由表中，对每个 目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表 可知道下一个将要到达的节点。首先对路由表中的信息素强度进行初始化。在 节点x ，以节点i 为目的地址，邻节点为j 处的信息素强度为ri l l = l d 。d 。为从 x 经节点j 到节点i 路径的最小费用值。然后周期性地释放蚂蚁来进行路由， 并修改相应的信息素的值。 将一个网络中的各路由表均用一种概率表来代替，或称此概率表为信息素 表，其中信息素的强度用概率来表示。每个节点均有其自己的信息素表与其每 一个可能的目标节点相对应。如果一个网络中共有3 0 个节点，某一节点又有4 个相邻的节点，则此节点将拥有2 9 个信息素表，而每个表中则包含4 项。信息 素表中的概率项影响蚂蚁在其通往目标节点的过程中选择下一个节点的概率。 蚂蚁施放信息素即可用概率的更新来表示。在网络仿真的每一个时间间隔中， 都可以任一节点作为源节点a 而放出一只人工蚂蚁，这些人工蚂蚁模仿呼叫的 建立过程，并随机地选择网络中其他任意一个节点b 作为其建立呼叫的目标节 点，然后这些蚂蚁从源节点a 开始一个一个节点地行进，并根据信息素表中的 概率选择通往其曰标节点的下一个节点。当一只蚂蚁到达途中的某一节点c 的 时候，就将修改节点c 的路哇| 表中与其源节点相对应的项的概率，相当于施放 第三章蚁群算法原理及其应用 了与其源节点相关的信息素，即该蚂蚁修改信息表的原则是增加指向其前一个 节点的概率，同时按照相应的比例减少选择其他节点的概率。每经过一个时间 间隔，这些人工蚂蚁移动一个节点，当人工蚂蚁到达其目标节点以后，其生命 便宣告结束：然后，不断地又有新的人工蚂蚁被放出。 引入人工蚂蚁的主要目的是让这些蚂蚁能够找到相应的两个节点之间的一 些较好的路由，并且所谓较好的路由是指那些避开了负载较重的节点的路由。 因此，对于上述算法还要加两项可变参数：第一个参数是蚂蚁的“年龄”，即 蚂蚁的年龄等于它走过的节点数，随着蚂蚁年龄的增加，上述两个公式中的 p 概率增量将相应地减小。这样做的结果将有利于蚂蚁寻找出一些相对较短的 路由。第二个参数是延迟。在人工蚂蚁移动的过程中，若走到一个呼叫业务被 某种程度地阻塞的节点，则此人工蚂蚁将被延迟一段时间，然后再让其继续行 进。而延迟的长短取决于该节点呼叫业务的负载情况和阻塞程度。此外还要考 虑其他一些因素，对此算法作一些调整和完善。这样一来，让此迭代过程继续 进行下去，就可以在该网络中利用人工蚂蚁来实现对路由表的调整。 另一方面，电信网络中各种呼叫业务的路由选择是借助上述路由表独立于 人工蚂蚁的操作而进行的。例如，有一个从某一节点a 发起的呼叫，其目标节 点是节点b ：于是将在节点a 的上述路由表中挑选对应节点b 的最大概率，与 此最大概率相关联的、与节点a 相邻的节点即为此呼叫选路的下一个节点。按 照这种方式进行下去，如果可以顺利到达目标节点b ，则此次呼叫允许建立； 如果按此方式选择的路由中，遇到有阻塞的节点，则此次呼叫失败。 仿真结果表明，无论呼叫是均匀分布还是集中分布，利用蚁群算法所得呼 叫拒绝率和平均路径长度均小于最小负载法结果；在呼叫符合集中分布时，蚁 群算法所得呼叫拒绝率低于最短路径法“o m ”。 3 5 3 凸整数规划问题 蚂蚁算法的模型已成功应用于求旅行商问题，二次指派问题，排序问题等 np 困难的组合最优化问题，结果可与模拟退火，遗传算法等通用的启发式算 法相媲美。蚁群算法和局部搜索算法相结合( 称为混合蚁群算法) 应用于解二次 指派问题和排序问题，得到的结果可以与专用算法相媲美。由于大量的组合最 优化问题可化为凸整数规划问题，改进混合蚁群算法并用于解凸整数规划问题 可取得良好效果“。 把凸整数规划问题( p ) 表示为个二部图g = ( v ，u ，e ) ，v 是n 个点的集 合，分别表示解的的i 1 个分量，u 是l 个点的集合( l = m a x l i l ，t = i ， r 1 ) ) ，l i l 是分量i 的最大可能取值，v 中的点i 与u 中的点0 ，1 ，l i l 有边相连，q ( i ，j ) 是边( i ，j ) 上的迹，如果v 中的的点i 与u 中的点j 无边相 连，则q ( i ，j ) = o ，迹矩阵q ( i ，j ) n * l 是一个n 行l 列矩阵。算法歼始时，所 有蚂蚁都集中在第1 个分量处，每个蚂蚁按照选择策略选择一条边，当选择完 一条边后马上更新该边上的迹，当m 个蚂蚁都选择好各自的第一个分量的值 后，都集中到第二个分量处，直到选择完第n 个分量的值，从而建立了m 个 解。以所建立的m 个解为起始点，进行局部搜索，根据得到的局部最优解计算 迹的增量，全局更新迹，全局更新迹后继续迭代直到满足停止条件，停止条件 是最大迭代次数瞄3 。 实验结果表明，该算法比多起始点局部搜索算法和蚁群算法得到好得多的 解。 第三章蚁群算法原理及其应用 3 5 4j s p 问题 j s p 问题可以用一个加权图描述。每条边的权值用参数对，t 1 。 表示。 信息素和可见度n 。是通过最长进程时间或者最短完成时间等要求决定。蚂蚁 遍历节点的顺序就是相应的解决答案。在解决1 0 x 1 0 和i o x l 5 的j s p 问题中， 蚂蚁算法的解与最优解的误差在1 0 之内。这是一个相当不错的结果“。 小结 一 本章主要介绍了蚁群算法的原理、模型、公式、流程，以及它在t s p 问题 研究中所取得的一些结果。同时也对其在大规模集成电路布线，电信网络路由 选择，凸整数规划问题，j s p 问题中的应用做了相关的介绍。在话继的章节 里，将分别介绍系统的后台a r c v i e wg i s 平台，m a p o b j e c t s 中间组件，以及蚁 群算法在交通网络中最佳路径搜索的实验结果。 第四章a r c v i e wg i s 平台 第四章a r c v i e wg i s 平台 地图数据库所储存和处理的信息分成两大类： 第一类是反映事物地理空间位置的信息称为空间属性或空间数据( 也称地图 数据、图形数据、几何数据) ，第二类是反映事物的其它信息，称为属性数据 ( 也称文字数据、非图形数据) 。电子地图的属性数据的储存、管理、处理同一 般信息系统，采用关系型数据库管理系统如v i s u a lf o x p r o 、o d b c 、m s s q l s e r v e r 等进行储存。 ” 电子地图的空间数据库的储存有两种方式：一种是栅格空间数据模型，另 一种是矢量空间数据模型。其建立的方式有两种，一是在现有的g i s 平台下( 如 a r c v i e w 、a r c i n f o 、m a p l n f o 等) 建立起来，这样处理需要将现有的电子地图的 数据转换成相应的g i s 平台下的数据，再利用g i s 平台拓扑化功能将数据拓扑 化，建立起完备的拓扑化的电子地图道路交通网络，通过外部的d b m s 管理属性 数据，从而能够完成电子地图的各种功能。这样建立起来的电子地图数据库能 够充分利用现有g i s 平台的强大功能( 如空间查询、叠合与缓冲区分析、网络分 析等) 。 二是利用现有的电子地图数据进行编程处理建立各种文档数据库和具有拓 扑关系的空间图形数据库。现在各大、中型城市都具有各种比例尺的a u t o c a d 下的道路图，充分利用这些道路交通图作为车载导航系统的基本数据，将这些 地图的基本数据编程处理，建立起能够满足车载导航系统的电子地图所具有的 各大功能，这样建立的电子地图数据库便于编程控制和修改，所占的空间少， 缺点是没有统一的接口，其数据结构在很大的程度上依赖于编程者的需要和编 程经验。 在a c a s 系统中，采用的是以a r c v i e w 为g i s 平台。 4 1g 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 s ) 产生于7 0 年代中 期。随着其自身的不断发展和应用的日趋广泛，g i s 的定义也各种各样，其中 比较准确且被广泛接受的表述为：g i s 是个能用于进行有效的搜集、储存、 更新、处理、分析和显示所有形式之地理信息的计算机硬件、软件、地理数据 和有关人员( 用户) 的有机集合。由此定义可知，g i s 是一种工具，但不仅仅是 一个制作地图的工具，虽然它可以按不同的比例尺、用不同的颜色绘制地图。 在g i s 当中，计算机硬件部分是骨架，没有硬件，其它部分就无从依附：g i s 的 软件部分是其精髓，没有软件，就不成其为g i s ：地理数据则如血液样，没有 了地理数据，地理信息系统就成了空壳：而对用户来说，当他能熟练地选择和使 用g i s 工具盒中的工具进行复杂的分析工作( 如空间分析和模拟预测等) 、并且 熟悉与所用的数据有关的知识时，才能视为g i s 的一部分o “。 g i s 所需要的硬件包括处理速度高且存储容量大的计算机，数据输入设各 如数字化仪、扫描仪，图形输出设备如绘图仪等。软件方面，有e s r i 的 a r c i n f o 和a r c v i e w 、e r d a s 的i m a g i n e 、u s a r m y 的g r a s s 等等。在我国应用较 广的为a r c v i e w ( i j 于w i n d o w s 9 8 n t 2 0 0 0 ) 、美国环境研究公司( e n v i r o n m e n t a l s y s t t i l l s l e s e a r c hi n s t it u t e ) 丌发的a r c i n f o ( 用于u n i x ) 和p c a r c i n f o ( 用 丁d o s ) 。 第四章a r c v i e wg i s 平台 4 2g i s 的基本原理 4 2 1g i s 中的信息存储方式 一幅地图包含的最基本的信息有两种：空间信息( s p a t i a l i n f o r m a t i o n ) 和 描述性信息( d e s c r i p t i v ei n f o r m a t i o n ) 。前者反映了地理特征( g e o g r a p h i c f e a