蚁群算法ppt课件.ppt

《蚁群算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《蚁群算法ppt课件.ppt（36页珍藏版）》请在三一办公上搜索。

1、1,蚁群算法,Yuehui ChenSchool of Inform.Sci.and Eng.University of Jinan,2011http:/,2,3,蚁群优化算法起源,20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发

2、展前景的算法,4,蚁群优化算法研究背景,群智能理论研究领域有两种主要的算法：蚁群算法(Ant Colony Optimization,ACO)和微粒群算法（Particle Swarm Optimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。,5,蚁群优化算法研究背景,与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面

3、：1 无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的鲁棒性 2 以非直接的信息交流方式确保了系统的扩展性 3 并行分布式算法模型，可充分利用多处理器 4 对问题定义的连续性无特殊要求 5 算法实现简单,6,蚁群优化算法研究背景,群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从

4、理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。,7,蚁群优化算法概念,1 蚁群算法原理2 简化的蚂蚁寻食过程3 自然蚁群与人工蚁群算法4 蚁群算法与TSP问题5 初始的蚁群优化算法基于图的蚁群系统（GBAS）6 一般蚁群算法的框架,8,1 蚁群算法原理,蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的

5、蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。,9,2 简化的蚂蚁寻食过程,蚂蚁从A点出发，速度相同

6、，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。,10,2 简化的蚂蚁寻食过程,本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,11,2 简化的蚂蚁寻食过程,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信

7、息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,12,3 自然蚁群与人工蚁群算法,基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，

8、来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。,13,4 蚁群算法与TSP问题,TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为，其中 为城市1,2，n的一个排列，。,14,4 蚁群算法与TSP问题,

9、TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值，也称信息素痕迹。2 可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。,15,4 蚁群算法与TSP问题,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后

10、，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,16,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的.算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧 赋信息素初值，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。,17,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,STEP 1（外循环

11、）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点 出发，用 表示蚂蚁s行走的城市集合，初始 为空集，。STEP 2(内循环)按蚂蚁 的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j，；若则到达重复STEP 2。,18,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,STEP 3 对，若，按 中城市的顺序计算路径程度；若，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若，则。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。得到新的，重复步骤STEP 1。,19,5

12、初始的蚁群优化算法基于图的蚁群系统（GBAS）,在STEP 3 中，挥发因子 对于一个固定的，满足并且 经过k次挥发，非最优路径的信息素逐渐减少至消失。,20,5初始的蚁群优化算法基于图的蚁群系统（GBAS）,以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程 1 信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。2 信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离

13、线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不与蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。在STEP 3中，蚁群永远记忆到目前为止的最优解。,21,图的蚁群系统（GBAS）,四个城市的非对称TSP问题，距离矩阵和城市图示如下：,22,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：

14、,23,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解,24,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。,25,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。,26,5 初始的蚁群优化算法基

15、于图的蚁群系统（GBAS）,重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：,27,5 初始的蚁群优化算法基于图的蚁群系统（GBAS）,蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化。假设第K次外循环后得到信息素矩阵，得到当前最优解。第K次循环前的信息素和最优解为，经过第K次外循环后，得到。由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程。,28,6 一般蚁群算法的框架,一般

16、蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。,29,应用,蚁群算法用于计算机网络路由参考文献：计算机网络中的组播路由算法 谢银祥,30,应用,蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（Ant Colony Routing,ACR）。,31,32,应用,蚁群算法用于聚类（蚁群蚁卵分类）思想：把待聚类的数据随机散布在一个平面上，放置若干只虚拟蚂蚁使其在平面上随机运动。当一只蚂蚁遇到一个数据时即拾起并

17、继续行走，在行走过程中，如果遇到附近的数据与背负的数据相似性高于设置的标准时则将数据放置在该位置，继续移动。重复以上过程即可实现数据聚类。,33,34,T1,T2,T3,35,蚁群优化算法参考书1,智能蚁群算法及应用 吴启迪 上海科技出版社 从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。主要内容有蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问题求解模式、算法的典型应用及拓展应用。,36,蚁群优化算法参考书2,蚁群算法及其应用 李士勇 哈工大出版社 国内首部蚁群算法的专著，系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的应用。本书可供人工智能、计算机科学、信息科学、控制工程、管理工程、交通工程、网络工程、智能优化算法及智能自动化等领域的广大师生和科技人员学习及参考。,