蚁群算法.x 修复的课件

1、蚁群算法蚁群算法的起源蚁群算法的原理自然蚁群与人工蚁群蚁群算法在TSP问题中的应用三种模型蚁群的规模及停止规则蚁群算法的特点蚁群算法的研究现状蚁群算法的其他应用参考书推荐总结 研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。 蚁群算法就是利用群集智能解决组合优化 题的典型例子。 20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 蚁群算法(Ant Colony Algorithm，AC

2、A)，一种仿生算法。蚁群算法的起源 它是继模拟退火算法、遗传算法、禁忌搜索(Tabu Search)算法、人工神经网络算法等启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法。蚁群算法的起源 蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成

3、的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 蚁群算法的原理 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。简化的蚂蚁寻食过程 本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。简化的蚂蚁寻食过程 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人

4、工蚁群中把具有简单功能的工作单元看作蚂蚁。两者相似之处在于：都是优先选择信息素浓度大的路径。两者的区别： （1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。 （2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的地的距离。自然蚁群与人工蚁群蚁群算法在TSP问题中的应用旅行商问题（TSP,traveling salesman problem）1960年首先提出。问题描述： 一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。TSP在许多工程领域具有广泛的应用价值 例如电路板布线、VLSI芯片设计、机器

5、人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。 TSP问题的数学描述TSP问题表示为一个N个城市的有向图G=(N,A)，其中城市之间距离目标函数为其中， ，为城市1,2，n的一 个排列， 。蚂蚁算法求解TSP其中：表示边（i，j）上的信息素浓度； 是启发信息，d是城市i和j之间的距离；和反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。 当所有蚂蚁完成周游后，按以下公式进行信息素更新。 蚂蚁算法求解TSP其中：为小于1的常数，表示信息的持久性。其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。 蚁量算

6、法（ant-quantity algorithm）的信息素更新为 ,Q为常量， 表示i到j的距离，这样信息浓度会随城市距离的减小而加大。蚁密算法（ ant-density algorithm ）信息素更新为 ，在此算法中，从城市i到j的蚂蚁在路径上残留的信息浓度为一个与路径无关的常量Q。 后两种算法与前一种算法的区别在于：后两种算法中每走一步(即从时间t到t+1)，都要更新残留信息素的浓度，而非等到所有蚂蚁完成对所有城市的访问 之后。 三种模型 通过实验表明，在这三种算法中：ant-cycle算法的效果最好，这是因为它用的是全局信息；而其余两种算法用的是局部信息。这种更新方法很好地保证了残留信

7、息不至于无限累积，非最优路径会逐渐随时间推移被忘记。三种模型一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件 1 给定一个外循环的最大数目； 2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。蚁群的规模及停止规则 其原理是一种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加信息素强度增加后来蚂蚁选择概率增大最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上。 它是一种通用型随机优化方法, 它吸收了蚂蚁的行为特点(内在搜索机制) , 它是使用人工蚂蚁仿真(也称蚂蚁系统) 来求解问题。但人工蚂蚁决不是对实际蚂

8、蚁的一种简单模拟, 它融进了人类的智能。人工蚂蚁有一定的记忆; 人工蚂蚁不完全是瞎的; 人工蚂蚁生活的时空是离散的。蚁群算法的特点 它是一种分布式的优化方法, 不仅适合目前的串行计算机, 而且适合未来的并行计算机。 它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题。 它是一种启发式算法, 计算复杂性为 , 其中Nc是迭代次数, m是蚂蚁数目, n是目的节点数目。蚁群算法的特点蚁群算法的研究现状 90年代Dorigo最早提出了蚁群优化算法-蚂蚁系统（Ant System, AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的

9、蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。蚁群算法的研究现状 因此，其后的ACO研究工作主要都集中于AS性能的改进方面。较早的一种改进方法是精英策略(Elitist Strategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为Tgb(全局

10、最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。 蚁群算法的研究现状 为了进一步克服AS中暴露出的问题，提出了蚁群系统(Ant Colony System, ACS)。该系统的提出是以Ant-Q算法为基础的。Ant-Q将蚂蚁算法和一种增强型学习算法Q-learning有机的结合了起来。ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。

11、其中，01是信息素挥发参数， 是从寻路开始到当前为止全局最优的路径长度。蚁群算法的研究现状 在对AS进行直接完善的方法中，MAX-MIN Ant System是一个典型代表。该算法修改了AS的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞，路径上的信息素浓度被限制在MAX，MIN 范围内，另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力。蚁群算法的研究现状 另一种对AS改进的算法是Rank-based Version AS。与“精英策略”相似，在此算法中总是更新更好进程上的信息素，选择的标准是其行程长度 决定的排序，且每个

12、蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，为每次迭代后放置信息素的蚂蚁总数。 蚁群算法的研究现状 这种算法求解TSP的能力与AS、精英策略AS、遗传算法和模拟退火算法进行了比较。在大型TSP问题中（最多包含132座城市），基于AS的算法都显示出了优于GA和SA的特性。而且在Rank-based AS和精英策略AS均优于基本AS的同时，前者还获得了比精英策略AS更好的解。 蚁群算法的其他应用 蚁群算法在解决很多组合问题上都取得比较理想的效果。其中有两个比较著名的组合问题，QAP问题和JSP问题(JobShop Scheduling Problem)作相应调整的蚁群算法可以比较好地解

13、决这两个组合问题。另外，将蚁群算法对实际问题的解决也取得一定的进展，如大规模集成电路中的综合布线以及电信网络中的路由等方面的应用。智能蚁群算法及应用 吴启迪 上海科技出版社从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。主要内容有蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问题求解模式、算法的典型应用及拓展应用。参考书推荐目前，除了业界已得到公认的遗传算法、模拟退火法、禁忌搜索法、人工神经网络等热门进化类方法，新加入这个行列的蚁群算法开始崭露头角，为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。蚁群算法思想在启发式方法范畴内已逐渐成为一个独立的分支，在有关国际会议上多次作为专题加以讨论。这种由欧洲学者提出并加以改进的新颖系统思想，正在受到越来越多的人的注意和研究，应用范围也开始遍及许多领域：例如交通网络中的最佳路径