蚁群算法原理与应用1

蚁群算法原理与应用1第一页，共62页。蚁群算法赵林亮计算机应用技术研究所第二页，共62页。参考文献APPEAREDINPROCEEDINGSOFECAL91-EUROPEANCONFERENCEONARTIFICIALLIFE,PARIS,FRANCE,ELSEVIERPUBLISHING,134–142.DistributedOptimizationbyAntColoniesAlbertoColorni,MarcoDorigo,VittorioManiezzoDipartimentodiElettronica,PolitecnicodiMilanoPiazzaLeonardodaVinci32,20133Milano,ItalyIEEETransactionsonSystems,Man,AndCybernetics-PartB:Cybernetics,Vol.26,No.1,Feb1996.29-41AntSystem:OptimizationbyaColonyofCooperatingAgentsMarcoDorigo,Member,IEEE,VittorioManiezzo,andAlbertoColornihttp://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/第三页，共62页。Fig.1.Anexamplewithrealantsa)AntsfollowapathbetweenpointsAandE.b)Anobstacleisinterposed;antscanchoosetogoarounditfollowingoneofthetwodifferentpathswithequalprobability.c)Ontheshorterpathmorepheromoneislaiddown.第四页，共62页。Fig.2.Anexamplewithartificialantsa)Theinitialgraphwithdistances.b)Attimet=0thereisnotrailonthegraphedges;therefore,antschoosewhethertoturnrightorleftwithequalprobability.c)Attimet=1trailisstrongeronshorteredges,whicharetherefore,intheaverage,preferredbyants.第五页，共62页。双桥实验(GossS,1989)Naturwissenschaften76,579-581(1989)Self-organizedShortcutsintheArgentineAntS.Goss,S.Aron,J.L.Deneubourg,andJ.M.PasteelsUnitofBehaviouralEcology,C.P.231,Universit6LibredeBruxelles,B-1050Bruxelles第六页，共62页。Fig.1.AcolonyofIhumilisselectingtheshortbranchesonbothmodulesofthebridgea)onemoduleofthebridgeb)andc):photostaken4and8minafterplacementofthebridge第七页，共62页。双桥实验数学模型假设条件：1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比；2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目 mA+mB=m当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：而选择桥B的概率为：第八页，共62页。参数h和k用以匹配真实实验数据第m+1只蚂蚁首先计算然后生成一个在区间[0,1]上均匀分布的随机数若，则选择桥A，否则选择桥B第九页，共62页。基本蚁群算法的数学模型第十页，共62页。P、NP、NP-C、NP-hard问题P类问题所有可用DTM(Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合。简记为O(p(n))即P={L:存在一个多项式时间DTM程序M，是的L=LM},其中LM表示程序M所识别的语言。若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题Π，即L[Π,e]∈P,则称该判定问题属于P类问题。第十一页，共62页。P、NP、NP-C、NP-hard问题NP类问题(Non-deterministicPolynomial)若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I)),其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I)),则称判定问题A为非多项式确定问题。NP类问题是所有可用NDTM(Non-Deterministicone-tapeTuringMachine)在多项式时间内求解的判定问题Π的集合第十二页，共62页。P、NP、NP-C、NP-hard问题NP-C类问题(NP-Complete)是NP类中最困难的一类问题。有重要实际意义和工程背景TSP(TravelingSalesmanProblem)Symmetric;AsymmetricNP-hard类问题NP-CNP-hardNPPNP-hardNP-C第十三页，共62页。基本蚁群算法模型基本假设蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响；蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。第十四页，共62页。TSP(TravelingSalesmanProblem)有向图有向图D的三元组为(V,E,f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。一个有向图Ｄ可简记为(V,E).第十五页，共62页。TSP(TravelingSalesmanProblem)TSP设C={c1,c2,…,cn}是n个城市的集合，L={lij|ci,cjC}是集合C中的元素（城市）两两连接的集合，dij(i,j=1,1,…,n)是lij的Euclidean距离，即G=(C,L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈，即一条对C={c1,c2,…,cn}中n个元素（城市）访问且只访问一次的最短封闭曲线第十六页，共62页。TSP(TravelingSalesmanProblem)TSP简单形象描述给定n个城市，一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径可分为对称TSP(SymmetricTravelingSalesmanProblem)和非对称TSP(AsymmetricTravelingSalesmanProblem)TSP是NP-C问题n城市规模的TSP，存在(n-1)!/2条不同闭合路径。第十七页，共62页。基本蚁群算法数学模型设bi(t)表示t时刻位于元素i的蚂蚁数目，τij(t)为t时刻路径(i,j)上的信息量，n表示TSP规模，m为蚁群中蚂蚁总数，则是t时刻集合C中元素（城市）两两连接lij上残留信息量的集合，在初始时刻各条路径上的信息量相等，并设τij(0)=const,基本蚁群算法的寻优是通过有向图g=(C,L,Γ)实现的。第十八页，共62页。蚂蚁k(k=1,2,…,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率：第十九页，共62页。其中allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则；ηij(t)为启发函数，ηij(t)=1/dij式中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ηij(t)越大，pijk也就越大。显然，该启发函数表示蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。第二十页，共62页。为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i,j)上的信息量可按如下规则进行调整第二十一页，共62页。式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为[0，1),Δτij(t)表示本次循环中路径(i,j)上的信息素增量，初始时刻Δτij(t)=0,Δτijk(t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。根据信息素更新策略的不同，DorigoM提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于Δτijk(t)求法的不同。第二十二页，共62页。Ant-Cycle模型式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。第二十三页，共62页。Ant-Quantity模型第二十四页，共62页。Ant-Density模型区别：式(5)和式(6)中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而式(4)中利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用式(4)作为蚁群算法的基本模型。第二十五页，共62页。基本蚁群算法的实现以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)蚂蚁数目k←k+1。第二十六页，共62页。基本蚁群算法的实现(5)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市)j并前进，j∈{C-tabuk}。(6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。(7)若集合C中元素(城市)未遍历完，即k<m，则跳转到第(4)步，否则执行第(8)步。(8)根据公式(2)和式(3)更新每条路径上的信息量。(9)若满足结束条件，即如果循环次数Nc≥Ncmax则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。第二十七页，共62页。基本蚁群算法程序流程图输出程序计算结果按式（2）和式（3）进行信息量更新修改禁忌表按式（1）选择下一元素蚂蚁k=1循环次数Nc←Nc+1初始化开始结束K≥m满足结束条件蚂蚁k=k+1NYYN第二十八页，共62页。复杂度分析对于TSP，所有可行的路径共有(n-1)!/2条，以此路径比较为基本操作，则需要(n-1)!/2-1次基本操作才能保证得到绝对最优解。若1MFLOPS，当n=10,需要0.19秒n=20,需要1929年n=30,需要1.4X10e17年时间复杂度空间复杂度第二十九页，共62页。算法标准正确性可用性可读性执行效率健壮性第三十页，共62页。蚁群算法应用赵林亮计算机应用技术研究所第三十一页，共62页。QualityofService,QoSQoS的英文全称为"QualityofService"，中文名为"服务质量"。QoS是网络的一种安全机制,是用来解决网络延迟和阻塞等问题的一种技术。

在正常情况下，如果网络只用于特定的无时间限制的应用系统，并不需要QoS，比如Web应用，或E-mail设置等。但是对关键应用和多媒体应用就十分必要。当网络过载或拥塞时，QoS能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。第三十二页，共62页。QoS网络路由网络路由方面的研究主要通过两个途径来提高服务质量(QoS）：一条途径是节点控制；另一条途径是整网或局部网络控制。节点控制在单节点或单链路完成，主要控制业务对单节点共享资源的占用；整网或局部网络控制通常通过对路由与信令的控制达到对业务流或业务连接在网络中传输的直接控制。因为路由直接关系到网络性能，所以QoS路由成为解决QoS问题的核心技术之一，也是当今网络技术领域内的一个研究热点。第三十三页，共62页。QoS指标：带宽单位时间内能够在线路上传送的数据量，bps(bitpersecond)。时延时延是指一个报文或分组从网络的一端传送到另一端所需要的时间。它包括了发送时延，传播时延，处理时延，他们的总和就是总时延时延抖动变化的时延被称作抖动（Jitter）费用QoS路由的任务在网络中寻找一条路径，使其能满足带宽、时延、时延抖动和费用的限制第三十四页，共62页。WangZ等证明了，如果QoS路由至少包含两个限制时，它是一个NP-C问题。传统的路由算法很难有效地解决NP-C问题，因此一些学者基于蚁群算法提出了许多行之有效的解决方案。第三十五页，共62页。随着Internet的飞速发展，对QoS路由的研究已经引起了众多关注。平面QoS路由所有路由器都在同一级内，以前对QoS路由的研究大多采用平面网络，分级QoS路由基本思想：将路由器分成多个逻辑组，每个组又可包含更小的组。第三十六页，共62页。平面QoS蚂蚁路由算法问题描述将网络模型表示为一个有向图G=(V，E)，其中V是图中所有交换节点组成的集合E是图中所有边的集合每一条边表示相邻两节点间的直达通信路径不失一般性，假定相邻两节点间最多仅有一条边。同时，假定B(l)表示链路l的可用带宽，对于一个路由请求w，路由算法如果能够找到一条具有小费用的路径，同时满足如下4个条件，则此路由请求w就可接受。第三十七页，共62页。(1)在w的路由的每条路径l上，带宽可用限制为(2)在w的路由上，端到端时延限制为(3)在w的路由上，端到端丢失率限制为(4)在目的节点，端到端时延抖动限制为第三十八页，共62页。符号Bw、Dw、Lw、Jw表示QoS要求的带宽、时延、丢失率、抖动限制DN：节点处理延时DL：链路时延V1：w路由的节点集合E1：w路由的链路集合LR：节点丢失率NDV：目的节点d的节点时延变化第三十九页，共62页。算法设计蚁群算法的两个步骤:按照信息素的量选择路径更新路径上的信息素数量假定平面QoS蚂蚁路由算法中有m只蚂蚁，设计如下的三个规则：状态转移规则全局信息素更新规则。局部信息素更新规则。第四十页，共62页。状态转移规则位于节点r的第i只蚂蚁依据下述规则来选择节点s：采用此定义来实现蚂蚁状态的转移可保证寻找优化路径时避免陷入局部最优。第四十一页，共62页。where,qisarandomnumberuniformlydistributedin[0,1],qo

aconstantsatisfying[0,1];pi(r,s)representstheprobabilitywithwhichtheithantpositionedonnoderchoosesthenextnodes,phero(i,r,s)theamountofpheromonedepositedontheedgebetweenthenodesrandscurrentlybytheithtypeofants,Ji(r)thenodesbetweenwhichandthenoderthereisanedgeandbywhichtheith-typeanthasnotpassedduringitschoosingpath.第四十二页，共62页。信息素局部更新规则对于第i只蚂蚁，如果节点r,s是该蚂蚁所选路径上的两个相邻节点，则信息素phero(i,r,s)用下式来调节；否则，不调节。where,0<α0

<1,consisaconstant.Adjustingtheamountofpheromonebytherulecanmakethedesirabilityofedgeschangedynamically.Inthisway,antswillmakeabetteruseofpheromoneinformation;withoutthelocalupdating,allantswouldsearchinanarrowneighborhoodofthebestpreviouspath.第四十三页，共62页。信息素全局更新规则对于第i只蚂蚁，如果节点r,s是该蚂蚁所选路径上的两个相邻节点，则信息素phero(i,r,s)按公式1调节,否则按公式2调节。where,0<α1

<1.Thepurposeoftheruleistosearchthegloballybestresolution.第四十四页，共62页。为定义限制函数F，引入几个符号定义：第四十五页，共62页。限制函数F的定义第四十六页，共62页。信息素的全局更新规则式中，N表示网络的节点数目；A、B和C分别表示带宽可用限制、端到端时延限制和端到端丢失率限制，且为正实数；F1表示费用限制；F2表示QoS限制。通过上述定义可见，如果所选路由的总费用最小，同时QoS限制也满足要求，那么最优蚂蚁所选路由的各链路上的信息素应该增加更多。第四十七页，共62页。算法设计为提高算法的收敛性能，做以下两点改进：在蚁群算法迭代中不考虑时延抖动，而是在算法执行前进行处理；通过删除带宽小于需求带宽的链路，把网络滤成一个新的简单网络，因此在F函数中设A=0第四十八页，共62页。平面QoS蚂蚁路由算法具体步骤(1)如果NDV(d)>Jw，那么退出；否则，跳转到第(2)步。(2)删除带宽小于需求带宽的链路，把网络滤成一个新的简单网络。(3)初始化网络拓扑中各边的相应信息素。第四十九页，共62页。平面QoS蚂蚁路由算法具体步骤(2)(4)从蚁巢开始放出m只蚂蚁去寻找食物源，在第一个时间单位，每只蚂蚁从节点集合中随机地选择一个节点，然后各蚂蚁通过重复应用状态转移规则来选择各自的路径。在选路过程中，如果蚂蚁在到达目的节点前死亡，另外一只和死亡的蚂蚁同类的蚂蚁重新放出来代替死亡的蚂蚁，重新开始选择从源节点到目的节点的路径。当某只蚂蚁成功地完成路由选择后，该蚂蚁所选路由各路径上的信息素根据局部更新规则进行更新。第五十页，共62页。平面QoS蚂蚁路由算法具体步骤(3)(5)对所有的蚂蚁重复第(4)步，直到m只蚂蚁都完成了第(4)步。(6)选择建立了最小费用并满足QoS限制的路由的蚂蚁，然后使用全局更新规则对该蚂蚁所选的路由的各路径上的信息素进行更新。(7)重复第(4)～(6)步，直到获得满意的结果。第五十一页，共62页。分级QoS蚂蚁路由算法当前的大多数大型网络,包括Internet,都使用分级选路方式.它的基本思想是:路由器被分成多个逻辑组,每个组又可以包含更小的组.计算机网络分簇结构特点网络管理路由计算资源利用Adhoc网络第五十二页，共62页。考虑一个二级网络。每个路由器即为一个level-0节点，由多个level-0节点和level-0链路形成的LAN称为level-1节点，level-1节点之间通过level-1链路连接。在大多数应用中，时延要求是最为重要的，为了方便起见，这里在研究QoS路由时仅考虑时延限制。第五十三页，共62页。第五十四页，共62页。算法构造(1)