蚁群算法最新课件.ppt

第五章第五章 蚁群算法蚁群算法智能优化方法智能优化方法信息系统与管理学院 1蚁群算法 最新蚁群优化算法1.蚁群优化算法概述2.蚁群优化算法概念3.算法模型和收敛性分析4.算法实现的技术问题5.应用2蚁群算法 最新5.1 蚁群优化算法概述5.1.1 起源5.1.2 应用领域5.1.3 研究背景5.1.5 应用现状3蚁群算法 最新5.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等 20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法—— 蚁群算法 该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势4蚁群算法 最新5.1.2 蚁群优化算法应用领域 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。

目前其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径5蚁群算法 最新5.1.3 蚁群优化算法研究背景 1/3群体智能理论研究领域有两种主要的算法：u蚁群算法(Ant Colony Optimization, ACO)–对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题u粒子群算法（Particle Swarm Optimization, PSO）–起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具 6蚁群算法 最新5.1.3 蚁群优化算法研究背景 2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法虽然概率搜索算法通常要采用较多的评价函数，其优点主要表现在：1.无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性 2.以非直接的信息交流方式确保了系统的扩展性 3.并行分布式算法模型，可充分利用多处理器 4.对问题定义的连续性无特殊要求 5.算法实现简单 7蚁群算法 最新5.1.3 蚁群优化算法研究背景 3/3群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。

而且，这种方法只需目标函数的输出值，而无需其梯度信息已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的 8蚁群算法 最新5.1.4 蚁群优化算法应用现状 1/5随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中比较典型的应用研究包括：u网络路由优化u数据挖掘以u一些经典的组合优化问题9蚁群算法 最新5.1.4 蚁群优化算法应用现状 2/5蚁群算法在电信路由优化中已取得了一定的应用成果HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（Ant Colony Routing, ACR）。

每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息这样，在当前最优路由出现拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似10蚁群算法 最新5.1.4 蚁群优化算法应用现状 3/5基于群智能的聚类算法起源于对蚁群蚁卵的分类研究Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据聚类分析其基本思想是将待聚类数据随机地散布到一个二维平面内，然后将虚拟蚂蚁分布到这个空间内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置，然后继续移动，重复上述数据搬运过程按照这样的方法可实现对相似数据的聚类11蚁群算法 最新5.1.4 蚁群优化算法应用现状 4/5ACO还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（QAP）、机器人路径规划、作业流程规划、图着色（Graph Coloring）等问题。

经过多年的发展，ACO已成为能够有效解决实际二次规划问题的几种重要算法之一AS在作业流程计划（Job-shop Scheduling）问题中的应用实例已经出现，这说明了AS在此领域的应用潜力利用MAX-MIN AS解决PAQ也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好，且与禁忌搜索算法性能相当利用ACO实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值12蚁群算法 最新5.1.4 蚁群优化算法应用现状 5/5许多研究者将ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesian networks的训练和集合覆盖等应用优化问题Costa和Herz还提出了一种AS在规划问题方面的扩展应用——图着色问题，并取得了可与其他启发式算法相比的效果13蚁群算法 最新5.2 蚁群优化算法概念5.2.1 蚁群算法原理5.2.2 简化的蚂蚁寻食过程5.2.3 自然蚁群与人工蚁群算法5.2.4 蚁群算法与TSP问题5.2.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS）5.2.6 一般蚁群算法的框架14蚁群算法 最新5.2.1 蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。

蚂蚁能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，蚂蚁在运动过程中能够感知以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大蚂蚁搜寻食物的具体过程：当碰到一个还没有走过的路口时．就随机地挑选一条路径前行与此同时释放出与路径长度有关的信息素路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大这样形成一个正反馈最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减最终整个蚁群会找出最优路径15蚁群算法 最新5.2.2 简化的蚂蚁寻食过程 1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程AD16蚁群算法 最新5.2.2 简化的蚂蚁寻食过程 2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。

17蚁群算法 最新5.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：118蚁群算法 最新5.2.3 自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题人工蚁群中把具有简单功能的工作单元看作蚂蚁二者的相似之处在于都是优先选择信息素浓度大的路径较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。

同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离19蚁群算法 最新5.2.4 蚁群算法与TSP问题 1/3TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为 ，其中 为城市1,2，…,n的一个排列， 20蚁群算法 最新5.2.4 蚁群算法与TSP问题 2/3TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹2 可见度，即先验值信息素的更新方式：1 挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；2 增强，给评价值“好”(有蚂蚁走过)的边增加信息素21蚁群算法 最新5.5.4 蚁群算法与TSP问题 3/3蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。

蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中22蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 1/12 初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，课本的参考文献2算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为 ，给TSP图中的每一条弧 赋信息素初值 ，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发 当前最好解是23蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 2/12STEP 1 （外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解否则使蚂蚁s从起点 出发，用 表示蚂蚁s已经过的城市集合，初始 为空， STEP 2 (内循环) 按蚂蚁 的顺序分别计算。

当蚂蚁在城市i，若 完成第s只蚂蚁的计算否则，若，则以概率，到达j， ；若则到达重复STEP 224蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 3/12STRP 3 对 ， 若 按 中城市的顺序计算路径程度；若 ，路径长度置为一个无穷大值（即不可达）比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t若 ，则 用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发 得到新的 ，重复步骤STEP 125蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 4/12在STEP 3 中，挥发因子 对于一个固定的 ，满足 并且 经过k次挥发，非最优路径的信息素逐渐减少至消失26蚁群算法 最新5.5.5初始的蚁群优化算法—基于图的蚁群系统（GBAS） 5/12 以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市到城市j的转移。

的转移 算法中包括信息素更新的过程算法中包括信息素更新的过程 1 信息素挥发（信息素挥发（evaporation）） 信息素痕迹的挥发过程是每个连接上的信信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展域的扩展 2 信息素增强（信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有更新方式）这种方式可以实现由单个蚂称为离线更新方式（还有更新方式）这种方式可以实现由单个蚂蚁无法实现的集中行动也就是说，增强过程体现在观察蚁群（蚁无法实现的集中行动也就是说，增强过程体现在观察蚁群（m只蚂蚁）只蚂蚁）中每只蚂蚁所找到的路径，并选择中每只蚂蚁所找到的路径，并选择其中最优路径上的弧其中最优路径上的弧进行信息素的增强，进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。

这种增强过程中进行的挥发过程是所有弧都进行的，不于蚂蚁数量相关这种增强过程中进行的信息素更新称为离线的信息素更新信息素更新称为离线的信息素更新 在在STEP 3中，蚁群永远记忆到目前为止的最优解中，蚁群永远记忆到目前为止的最优解27蚁群算法 最新5.5.5初始的蚁群优化算法—基于图的蚁群系统（GBAS） 6/12可以验证，下式满足：可以验证，下式满足：即即 是一个随机矩阵是一个随机矩阵四个城市的非对称四个城市的非对称TSP问题，距离矩阵和城市图示如下：问题，距离矩阵和城市图示如下：28蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 7/12假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 此时，观察GBAS的计算过程 矩阵共有12条弧，初始信息素记忆矩阵为：29蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 8/12执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为3.5，这个解是截止到当前的最优解，碰巧是实际最优解30蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 9/12按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。

31蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 10/12重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发得到更新矩阵这是第一次外循环结束的状态32蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 11/12重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发第三次外循环后得到的信息素矩阵为：33蚁群算法 最新5.5.5 初始的蚁群优化算法—基于图的蚁群系统（GBAS） 12/12 蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化假设第K次外循环后得到信息素矩阵 ，得到当前最优解 第K次循环前的信息素和最优解为 ，经过第K次外循环后，得到 。

由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程34蚁群算法 最新5.2.6 一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同，有三个组成部分：n蚁群的活动n信息素的挥发n信息素的增强主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式35蚁群算法 最新5.3 蚁群优化算法—算法模型和收敛性分析5.3.0 马氏过程的收敛定义5.3.1 GBAS算法的收敛性分析5.3.2 其他算法及收敛性分析36蚁群算法 最新5.3.0 马氏过程的收敛定义蚁群优化算法的每步迭代对应随机变量其中 为信息素痕迹； 为n城市的一个排列，最多有 个状态第s只蚂蚁在第k轮转移只由 决定，这个蚂蚁行走的路径和 一起，共同决定了 ，再通过信息素的更新原则可以进一步得到 的变化仅由 决定，而与先前的状态无关，这是一个典型的马尔可夫过程 定义定义：若一个马尔可夫过程 ，对任意给定的 满足 则称马尔可夫过程 依概率1收敛到 。

37蚁群算法 最新5.3.1 GBAS算法的收敛性分析 1/8 定理 满足指定条件的马尔可夫过程 依概率1收敛到 ,其中 为一条最优路径, 定义为: 证明分析: 蚁群算法中,一但达到全局最优,由 只记录第一个最优解.证明分三部分:u 证明以概率1达到一个最优路径u 证明(1)上式成立u 证明以概率1收敛到一个最优路径38蚁群算法 最新5.3.1 GBAS算法的收敛性分析 2/8 证明以概率1到达一个最优路径 对于最优路径 ,令 为蚁群中的一个蚂蚁在第k次外循环后第一次走到最优路径 的事件. 表示仅第k次外循环没有走到 的事件,但前k-1次可能走到过这条最优路径. 永远不会被走到的事件为 ,其概率为:39蚁群算法 最新5.3.1 GBAS算法的收敛性分析 3/8 任意给定的固定弧(i,j),在第k次循环后,其信息素值的下界可以计算出：40蚁群算法 最新5.3.1 GBAS算法的收敛性分析 4/8令,任何一个固定节点最多有(n-1)后续节点,并且其弧上的信息素值都小于1或者等于1.得:蚁群中的一只蚂蚁在第 次循环走到路径 W* 的概率为一个蚁群中至少有一只蚂蚁，因此这是一个蚁群到达最优路径的一个下界. 上式右侧与k无关41蚁群算法 最新5.3.1 GBAS算法的收敛性分析 5/8 则取对数有从而得到42蚁群算法 最新5.3.1 GBAS算法的收敛性分析 6/8 证明右式成立 随机过程 以概率1达到一条最优路径.当某条最优路径Z在第k次循环被首次走到后,在第k+1轮循环按信息素的更新原则,可以用归纳法证明,对于任意43蚁群算法 最新5.3.1 GBAS算法的收敛性分析 7/8由于级数 是发散的,可知 .因此,当 时,在第K轮迭代之后,该弧永远不再被加强,从而有 也既 弧上的信息素之和将趋于0.对于信息素的更新公式(2),可以归纳证明(6)式的第二项与(i,j)弧无关,结合(7)式可得 的极限存在,且所有的极限之和为1.对于所有的44蚁群算法 最新5.3.1 GBAS算法的收敛性分析 8/8 结合前两部分讨论,当Xn首次到达最优路径后,对于任何最优路径上的弧,(1)式的转移概率 ,即 依概率1收敛到 .45蚁群算法 最新5.3.2 其他算法及收敛性分析 1/4 MAX-MIN蚁群优化算法指定挥发系数不随时间变化,这是和GBAS算法不同的一点,改变了信息素挥发和增强的规则(9)式，同时给出一个下界 控制信息素的挥发. 定理 在MAX-MIN算法中,46蚁群算法 最新5.3.2 其他算法及收敛性分析 2/447蚁群算法 最新5.3.2 其他算法及收敛性分析 3/448蚁群算法 最新5.3.2 其他算法及收敛性分析 4/449蚁群算法 最新5.4 蚁群优化算法—技术问题4.1 解的表达形式与算法的实现4.2 每一节点的记忆信息和系数的确定4.3 蚁群的规模和停止规则4.4 信息素的更改50蚁群算法 最新5.4.1 解的表达形式与算法的实现 1/4 ----解的表达形式解的表达形式 基于TSP问题的蚁群优化算法，其解的形式是所有城市的一个排列（闭圈，这种情况下谁在第一并不重要），信息素痕迹按每个弧记录。

而对于一般以顺序作为解的优化问题，谁在第一是很重要的蚁群算法在解决这类问题时，只需要建立一个虚拟的始终点，就可以把TSP问题的解法推广，用于诸多的优化问题诸如车间作业及下料等问题，他们的共同特点是解以一个顺序表示TSP问题寻找的是最短回路，而一般优化问题中，STEP 3 中的判断条件 需要根据实际问题进行修改51蚁群算法 最新5.4.1 解的表达形式与算法的实现 2/4 ----算法的实现例：0-1背包问题的解顺序表达形式与算法实现设有一个容积为b的背包，n个尺寸分别为 ，价值分别为 的物品，0-1背包问题的数学模型为：假设其解的顺序表达形式为　　　　　　　　，其中　　　为　　　　　　的一个排列52蚁群算法 最新5.4.1 解的表达形式与算法的实现 3/4 ----算法的实现建立有向图 ，其中 A中共有 条弧初始信息素痕迹定义为 。

设第s只蚂蚁第k步所走的路线为 ，表示蚂蚁从0点出发，顺序到达 第 步按TSP算法的转移概率公式行走选择 若 则 ，否则，此蚂蚁不再继续行走，退回起点53蚁群算法 最新5.4.1 解的表达形式与算法的实现4/4 ----算法的实现 对蚁群重复以上过程，比较m只蚂蚁的装包值 并记忆具有最大装包值的蚂蚁为t把GBAS算法中步骤3中的改为 ，若满足此条件则替换当前最好解为 ，对W上的弧进行信息素的加强，其他弧进行信息素的挥发 算法中记录了三个信息：信息素痕迹 ；行走路线 ；和问题的约束条件，以确定是否将 加入。

54蚁群算法 最新5.4.2 每一节点的记忆信息和系数的确定----需要记忆的信息 1/3算法中需要记忆的信息有三部分第一部分信息是存在每个节点的路由表数据结构 ，由此决定的的转移概率为其中T可以看成节点i的邻域55蚁群算法 最新5.4.2 每一节点的记忆信息和系数的确定----需要记忆的信息 2/3 第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息，这一部分主要由算法的中的 记忆，表示蚂蚁已经行走过的节点 第三部分为问题的约束条件在GBAS中，T集合表示满足约束条件的候选集，在背包问题的蚁群算法中由判别条件 ，来实现记忆功能56蚁群算法 最新5.4.2 每一节点的记忆信息和系数的确定----系数的确定 3/3 残留信息的相对重要程度 和预见值的相对重要程度 体现了相关信息痕迹和预见度对蚂蚁决策的相对影响Dorigo在求解TSP问题时，推荐参数的最佳设置为： 。

57蚁群算法 最新5.4.3 蚁群的规模和停止规则一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数二、终止条件1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续；3 目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止58蚁群算法 最新5.4.4 信息素的更改 1/6信息素的更新分为离线和两种方式离线方式（同步更新方式）的主要思想是在若干只蚂蚁完成n个城市的访问后，统一对残留信息进行更新处理信息素的更新（异步更新方式）即蚂蚁每行走一步，立即回溯并且更新行走路径上的信息素59蚁群算法 最新5.4.4 信息素的更改 2/6离线方式的信息素更新分为单蚂蚁离线更新和蚁群离线更新n蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问（第k-1次蚁群循环）后，统一对残留信息进行更新处理其中， 为第k-1次循环后的的信息素的痕迹值n单蚂蚁离线更新是在第s只蚂蚁完成对所有n个城市的访问后，进行路径回溯，更新行走路径上的信息素，同时释放分配给它的资源。

更新公式为 第s+1只蚂蚁根据 重新计算路由表 60蚁群算法 最新5.4.4 信息素的更改 3/6TSP问题中，蚁群优化算法根据信息素痕迹更新方式不同可以分为不同的算法，采用离线方式，其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走的一条路径Q为一个常数，该算法名为蚁周算法（ant-cycle algorithm）,特点是行走的路径越短对应保存的信息素的值就越大61蚁群算法 最新5.4.4 信息素的更改 4/6GBAS算法是典型的离线信息素更新方式该算法中，蚁群中蚂蚁的先后出行顺序没有相关性，但是每次循环需要记忆m只蚂蚁的行走路径，以进行比较选择最优路径相对而言，单蚂蚁离线更新方式记忆信息少，只需要记忆第s只蚂蚁的路径，并通过信息素更新后，释放该蚂蚁的所有记录信息实际上这种方式等价于蚁群离线方式中只有一只蚂蚁62蚁群算法 最新5.4.4 信息素的更改 5/6与单蚂蚁离线更新方式相比，信息量记忆更小的是信息素更新方式，即蚂蚁每走一步，马上回溯并且更新刚刚走过的路径上的信息素，其规则为 其中，k为蚂蚁行走的第k步63蚁群算法 最新5.4.4 信息素的更改 6/6蚁量算法（ant-quantity algorithm）的信息素更新为 Q为常量， 表示i到j的距离，这样信息浓度会随城市距离的减小而加大。

蚁密算法（ ant-density algorithm ）信息素更新为 以上三种算法中，蚁周算法效果最好，因为他用的是全局信息，而其余两种算法用的是局部信息蚁周离线更新方法很好地保证了残留信息不至于无限积累，非最优路径会逐渐随时间推移被忘记64蚁群算法 最新5.5 应用 1/55.5.1 光网络的智能管理 分布式动态选路及波长分配( RWA , Routing and Wavelength Assignment ) 是指在实时业务情况下光通路的路由选择和波长分配的优化问题,是实现自动交换光网络(ASON ,Automatically Switched Optical Network) 的关键技术之一研究RWA 问题的目的是尽可能减少所需要的波长数和降低光路连接请求的阻塞率由于RWA 问题是NP-C 问题,文献中大多将RWA 问题拆分成路由和波长分配两个子问题分别加以解决但是,由于RWA 问题本身是一个不可分割的整体,把RWA 分开考虑必然造成难以得到全局最优解的后果65蚁群算法 最新5.5 应用 2/5 同时,分布式的计算方式则克服了传统集中式算法可扩展性差的缺点,更适应现代频繁变化的大型光网络。

因此,近年来国内外对RWA 并行的分布式算法表现出极大的兴趣,此类算法建立的基础是分层图模型 用蚁群算法在分层图模型的基础上求解动态RWA 问题基于蚂蚁“信息素表”来完成局部信息的刷新计算以分布的形式做少量的计算来刷新全局路由选择信息 参考文献：孙海金, 朱　娜, 周乃富 基于蚁群系统的分布式RWA算法研究[J].光通信研究,2005.566蚁群算法 最新5.5应用 3/5蚁群算法用于计算机网络路由参考文献：谢银祥计算机网络中的组播路由算法67蚁群算法 最新5.5 应用 4/568蚁群算法 最新5.5应用 5/55.5.3 蚁群算法用于聚类（蚁群蚁卵分类） 思想：把待聚类的数据随机散布在一个平面上，放置若干只虚拟蚂蚁使其在平面上随机运动当一只蚂蚁遇到一个数据时即拾起并继续行走，在行走过程中，如果遇到附近的数据与背负的数据相似性高于设置的标准时则将数据放置在该位置，继续移动重复以上过程即可实现数据聚类69蚁群算法 最新第五章第五章 结束结束智能优化方法智能优化方法信息系统与管理学院 70蚁群算法 最新5.1.4 蚁群优化算法研究现状 1/790年代Dorigo最早提出了蚁群优化算法---蚂蚁系统（Ant System, AS）并将其应用于解决优化算法中经典的旅行商问题（TSP）。

从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量71蚁群算法 最新5.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(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会这种改进型算法能够以更快的速度获得更好的解但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞 72蚁群算法 最新5.1.4蚁群优化算法研究现状 3/7为了进一步克服AS中暴露出的问题，提出了蚁群系统(Ant Colony System, ACS)该系统的提出是以Ant-Q算法为基础的Ant-Q将蚂蚁算法和一种增强型学习算法Q-learning有机的结合了起来ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素其中，0<ρ<1是信息素挥发参数， 是从寻路开始到当前为止全局最优的路径长度73蚁群算法 最新5.1.4蚁群优化算法研究现状 4/7再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。

74蚁群算法 最新5.1.4蚁群优化算法研究现状 5/7在对AS进行直接完善的方法中，MAX-MIN Ant System是一个典型代表该算法修改了AS的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解为了避免搜索停滞，路径上的信息素浓度被限制在[MAX，MIN ]范围内，另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力75蚁群算法 最新5.1.4蚁群优化算法研究现状 6/7另一种对AS改进的算法是Rank-based Version AS与“精英策略”相似，在此算法中总是更新更好进程上的信息素，选择的标准是其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，ｗ为每次迭代后放置信息素的蚂蚁总数 76蚁群算法 最新5.1.4蚁群优化算法研究现状 7/7这种算法求解TSP的能力与AS、精英策略AS、遗传算法和模拟退火算法进行了比较在大型TSP问题中（最多包含132座城市），基于AS的算法都显示出了优于GA和SA的特性而且在Rank-based AS和精英策略AS均优于基本AS的同时，前者还获得了比精英策略AS更好的解。

77蚁群算法 最新。