人工智能算法.pdf

s什么是人工智能算法随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，当前存在的一些智能算法有人 工神经网络遗传算法模拟退火算法群集智能蚁群算法粒子群算等等。蚁群算法只是其中的一种。人工智能计算也有人称之为“软计算”，是 们受自然（生物界）规律的启迪，根据其原理，模仿 求解问题的算法。从自然界得到启迪，模仿其结 构进行发明创造，这就是仿生学。这是我们向自 然界学习的一个方面。另一方面，我们还可以利 用仿生原理进行设计（包括设计算法），这就是智能 计算的思想。第一页，编辑于星期六：十五点四十六分。蚁群算法 起源 应用领域 研究背景 基本原理第二页，编辑于星期六：十五点四千六分。蚁群优化算法起源_蚁群算法最开始的提出是在90年代有人受了蚂蚁觅食时的通讯 机制的启发用来解决计算机算法学中经典的“旅行商问题(Traveling Salesman Problem,TSP)”。TSP问题属于易于描述但难于解决的著名难题之一，至今世界上还有 不少人在研究它。该问题的基本描述是：某售货员要到若干个村庄售 货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在 商店出发，到每个村庄都售货一次后再返回商店，问他应选择一条什 么路线才能使所走的总路程最短？其实有很多实际问题可归结为 TSP问题。第三页，编辑于星期六：十五点四千六分。蚁群优化算法起源_例如邮路问题就是一个TSP问题。假定有一辆邮车要到 n个不同的地点收集邮件，这种情况可以用n十1个结点的 图来表示。一个结点表示此邮车出发并要返回的那个邮局，其 余的n个结点表示要收集邮件的n个地点。邮车所行经的路线是 一条周游路线，希望求出具有最小长度的周游路线。再举一 个例子在一条装配线上用一个机械手去紧固待装配部件上的 螺帽问题。机械手由其初始位置（该位置在第一个要紧固的螺 帽的上方）开始，依次移动到其余的每一个螺帽，最后返回到初 始位置。一条最小成本周游路线将使这机械手完成其工作所用 的时间取最小值。所以TSP问题的研究也是具有很多实际价值。第四页，编辑于星期六：十五点四十六分。蚁群算法应用领域这种方法能够被用于解决大多数优化问题或者 能够转化为优化求解的问题。现在其应用领域已扩 展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途 径。第五页，编辑于星期六：十五点四千六分。蚁群优化算法研究背景1/3蚁群算法属于群智理论。群智能理论研究领 域有两种主要的算法：蚁群算法(Ant Colony Optimization,ACO)和微粒群算法(Particle Swarm Optimization,PSO)。前者是对蚂蚁群落食物 采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初 是模拟鸟群觅食的过程，但后来发现它是一种很好的 优化工具。第六页，编辑于星期六：十五点四千六分。.蚁群优化算法研究背景2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面：1无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的可靠性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型，可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单第七页，编辑于星期六：十五点四4六分。蚁群优化算法研究背景3/3群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法 只需目标函数的输出值，而无需其梯度信息。已完成的群智 能理论和应用方法研究证明群智能方法是一种能够有效解决 大多数全局优化问题的新方法。更为重要是，群智能潜在的 并行性和分布式特点为处理大量的以数据库形式存在的数据 提供了技术保证。无论是从理论研究还是应用研究的角度分 析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。第八页，编辑于星期六：十五点四斗六分。蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算 法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激 素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感 知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁 群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越 多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是 因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一 个还没有走过的路口时.就随机地挑选一条路径前行。与此同时释放出与路 径长度有关的信息素。路径越长，释放的激素浓度会越低当后来的蚂蚁再 次碰到这个路口的时候.选择激素浓度较高路径概率就会相对较大。这 样形成一个正反馈。最优路径上的激索浓度越来越大.而其它的路径上 激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。第九页，编辑于星期六：十五点四千六分。简化的蚂蚁寻食过程1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或 ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过 9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走 到C点，为一半路程。10第十页，编辑于星期六：十五点由Q六分。简化的蚂蚁寻食过程2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达 终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。11第十一页，编辑于星期六：十五,31十六分。简化的蚂蚁寻食过程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：lo若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这 也就是前面所提到的正反馈效应。12第十二页，编辑于星期六：十五3%十六分。自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造 人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的 相似之处在于都是优先选择信息素浓度大的路径。较短路径的 信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的 优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已 经访问过的节点。同时，人工蚁群再选择下一条路径的时候是 按一定算法规律有意识地寻找最短路径，而不是盲目的。例如 在TSP问题中，可以预先知道当前城市到下一个目的地的距离。13第十三页，编辑于星期六：十五工1十六分。蚁群算法与TSP问题1/3TSP问题表示为一个N个城市的有向图6=(N,A),其中 N=1,2,n A=(i,j)|5N城市之间距离(a、ij)nxn目标函数为n1=1其中W=(I2，O城市”n的一个排列，。ln+l 1114第十四页，编辑于星期六：十五工&十六分。蚁群算法与TSP问题2/3TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节 点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步 转移概率由图中的每条边上的两类参数决定：1信息素值也 称信息素痕迹。2可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路 径上的信息素以一定的比率进行减少，模拟自然蚁群的信 息素随时间挥发的过程；二是增强，给评价值“好”（有蚂 蚁走过）的边增加信息素。15第十五页，编辑于星期六：十五33十六分。蚁群算法与TSP问题3/3蚂蚁向下一个目标的运动是通过一个 随机原则来实现的，也就是运用当前所在节 点存储的信息，计算出下一步可达节点的概 率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把 评价信息保存在相关连接的信息素中。16第十六页，编辑于星期六：十五3瓜十六分。初始的蚁群优化算法一基于图的蚁群系统l（GBAS）1/12初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS,是由Gutjahr W J在2000年的FutureGeneration Computing Systems提出的，算法步骤如下：STEP0对n个城市的TSP问题，城市间的距离矩阵为 N1小溶柑前小需展匕条弧 赋信息素初寞，假设m只蚂蚁在工作，所夜期都从同一城市 出发坪零弹是 Ovv=（1,2,，拉）17第十七页，编辑于星期六：十五点1&十六分。初始的蚁群优化算法一基于图的蚁群系统JGBAS)2/12STEP 1(外循环)如果满足算法的停止规则，则停止计算并输出计算 得到的最好解。否则使蚂蚁s从起点 出发，用i 表示蚂雕所走的 城市集合，初始 为空集，乙(s)o ismSTEP 2(内循环)按蚂蚁 的顺序分别计算。当蚂蚁在城市i,若(s)=N或/|(z,1)A,l 史 L(s)二完成第S只蚂蚁的计算。否则，若L(s)w N且7=Z|(z,Z)g A,Z()-z0 w 金(D.t n，则以概率%，Pij=至U达j，(5)=(5)|Jj，：=/若(S)WN且T=/&/)则到达 z(s)=(s)U。惠举TEP 2。eA/e。）-偏=8 Oora1X 一I l n N第十八页，编辑于星期六：十五十K分。初始的蚁群优化算法一基于图的蚁群系统.(GBAS)3/12STRP3对IVsVm，若 L(s)=N,按 用城市的顺序计算 路径程度；若L(s)wN路径长度置为一个无穷大值(即不可 达)。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若/(L)K并且OO2夕左 k=l=QO经过k次挥发，非最优路径的信息素逐渐减少至消失。第二十页，编辑于星期六：十五Oora222十K分。I初始的蚁群优化算法一基于图的蚁群系统4（GBAS）5/12以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程1信息素jJYievaporation）信息素痕迹的挥发过程是每个连接上的信 息素痕迹的浓度自动逐渐减弱的过程，由（i-n v m 表示，这个 挥发过程主要用于避免算法过快地向局部最初区康集甲，青助于搜索区 域的扩展。2信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂 蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的 信息素更新称为离线的信息素更新。在STEP 3中，蚁群永远记忆到目前为止的最优解。21第二十一页，编辑于星期六：十 四十六分。的蚁群系统(GBAS)6/12可以验证，下式满足：z Tij(k)=iyk0即改左)是一个随机矩阵。四个城市的非对称TSP问题，距离矩阵和城市图示如下:D=(%)=(011.510510.510111101722第二十二页，编辑于星期六：十22四十六分。初始的蚁群优化算法一基于图的蚁群系统l（GBAS）7/12假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子0=%/=1,2,3 o此时，观察GBAS的计算过程。矩阵 共有人架弧，初始信息素记忆矩阵为：7（。）二（/（。）=2 2 21X 1X 1XV V V 2 2 2 1A 1A 1A V V V 2 2 21A 1A 1X V V V2 2 2 1X 1X 1X C V V V23第二十三页，编辑于星期六：十盈四十六分。初始的蚁群优化算法一基于图的蚁群系.统(GBAS)8/12执行GBAS算法的步骤2,假设蚂蚁的行走路线分别为：第一只f B f C-O f AJ(W1)=4;第二只W2:A f C f O-B f A J(W2)=3.5;第三只卬3:A-。f C-5 3 A/(W3)=8;第四只卬4:A-5 3。-C 3 A,/(W4)=4.5;当前最优解为，这个解是截止到当前的最优解，碰巧是实际 最优解24第二十四页，编辑于星期六：十2g四十六分。初始的蚁群优化算法一基于图的蚁群系统$（GBAS）9/12按算法步骤3的信息素更新规则，得到更新矩阵（0 1/24 1/61/6 0 1/24（1）=（小1）=1/24 1/12 0U/24 1/6 1/24这是第一次外循环结束的状态。/5O725第二十五页，编辑于星期六：十盈四十六分。初始的蚁群优化算法一基于图的蚁群系统(GBAS)10/12重复外循环，由于上一次得到的W2已经是全局最优 解，因此按算法步骤3的信息素更新规则，无论 蚂蚁如何行走，都只是对W2路线上的城市信息素 进行增强，其他的城市信息素进行挥发。得到更新 矩阵(0 5/24 心=(/)=J481/48 5/24 1/48、0 1/48 1/481/48 0 5/245/24 1/48 0)26第二十六页，编辑于星期六：十/R四十六分。初始的蚁群优化算法一基于图的蚁群系 统（GBAS）11/12重复外循环，由于W2全局最优解，GBAS只记录第 一个最优解，因此一但得到了全局最优解，信息 素的更新将不再依赖于以群的行走路线，而只是 不断增强最优路线的信息素，同时进行挥发。第 三次外循环后得到的信息素矩阵为：3)=(金(3)=11/48 1/9611/961/96 0 1/96 11/4811/48 1/96、1/96 1/960 11/481/96 0)27(0第二十七页，编辑于星期六：十.四十六分。初始的蚁群优化算法一基于图的蚁群系.统（GBAS）12/12.蚂蚁以一定的概率从城市倒城市j进行转移，信息素的更新在STEP 3完亦 并随K而变化。假设第K次外循环后得到信息素矩阵（左）=（金（左）|（厉）为得到当前最优解 W（左）第K次循环前的信息素和最优解为 上（1）,卬（左-4）转过第K次外循环后，得到上（左）,卬（左）o由于蚂蚁的一步转移 概率是随机的，从T（k-lW（k-l）到上伏）,W/）也是随机的，是一个马 1尔可夫过程。,1；28十樨四十六分。第二十八页,编辑于星期六:一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同，有三个组成 部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现4前面向算法中步骤2和步骤3中的转移概 率公式和信息素更新公式。29第二十九页，编辑于星期六：十役四十六分。蚁群优化算法一算法模型和收敛性分析马氏过程的收敛定义 GBAS算法的收敛性分析 其他算法及收敛性分析Oora3 32十K分。第三十页，编辑于星期六：十五马氏过程的收敛定义蚁群优化算法的每步迭代对应随机变量 Xk=（左）,W（左）,左二0,1,.,其中武左为信息素痕迹；舸城市的一个排列，最多有个状叁第s只蚂蚁在第k 轮转移只由 决定，土企蚂）蚁行走的路径和 一起，共同决定了，再通过信息素能离新原则可以进一步得到。的变化仅由7（左）决定，丽与先前的状态无筹，这是一个典型的马尔可夫过程。e定义：若5个马尔可夫过程，对任意给定的 满足Xk,k=ox.0则称马尔女X舄国1收4至IX%#=0,1,2,.X*31第三十一页，编辑于星期六：十.四十六分。GBAS算法的收敛性分析1/8定理满足指定条件的马尔可夫过程Xk=(Q,W(Q),左=0,1,.,依概率1收敛到x*=(*初某中 为一条最优路径，定忒为:，；=高，0，力为亚*的一条弧.(1)0 其他证明分析：蚁群算法中，一但达到全局最优，由f(L(t)f曷记录第 一个最优解.证明分三部分：证明以概率1达到一个最优路径-证明(1)上式成立-证明以概率1收敛到一个最优路径32第三十二页，编辑于星期六：十.四十六分。GBAS算法的收敛性分析2/8证明以概率1到达一个最优路径对于最优路径W*,令 空蚁群中的一个蚂蚁在第k次外循环后第一次走到 最优路径 的事件M*表示仅第蹴外循环没有走到的事件，但前k-击次 可能走到过这条最优路径,永远不会被走到的事佛为，其概率为,P(Fip|F2n)00K蚁群中的一只蚂蚁在第 k(k访循环走到路径W*的概率为n Pij(k)N(U)W*A(一 1)In 左(4)一个蚁群中至少有一只蚂蚁，因此这是一个蚁群到达最优路径 的一个下界,上式右侧与k无关,35编辑于星期六：十箱四十六分。第三十五页,GBAS算法的收敛性分析5/8尸前左次循环蚁群没有走到卬*vi-n pk左）4i-（-严 则 g（芍即*）（n-l）ln、n尸前上次循环蚁群没有走到川*（2）k=l00 A小（1-（477此 k=KA(n-l)ln取对数有从而得到002(1-(k=K00k二KA(n-1)ln=00尸（月U名U）=136第三十六页，编辑于星期六：十或四十六分。GBAS算法的收敛性分析6/8 证明右式成立可二而,“为w*的一条弧0 其他随机过程以概率1达到一条最优路径,当某条最优路径Z在第k次循 环被首次走到后，在第k+1轮循环按信息素的更新原则，可以用归纳法证明，对于任意（i,j）g W*,r=l,2,.K+r-%(K+r)二 口(1-哂(K)+I二 KpK+/h(l-pK+q)/=0=/+1(6)137第三十七页，编辑于星期六：十.四十六分。S GBAS算法的收敛性分析7/8QO由于级数Z疆发散的，可知 口(1-Q)姻此，当(5)任W*时，在第K轮迭代之后，该弧永远.后被加强,从而有K+r-1金(K+)=n(1-%(K)-0(7)l=K也既亿弧上的信息素之和将趋于0.对于信息素的更新公式(2),可以归纳证明 z%心)=1,皿成立(6)式的第二项与(i,j)弧无关，结合式可得的极限存在,且所有的极限之和为L对于所有的 W*1J型%(长+)=所,即可得limX/=(/*,W*).(8)Is38第三十八页，编辑于星期六：十?1四十六分。GBAS算法的收敛性分析8/8结合前两部分讨论，当Xn首次到达最优路径后，对于 任何最优路径上的弧,(1)式的转移概率P)(/)-1，即%=(*左),w(左),左=0,1,依概率1收敛 到 x*=*W)39第三十九页，编辑于星期六：十四十六分。.其他算法及收敛性分析1/4MAX-MIN蚁群优化算法指定挥发系数不随时间变化，这是和GBAS算法不同 的一点，改变了信息素挥发和增强的规则（9式），同时给出一个下界 控带幅曾朦铀辉发.r（左）max（1-2居（左-1）+/|叫,%（左-1）.（z,j）g W%max（l 夕）%（左 一1）,金（左 一1）.其他其中,0夕lIn（k+1）其中lim相 0,则定理5.2.1的结论也成立。左一0040第四十页，编辑于星期六：十五30十六分。其他算法及收敛性分析2/4_式蚂蚁转移概率更一般的规则由存储在每个节点的路由表数据结构Aj=aj（i,j）eA决定，即转移概率为%（左1）守公-j gTpq=v an（k 1）、o.j 丈T其中，七（左-1）=为（左-1）|（2,J）e A取决于三部分因素，T是从i可以直 接到达的节点结合。第一部分为每个节点的信息素为（左-1）痕迹和预见度（左-1）.第二部分为每个蚂蚁自身的记忆表中存储的历史信息.第三部分为问题的约束条件.41第四十一页，编辑于星期六：十盘四十六分。rRVO其他算法及收敛性分析3/4 的路由表信息由下式求得:力(k-D曲kf.Ta.(-1)=Z?,r，左，左+1)女+1 i-t r鸡尸JT此蚂蚁不再继续行走，退回起点。47第四十七页，编辑于星期六：十盅四十六分。解的表达形式与算法的实现4/4 一一算法 的实现对蚁群重复以上过程，比较m只蚂蚁的装包值Z q，s=L2,根iwL(s)厚0并记忆具有最大装包值的蚂蚁为t。把GBAS算法中步骤3中的 f(w)改为f(w)若满足此条件则替换当前最好解为 W：=L(t)对W上的弧进行信息素的加强，其他弧进行信息素的挥发。算法中记录了三个信息：信息素痕迹；彳呼路线lk+lZq-bJT48第四十八页，编辑于星期六：十盥四十六分。每一节点的记忆信息和系数的确定-.需要记忆的信息1/3_算法中需要记忆的信息有三部分。第一部分信息是存在每个节点的路由表数据结构a=&；)g a)由此决定的的转移概率为r%(k 1)P=Zaii(k-1)J C、j 史T其中T可以看成节点i的邻域o 4(左-1)=%.(-1)|(/,j)G A)，琮(1)成.1)g(k l)=瑞也-1)褶第-1)工丁 lJ leT0 j订49第四十九页，编辑于星期六：十盘四十六分。每一节点的记忆信息和系数的确定-需要记忆的信息2/3第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史 信息，这一部分主要由算法的中的 记忆年滤示蚂蚁已经行走过的节点。第三部分为问题的约束条件。在GBAS中，T集合表示满足约束条件的候 选集，在背包问题的蚁群算法中由判别条件Vzv 3=5 p=0.551第五十一页，编辑于星期六：十矗四十六分。蚁群的规模和停止规则一、蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件1给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；2当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经 收敛，不再需要继续；3目标值控制规则，给定优化问题（目标最小化）的一个下界和一 个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。52第五十二页，编辑于星期六：十?四十六分。信息素的更改1/6_信息素的更新分为离线和在线两种方式。离线方式（同步更新方式）的主要思想是在若干只蚂蚁完成n个城市的访问后，统一对残留信息进行更新处理。信息素的在线更新（异步更新方式）即蚂蚁每行走 一步，立即回溯并且更新行走路径上的信息素。53第五十三页，编辑于星期六：十.四十六分。信息素的更改2/6离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新。蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问（第k-1次蚁群循环）后，统一对残留信息进行更新处理。其中，为第k五总般南南f族素施（k-1）单蚂耳离缘零新是在第s只蚂蚁完成对所有n个城市的访问后，进行路径回溯，更新行 走路桂小酚禧息素，同时释放分配给它的资源。更新公式为第s+1只蚂蚁根据/（S+1）重啊塞跳由塞马（S）号（s+1）54第五十四页，编辑于星期六：十四四十六分。信息素的更改3/6TSP问题中，蚁群优化算法根据信息素痕迹更新方式不同可以分为不 同的算法，采用离线方式，并且 Ac.(左-1)或.($)为IJ IJQA%)=|W|,G 0-w时，其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走 的一条路径。Q为一个常数，该算法名为蚁环算法(ant-cycle algotithm)，特点是行走的路径越短对应保存的信息素的值就越大。第五十五页，编辑于星期六:5 32 5F 十四十六分。信息素的更改4/6GBAS算法是典型的离线信息素更新方式。该算 法中，蚁群中蚂蚁的先后出行顺序没有相关性，但是每次循环需要记忆m只蚂蚁的行走路径，以 进行比较选择最优路径。相对而言，单蚂蚁离线更 新方式记忆信息少，只需要记忆第s只蚂蚁的路径，并通过信息素更新后，释放该蚂蚁的所有记录信息。实际上这种方式等价于蚁群离线方式中只有一只蚂蚁。56第五十六页，编辑于星期六：十题四十六分。信息素的更改5/6与单蚂蚁离线更新方式相比，信息量记忆更小的是信 息素在线更新方式，即蚂蚁每走一步，马上回溯并且 更新刚刚走过的路径上的信息素，其规则为 其中，寮畴虫逅盘谿釐趣57第五十七页，编辑于星期六：十mz四十六分。y信息素的更改6/6蚁量算法(ant-quantity algorithm)的信息素更新为%)=+4为常量，4表示倒j的距离，这样信息浓度会随城希距离的减小而加大。蚁密算法(ant-density algorithm)信息素更新为。以上强.翻算适中，蚁环算法效果最好，因为他用的是全局信息，而其条两种算法用的是局部信息。蚁环离线更新方法很好地保证 了残留信息不至于无限积累，非最优路径会逐渐随时间推移被忘 记。58第五十八页，编辑于星期六：十翔四十六分。应用1/5曝网络的智能管理分布式动态选路及波长分配(RWA,Routing and Wavelength Assignment)是指在实时业务情况下光通路 的路由选择和波长分配的优化问题,是实现自动交换光 网络(ASON,Automatically Switched Optical Network)的关键技术之一。研究RWA问题的目的是尽可 能减少所需要的波长数和降低光路连接请求的阻塞率。由于RWA问题是NP-C问题,文献中大多将RWA问题拆分成 路由和波长分配两个子问题分别加以解决。但是，由于 RWA问题本身是一个不可分割的整体，才巴RWA分开考虑必然 造成难以得到全局最优解的后果。第五十九页，编辑于星期六:95F四十六分。应用2/5同时,分布式的计算方式则克服了传统集中式算法可扩展性差的缺点,更适应现代频繁变化的大型光网络。因止匕，近年来国内外对RWA并行的 分布式算法表现出极大的兴趣,此类算法建立的基础是分层图模型。用蚁群算法在分层图模型的基础上求解动态RWA问题。基于蚂蚁“信息素表”来完成局部信息的刷新计算。以分布的形式做少量的 计算来刷新全局路由选择信息。参考文献:基于蚁群系统的分布式RWA算法研究孙海金，朱 娜，周乃富2005年第2期光通信研究60第六十页，编辑于星期六：十五十六分。应用3/5蚁群算法用于计算机网络路由参考文献：计算机网络中的组播路由算法谢银祥为进行有效地组播通信，确定组播路由是最关健，其中组播路由算法是用来 确定组播树.下面对组播路由算法进行介绍静态和动态组播路由算法路径计算是路由中最关健技术,根据路由算法所依据的网络拓扑和状态信息 的不同，可分为动态和静态路由算法.动态算法是根据网络的实时状态信息进行 的，而文献.内中，静态路由算法不利用网络当时的状态信息，它认为网络的拓朴 和状态信息是固定不变的,静态路由算法实现起来很简单，但是不适应网络状态 的动态变化。动态路由算法则能实时根据网络的拓扑和状态变化调整其所选的路 径。日前研究的动态路山算法主要有三种：61第六十一页，编辑于星期六：十f工四十六分。、应用4/5第一种是树结构不可调的动态路由算法,成员变化时只对树采用最小的变化.如文献中算法，成员加入则通过点到树的最短路由来完成，成员离开时，若离开。点是叶力点，则采用剪枝法删除节点，否则不进行操作.在该方法中每个组成 员之间相互独立，闪此树的性能不受组动态变化的影响0第二种是树结构全面调 整的重构动态路山算法，即在成员变更后，对整个组重新进行路由。这将对组中 原来成员通信产生干扰（数据分组顺序打乱），当成员剧烈变化时，这种方法是不 实用的。第三种是树结构部分调整的动态路由算法,如文献网给出了一种改进算法。首先节点的加入和离开仿照前面第一种方式实现，但在树的局部范围内，考察节 点的加入和离开对树的累计损伤，当累计损伤超过一定门限时，在局部范围内重 新优化路由，通过改变门限值达到树的优化和计算时间、复杂性之间的平衡。62第六十二页，编辑于星期六：十盅四十六分。）应用5/5爆群算法用于聚类（蚁群蚁卵分类）思想：把待聚类的数据随机散布在一个平面上,放置若干只虚拟蚂蚁使其在平面上随机运动。当一只蚂蚁遇到一个数据时即拾起并继续行走,在行走过程中，如果遇到附近的数据与背负的 数据相似性高于设置的标准时则将数据放置在 该位置，继续移动。重复以上过程即可实现数 据聚类。63第六十三页，编辑于星期六：十.四十六分。.智能算法前景目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发 展。不仅仅只是功能模仿要持有信息机理一致的观 点。即人工脑与生物脑将不只是功能模仿，而是具 有相同的特性。这两者的结合将开辟一个全新的领 域，开辟很多新的研究方向。智能计算将探索智能 的新概念，新理论，新方法和新技术，而这一切将 在以后的发展中取得重大成就。64第六十四页，编辑于星期六：十翻 四十六分。j ThanksEND65第六十五页，编辑于星期六：十四十六分。