蚁群算法详细解PPT课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,蚁群算法及其应用,蚂蚁觅食行为与觅食策略,蚂蚁系统,蚁群系统的原型,改进的蚁群优化算法,蚁群优化算法的仿真研究,蚁群算法的应用,对,QoS,组播路由问题求解,1,.,2,.,3,.,1.1,蚁群优化算法概述,1.1.1,起源,1.1.2,应用领域,1.1.3,研究背景,1.1.4,研究现状,1.1.5,应用现状,4,.,1.1.1,蚁群优化算法起源,20,世纪,50,年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。,20,世纪,90,年代意大利学者,M,Dorigo,，,V,Maniezzo,，,A,Colorni,等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法,蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解,TSP,问题、分配问题、,job-shop,调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法,5,.,1.1.2,蚁群优化算法应用领域,这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信,QoS,管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径,。,6,.,2.1.3,蚁群优化算法研究背景,1/3,群智能理论研究领域有两种主要的算法：蚁群算法,(Ant Colony Optimization,ACO),和微粒群算法（,Particle Swarm Optimization,PSO,）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。,7,.,1.1.3,蚁群优化算法研究背景,2/3,与大多数基于梯度的应用优化算法不同，群智能依靠的是,概率搜索算法。虽然概率搜索算法通常要采用较多的评价,函数，但是与梯度方法及传统的演化算法相比，其优点还,是显著的，主要表现在以下几个方面：,1,无集中控制约束，不会因个别个体的故障影响整个问题,的求解，确保了系统具备更强的鲁棒性,2,以非直接的信息交流方式确保了系统的扩展性,3,并行分布式算法模型，可充分利用多处理器,4,对问题定义的连续性无特殊要求,5,算法实现简单,8,.,1.1.3,蚁群优化算法研究背景,3/3,群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对,CPU,和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。,9,.,1.1.4,蚁群优化算法研究现状,1/7,90,年代,Dorigo,最早提出了蚁群优化算法,-,蚂蚁系统（,Ant System,AS,）并将其应用于解决计算机算法学中经典的旅行商问题（,TSP,）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在,TSP,以及许多实际优化问题求解中进一步得到了验证。这些,AS,改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的,ACO,是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。,10,.,1.1.4,蚁群优化算法研究现状,2/7,最初提出的,AS,有三种版本：,Ant-density,、,Ant-quantity,和,Ant-cycle,。在,Ant-density,和,Ant-quantity,中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在,Ant-cycle,中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于,75,城市的,TSP,中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，,AS,的解题能力大幅度下降。,因此，其后的,ACO,研究工作主要都集中于,AS,性能的改进方面。较早的一种改进方法是精英策略,(Elitist Strategy),，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为,Tgb,(,全局最优行程,),，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为,“,精英,”,，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。,11,.,1.1.4,蚁群优化算法研究现状,3/7,为了进一步克服,AS,中暴露出的问题，提出了蚁群系统,(Ant Colony System,ACS),。该系统的提出是以,Ant-Q,算法为基础的。,Ant-Q,将蚂蚁算法和一种增强型学习算法,Q-learning,有机的结合了起来。,ACS,与,AS,之间存在三方面的主要差异：首先，,ACS,采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。其中，,01,是信息素挥发参数，是从寻路开始到当前为止全局最优的路径长度。,12,.,1.1.4,蚁群优化算法研究现状,4/7,再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。,13,.,1.1.4,蚁群优化算法研究现状,5/7,在对,AS,进行直接完善的方法中，,MAX-MIN Ant System,是一个典型代表。该算法修改了,AS,的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞，路径上的信息素浓度被限制在,MAX,，,MIN,范围内，另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力。,14,.,1.1.4,蚁群优化算法研究现状,6/7,另一种对,AS,改进的算法是,Rank-based Version AS,。与,“,精英策略,”,相似，在此算法中总是更新更好进程上的信息素，选择的标准是其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，为每次迭代后放置信息素的蚂蚁总数。,15,.,1.1.4,蚁群优化算法研究现状,7/7,这种算法求解,TSP,的能力与,AS,、精英策略,AS,、遗传算法和模拟退火算法进行了比较。在大型,TSP,问题中（最多包含,132,座城市），基于,AS,的算法都显示出了优于,GA,和,SA,的特性。而且在,Rank-based AS,和精英策略,AS,均优于基本,AS,的同时，前者还获得了比精英策略,AS,更好的解。,16,.,1.1.5,蚁群优化算法应用现状,1,/5,随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。,蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。,17,.,1.1.5,蚁群优化算法应用现状,2,/5,蚁群算法在电信路由优化中已取得了一定的应用成果。,HP,公司和英国电信公司在,90,年代中后期都开展了这方面的研究，设计了蚁群路由算法（,Ant Colony Routing,ACR,）。,每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，,ACR,算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与,ACO,的算法本质和特性非常相似。,18,.,1.1.5,蚁群优化算法应用现状,3,/5,基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。,Lumer,和,Faieta,将,Deneubourg,提出将蚁巢分类模型应用于数据聚类分析。其基本思想是将待聚类数据随机地散布到一个二维平面内，然后将虚拟蚂蚁分布到这个空间内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置，然后继续移动，重复上述数据搬运过程。按照这样的方法可实现对相似数据的聚类。,19,.,1.1.5,蚁群优化算法应用现状,4,/5,ACO,还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（,QAP,）、机器人路径规划、作业流程规划、图着色（,Graph Coloring,）等问题。,经过多年的发展，,ACO,已成为能够有效解决实际二次规划问题的几种重要算法之一。,AS,在作业流程计划（,Job-shop Scheduling,）问题中的应用实例已经出现，这说明了,AS,在此领域的应用潜力。利用,MAX-MIN AS,解决,PAQ,也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理,PAQ,比较早的,SA,算法更好，且与禁忌搜索算法性能相当。利用,ACO,实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了,ACO,的工程应用价值。,20,.,1.1.5,蚁群优化算法应用现状,5/5,许多研究者将,ACO,用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、,Bayesian networks,的训练和集合覆盖等应用优化问题。,Costa,和,Herz,还提出了一种,AS,在规划问题方面的扩展应用,图着色问题，并取得了可与其他启发式算法相比的效果。,21,.,1.2,蚁群优化算法概念,1.2.1,蚁群算法原理,1.2.2,简化的蚂蚁寻食过程,1.2.3,自然蚁群与人工蚁群算法,1.2.4,蚁群算法与,TSP,问题,1.2.5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,1.2.6,一般蚁群算法的框架,22,.,1.2.1,蚁群算法原理,蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素,(pheromone),的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低,.,当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。,23,.,1.2.2,简化的蚂蚁寻食过程,1/3,蚂蚁从,A,点出发，速度相同，食物在,D,点，可能随机选择路线,ABD,或,ACD,。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过,9,个时间单位时的情形：走,ABD,的蚂蚁到达终点，而走,ACD,的蚂蚁刚好走到,C,点，为一半路程。,24,.,1.2.2,简化的蚂蚁寻食过程,2/3,本图为从开始算起，经过,18,个时间单位时的情形：走,ABD,的蚂蚁到达终点后得到食物又返回了起点,A,，而走,ACD,的蚂蚁刚好走到,D,点。,25,.,1.2.2,简化的蚂蚁寻食过程,3/3,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过,36,个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从,D,点取得了食物，此时,ABD,的路线往返了,2,趟，每一处的信息素为,4,个单位，而,ACD,的路线往返了一趟，每一处的信息素为,2,个单位，其比值为,2,：,1,。,寻找食物的过程继续进行，则按信息素的指导，蚁群在,ABD,路线上增派一只蚂蚁（共,2,只），而,ACD,路线上仍然为一只蚂蚁。再经过,36,个时间单位后，两条线路上的信息素单位积累为,12,和,4,，比值为,3,：,1,。,若按以上规则继续，蚁群在,ABD,路线上再增派一只蚂蚁（共,3,只），而,ACD,路线上仍然为一只蚂蚁。再经过,36,个时间单位后，两条线路上的信息素单位积累为,24,和,6,，比值为,4,：,1,。,若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃,ACD,路线，而都选择,ABD,路线。这也就是前面所提到的正反馈效应。,26,.,1.2.3,自然蚁群与人工蚁群算法,基于以上蚁群寻找食物时的最优路径选择问题，可以构造,人工蚁群，来解决最优化问题，如,TSP,问题。,人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的,相似之处在于都是优先选择信息素浓度大的路径。较短路径的,信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的,优化结果。,两者的区别在于人工蚁群有一定的记忆能力，能够记忆已,经访问过的节点。同时，人工蚁群再选择下一条路径的时候是,按一定算法规律有意识地寻找最短路径，而不是盲目的。例如,在,TSP,问题中，可以预先知道当前城市到下一个目的地的距离。,27,.,1.2.4,蚁群算法与,TSP,问题,1/3,TSP,问题表示为一个,N,个城市的有向图,G=,（,N,，,A,），,其中,城市之间距离,目标函数为 ，,其中 为城市,1,2,，,n,的,一个排列，。,28,.,1.2.4,蚁群算法与,TSP,问题,2/3,TSP,问题的人工蚁群算法中，假设,m,只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：,1,信息素值 也称信息素痕迹。,2,可见度，即先验值。,信息素的更新方式有,2,种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值,“,好,”,(,有蚂蚁走过,),的边增加信息素。,29,.,1.2.4,蚁群算法与,TSP,问题,3/3,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。,蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,30,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,1/12,初始的蚁群算法是基于图的蚁群算法，,graph-based ant system,简称为,GBAS,，是由,Gutjahr W J,在,2000,年的,Future Generation Computing Systems,提出的，课本的参考文献,2,。算法步骤如下：,STEP 0,对,n,个城市的,TSP,问题，,城市间的距离矩阵为 ，给,TSP,图中的每一条弧 赋信息素初值 ，假设,m,只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。,31,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,2/12,STEP 1,（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁,s,从起点 出发，用 表示蚂蚁,s,行走的城市集合，初始 为空集，。,STEP 2,(,内循环,),按蚂蚁 的顺序分别计算。当蚂蚁在城市,i,，若,完成第,s,只蚂蚁的计算。否则，若,，则以概率，,到达,j,，；若,则到达重复,STEP 2,。,32,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,3/12,STRP 3,对 ，若 ，按 中城市的顺序计算,路径程度；若 ，路径长度置为一个无穷大值（即不可,达）。比较,m,只蚂蚁中的路径长度，记走最短路径的蚂蚁为,t,。,若 ，则 。用如下公式对,W,路径,上的信息素痕迹加强，对其他路径上的信息素进行挥发。,得到新的 ，重复步骤,STEP 1,。,33,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,4/12,在,STEP 3,中，挥发因子 对于一个固定的 ，满足,并且,经过,k,次挥发，非最优路径的信息素逐渐减少至消失。,34,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,5/12,以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市,i,到城市,j,的转移。,算法中包括信息素更新的过程,1,信息素挥发（,evaporation,）信息素痕迹的挥发过程是每个连接上的信,息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个,挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区,域的扩展。,2,信息素增强（,reinforcement,）增强过程是蚁群优化算法中可选的部分，,称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂,蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（,m,只蚂蚁）,中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，,挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的,信息素更新称为离线的信息素更新。,在,STEP 3,中，蚁群永远记忆到目前为止的最优解。,35,.,图的蚁群系统（,GBAS,）,6/12,可以验证，下式满足：,即 是一个随机矩阵。,四个城市的非对称,TSP,问题，距离矩阵和城市图示如下：,36,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,7/12,假设共,4,只蚂蚁，所有蚂蚁都从城市,A,出发，挥发因子,。此时，观察,GBAS,的计算过程。矩阵,共有,12,条弧，初始信息素记忆矩阵为：,37,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,8/12,执行,GBAS,算法的步骤,2,，假设蚂蚁的行走路线分别为：,当前最优解为，这个解是截止到当前的最优解，碰巧是实际,最优解,38,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,9/12,按算法步骤,3,的信息素更新规则，得到更新矩阵,这是第一次外循环结束的状态。,39,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,10/12,重复外循环，由于上一次得到的,W2,已经是全局最优解，因此按算法步骤,3,的信息素更新规则，无论蚂蚁如何行走，都只是对,W2,路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵,这是第一次外循环结束的状态。,40,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,11/12,重复外循环，由于,W2,全局最优解，,GBAS,只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：,41,.,1.2,.,5,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,12/12,蚂蚁以一定的概率从城市,i,到城市,j,进行转移，信息素的,更新在,STEP 3,完成，并随,K,而变化。假设第,K,次外循环后得,到信息素矩阵 ，得到当前最优解 。,第,K,次循环前的信息素和最优解为 ，经过,第,K,次外循环后，得到 。由于蚂蚁的一步转移,概率是随机的，从 到,也是随机的，是一个马尔可夫过程。,42,.,1.2.6,一般蚁群算法的框架,一般蚁群算法的框架和,GBAS,基本相同，有三个组成部分：,蚁群的活动；,信息素的挥发；,信息素的增强；,主要体现在前面的算法中步骤,2,和步骤,3,中的转移概率公式和信息素更新公式。,43,.,1.3,蚁群优化算法,算法模型和收敛性分析,1.3.0,马氏过程的收敛定义,1.3.1 GBAS,算法的收敛性分析,1.3.2,其他算法及收敛性分析,44,.,1.3.0,马氏过程的收敛定义,蚁群优化算法的每步迭代对应随机变量,其中 为信息素痕迹；为,n,城市的一个排列，最多有 个状态。第,s,只蚂蚁在第,k,轮转移只由 决定，这个蚂蚁行走的路径和 一起，共同决定了 ，再通过信息素的更新原则可以进一步得到 。的变化仅由 决定，而与先前的状态无关，这是一个典型的马尔可夫过程。,定义,：若一个马尔可夫过程 ，对任意给定的,满足,则称马尔可夫过程 依概率,1,收敛到 。,45,.,1.3.1 GBAS,算法的收敛性分析,1/8,定理,满足,指定条件,的马尔可夫过程,依概率,1,收敛到,其中 为一条最优路径,定义为,:,证明分析,:,蚁群算法中,一但达到全局最优,由 只记录第一个最优解,.,证明分三部分,:,证明以概率,1,达到一个最优路径,证明,(1),上式成立,证明以概率,1,收敛到一个最优路径,46,.,1.3.1,GBAS,算法的收敛性分析,2/8,证明以概率,1,到达一个最优路径,对于最优路径,令 为蚁群中的一个蚂蚁在第,k,次外循环后第一次走到最优路径 的事件,.,表示仅第,k,次外循环没有走到 的事件,但前,k-1,次可能走到过这条最优路径,.,永远不会被走到的事件为,其概率为,:,47,.,1.3.1,GBAS,算法的收敛性分析,3/8,任意给定的固定弧,(i,j),在第,k,次循环后,其信息素值的下界可以计算出,.,48,.,1.3.1,GBAS,算法的收敛性分析,4/8,令,任何一个固定节点最多有,(n-1),后续节点,并且其弧上的信息素值都小于,1,或者等于,1.,得,:,蚁群中的一只蚂蚁在第 次循环走到路径,W*,的概率为,一个蚁群中至少有一只蚂蚁，因此这是一个蚁群到达最优路径,的一个下界,.,上式右侧与,k,无关,49,.,1.3.1,GBAS,算法的收敛性分析,5/8,则,取对数有,从而得到,50,.,1.3.1,GBAS,算法的收敛性分析,6/8,证明右式成立,随机过程 以概率,1,达到一条最优路径,.,当某条最优路径,Z,在第,k,次循环被首次走到后,在第,k+1,轮循环按信息素的更新原则,可以用归纳法证明,对于任意,51,.,1.3.1,GBAS,算法的收敛性分析,7/8,由于级数 是发散的,可知,.,因此,当,时,在第,K,轮迭代之后,该弧永远不再被加强,从而有,也既 弧上的信息素之和将趋于,0.,对于信息素的更新公式,(2),可以归纳证明,(6),式的第二项与,(i,j),弧无关,结合,(7),式可得,的极限存在,且所有的极限之和为,1.,对于所有的,52,.,1.3.1,GBAS,算法的收敛性分析,8/8,结合前两部分讨论,当,Xn,首次到达最优路径后,对于任何最优路径上的弧,(1),式的转移概率,即 依概率,1,收敛到,.,53,.,1.3.2,其他算法及收敛性分析,1/4,MAX-MIN,蚁群优化算法指定挥发系数不随时间变化,这是和,GBAS,算法不同的一点,改变了信息素挥发和增强的规则,(,9,式,),，同时给出一个下界 控制信息素的挥发,.,定理,在,MAX-MIN,算法中,54,.,1.3.2,其他算法及收敛性分析,2/4,55,.,1.3.2,其他算法及收敛性分析,3/4,56,.,1.3.2,其他算法及收敛性分析,4/4,57,.,1.4,蚁群优化算法,技术问题,1.4.1,解的表达形式与算法的实现,1.4.2,每一节点的记忆信息和系数的确定,1.4.3,蚁群的规模和停止规则,1.4.4,信息素的更改,58,.,1.4.1,解的表达形式与算法的实现,1/4-,解的表达形式,解的表达形式 基于,TSP,问题的蚁群优化算法，其解的形式是所有城市的一个排列（闭圈，这种情况下谁在第一并不重要），信息素痕迹按每个弧记录。而对于一般以顺序作为解的优化问题，谁在第一是很重要的。蚁群算法在解决这类问题时，只需要建立一个虚拟的始终点，就可以把,TSP,问题的解法推广，用于诸多的优化问题。,诸如车间作业及下料等问题，他们的共同特点是解以一个顺序表示。,TSP,问题寻找的是最短回路，而一般优化问题中，,STEP 3,中的判断条件 需要根据实际问题进行修改。,59,.,1.4.1,解的表达形式与算法的实现,2/4-,算法的实现,例：,0-1,背包问题的解顺序表达形式与算法实现。设有一个容积为,b,的背包，,n,个尺寸分别为 ，价值分别为,的物品，,0-1,背包问题的数学模型为：,假设其解的顺序表达形式为，其中,为的一个排列。,60,.,1.4.1,解的表达形式与算法的实现,3/4-,算法的实现,建立有向图 ，其中,A,中共有 条弧。初始信息素痕迹定义为 。,设第,s,只蚂蚁第,k,步所走的路线为 ，,表示蚂蚁从,0,点出发，顺序到达 。第 步按,TSP,算法,的转移概率公式行走选择 。若 则,，否则，此蚂蚁不再继续行走，退回起点。,61,.,1.4.1,解的表达形式与算法的实现,4/4-,算法的实现,对蚁群重复以上过程，比较,m,只蚂蚁的装包值,并记忆具有最大装包值的蚂蚁为,t,。把,GBAS,算法中步骤,3,中的,改为 ，若满足此条件则替换当前最好解为 ，,对,W,上的弧进行信息素的加强，其他弧进行信息素的挥发。,算法中记录了三个信息：信息素痕迹 ；行走路线,；和问题的约束条件，,以确定是否将 加入。,62,.,1.4.2,每一节点的记忆信息和系数的确定,-,需要记忆的信息,1/3,算法中需要记忆的信息有三部分。,第一部分信息是存在每个节点的路由表数据结构 ，由此决定的的转移概率为,其中,T,可以看成节点,i,的邻域。,63,.,1.4.2,每一节点的记忆信息和系数的确定,-,需要记忆的信息,2/3,第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息，这一部分主要由算法的中的 记忆，表示蚂蚁已经行走过的节点。,第三部分为问题的约束条件。在,GBAS,中，,T,集合表示满足约束条件的候选集，在背包问题的蚁群算法中由判别条件,，来实现记,忆功能。,64,.,1.4.2,每一节点的记忆信息和系数的确定,-,系数的确定,3/3,残留信息的相对重要程度 和预见值的相对重要程度 体现了相关信息痕迹和预见度对蚂蚁决策的相对影响。,Dorigo,在求解,TSP,问题时，推荐参数的最佳设置为：,。,65,.,1.4.3,蚁群的规模和停止规则,一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过,TSP,图中节点的个数。,二、终止条件,1,给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；,2,当前最优解连续,K,次相同而停止，其中,K,是一个给定的整数，表示算法已经收敛，不再需要继续；,3,目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。,66,.,1.4.4,信息素的更改,1/6,信息素的更新分为离线和在线两种方式。离线方式（同步更新方式）的主要思想是在若干只蚂蚁完成,n,个城市的访问后，统一对残留信息进行更新处理。,信息素的在线更新（异步更新方式）即蚂蚁每行走一步，立即回溯并且更新行走路径上的信息素。,67,.,1.4.4,信息素的更改,2/6,离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新。,蚁群离线更新方式是在蚁群中的,m,只蚂蚁全部完成,n,城市的访问（第,k-1,次蚁群循环）后，统一对残留信息进行更新处理。,其中，为第,k-1,次循环后的的信息素的痕迹值。,单蚂蚁离线更新是在第,s,只蚂蚁完成对所有,n,个城市的访问后，进行路径回溯，更新行走路径上的信息素，同时释放分配给它的资源。更新公式为,第,s+1,只蚂蚁根据 重新计算路由表。,68,.,1.4.4,信息素的更改,3/6,TSP,问题中，蚁群优化算法根据信息素痕迹更新方式不同可以分为不,同的算法，采用离线方式，并且,时，其中,W,为,t,循环中,m,只蚂蚁所行走的最佳路线或第,t,只蚂蚁所行走,的一条路径。,Q,为一个常数，该算法名为蚁环算法（,ant-cycle,algotithm,）,特点是行走的路径越短对应保存的信息素的值就越大。,69,.,1.4.4,信息素的更改,4/6,GBAS,算法是典型的离线信息素更新方式。该算法中，蚁群中蚂蚁的先后出行顺序没有相关性，但是每次循环需要记忆,m,只蚂蚁的行走路径，以进行比较选择最优路径。相对而言，单蚂蚁离线更新方式记忆信息少，只需要记忆第,s,只蚂蚁的路径，并通过信息素更新后，释放该蚂蚁的所有记录信息。实际上这种方式等价于蚁群离线方式中只有一只蚂蚁。,70,.,1.4.4,信息素的更改,5/6,与单蚂蚁离线更新方式相比，信息量记忆更小的是信息素在线更新方式，即蚂蚁每走一步，马上回溯并且更新刚刚走过的路径上的信息素，其规则为,其中，,k,为蚂蚁行走的第,k,步。,71,.,1.4.4,信息素的更改,6/6,蚁量算法（,ant-quantity algorithm,）的信息素更新,为,Q,为常量，表示,i,到,j,的距离，这样信息,浓度会随城市距离的减小而加大。,蚁密算法（,ant-density algorithm,）信息素更新为 。,以上三种算法中，蚁环算法效果最好，因为他用的是全局信息，而其余两种算法用的是局部信息。蚁环离线更新方法很好地保证了残留信息不至于无限积累，非最优路径会逐渐随时间推移被忘记。,72,.,1.5,应用,1/5,1.5.1,光网络的智能管理,分布式动态选路及波长分配,(RWA,Routing and Wavelength Assignment),是指在实时业务情况下光通路的路由选择和波长分配的优化问题,是实现自动交换光网络,(ASON,Automatically Switched Optical Network),的关键技术之一。研究,RWA,问题的目的是尽可能减少所需要的波长数和降低光路连接请求的阻塞率。由于,RWA,问题是,NP-C,问题,文献中大多将,RWA,问题拆分成路由和波长分配两个子问题分别加以解决。但是,由于,RWA,问题本身是一个不可分割的整体,把,RWA,分开考虑必然造成难以得到全局最优解的后果。,73,.,1.5,应用,2/5,同时,分布式的计算方式则克服了传统集中式算法可扩展性差的缺点,更适应现代频繁变化的大型光网络。因此,近年来国内外对,RWA,并行的分布式算法表现出极大的兴趣,此类算法建立的基础是分层图模型,。,用蚁群算法在分层图模型的基础上求解动态,RWA,问题。基于蚂蚁,“,信息素表,”,来完成局部信息的刷新计算。以分布的形式做少量的计算来刷新全局路由选择信息。,参考文献：,基于蚁群系统的分布式,RWA,算法研究,孙海金,朱娜,周乃富,2005,年第,2,期 光通信研究,74,.,1.5,应用,3/5,1.5.2,蚁群算法用于计算机网络路由,参考文献：计算机网络中的组播路由算法 谢银祥,75,.,1.5,应用,4/5,76,.,1.5,应用,5/5,2.5.3,蚁群算法用于聚类（蚁群蚁卵分类）,思想：把待聚类的数据随机散布在一个平面上，放置若干只虚拟蚂蚁使其在平面上随机运动。当一只蚂蚁遇到一个数据时即拾起并继续行走，在行走过程中，如果遇到附近的数据与背负的数据相似性高于设置的标准时则将数据放置在该位置，继续移动。重复以上过程即可实现数据聚类。,77,.,1.6,蚁群优化算法,参考书,1,智能蚁群算法及应用 吴启迪 上海科技出版社从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。主要内容有蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问题求解模式、算法的典型应用及拓展应用。,78,.,1.6,蚁群优化算法,参考书,2,蚁群算法及其应用 李士勇 哈工大出版社,国内首部蚁群算法的专著，系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的应用。本书可供人工智能、计算机科学、信息科学、控制工程、管理工程、交通工程、网络工程、智能优化算法及智能自动化等领域的广大师生和科技人员学习及参考。,79,.,1.6,蚁群优化算法,参考文献,题目：群智能理论及应用,电子学报,2003,年,S1,期,【,作者,】,彭喜元 彭宇 戴毓丰,【,关键词,】,群智能 微粒群算法 蚁群算法 优化算法,80,.,That,s all.Thanks.,Thanks,81,.,