《蚁群算法原理与应用1资料优秀PPT.ppt》由会员分享，可在线阅读，更多相关《蚁群算法原理与应用1资料优秀PPT.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、自然计算与群体智能自然计算与群体智能赵林亮赵林亮计算机应用技术探讨所计算机应用技术探讨所1蚁群算法蚁群算法赵林亮赵林亮计算机应用技术探讨所计算机应用技术探讨所2参考文献参考文献APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE,PARIS,FRANCE,ELSEVIER PUBLISHING,134142.Distributed Optimization by Ant ColoniesAlberto Colorni,Marco Dorigo,Vittorio ManiezzoDipartimento
2、di Elettronica,Politecnico di MilanoPiazza Leonardo da Vinci 32,20133 Milano,ItalyIEEE Transactions on Systems,Man,And Cybernetics-Part B:Cybernetics,Vol.26,No.1,Feb 1996.29-41Ant System:Optimization by a Colony of Cooperating AgentsMarco Dorigo,Member,IEEE,Vittorio Maniezzo,and Alberto Colorni :/ir
3、idia.ulb.ac.be/mdorigo/HomePageDorigo/3Fig.1.An example with real antsa)Ants follow a path between points A and E.b)An obstacle is interposed;ants can choose to go around it following one of the two different paths with equal probability.c)On the shorter path more pheromone is laid down.4Fig.2.An ex
4、ample with artificial antsa)The initial graph with distances.b)At time t=0 there is no trail on the graph edges;therefore,ants choose whether to turn right or left with equal probability.c)At time t=1 trail is stronger on shorter edges,which are therefore,in the average,preferred by ants.5双桥试验双桥试验(G
5、oss S,1989)Naturwissenschaften 76,579-581(1989)Self-organized Shortcuts in the Argentine AntS.Goss,S.Aron,J.L.Deneubourg,and J.M.PasteelsUnit of Behavioural Ecology,C.P.231,Universit6 Libre de Bruxelles,B-1050 Bruxelles6Fig.1.A colony of I humilis selecting the short branches on both modules of the
6、bridgea)one module of the bridgeb)and c):photos taken 4 and 8 min after placement of the bridge7双桥试验数学模型双桥试验数学模型假设条件：假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁依据桥上残留的信息量多少来选择其中某座桥、某一时刻蚂蚁依据桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为设短桥为A
7、，长桥为，长桥为B，mA和和mB分别表示经过桥分别表示经过桥A和桥和桥B的蚂蚁数目的蚂蚁数目mA+mB=m当全部当全部m只蚂蚁都经过两座桥之后，第只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥只蚂蚁选择桥A的概率为：的概率为：而选择桥而选择桥B的概率为：的概率为：8参数参数h 和和 k用以匹配真实试验数据用以匹配真实试验数据第第m+1只蚂蚁首先计算只蚂蚁首先计算 然后生成一个在区间然后生成一个在区间0,1上匀整分布的随机数上匀整分布的随机数若若 ，则选择桥，则选择桥A，否则选择桥，否则选择桥B9基本蚁群算法的数学模型基本蚁群算法的数学模型10P、NP、NP-C、NP-hard问题问题P类问题类问
8、题全部可用全部可用DTM(Deterministic one-tape Turing Machine)在多项式时间内求解的判在多项式时间内求解的判定问题定问题的集合。简记为的集合。简记为O(p(n)即即 P=L:存在一个多项式时间存在一个多项式时间DTM程序程序M，是的，是的L=LM,其中其中LM表示程序表示程序M所识别所识别的语言。的语言。若存在一个多项式时间若存在一个多项式时间DTM程序，它在编程序，它在编码策略码策略e之下求解判定问题之下求解判定问题，即，即L,eP,则称该判定问题属于则称该判定问题属于P类问题。类问题。11P、NP、NP-C、NP-hard问题问题NP类问题类问题(No
9、n-deterministic Polynomial)若存在一个多项式函数若存在一个多项式函数 g(x)和一个验证算和一个验证算法法H,对一类判定问题对一类判定问题A的任何一个的任何一个“是是”回答，满足其输入长度回答，满足其输入长度d(s)不超过不超过g(d(I),其其中中d(I)为为I的输入长度，且验证算法中的输入长度，且验证算法中S为为I的的“是是”回答的计算时间不超过回答的计算时间不超过g(d(I),则称则称判定问题判定问题A为非多项式确定问题。为非多项式确定问题。NP类问题是全部可用类问题是全部可用NDTM(Non-Deterministic one-tape Turing Mach
10、ine)在在多项式时间内求解的判定问题多项式时间内求解的判定问题的集合的集合12P、NP、NP-C、NP-hard问题问题NP-C类问题类问题(NP-Complete)是是NP类中最困难的一类问题。类中最困难的一类问题。有重要实际意义和工程背景有重要实际意义和工程背景TSP(Traveling Salesman Problem)Symmetric;AsymmetricNP-hard类问题类问题NP-C NP-hardNPPNP-hardNP-C13基本蚁群算法模型基本蚁群算法模型基本假设基本假设蚂蚁之间通过信息素和环境进行通信。每蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅依据其四周的局部环境
11、作出反应，只蚂蚁仅依据其四周的局部环境作出反应，也只对四周的局部环境产生影响；也只对四周的局部环境产生影响；蚂蚁对环境的反应由其内部模式确定。即蚂蚁对环境的反应由其内部模式确定。即蚂蚁是反应型适应性主体蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅依据环境做出在个体水平上，每只蚂蚁仅依据环境做出独立选择；在群体水平上，单只蚂蚁的行独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。成高度有序的群体行为。14TSP(Traveling Salesman Problem)有向图有向图有向图有向图D的三元组为的三元组为(V
12、,E,f)，其中，其中V是一个非是一个非空集合，其元素称为有向图的结点；空集合，其元素称为有向图的结点；E是一个是一个集合，其元素称为有向图的弧段（边）；集合，其元素称为有向图的弧段（边）；f是从是从E到到VxV上的一个映射（函数）。上的一个映射（函数）。E中的元素总是和中的元素总是和V中的序偶对有对应关系，可中的序偶对有对应关系，可用用V中的序偶代替中的序偶代替E中的元素。中的元素。一个有向图可简记为一个有向图可简记为(V,E).15TSP(Traveling Salesman Problem)TSP设设C=c1,c2,cn 是是n个城市的集合，个城市的集合，L=lij|ci,cj C是集合
13、是集合C中的元素（城市）两两连接的中的元素（城市）两两连接的集合，集合，dij(i,j=1,1,n)是是lij的的Euclidean距离，即距离，即G=(C,L)是一个有向图，是一个有向图，TSP的目的是从有向图的目的是从有向图G中寻中寻出长度最短的出长度最短的Hamilton圈，圈，即一条对即一条对C=c1,c2,cn中中n个元素（城市）访问且只个元素（城市）访问且只访问一次的最短封闭曲线访问一次的最短封闭曲线16TSP(Traveling Salesman Problem)TSP简洁形象描述简洁形象描述给定给定n个城市，一个旅行商从某一城市动身，访个城市，一个旅行商从某一城市动身，访问各城
14、市一次且仅有一次后再回到原动身城市，问各城市一次且仅有一次后再回到原动身城市，要求找出一条最短的巡回路径要求找出一条最短的巡回路径可分为对称可分为对称TSP(Symmetric Traveling Salesman Problem)和非对称和非对称TSP(Asymmetric Traveling Salesman Problem)TSP是是NP-C问题问题n城市规模的城市规模的TSP，存在，存在(n-1)!/2条不同闭合路径。条不同闭合路径。17基本蚁群算法数学模型基本蚁群算法数学模型设设bi(t)表示表示t时刻位于元素时刻位于元素i的蚂蚁数目，的蚂蚁数目，ij(t)为为t时刻路径时刻路径(i
15、,j)上的信息量，上的信息量，n表示表示TSP规模，规模，m为蚁群中蚂蚁总数，则为蚁群中蚂蚁总数，则 是是t时刻集合时刻集合C中元素（城中元素（城市）两两连接市）两两连接lij上残留信息量的集合，在初始时刻上残留信息量的集合，在初始时刻各条路径上的信息量相等，并设各条路径上的信息量相等，并设ij(0)=const,基基本蚁群算法的寻优是通过有向图本蚁群算法的寻优是通过有向图g=(C,L,)实现实现的。的。18蚂蚁蚂蚁k(k=1,2,m)在运动过程中，依据各条路径上的信息在运动过程中，依据各条路径上的信息量确定其转移方向。这里用禁忌表量确定其转移方向。这里用禁忌表tabuk来记录蚂蚁来记录蚂蚁k
16、当前当前所走过的城市，集合随着所走过的城市，集合随着tabuk进化过程做动态调整。在进化过程做动态调整。在搜寻过程中，蚂蚁依据各条路径上的信息量及路径的启发搜寻过程中，蚂蚁依据各条路径上的信息量及路径的启发信息来计算状态转移概率。在信息来计算状态转移概率。在t时刻蚂蚁时刻蚂蚁k由元素（城市）由元素（城市）i转移到元素（城市）转移到元素（城市）j的状态转移概率：的状态转移概率：19其中其中allowedk=C-tabuk表示蚂蚁表示蚂蚁k下一步允许选择的城下一步允许选择的城市；市；为信息启发式因子，表示轨迹的相对重要性，反映为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息
17、在蚂蚁运动时所起的作用，了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；蚂蚁之间的协作性越强；为期望启发式因子，表示能见为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则；概率越接近于贪心规则；ij(t)为启发函数，为启发函数，ij(t)=1/dij式中式中dij表示相邻两个城
18、市之间的距离。对蚂蚁表示相邻两个城市之间的距离。对蚂蚁k而言，而言，dij越小，则越小，则ij(t)越大，越大，pijk也就越大。明显，该启发函数表也就越大。明显，该启发函数表示蚂蚁从元素（城市）示蚂蚁从元素（城市）i转移到元素（城市）转移到元素（城市）j的期望程度。的期望程度。20为了避开残留信息素过多引起残留信息沉没启发信息，为了避开残留信息素过多引起残留信息沉没启发信息，在每只蚂蚁走完一步或者完成对全部在每只蚂蚁走完一步或者完成对全部n个城市的遍历个城市的遍历(也即一个循环结束也即一个循环结束)后，要对残留信息进行更新处理。后，要对残留信息进行更新处理。这种更新策略仿照了人类大脑记忆的特
19、点，在新信息不这种更新策略仿照了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的断存人大脑的同时，存储在大脑中的旧信息随着时间的推移渐渐淡化，甚至遗忘。由此，推移渐渐淡化，甚至遗忘。由此，t+n时刻在路径时刻在路径(i,j)上的信息量可按如下规则进行调整上的信息量可按如下规则进行调整 21式中，式中，表示信息素挥发系数，则表示信息素挥发系数，则1-表示信息素表示信息素残留因子，为了防止信息的无限积累，残留因子，为了防止信息的无限积累，的取值的取值范围为范围为0，1),ij(t)表示本次循环中路径表示本次循环中路径(i,j)上上的信息素增量，初始时刻的信息素增量，初
20、始时刻ij(t)=0,ijk(t)表示表示第第k只蚂蚁在本次循环中留在路径只蚂蚁在本次循环中留在路径(i,j)上的信息上的信息量。量。依据信息素更新策略的不同，依据信息素更新策略的不同，Dorigo M提出了三提出了三种不同的基本蚁群算法模型，分别称之为种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、模型、Ant-Quantity模型及模型及Ant-Density模型，模型，其差别在于其差别在于ijk(t)求法的不同。求法的不同。22Ant-Cycle模型模型式中，式中，Q表示信息素强度，它在确定程度上影响表示信息素强度，它在确定程度上影响算法的收敛速度；算法的收敛速度；Lk表示第
21、表示第k只蚂蚁在本次循环只蚂蚁在本次循环中所走路径的总长度。中所走路径的总长度。23 Ant-Quantity模型模型 24 Ant-Density模型模型 区分：区分：式式(5)和式和式(6)中利用的是局部信息，即蚂蚁完成中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而式一步后更新路径上的信息素；而式(4)中利用的中利用的是整体信息，即蚂蚁完成一个循环后更新全部路是整体信息，即蚂蚁完成一个循环后更新全部路径上的信息素，在求解径上的信息素，在求解TSP时性能较好，因此通时性能较好，因此通常接受式常接受式(4)作为蚁群算法的基本模型。作为蚁群算法的基本模型。25基本蚁群算法的实现基本蚁
22、群算法的实现以以TSP为例，基本蚁群算法的具体实现步骤为例，基本蚁群算法的具体实现步骤如下：如下：(1)参数初始化。令时间参数初始化。令时间t=0和循环次数和循环次数Nc=0，设置最大循环次数，设置最大循环次数Ncmax,将将m个蚂个蚂蚁置于蚁置于n个元素个元素(城市城市)上，令有向图上每条上，令有向图上每条边边(i,j)的初始化信息量的初始化信息量ij(t)=const,其中其中const表示常数，且初始时刻表示常数，且初始时刻ij(0)=0 (2)循环次数循环次数Nc Nc+1。(3)蚂蚁的禁忌表索引号蚂蚁的禁忌表索引号k=1。(4)蚂蚁数目蚂蚁数目 kk+1。26基本蚁群算法的实现基本蚁
23、群算法的实现(5)蚂蚁个体依据状态转移概率公式蚂蚁个体依据状态转移概率公式(1)计算的概计算的概率选择元素率选择元素(城市城市)j 并前进，并前进，jC-tabuk。(6)修改禁忌表指针，即选择好之后将蚂蚁移动修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素到新的元素(城市城市)，并把该元素，并把该元素(城市城市)移动到移动到该蚂蚁个体的禁忌表中。该蚂蚁个体的禁忌表中。(7)若集合若集合C中元素中元素(城市城市)未遍历完，即未遍历完，即km，则，则跳转到第跳转到第(4)步，否则执行第步，否则执行第(8)步。步。(8)依据公式依据公式(2)和式和式(3)更新每条路径上的信息更新每条路径上的信息量
24、。量。(9)若满足结束条件，即假如循环次数若满足结束条件，即假如循环次数Nc Ncmax 则循环结束并输出程序计算结果，否则则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第清空禁忌表并跳转到第(2)步。步。27基本蚁群算法程序流程图基本蚁群算法程序流程图输出程序计算结果输出程序计算结果按式（按式（2）和式（）和式（3）进行信息量更新）进行信息量更新修改禁忌表修改禁忌表按式（按式（1）选择下一元素）选择下一元素蚂蚁蚂蚁k=1循环次数循环次数Nc Nc+1初始化初始化开始开始结束结束Km满足结束条件满足结束条件蚂蚁蚂蚁k=k+1NYYN28困难度分析困难度分析对于对于TSP，全部可行的路径共
25、有，全部可行的路径共有(n-1)!/2条，条，以此路径比较为基本操作，则须要以此路径比较为基本操作，则须要(n-1)!/2-1次基本操作才能保证得到确定最优解。次基本操作才能保证得到确定最优解。若若1M FLOPS，当，当n=10,须要须要0.19秒秒n=20,须要须要1929年年n=30,须要须要1.4X10e17年年时间困难度时间困难度空间困难度空间困难度29算法标准算法标准正确性正确性可用性可用性可读性可读性执行效率执行效率健壮性健壮性30蚁群算法应用蚁群算法应用赵林亮赵林亮计算机应用技术探讨所计算机应用技术探讨所31Quality of Service,QoSQoS的英文全称为的英文全
26、称为Quality of Service，中文名，中文名为为服务质量服务质量。QoS是网络的一种平安机制是网络的一种平安机制,是用是用来解决网络延迟和堵塞等问题的一种技术。来解决网络延迟和堵塞等问题的一种技术。在正常状况下，假如网络只用于特定的无时间限在正常状况下，假如网络只用于特定的无时间限制的应用系统，并不须要制的应用系统，并不须要QoS，比如，比如Web应用，应用，或或E-mail设置等。但是对关键应用和多媒体应用设置等。但是对关键应用和多媒体应用就特别必要。当网络过载或拥塞时，就特别必要。当网络过载或拥塞时，QoS 能确保能确保重要业务量不受延迟或丢弃，同时保证网络的高重要业务量不受延
27、迟或丢弃，同时保证网络的高效运行。效运行。32QoS网络路由网络路由网络路由方面的探讨主要通过两个途径来提高服网络路由方面的探讨主要通过两个途径来提高服务质量务质量(QoS）：一条途径是节点限制；另一条途）：一条途径是节点限制；另一条途径是整网或局部网络限制。节点限制在单节点或径是整网或局部网络限制。节点限制在单节点或单链路完成，主要限制业务对单节点共享资源的单链路完成，主要限制业务对单节点共享资源的占用；整网或局部网络限制通常通过对路由与信占用；整网或局部网络限制通常通过对路由与信令的限制达到对业务流或业务连接在网络中传输令的限制达到对业务流或业务连接在网络中传输的干脆限制。因为路由干脆关系
28、到网络性能，所的干脆限制。因为路由干脆关系到网络性能，所以以QoS路由成为解决路由成为解决QoS问题的核心技术之一，也问题的核心技术之一，也是当今网络技术领域内的一个探讨热点。是当今网络技术领域内的一个探讨热点。33QoS指标：指标：带宽带宽单位时间内能够在线路上传送的数据量，单位时间内能够在线路上传送的数据量，bps(bit per second)。时延时延时延是指一个报文或分组从网络的一端传送到另时延是指一个报文或分组从网络的一端传送到另一端所须要的时间。它包括了发送时延，传播时一端所须要的时间。它包括了发送时延，传播时延，处理时延，他们的总和就是总时延延，处理时延，他们的总和就是总时延时
29、延抖动时延抖动变更的时延被称作抖动（变更的时延被称作抖动（Jitter）费用费用QoS路由的任务路由的任务在网络中找寻一条路径，使其能满足带宽、时延、在网络中找寻一条路径，使其能满足带宽、时延、时延抖动和费用的限制时延抖动和费用的限制34Wang Z等证明白，假如等证明白，假如QoS路由至少包含路由至少包含两个限制时，它是一个两个限制时，它是一个NP-C问题。传统的问题。传统的路由算法很难有效地解决路由算法很难有效地解决NP-C问题，因此问题，因此一些学者基于蚁群算法提出了很多行之有一些学者基于蚁群算法提出了很多行之有效的解决方案。效的解决方案。35 随着随着Internet的飞速发展，对的飞
30、速发展，对QoS路由的探路由的探讨已经引起了众多关注。讨已经引起了众多关注。平面平面QoS路由路由全部路由器都在同一级内，全部路由器都在同一级内，以前对以前对QoS路由的探讨大多接受平面网络，路由的探讨大多接受平面网络，分级分级QoS路由路由基本思想：将路由器分成多个逻辑组，每基本思想：将路由器分成多个逻辑组，每个组又可包含更小的组。个组又可包含更小的组。36平面平面QoS蚂蚁路由算法蚂蚁路由算法 问题描述问题描述将网络模型表示为一个有向图将网络模型表示为一个有向图G=(V，E)，其中其中V是图中全部交换节点组成的集合是图中全部交换节点组成的集合E是图中全部边的集合是图中全部边的集合每一条边表
31、示相邻两节点间的直达通信路每一条边表示相邻两节点间的直达通信路径径不失一般性，假定相邻两节点间最多仅有不失一般性，假定相邻两节点间最多仅有一条边。同时，假定一条边。同时，假定B(l)表示链路表示链路l的可用带的可用带宽，对于一个路由恳求宽，对于一个路由恳求w，路由算法假如能，路由算法假如能够找到一条具有小费用的路径，同时满足够找到一条具有小费用的路径，同时满足如下如下4个条件，则此路由恳求个条件，则此路由恳求w就可接受。就可接受。37(1)在在w的路由的每条路径的路由的每条路径l上，带宽可用限制为上，带宽可用限制为(2)在在w的路由上，端到端时延限制为的路由上，端到端时延限制为(3)在在w的路
32、由上，端到端丢失率限制为的路由上，端到端丢失率限制为(4)在目的节点，端到端时延抖动限制为在目的节点，端到端时延抖动限制为 38符号符号Bw、Dw、Lw、Jw表示表示QoS要求的带宽、要求的带宽、时延、丢失率、抖动限制时延、丢失率、抖动限制DN：节点处理延时：节点处理延时DL：链路时延：链路时延V1：w路由的节点集合路由的节点集合E1：w路由的链路集合路由的链路集合LR：节点丢失率：节点丢失率NDV：目的节点：目的节点d的节点时延变更的节点时延变更39算法设计算法设计蚁群算法的两个步骤蚁群算法的两个步骤:依据信息素的量选择路径依据信息素的量选择路径更新路径上的信息素数量更新路径上的信息素数量假
33、定平面假定平面QoS蚂蚁路由算法中有蚂蚁路由算法中有m只蚂蚁，只蚂蚁，设计如下的三个规则：设计如下的三个规则：状态转移规则状态转移规则全局信息素更新规则。全局信息素更新规则。局部信息素更新规则。局部信息素更新规则。40状态转移规则状态转移规则 位于节点位于节点r的第的第i只蚂蚁依据下述规则来选择节点只蚂蚁依据下述规则来选择节点s：接受此定义来实现蚂蚁状态的转移可保证找寻优化接受此定义来实现蚂蚁状态的转移可保证找寻优化路径时避开陷入局部最优。路径时避开陷入局部最优。41where,q is a random number uniformly distributed in 0,1,qo a con
34、stant satisfying 0,1;pi(r,s)represents the probability with which the ith ant positioned on node r chooses the next node s,phero(i,r,s)the amount of pheromone deposited on the edge between the nodes r and s currently by the ith type of ants,Ji(r)the nodes between which and the node r there is an edg
35、e and by which the ith-type ant has not passed during its choosing path.42信息素局部更新规则信息素局部更新规则对于第对于第i只蚂蚁，假如节点只蚂蚁，假如节点r,s是该蚂蚁所选路径是该蚂蚁所选路径上的两个相邻节点，则信息素上的两个相邻节点，则信息素phero(i,r,s)用下式用下式来调整；否则，不调整。来调整；否则，不调整。where,00 1,cons is a constant.Adjusting the amount of pheromone by the rule can make the desirabilit
36、y of edges change dynamically.In this way,ants will make a better use of pheromone information;without the local updating,all ants would search in a narrow neighborhood of the best previous path.43信息素全局更新规则信息素全局更新规则对于第对于第i只蚂蚁，假如节点只蚂蚁，假如节点r,s是该蚂蚁所选路径是该蚂蚁所选路径上的两个相邻节点，则信息素上的两个相邻节点，则信息素phero(i,r,s)按公式按公
37、式1调整调整,否则按公式否则按公式2调整。调整。where,0 1 Jw，那么退出；否则，跳转，那么退出；否则，跳转到第到第(2)步。步。(2)删除带宽小于需求带宽的链路，把网络滤删除带宽小于需求带宽的链路，把网络滤成一个新的简洁网络。成一个新的简洁网络。(3)初始化网络拓扑中各边的相应信息素。初始化网络拓扑中各边的相应信息素。49平面平面QoS蚂蚁路由算法具体步骤蚂蚁路由算法具体步骤(2)(4)从蚁巢起先放出从蚁巢起先放出m只蚂蚁去找寻食物源，只蚂蚁去找寻食物源，在第一个时间单位，每只蚂蚁从节点集合中随在第一个时间单位，每只蚂蚁从节点集合中随机地选择一个节点，然后各蚂蚁通过重复应用机地选择一
38、个节点，然后各蚂蚁通过重复应用状态转移规则来选择各自的路径。在选路过程状态转移规则来选择各自的路径。在选路过程中，假如蚂蚁在到达目的节点前死亡，另外一中，假如蚂蚁在到达目的节点前死亡，另外一只和死亡的蚂蚁同类的蚂蚁重新放出来代替死只和死亡的蚂蚁同类的蚂蚁重新放出来代替死亡的蚂蚁，重新起先选择从源节点到目的节点亡的蚂蚁，重新起先选择从源节点到目的节点的路径。当某只蚂蚁成功地完成路由选择后，的路径。当某只蚂蚁成功地完成路由选择后，该蚂蚁所选路由各路径上的信息素依据局部更该蚂蚁所选路由各路径上的信息素依据局部更新规则进行更新。新规则进行更新。50平面平面QoS蚂蚁路由算法具体步骤蚂蚁路由算法具体步骤
39、(3)(5)对全部的蚂蚁重复第对全部的蚂蚁重复第(4)步，直到步，直到m只蚂蚁只蚂蚁都完成了第都完成了第(4)步。步。(6)选择建立了最小费用并满足选择建立了最小费用并满足QoS限制的路限制的路由的蚂蚁，然后运用全局更新规则对该蚂蚁所由的蚂蚁，然后运用全局更新规则对该蚂蚁所选的路由的各路径上的信息素进行更新。选的路由的各路径上的信息素进行更新。(7)重复第重复第(4)(6)步，直到获得满足的结果。步，直到获得满足的结果。51分级分级QoS蚂蚁路由算法蚂蚁路由算法 当前的大多数大型网络当前的大多数大型网络,包括包括Internet,都运都运用分级选路方式用分级选路方式.它的基本思想是它的基本思想
40、是:路由器路由器被分成多个逻辑组被分成多个逻辑组,每个组又可以包含更小每个组又可以包含更小的组的组.计算机网络分簇结构特点计算机网络分簇结构特点网络管理网络管理路由计算路由计算资源利用资源利用Ad hoc网络网络52考虑一个二级网络。每个路由器即为一个考虑一个二级网络。每个路由器即为一个level-0节点，由多个节点，由多个level-0节点和节点和level-0链链路形成的路形成的LAN称为称为level-1节点，节点，level-1节点节点之间通过之间通过level-1链路连接。链路连接。在大多数应用中，时延要求是最为重要的，在大多数应用中，时延要求是最为重要的，为了便利起见，这里在探讨为
41、了便利起见，这里在探讨QoS路由时仅考路由时仅考虑时延限制。虑时延限制。5354算法构造算法构造(1)初始化。初始化。(2)依据呼叫的源一目的节点，确定此源一依据呼叫的源一目的节点，确定此源一目的节点是否在同一级内：若在目的节点是否在同一级内：若在(如如x.1x.3)，干脆在相应级，干脆在相应级x内调用蚁群算法内调用蚁群算法进行选路进行选路(1evel-0路由路由)；若不在同一级内，；若不在同一级内，则执行第则执行第(3)步。步。(3)依据依据level-1节点的相邻关系，选最少节点的相邻关系，选最少level-1节点数的路由节点数的路由(称为称为level-1路由路由)。55算法构造算法构造
42、(2)(4)依据此路由，确定每个依据此路由，确定每个level-1节点内的节点内的源一目的节点，作为蚁群算法的输入，同源一目的节点，作为蚁群算法的输入，同时调用蚁群算法进行选路时调用蚁群算法进行选路(称为称为level-0路由路由)，并记录结果。，并记录结果。(5)依据第依据第(3)、(4)步的结果，扩展出最终步的结果，扩展出最终路由，推断是否满足要求：若满足，则结路由，推断是否满足要求：若满足，则结束此次选路；否则，推断是否还存在束此次选路；否则，推断是否还存在level-1路由：若存在，则接受最短路径法在剩余路由：若存在，则接受最短路径法在剩余的可行路由中选择最短的一条，并将其定的可行路由
43、中选择最短的一条，并将其定为新的为新的level-1路由，跳转到第路由，跳转到第(4)步；否则，步；否则，此次呼叫没有可用路由，算法结束。此次呼叫没有可用路由，算法结束。56分级路由实例分级路由实例找寻找寻x.0 c.2的路由的路由首先确定出首先确定出level-1路由：路由：xbc或或 xac 假定选假定选 xac,则可得出三个源一目的对则可得出三个源一目的对:(x.0,x.3)(a.2,a.2)(c.3,c.2)同时启动三个蚁群算法计算出满足要求的路由链同时启动三个蚁群算法计算出满足要求的路由链路路(x.0 x.1x.3),(a.2a.2),(c.3 c.0c.1c.2)依据此结果，可扩展
44、出最终路由依据此结果，可扩展出最终路由x.0 x.1x.3a.2c.3c.0c.1c.2)若此路由满足要求就结束；否则，重新选定若此路由满足要求就结束；否则，重新选定level-1路由，进行新的选路。路由，进行新的选路。57基于蚁群算法的基于蚁群算法的level-0路由算法的状态转移路由算法的状态转移规则和信息素局部更新规则同前所述，但规则和信息素局部更新规则同前所述，但对信息素全局更新规则中的限制函数对信息素全局更新规则中的限制函数F的定的定义做了如下改进。义做了如下改进。5859参考文献参考文献Zhang S B,Liu Z M.A QoS routing algorithm based on ant algorithm.Proceedings of the IEEE ICC,2001,5:1581-1585张素兵张素兵,刘泽民刘泽民.基于蚂蚁算法的分级基于蚂蚁算法的分级QoS 路由调度方法路由调度方法.北京邮电高校学报北京邮电高校学报.2000,23(4):11-1560aai_ise126 /aai2009课件课件论文论文61