蚁群算法及其应用讲座ppt课件

1、蚁群算法及其运用启发式算法_分类现代优化算法：现代优化算法： 80年代初兴起年代初兴起忌讳搜索忌讳搜索tabu search模拟退火模拟退火simulated annealing神经网络神经网络neural networks遗传算法遗传算法genetic algorithms蚂蚁算法蚂蚁算法Ant Algorithm，群体智能，群体智能，Swarm Intelligence遗传算法 n遗传算法(Genetic Algorithm, GA)是1962年亲密根大学Holland教授初次提出的一种全局优化算法，它借用了生物遗传学的观念，经过自然选择、遗传、变异等作用机制，实现各个体的顺应性的提高，并

2、迅速推行到优化、搜索、机器学习等方面。 遗传算法的过程 编码和初始群体生成编码和初始群体生成个体顺应度的评测个体顺应度的评测(适值函数适值函数 )选择选择交叉交叉变异变异蚁群算法1 1 原理原理2 2 在在TSPTSP中的运用及改良中的运用及改良3 3 在在QoSQoS多播路由中的运用多播路由中的运用1 蚁群算法原理n20 20 世纪世纪90 90 年代初，意大利学者年代初，意大利学者Dorigo Dorigo 等等受蚂蚁寻食行为的启发，提出了蚁群算法，是受蚂蚁寻食行为的启发，提出了蚁群算法，是一种仿生算法。一种仿生算法。n蚂蚁在寻食过程中可以找出巢穴到食物源的最蚂蚁在寻食过程中可以找出巢穴到

3、食物源的最短途径，为什么？短途径，为什么？n1 1信息素信息素(pheromone)(pheromone)n2 2正反响景象：某一途径上走过的正反响景象：某一途径上走过的蚂蚁越多，那么后来者选择该途径的概率就越蚂蚁越多，那么后来者选择该途径的概率就越大。大。简化的蚂蚁寻食过程蚂蚁从蚂蚁从A A点出发，速度一样，食物在点出发，速度一样，食物在D D点，能够随机点，能够随机选择道路选择道路ABDABD或或ACDACD。假设初始时每条分配道路一只。假设初始时每条分配道路一只蚂蚁，每个时间单位行走一步，本图为经过蚂蚁，每个时间单位行走一步，本图为经过9 9个时个时间单位时的情形：走间单位时的情形：走A

4、BDABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到C C点，为一半路程。点，为一半路程。简化的蚂蚁寻食过程经过经过1818个时间单位时的情形：走个时间单位时的情形：走ABDABD的蚂蚁到达的蚂蚁到达终点后得到食物又前往了起点终点后得到食物又前往了起点A A，而走，而走ACDACD的蚂蚁的蚂蚁刚好走到刚好走到D D点。点。自然蚁群与人工蚁群类似之处在于：都是优先选择信息素浓度大的途径。类似之处在于：都是优先选择信息素浓度大的途径。两者的区别：两者的区别：1在于人工蚁群有一定的记忆才干，可以记忆在于人工蚁群有一定的记忆才干，可以记忆曾经访问过的节点。曾经访问

5、过的节点。2人工蚁群选择途径时不是盲目的。而是按一人工蚁群选择途径时不是盲目的。而是按一定规律有认识地寻觅最短途径。例如，在定规律有认识地寻觅最短途径。例如，在TSP问题中，可问题中，可以预先知道当前城市到下一个目的地的间隔。以预先知道当前城市到下一个目的地的间隔。运用一：TSP问题n游览商问题游览商问题TSP,traveling salesman TSP,traveling salesman problemproblem19601960年首先提出。年首先提出。n问题描画：问题描画：n一商人去一商人去n n个城市销货，一切城市走一个城市销货，一切城市走一遍再回到起点，使所走路程最短。遍再回到起

6、点，使所走路程最短。nTSPTSP在许多工程领域具有广泛的运用价值在许多工程领域具有广泛的运用价值n例如电路板布线、例如电路板布线、VLSIVLSI芯片设计、机芯片设计、机器人控制、交通路由等。器人控制、交通路由等。nTSPTSP的求解是的求解是NP-hardNP-hard问题。随着城市数目的增问题。随着城市数目的增多多, ,问题空间将呈指数级增长。问题空间将呈指数级增长。 TSP问题的数学描画TSP问题表示为一个问题表示为一个N个城市的有向图个城市的有向图G=N，A，其中，其中城市之间间隔城市之间间隔目的函数为目的函数为其中，其中， ，为城市，为城市1,2，n的的一个陈列，一个陈列， 。,

7、|j), (iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin蚂蚁算法求解TSPn下面以下面以TSPTSP为例阐明根本蚁群算法模型。为例阐明根本蚁群算法模型。n首先将首先将m m只蚂蚁随机放置在只蚂蚁随机放置在n n个城市，位个城市，位于城市于城市i i的第的第k k只蚂蚁选择下一个城市只蚂蚁选择下一个城市j j的的概率为概率为: : 蚂蚁算法求解TSP其中：其中：表示边表示边i i，j j上的信息素浓度；上的信息素浓度； 是启发信息，是启发信息，d d是城市是城市i i和和j j之间的间隔；之间的间隔； 和和反映了信息素与启发信息的相对重要性；

8、反映了信息素与启发信息的相对重要性；表示蚂蚁表示蚂蚁k k曾经访问过的城市列表。曾经访问过的城市列表。 当一切蚂蚁完成周游后，按以下公式进展信息素更新。当一切蚂蚁完成周游后，按以下公式进展信息素更新。 ) 1 (,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(/1),(jidji),(jiktabu蚂蚁算法求解TSPn其中：其中：为小于为小于1 1的常数，表示信息的耐久性。的常数，表示信息的耐久性。)2()()(1mkkijijijijijtnt) 3(0otherwiselijLQkkkijn其中：其中：Q Q为常数；为常数；l

9、klk表示第表示第k k只蚂蚁在本次迭代只蚂蚁在本次迭代中走过的途径，中走过的途径，LkLk为途径长度。为途径长度。 求解求解TSPTSP算法步骤算法步骤 初始化随机放置蚂蚁，为每只蚂蚁建立忌讳表初始化随机放置蚂蚁，为每只蚂蚁建立忌讳表tabuktabuk，将初始节，将初始节点置入忌讳表中点置入忌讳表中; ;迭代过程迭代过程k=1k=1while k=ItCount do (while k=ItCount do (执行迭代执行迭代) )for i = 1 to m do (for i = 1 to m do (对对m m只蚂蚁循环只蚂蚁循环) ) for j = 1 to n - 1 do (

10、 for j = 1 to n - 1 do (对对n n个城市循环个城市循环) ) 根据式根据式(1)(1)，采用轮盘赌方法在窗口外选择下一个城市，采用轮盘赌方法在窗口外选择下一个城市j;j; 将将j j置入忌讳表置入忌讳表, ,蚂蚁转移到蚂蚁转移到j;j; end for end for end for end for 计算每只蚂蚁的途径长度计算每只蚂蚁的途径长度; ; 根据式根据式(2)(2)更新一切蚂蚁途径上的信息量更新一切蚂蚁途径上的信息量; ; k = k + 1; k = k + 1;end whileend while输出结果输出结果, ,终了算法终了算法. .蚁群的规模和停顿

11、规那么一、蚁群大小一、蚁群大小 普通情况下蚁群中蚂蚁的个数不超越普通情况下蚁群中蚂蚁的个数不超越TSPTSP图中节点的个图中节点的个数。数。二、终止条件二、终止条件 1 1 给定一个外循环的最大数目；给定一个外循环的最大数目； 2 2 当前最优解延续当前最优解延续K K次一样而停顿，其中次一样而停顿，其中K K是一个给定是一个给定的整数，表示算法曾经收敛，不再需求继续。的整数，表示算法曾经收敛，不再需求继续。蚂蚁算法的缺陷蚂蚁算法的缺陷蚂蚁算法的缺陷：蚂蚁算法的缺陷：1 1收敛速度慢收敛速度慢2 2易于堕入部分最优易于堕入部分最优改良：改良：1 1采用部分优化，设计了三种优化算子。采用部分优化

12、，设计了三种优化算子。2 2采用蚁群优化算法。采用蚁群优化算法。3 3其它优化算法其它优化算法改良一：部分优化算子改良一：部分优化算子1 1 n对Kroa100，算子1优化前后的途径如下图。优化前28596，算子1优化后26439 改良一：部分优化算子改良一：部分优化算子2 n对Kroa100，算子2优化前后的途径如下图。算子126439，算子2优化后23012 nTSPTSP具有邻域特征，设置候选窗口，窗口大小应具有邻域特征，设置候选窗口，窗口大小应取一个合理值。取一个合理值。n蚂蚁总是优先选择候选窗口中的城市。搜索终蚂蚁总是优先选择候选窗口中的城市。搜索终了后，根据候选窗口对途径进展优化，

13、假设将候了后，根据候选窗口对途径进展优化，假设将候选窗口内的节点交换到当前节点附近后间隔更短，选窗口内的节点交换到当前节点附近后间隔更短，那么进展变异。那么进展变异。 改良一：部分优化算子改良一：部分优化算子3 n对Kroa100，算子3优化前后的途径如下图。23012，算子3优化后21282 收敛特性对比 改良二：蚁群优化算法n1)ACS采用了更为大胆的行为选择规那么，在城市r的蚂蚁k转移到城市s的规那么为:2.1.4蚁群优化算法第三，仅对全局最优解边上的信息素进展加强，更新如下第三，仅对全局最优解边上的信息素进展加强，更新如下: :其它改良1精英战略2基于排序的蚂蚁系统3 MAX-MIN蚂

14、蚁系统运用二：QoS多播路由问题什么是多播路由？什么是多播路由？构造一棵费用最小的多播树，且满足构造一棵费用最小的多播树，且满足以下限制条件：以下限制条件：(1) d(T(s, D)D (1) d(T(s, D)D 延时延时(2) dj(T(s, D)DJ (2) dj(T(s, D)DJ 抖动抖动(3) pl(T(s, D)PL (3) pl(T(s, D)PL 丢包率丢包率(4) b(T(s, D)B. (4) b(T(s, D)B. 带宽带宽途径的QoS参数计算(1)d(n)d(e)dd(p(s,)dp(s,n)dp(s,eiii(2)dj(n)dj(e)ddj(p(s,)dp(s,n)

15、d p(s,eiii(3)(1 (1)dpl(p(s,)p(s,dniinpl多播树的QoS参数计算(4)|),(maxD)d(T(s,Dddspdii)5(|),(maxD)dj(T(s,Dddspdjii)6(|),(maxD)pl(T(s,Dddspplii)7(),(| )(minD)b(T(s,DsTeeb)8(c(n)c(e)D)c(T(s,D)(s,nD)(s,eTT算法n方法方法1 1：用蚁群算法找到去每一个目的节：用蚁群算法找到去每一个目的节点的点的QoSQoS最优途径，再交融。最优途径，再交融。n方法方法2 2：找到一条：找到一条QoSQoS最优途径，其它目最优途径，其它目的节点再依次参与多播树中。的节点再依次参与多播树中。12356478(18,3,100,9)(8,1,110,21)(4,1,130,10)(12,2,80,