蚁群算法原理与应用1.ppt

1,自然计算与群体智能,赵林亮 计算机应用技术研究所 ,2,蚁群算法,赵林亮 计算机应用技术研究所 ,3,参考文献,APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE, ELSEVIER PUBLISHING,134142. Distributed Optimization by Ant Colonies Alberto Colorni, Marco Dorigo, Vittorio Maniezzo Dipartimento di Elettronica, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, Italy IEEE Transactions on Systems, Man, And Cybernetics- Part B: Cybernetics,Vol.26, No.1, Feb 1996. 29-41 Ant System: Optimization by a Colony of Cooperating Agents Marco Dorigo, Member, IEEE, Vittorio Maniezzo, and Alberto Colorni http:/iridia.ulb.ac.be/mdorigo/HomePageDorigo/,4,Fig. 1. An example with real ants,a) 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.,5,Fig. 2. An example with artificial ants,a) 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.,6,双桥实验(Goss S, 1989),Naturwissenschaften 76, 579-581 (1989) Self-organized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels Unit of Behavioural Ecology, C.P. 231, Universit6 Libre de Bruxelles, B- 1050 Bruxelles,7,Fig. 1. A colony of I humilis selecting the short branches on both modules of the bridge,a) one module of the bridge b) and c): photos taken 4 and 8 min after placement of the bridge,8,双桥实验数学模型,假设条件： 1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比； 2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥 3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大,设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目 mA + mB = m 当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：,而选择桥B的概率为：,9,参数h 和 k用以匹配真实实验数据 第m+1只蚂蚁首先计算 然后生成一个在区间0,1上均匀分布的随机数 若 ，则选择桥A，否则选择桥B,10,基本蚁群算法的数学模型,11,P、NP、NP-C、NP-hard问题,P类问题 所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的集合。简记为O(p(n) 即 P=L: 存在一个多项式时间DTM程序M，是的L=LM , 其中LM表示程序M所识别的语言。 若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题，即L, eP,则称该判定问题属于P类问题。,12,P、NP、NP-C、NP-hard问题,NP类问题 (Non-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 Machine)在多项式时间内求解的判定问题的集合,13,P、NP、NP-C、NP-hard问题,NP-C类问题 (NP-Complete) 是NP类中最困难的一类问题。 有重要实际意义和工程背景 TSP (Traveling Salesman Problem) Symmetric; Asymmetric NP-hard类问题 NP-C NP-hard,NP,P,NP-hard,NP-C,14,基本蚁群算法模型,基本假设 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响； 蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。,15,TSP (Traveling Salesman Problem),有向图 有向图D的三元组为 (V, E, f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。 E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。 一个有向图可简记为(V, E).,16,TSP (Traveling Salesman Problem),TSP 设C=c1, c2, , cn 是n个城市的集合， L=lij|ci, cj C是集合C中的元素（城市）两两连接的集合， dij(i, j=1,1,n)是lij的Euclidean距离，即,G=(C, L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈， 即一条对C=c1, c2, , cn中n个元素（城市）访问且只访问一次的最短封闭曲线,17,TSP (Traveling Salesman Problem),TSP简单形象描述 给定n个城市，一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径 可分为对称TSP (Symmetric Traveling Salesman Problem) 和非对称TSP (Asymmetric Traveling Salesman Problem) TSP是NP-C问题 n城市规模的TSP，存在(n-1)!/2条不同闭合路径。,18,基本蚁群算法数学模型,设bi(t)表示t时刻位于元素i的蚂蚁数目，ij (t)为t时刻路径(i, j)上的信息量，n表示TSP规模，m为蚁群中蚂蚁总数，则 是t时刻集合C中元素（城市）两两连接lij上残留信息量的集合，在初始时刻各条路径上的信息量相等，并设ij(0)=const, 基本蚁群算法的寻优是通过有向图g=(C, L, )实现的。,19,蚂蚁k(k=1,2,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率：,20,其中allowedk=C-tabuk表示蚂蚁k下一步允许选择的城市；为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则； ij(t)为启发函数， ij(t) =1/dij 式中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ij(t)越大，pijk也就越大。显然，该启发函数表示蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。,21,为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i, j)上的信息量可按如下规则进行调整,22,式中，表示信息素挥发系数，则1-表示信息素残留因子，为了防止信息的无限积累， 的取值范围为0，1), ij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻ij(t) =0, ijk(t) 表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量。 根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于ijk(t)求法的不同。,23,Ant-Cycle模型 式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。,24,Ant-Quantity模型,25,Ant-Density模型 区别： 式(5)和式(6)中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而式(4)中利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用式(4)作为蚁群算法的基本模型。,26,基本蚁群算法的实现,以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 。,27,基本蚁群算法的实现,(5)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市) j 并前进，jC - tabuk。 (6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。 (7)若集合C中元素(城市)未遍历完，即km，则跳转到第(4)步，否则执行第(8)步。 (8)根据公式(2)和式(3)更新每条路径上的信息量。 (9)若满足结束条件，即如果循环次数Nc Ncmax 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。,28,基本蚁群算法程序流程图,29,复杂度分析 对于TSP，所有可行的路径共有(n-1)!/2条，以此路径比较为基本操作，则需要(n-1)!/2-1次基本操作才能保证得到绝对最优解。 若1M FLOPS，当n=10, 需要0.19秒 n=20, 需要1929年 n=30, 需要1.4X10e17年 时间复杂度 空间复杂度,30,算法标准 正确性 可用性 可读性 执行效率 健壮性,31,蚁群算法应用,赵林亮 计算机应用技术研究所 ,32,Quality of Service, QoS,QoS的英文全称为“Quality of Service“，中文名为“服务质量“。QoS是网络的一种安全机制, 是用来解决网络延迟和阻塞等问题的一种技术。 在正常情况下，如果网络只用于特定的无时间限制的应用系统，并不需要QoS，比如Web应用，或E-mail设置等。但是对关键应用和多媒体应用就十分必要。当网络过载或拥塞时，QoS 能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。,33,QoS网络路由,网络路由方面的研究主要通过两个途径来提高服务质量 (QoS）：一条途径是节点控制；另一条途径是整网或局部网络控制。节点控制在单节点或单链路完成，主要控制业务对单节点共享资源的占用；整网或局部网络控制通常通过对路由与信令的控制达到对业务流或业务连接在网络中传输的直接控制。因为路由直接关系到网络性能，所以QoS路由成为解决QoS问题的核心技术之一，也是当今网络技术领域内的一个研究热点。,34,QoS指标： 带宽 单位时间内能够在线路上传送的数据量，bps(bit per second)。 时延 时延是指一个报文或分组从网络的一端传送到另一端所需要的时间。它包括了发送时延，传播时延，处理时延，他们的总和就是总时延 时延抖动 变化的时延被称作抖动（Jitter） 费用 QoS路由的任务 在网络中寻找一条路径，使其能满足带宽、时延、时延抖动和费用的限制,35,Wang Z等证明了，如果QoS路由至少包含两个限制时，它是一个NP-C问题。传统的路由算法很难有效地解决NP-C问题，因此一些学者基于蚁群算法提出了许多行之有效的解决方案。,36,随着Internet的飞速发展，对QoS路由的研究已经引起了众多关注。 平面QoS路由 所有路由器都在同一级内， 以前对QoS路由的研究大多采用平面网络， 分级QoS路由 基本思想：将路由器分成多个逻辑组，每个组又可包含更小的组。,37,平面QoS蚂蚁路由算法,问题描述 将网络模型表示为一个有向图G =(V，E)， 其中V是图中所有交换节点组成的集合 E是图中所有边的集合 每一条边表示相邻两节点间的直达通信路径 不失一般性，假定相邻两节点间最多仅有一条边。同时，假定B(l)表示链路l的可用带宽，对于一个路由请求w，路由算法如果能够找到一条具有小费用的路径，同时满足如下4个条件，则此路由请求w就可接受。,38,(1)在w的路由的每条路径l上，带宽可用限制为,(2)在w的路由上，端到端时延限制为,(3)在w的路由上，端到端丢失率限制为,(4)在目的节点，端到端时延抖动限制为,39,符号,Bw、Dw、Lw、 Jw表示QoS要求的带宽、时延、丢失率、抖动限制 DN：节点处理延时 DL：链路时延 V1：w路由的节点集合 E1： w路由的链路集合 LR：节点丢失率 NDV：目的节点d的节点时延变化,40,算法设计,蚁群算法的两个步骤: 按照信息素的量选择路径 更新路径上的信息素数量 假定平面QoS蚂蚁路由算法中有m只蚂蚁，设计如下的三个规则： 状态转移规则 全局信息素更新规则。 局部信息素更新规则。,41,状态转移规则,位于节点r的第i只蚂蚁依据下述规则来选择节点s：,采用此定义来实现蚂蚁状态的转移可保证寻找优化路径时避免陷入局部最优。,42,where, q is a random number uniformly distributed in 0,1, qo a constant 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 edge and by which the ith-type ant has not passed during its choosing path.,43,信息素局部更新规则,对于第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 desirability 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.,44,信息素全局更新规则,对于第i只蚂蚁，如果节点r, s是该蚂蚁所选路径上的两个相邻节点，则信息素phero(i, r, s)按公式1调节, 否则按公式2调节。 where, 0 1 1 . The purpose of the rule is to search the globally best resolution.,45,为定义限制函数F，引入几个符号定义：,46,限制函数F的定义,47,信息素的全局更新规则,式中，N表示网络的节点数目；A、B和C分别表示带宽可用限制、端到端时延限制和端到端丢失率限制，且为正实数； F1表示费用限制；F2表示QoS限制。 通过上述定义可见，如果所选路由的总费用最小，同时QoS限制也满足要求，那么最优蚂蚁所选路由的各链路上的信息素应该增加更多。,48,算法设计,为提高算法的收敛性能，做以下两点改进： 在蚁群算法迭代中不考虑时延抖动，而是在算法执行前进行处理； 通过删除带宽小于需求带宽的链路，把网络滤成一个新的简单网络，因此在F函数中设A=0,49,平面QoS蚂蚁路由算法具体步骤,(1)如果NDV(d)Jw，那么退出；否则，跳转到第(2)步。 (2)删除带宽小于需求带宽的链路，把网络滤成一个新的简单网络。 (3)初始化网络拓扑中各边的相应信息素。,50,平面QoS蚂蚁路由算法具体步骤(2),(4)从蚁巢开始放出m只蚂蚁去寻找食物源，在第一个时间单位，每只蚂蚁从节点集合中随机地选择一个节点，然后各蚂蚁通过重复应用状态转移规则来选择各自的路径。在选路过程中，如果蚂蚁在到达目的节点前死亡，另外一只和死亡的蚂蚁同类的蚂蚁重新放出来代替死亡的蚂蚁，重新开始选择从源节点到目的节点的路径。当某只蚂蚁成功地完成路由选择后，该蚂蚁所选路由各路径上的信息素根据局部更新规则进行更新。,51,平面QoS蚂蚁路由算法具体步骤(3),(5)对所有的蚂蚁重复第(4)步，直到m只蚂蚁都完成了第(4)步。 (6)选择建立了最小费用并满足QoS限制的路由的蚂蚁，然后使用全局更新规则对该蚂蚁所选的路由的各路径上的信息素进行更新。 (7)重复第(4)(6)步，直到获得满意的结果。,52,分级QoS蚂蚁路由算法,当前的大多数大型网络, 包括Internet, 都使用分级选路方式. 它的基本思想是: 路由器被分成多个逻辑组, 每个组又可以包含更小的组. 计算机网络分簇结构特点 网络管理 路由计算 资源利用 Ad hoc网络,53,考虑一个二级网络。每个路由器即为一个level-0节点，由多个level-0节点和level-0链路形成的LAN称为level-1节点，level-1节点之间通过level-1链路连接。