蚁群算法简述.pptx

《蚁群算法简述.pptx》由会员分享，可在线阅读，更多相关《蚁群算法简述.pptx（36页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、会计学1蚁群算法简述蚁群算法简述1.蚁群算法的提出蚁群算法的提出n n算法的提出蚁群算法（Ant Colony Optimization,ACO），又称蚂蚁算法一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system:optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。最早用于解决著名的旅行商问题(TSP,traveling salesman problem)。第1页/共36页1.蚁群算法的提出蚁群算法的提出n n概念原型概念原型各个蚂蚁

2、在没有事先告诉他们食物在什么地方的前提下开始寻找食物。各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone(pheromone(称为信息素称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开

3、辟有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，就可能会出现一条最短的路径被大多数蚂蚁重复着。最后，经过一段时间运行，就可能会出现一条最短的路径被大多数蚂蚁重复着。第2页/共36页1.蚁群算法的提出蚁群算法的提出n n基本原理基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。仿生算法。蚂蚁在运动过程中，能够在它所经过的路径

4、上留下一种称之为蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素外激素(pheromone)(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。上走过的蚂蚁越多，则后来者选择该路径的概率就越大。第3页/共36页1.蚁群算法的提出蚁群算法的提出n n简化的蚂蚁寻食过

5、程简化的蚂蚁寻食过程蚂蚁从蚂蚁从A A点出发，速度相同，食物在点出发，速度相同，食物在DD点，可能随机选择路线点，可能随机选择路线ABDABD或或ACDACD。假设初。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9 9个时间单位时的情形：个时间单位时的情形：走走ABDABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到C C点，为一半路程。点，为一半路程。第4页/共36页1.蚁群算法的提出蚁群算法的提出本图为从开始算起，经过本图为从开始算起，经过1818个时间单位时的情形：走个时间单

6、位时的情形：走ABDABD的蚂蚁的蚂蚁到达终点后得到食物又返回了起点到达终点后得到食物又返回了起点A A，而走，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到DD点。点。第5页/共36页1.蚁群算法的提出蚁群算法的提出假设蚂蚁每经过一处所留下的信息素为一个单位，则经过假设蚂蚁每经过一处所留下的信息素为一个单位，则经过3636个时间单位后，所有个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从开始一起出发的蚂蚁都经过不同路径从DD点取得了食物，此时点取得了食物，此时ABDABD的路线往返了的路线往返了2 2趟，每趟，每一处的信息素为一处的信息素为4 4个单位，而个单位，而 ACDACD的路线往返

7、了一趟，每一处的信息素为的路线往返了一趟，每一处的信息素为2 2个单位，其比个单位，其比值为值为2 2：1 1。寻找食物的过程继续进行，则按信息素的指导，蚁群在寻找食物的过程继续进行，则按信息素的指导，蚁群在ABDABD路线上增派一只蚂蚁（共路线上增派一只蚂蚁（共2 2只），而只），而ACDACD路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过3636个时间单位后，两条线路上的信息素单个时间单位后，两条线路上的信息素单位积累为位积累为1212和和4 4，比值为，比值为3 3：1 1。若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABDABD路线上再增派一只蚂蚁（共路线上再增派一只蚂蚁

8、（共3 3只），而只），而ACDACD路线上仍路线上仍然为一只蚂蚁。再经过然为一只蚂蚁。再经过3636个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为2424和和6 6，比值为，比值为4 4：1 1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACDACD路线，而都选择路线，而都选择ABDABD路路线。这也就是前面所提到的正反馈效应。线。这也就是前面所提到的正反馈效应。第6页/共36页1.蚁群算法的提出蚁群算法的提出n n人工蚁群算法人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁基

9、于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如群，来解决最优化问题，如TSPTSP问题。问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再

10、选择下一条路径的时候是按一定算法规律过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在有意识地寻找最短路径，而不是盲目的。例如在TSPTSP问题中，可以预先问题中，可以预先知道当前城市到下一个目的地的距离。知道当前城市到下一个目的地的距离。第7页/共36页1.蚁群算法的提出蚁群算法的提出n n1)1)标有距离的路径图标有距离的路径图标有距离的路径图标有距离的路径图n n2)2)在在在在0 0时刻，路径上没有信息素累积，蚂蚁选择路径为任意时刻，路径上没有信息素累积，蚂蚁选择路径为任意时刻，路径上没有信息素累积，蚂蚁选择路径为任意时刻，路径上没

11、有信息素累积，蚂蚁选择路径为任意n n3)3)在在在在1 1时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择ABCDEABCDE第8页/共36页2.蚁群算法的特征蚁群算法的特征n n蚁群算法蚁群算法采用了分布式正反馈并行计算机制采用了分布式正反馈并行计算机制,易于与其他方法结合易于与其他方法结合,并具有较强的鲁棒性。并具有较强的鲁棒性。n n（1 1）其原理是一种正反馈机制或称增强型学习系

12、统；）其原理是一种正反馈机制或称增强型学习系统；）其原理是一种正反馈机制或称增强型学习系统；）其原理是一种正反馈机制或称增强型学习系统；它通过信息素的不断更新达到最终收敛它通过信息素的不断更新达到最终收敛于最优路径上；于最优路径上；n n（2 2）它是一种通用型随机优化方法；）它是一种通用型随机优化方法；）它是一种通用型随机优化方法；）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；了人类的智能；n n（3 3）它是一种分布式的优化方法；）它是一种分布式的优化方法；）它是一种分布式的优化方法；）它是一种分

13、布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机；不仅适合目前的串行计算机，而且适合未来的并行计算机；n n（4 4）它是一种全局优化的方法；）它是一种全局优化的方法；）它是一种全局优化的方法；）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；化问题；n n（5 5）它是一种启发式算法；）它是一种启发式算法；）它是一种启发式算法；）它是一种启发式算法；计算复杂性为计算复杂性为 O O(NC*m*n(NC*m*n2 2)，其中，其中NC NC 是迭代次数，是迭代次数，m m 是蚂蚁数目，是蚂

14、蚁数目，n n 是目的节点数目。是目的节点数目。第9页/共36页2.蚁群算法的特征蚁群算法的特征下面是对蚁群算法的进行过程中采用的规则进行的一些说明。下面是对蚁群算法的进行过程中采用的规则进行的一些说明。n n范围范围范围范围蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3 3），那么它能），那么它能观察到的范围就是观察到的范围就是3*33*3个方格世界，并且能移动的距离也在这个范围之内。个方格世界，并且能移动的距离也在这个范围之内。n n环境环境环境环境蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，

15、还有信息素，信息素有蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。n n觅食规则觅食规则觅食规则觅食规则在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较

16、在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。过它对窝的信息素做出反应，而对食物信息素没反应。第10页/共36页2.蚁群算法的特征蚁群算法的特征n n移动规则移动规则移动规则移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运

17、每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。n n避障规则避障规则避障规则避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个

18、方向，并且有信息素指引的话，它会按照觅食的规则行为。照觅食的规则行为。n n信息素规则信息素规则信息素规则信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿纽带，实际上把各个蚂蚁之间关联

19、起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。息素的指引找到了食物。第11页/共36页2.蚁群算法的特征蚁群算法的特征n n基本蚁群算法流程图（详细）1.在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。2.在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它

20、们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息素多的路径走（当然也有随机性）。3.又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。第12页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n一般蚁群算法的框架主要有三个组成部分：1.1.蚁群的活动；2.2.信息素的挥发；3.3.信息素的增

21、强；n n主要体现在转移概率公式和信息素更新公式。第13页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n蚁群算法数学模型在路径搜索过程中，蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移。蚂蚁在在路径搜索过程中，蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移。蚂蚁在时刻由节点转移到节点的状态转移概率如式所示：时刻由节点转移到节点的状态转移概率如式所示：第14页/共36页3.蚁群算法的数学模型蚁群算法的数学模型另外，为了避免残留信息素过多引起残留信息淹没启发信息另外，为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所在每只蚂蚁走完一步或

22、者完成对所有有n n个元素的遍历后个元素的遍历后,要对残留信息进行更新处理。由此要对残留信息进行更新处理。由此,t+n,t+n时刻在路径时刻在路径(i,j)(i,j)上的信息量可按如下规则进上的信息量可按如下规则进行调整其更新规则如下式所示：行调整其更新规则如下式所示：由于信息素更新策略的不同由于信息素更新策略的不同,以及以及城市规模取值在适当范围时，全局搜索能使城市规模取值在适当范围时，全局搜索能使之之得到更优的解，得到更优的解，因此采用因此采用全局信息素更新规则，形式如下：全局信息素更新规则，形式如下：式中，式中，QQ表示蚂蚁循环一周，且在一定程度上影响算法收敛速度的信息素总量；表示蚂蚁循

23、环一周，且在一定程度上影响算法收敛速度的信息素总量；LkLk表示本次循表示本次循环中，蚂蚁环中，蚂蚁k k所走路段的长度。所走路段的长度。第15页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n蚁群的规模和停止规则蚁群的规模和停止规则n n蚁群大小蚁群大小:一般情况下蚁群中蚂蚁的个数不超过一般情况下蚁群中蚂蚁的个数不超过TSPTSP图中节点的个数。图中节点的个数。n n终止条件终止条件:1 1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；2 2 当前最优解连续当前最优解连续K K次相同而停止，其中次相同而停止，其中K K是一个

24、给定的整数，表示算法已经收敛，不再需是一个给定的整数，表示算法已经收敛，不再需要继续；要继续；3 3 目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。的目标值同下界之差小于给定的误差值时，算法终止。第16页/共36页4.蚁群算法的模型类型蚁群算法的模型类型根据信息素更新策略的不同根据信息素更新策略的不同,M.Dorigo,M.Dorigo 曾提出曾提出3 3 种不同的基本蚁群种不同的基本蚁群算法模型算法模型,其差别在于其差别在于k kij ij

25、(t)(t)求法的不同求法的不同,即即:n nAnt-Cycle Ant-Cycle 模型模型n nAnt-Quantity Ant-Quantity 模型模型n nAnt-Density Ant-Density 模型模型其中其中Ant-antity Ant-antity 模型和模型和Ant-Density Ant-Density 模型利用的是局部信息模型利用的是局部信息;而而Ant-Ant-Cycle Cycle 模型利用的是整体信息模型利用的是整体信息,在求解在求解TSP TSP 时性能较好时性能较好,因此通常采用因此通常采用Ant Ant-Cycle-Cycle 模型模型模型模型作为蚁群

26、算法的基本模型。作为蚁群算法的基本模型。第17页/共36页4.蚁群算法的模型类型蚁群算法的模型类型n nAnt-Cycle模型n n式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk k表示第k只蚂蚁在本次循环中所走路径的总长度。第18页/共36页4.蚁群算法的模型类型蚁群算法的模型类型n nAnt-Quantity模型n n Ant-DensityAnt-Density模型模型 第19页/共36页4.蚁群算法的模型类型蚁群算法的模型类型n n区别后两个式子中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而第一个式中利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息

27、素，在求解TSP时性能较好，因此通常采用第一个模型作为蚁群算法的基本模型。第20页/共36页4.蚁群算法的模型类型蚁群算法的模型类型n n下面是一些最常用的下面是一些最常用的变异蚁群算法变异蚁群算法变异蚁群算法变异蚁群算法n n1.1.精英蚂蚁系统精英蚂蚁系统全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素。全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素。n n2.2.最大最小蚂蚁系统（最大最小蚂蚁系统（MMASMMAS）添加的最大和最小的信息素量添加的最大和最小的信息素量 max max，min min，只有全局最佳或迭代最好的巡逻沉积的信息素。所有，只有全局最佳或迭代最好

28、的巡逻沉积的信息素。所有的边缘都被初始化为的边缘都被初始化为maxmax并且当接近停滞时重新初始化为并且当接近停滞时重新初始化为maxmax。n n3.3.蚁群系统蚁群系统蚁群系统已被提出。蚁群系统已被提出。n n4.4.基于排序的蚂蚁系统（基于排序的蚂蚁系统（ASrank ASrank）所有解决方案都根据其长度排名。然后为每个解决方案衡量信息素的沉积量，最短路径相比较长路径所有解决方案都根据其长度排名。然后为每个解决方案衡量信息素的沉积量，最短路径相比较长路径的解沉积了更多的信息素。的解沉积了更多的信息素。n n5.5.连续正交蚁群（连续正交蚁群（COACCOAC）COACCOAC的信息素沉

29、积机制能使蚂蚁协作而有效地寻解。的信息素沉积机制能使蚂蚁协作而有效地寻解。利用正交设计方法，在可行域的蚂蚁可以使用利用正交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。正交设计方法和自适应半径调整方法也可正交设计方法和自适应半径调整方法也可推广到其他优化算法中，在解决实际问题施展更大的威力。推广到其他优化算法中，在解决实际问题施展更大的威力。第21页/共36页5.蚁群算法的优缺点蚁群算法的优缺点蚁群算法的优点：n n蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模

30、型蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。稍加修改，便可以应用于其他问题）和搜索较好解的能力。n n蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。n n蚁群算法很容易与多种启发式算法结合，以改善算法性能。蚁群算法很容易与多种启发式算法结合，以改善算法性能。第22页/共36页5.蚁群算法的优缺点蚁群算法的优缺点蚁群算法存在的问题：蚁群算法存在的问题：n nTSPTSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间

31、距离的条件下，找到一条遍历所有城问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSPTSP问题应用中取得了良好的效果，但是也存问题应用中取得了良好的效果，但是也存在一些不足：在一些不足：（1 1）如果参数设置不当，导致求解速度很慢且所得解的质量特别差。）如果参数设置不当，导致求解速度很慢且所得解的质量特别差。（2 2）基本蚁群算法计算量大，求解所需时间较长。）基本蚁群算法计算量大，求解所需时间较长。（3 3）基本蚁群算法中理论上要求所有的蚂蚁选

32、择同一路线，该线路即为所求的最优线路；但在实际计算中，在给）基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。定一定循环数的条件下很难达到这种情况。另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。蚁群算

33、法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好

34、的解。第23页/共36页6.蚁群算法所解决的问题蚁群算法所解决的问题n n调度问题调度问题调度问题调度问题1.1.车间作业调度问题（车间作业调度问题（JSP JSP）2.2.开放式车间调度问题（开放式车间调度问题（OSP OSP）3.3.排列流水车间问题（排列流水车间问题（PFSP PFSP）4.4.单机总延迟时间问题（单机总延迟时间问题（SMTTP SMTTP）5.5.单机总加权延迟问题（单机总加权延迟问题（SMTWTP SMTWTP）6.6.资源受限项目调度问题（资源受限项目调度问题（RCPSP RCPSP）7.7.车间组调度问题（车间组调度问题（GSP GSP）8.8.附带依赖安装时间顺

35、序的单机总延迟问题（附带依赖安装时间顺序的单机总延迟问题（SMTTPDST SMTTPDST）9.9.附带顺序相依设置附带顺序相依设置/转换时间的多阶段流水车间调度问题（转换时间的多阶段流水车间调度问题（MFSP MFSP）n n车辆路径问题车辆路径问题车辆路径问题车辆路径问题1.1.限量车辆路径问题（限量车辆路径问题（CVRP CVRP）2.2.多站车辆路径问题（多站车辆路径问题（MDVRP MDVRP）3.3.周期车辆路径问题（周期车辆路径问题（PVRP PVRP）4.4.分批配送车辆路径问题（分批配送车辆路径问题（SDVRP SDVRP）5.5.随机车辆路径问题（随机车辆路径问题（SVR

36、P SVRP）6.6.装货配送的车辆路径问题（装货配送的车辆路径问题（VRPPD VRPPD）7.7.带有时间窗的车辆路径问题（带有时间窗的车辆路径问题（VRPTWVRPTW）8.8.依赖时间的时间窗车辆路径问题（依赖时间的时间窗车辆路径问题（TDVRPTW TDVRPTW）9.9.带时间窗和复合服务员工的车辆路径问题（带时间窗和复合服务员工的车辆路径问题（VRPTWMS VRPTWMS）第24页/共36页6.蚁群算法所解决的问题蚁群算法所解决的问题nn分配问题分配问题分配问题分配问题1.1.二次分配问题（二次分配问题（QAPQAP）2.2.广义分配问题（广义分配问题（GAPGAP）3.3.频

37、率分配问题（频率分配问题（FAP FAP）4.4.冗余分配问题（冗余分配问题（RAP RAP）nn设置问题设置问题设置问题设置问题1.1.覆盖设置问题（覆盖设置问题（SCP SCP）2.2.分区设置问题（分区设置问题（SPP SPP）3.3.约束重量的树图划分问题（约束重量的树图划分问题（WCGTPP WCGTPP）4.4.加权弧加权弧L-L-基数树问题（基数树问题（AWlCTP AWlCTP）5.5.多背包问题（多背包问题（MKPMKP）6.6.最大独立集问题（最大独立集问题（MIS MIS）nn其他其他其他其他1.1.面向关系的网络路由面向关系的网络路由2.2.无连接网络路由无连接网络路由

38、3.3.数据挖掘数据挖掘4.4.项目调度中的贴现现金流项目调度中的贴现现金流5.5.分布式信息检索分布式信息检索6.6.网格工作流调度问题网格工作流调度问题7.7.图像处理图像处理8.8.系统识别系统识别9.9.蛋白质折叠蛋白质折叠10.10.电子电路设计电子电路设计第25页/共36页6.蚁群算法所解决的问题蚁群算法所解决的问题蚁群优化算法已应用于许多组合优化问题，包括蛋白质折叠或路由车辆的二次分蚁群优化算法已应用于许多组合优化问题，包括蛋白质折叠或路由车辆的二次分配问题，很多派生的方法已经应用于实变量动力学问题，随机问题，多目标并行的实现。配问题，很多派生的方法已经应用于实变量动力学问题，随

39、机问题，多目标并行的实现。它也被用于产生货郎担问题的拟最优解。在图表动态变化的情况下解决相似问题时，他它也被用于产生货郎担问题的拟最优解。在图表动态变化的情况下解决相似问题时，他们相比模拟退火和遗传算法方法有优势；蚁群算法可以连续运行并适应实时变化。这在们相比模拟退火和遗传算法方法有优势；蚁群算法可以连续运行并适应实时变化。这在网络路由和城市交通系统中是有利的。网络路由和城市交通系统中是有利的。第一蚁群优化算法被称为第一蚁群优化算法被称为“蚂蚁系统蚂蚁系统”，它旨在解决货郎担问题，其目标是要找，它旨在解决货郎担问题，其目标是要找到一系列城市的最短遍历路线。总体算法相对简单，它基于一组蚂蚁，每只

40、完成一次城到一系列城市的最短遍历路线。总体算法相对简单，它基于一组蚂蚁，每只完成一次城市间的遍历。在每个阶段，蚂蚁根据一些规则选择从一个城市移动到另一个：它必须访市间的遍历。在每个阶段，蚂蚁根据一些规则选择从一个城市移动到另一个：它必须访问每个城市一次问每个城市一次;一个越远的城市被选中的机会越少（能见度更低）一个越远的城市被选中的机会越少（能见度更低）;在两个城市边际的一在两个城市边际的一边形成的信息素越浓烈，这边被选择的概率越大边形成的信息素越浓烈，这边被选择的概率越大;如果路程短的话，已经完成旅程的蚂蚁如果路程短的话，已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素，每次迭代后，信息

41、素轨迹挥发。会在所有走过的路径上沉积更多信息素，每次迭代后，信息素轨迹挥发。第26页/共36页6.蚁群算法所解决的问题蚁群算法所解决的问题n n在实验和应用中，蚁群算法有他的优势也有自己的劣势，但若与其他方法相结合，也能对解决问题的可行性和有效性有一在实验和应用中，蚁群算法有他的优势也有自己的劣势，但若与其他方法相结合，也能对解决问题的可行性和有效性有一定的帮助。下面列出与蚁群算法相关的方法定的帮助。下面列出与蚁群算法相关的方法n n遗传算法（遗传算法（GAGA）支持一系列的解决方案。解的合并或突变增加了解集，其中质量低劣的解被丢弃，寻找高级解决方案的过）支持一系列的解决方案。解的合并或突变增

42、加了解集，其中质量低劣的解被丢弃，寻找高级解决方案的过程模仿了这一演变。程模仿了这一演变。n n模拟退火（模拟退火（SASA）是一个全局优化相关）是一个全局优化相关的通过产生当前解的相邻解来遍历搜索空间的技术。高级的相邻解总是可接受的。低的通过产生当前解的相邻解来遍历搜索空间的技术。高级的相邻解总是可接受的。低级的相邻解可能会根据基于质量和温度参数德差异的概率被接受。温度参数随着算法的进程被修改以改变搜索的性质。级的相邻解可能会根据基于质量和温度参数德差异的概率被接受。温度参数随着算法的进程被修改以改变搜索的性质。n n反作用搜索优化的重点在于将机器学习与优化的结合，加入内部反馈回路以根据问题

43、、根据实例、根据当前解的附近情况反作用搜索优化的重点在于将机器学习与优化的结合，加入内部反馈回路以根据问题、根据实例、根据当前解的附近情况的特点自动调整算法的自由参数。的特点自动调整算法的自由参数。n n禁忌搜索（禁忌搜索（TS TS）类似于模拟退火，他们都是通过测试独立解的突变来遍历解空间的。而模拟退火算法对于一个独立解只生）类似于模拟退火，他们都是通过测试独立解的突变来遍历解空间的。而模拟退火算法对于一个独立解只生成一个突变，禁忌搜索会产生许多变异解并且移动到产生的解中的符合度最低的一个。为了防止循环并且促进在解空间中成一个突变，禁忌搜索会产生许多变异解并且移动到产生的解中的符合度最低的一

44、个。为了防止循环并且促进在解空间中的更大进展，由部分或完整的解组建维系了一个禁忌列表。移动到元素包含于禁忌列表的解是禁止，禁忌列表随着解遍历的更大进展，由部分或完整的解组建维系了一个禁忌列表。移动到元素包含于禁忌列表的解是禁止，禁忌列表随着解遍历解空间的过程而不断更新。解空间的过程而不断更新。n n人工免疫系统（人工免疫系统（AISAIS）算法仿照了脊椎动物的免疫系统。）算法仿照了脊椎动物的免疫系统。n n粒子群优化（粒子群优化（PSO PSO），群智能方法），群智能方法n n引力搜索算法（引力搜索算法（GSA GSA），群智能方法），群智能方法n n蚁群聚类方法（蚁群聚类方法（ACCMACC

45、M中）中），这个方法利用了聚类方法扩展了蚁群优化。，这个方法利用了聚类方法扩展了蚁群优化。n n随机传播搜索（随机传播搜索（SDS SDS），基于代理的概率全局搜索和优化技术，最适合于将目标函数分解成多个独立的分布函数的优化问），基于代理的概率全局搜索和优化技术，最适合于将目标函数分解成多个独立的分布函数的优化问题。题。第27页/共36页7.蚁群算法的应用蚁群算法的应用n n应用领域蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统

46、辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。第28页/共36页7.蚁群算法的应用蚁群算法的应用n n蚁群算法的模型改进及其应用近年来,国内外学者在蚁群算法的模型改进和应用方面做了大量的工作,其共同目的是在合理时间复杂度的限制条件下,尽可能提高蚁群算法在一定空间复杂度下的寻优能力,从而改善蚁群算法的全局收敛性,并拓宽蚁群算法的应用领域。(部分的蚁群算法改进模型及其应用情况-附Pr-1)第29页/共36页7.蚁群算法的应用蚁群算法的应用n n蚁群优化算法应用现状蚁群优化算法应用现状随着群智能理论和应用算法研究的不断发展，研究者已尝试着将随着群智能理论和应用算法研究的不断发展，研究

47、者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在群智能在离散求解空间和连续求解空间离散求解空间和连续求解空间中均表现出良好的搜索效果，并中均表现出良好的搜索效果，并在组合优化问题中表现突出。在组合优化问题中表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以

48、及一些经典的组合优典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。化问题。第30页/共36页7.蚁群算法的应用蚁群算法的应用蚁群算法在电信路由优化中已取得了一定的应用成果。蚁群算法在电信路由优化中已取得了一定的应用成果。HPHP公司和英国电信公司和英国电信公司在公司在9090年代中后期都开展了这方面的研究，设计了年代中后期都开展了这方面的研究，设计了蚁群路由算法蚁群路由算法（Ant Colony Ant Colony Routing,ACRRouting,ACR）。）。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路每只蚂蚁就像蚁群优化算法中一样，根

49、据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，ACRACR算法就能算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用

50、率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与动态特性以及网络状态的异步演化与ACOACO的算法本质和特性非常相似。的算法本质和特性非常相似。第31页/共36页7.蚁群算法的应用蚁群算法的应用基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。LumerLumer和和FaietaFaieta将将DeneubourgDeneubourg提出将蚁巢分类模型应用于数据聚类分析。其基本提出将蚁巢分类模型应用于数据聚类分析。其基本思