1、蚁群算法及其应用1第1页，共34页。启发式算法_分类现代优化算法：现代优化算法：80年代初兴起n禁忌搜索（tabu search）n模拟退火（simulated annealing）n神经网络（neural networks）n遗传算法（genetic algorithms）n蚂蚁算法（Ant Algorithm，群体智能，Swarm Intelligence）2第2页，共34页。遗传算法 n遗传算法(Genetic Algorithm,GA)是1962年密切根大学Holland教授首次提出的一种全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个体的适应性的提
2、高，并迅速推广到优化、搜索、机器学习等方面。3第3页，共34页。遗传算法的过程 编码和初始群体生成编码和初始群体生成个体适应度的评测个体适应度的评测(适值函数适值函数)选择选择交叉交叉变异变异4第4页，共34页。蚁群算法1 1 原理原理2 2 在在TSPTSP中的应用及改进中的应用及改进3 3 在在QoSQoS多播路由中的应用多播路由中的应用5第5页，共34页。1 蚁群算法原理n20 20 世纪世纪90 90 年代初，意大利学者年代初，意大利学者Dorigo Dorigo 等等受蚂蚁觅食行为的启发，提出了蚁群算法，是受蚂蚁觅食行为的启发，提出了蚁群算法，是一种一种仿生算法仿生算法。n蚂蚁在觅食
3、过程中可以找出巢穴到食物源的最蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径，为什么？短路径，为什么？（1 1）信息素信息素(pheromone)(pheromone)（2 2）正反馈正反馈现象：某一路径上走过的蚂蚁现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。越多，则后来者选择该路径的概率就越大。6第6页，共34页。简化的蚂蚁寻食过程蚂蚁从蚂蚁从A A点出发，速度相同，食物在点出发，速度相同，食物在D D点，可能随机点，可能随机选择路线选择路线ABDABD或或ACDACD。假设初始时每条分配路线一只。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过蚂蚁，每个
4、时间单位行走一步，本图为经过9 9个时个时间单位时的情形：走间单位时的情形：走ABDABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到C C点，为一半路程。点，为一半路程。7第7页，共34页。简化的蚂蚁寻食过程经过经过1818个时间单位时的情形：走个时间单位时的情形：走ABDABD的蚂蚁到达的蚂蚁到达终点后得到食物又返回了起点终点后得到食物又返回了起点A A，而走，而走ACDACD的蚂蚁的蚂蚁刚好走到刚好走到D D点。点。8第8页，共34页。自然蚁群与人工蚁群相似之处相似之处在于：都是优先选择信息素浓度大的路径。在于：都是优先选择信息素浓度大的路径。两者的区
5、别两者的区别：（1）在于人工蚁群有一定的记忆能力，能够记忆）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。已经访问过的节点。（2）人工蚁群选择路径时不是盲目的。而是按一）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在定规律有意识地寻找最短路径。例如，在TSP问题中，可问题中，可以预先知道当前城市到下一个目的地的距离。以预先知道当前城市到下一个目的地的距离。9第9页，共34页。应用一：TSP问题n旅行商问题旅行商问题（TSP,traveling salesman problemTSP,traveling salesman problem）19601960年首
6、先提出。年首先提出。n问题描述问题描述：一商人去一商人去n n个城市销货，所有城市走一遍再回到起个城市销货，所有城市走一遍再回到起点，使所走路程最短。点，使所走路程最短。nTSPTSP在许多工程领域具有广泛的在许多工程领域具有广泛的应用价值应用价值例如电路板布线、例如电路板布线、VLSIVLSI芯片设计、机器人控制、芯片设计、机器人控制、交通路由等。交通路由等。nTSPTSP的求解是的求解是NP-hardNP-hard问题问题。随着城市数目的增多。随着城市数目的增多,问问题空间将呈指数级增长。题空间将呈指数级增长。10第10页，共34页。TSP问题的数学描述TSP问题表示为一个问题表示为一个N
7、个城市的有向图个城市的有向图G=（N，A），其中），其中城市之间距离城市之间距离目标函数为目标函数为其中，其中，为城市，为城市1,2，nn的的一个排列，一个排列，。,|j),(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin11第11页，共34页。蚂蚁算法求解TSPn下面以下面以TSPTSP为例说明基本蚁群算法模型。为例说明基本蚁群算法模型。n首先将首先将m m只蚂蚁随机放置在只蚂蚁随机放置在n n个城市，位个城市，位于城市于城市i i的第的第k k只蚂蚁选择下一个城市只蚂蚁选择下一个城市j j的的概率为概率为:12第12页，共34页。蚂蚁算法
8、求解TSP其中：其中：表示边（表示边（i i，j j）上的信息素浓度；）上的信息素浓度；是启发信息，是启发信息，d d是城市是城市i i和和j j之间的距离；之间的距离；和和反映了信息素与启发信息的相对重要性；反映了信息素与启发信息的相对重要性；表示蚂蚁表示蚂蚁k k已经访问过的城市列表。已经访问过的城市列表。当所有蚂蚁完成周游后，按以下公式进行信息素更新。当所有蚂蚁完成周游后，按以下公式进行信息素更新。)1(,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(/1),(jidji),(jiktabu13第13页，共34页。蚂蚁算法求
9、解TSPn其中：其中：为小于为小于1 1的常数，表示信息的持久性。的常数，表示信息的持久性。)2()()(1mkkijijijijijtnt)3(0otherwiselijLQkkkijn其中：其中：Q Q为常数；为常数；l lk k表示第表示第k k只蚂蚁在本次迭代中走过只蚂蚁在本次迭代中走过的路径，的路径，L Lk k为路径长度。为路径长度。14第14页，共34页。求解求解TSPTSP算法步骤算法步骤 初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表tabutabuk k，将初始节点置入，将初始节点置入禁忌表中禁忌表中;迭代过程迭代过程k=1k=1while
10、 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 (for j=1 to n-1 do (对对n n个城市循环个城市循环)根据式根据式(1)(1)，采用轮盘赌方法在窗口外选择下一个城市，采用轮盘赌方法在窗口外选择下一个城市j;j;将将j j置入禁忌表置入禁忌表,蚂蚁转移到蚂蚁转移到j;j;end forend for end for end for 计算每只蚂蚁的路径长度计算每只蚂蚁的路径长度;根据式根据式(2)(2)更新所有
11、蚂蚁路径上的信息量更新所有蚂蚁路径上的信息量;k=k+1;k=k+1;end whileend while输出结果输出结果,结束算法结束算法.15第15页，共34页。蚁群的规模和停止规则一、蚁群大小一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过一般情况下蚁群中蚂蚁的个数不超过TSPTSP图中节点的个数。图中节点的个数。二、终止条件二、终止条件 1 1 给定一个外循环的最大数目；给定一个外循环的最大数目；2 2 当前最优解连续当前最优解连续K K次相同而停止，其中次相同而停止，其中K K是一个给定的整数，是一个给定的整数，表示算法已经收敛，不再需要继续。表示算法已经收敛，不再需要继续。16第16
12、页，共34页。蚂蚁算法的缺点蚂蚁算法的缺点蚂蚁算法的缺点：蚂蚁算法的缺点：n1 1）收敛速度慢）收敛速度慢n2 2）易于陷入局部最优）易于陷入局部最优改进：改进：1 1）采用局部优化，设计了三种优化算子。）采用局部优化，设计了三种优化算子。2 2）采用蚁群优化算法。）采用蚁群优化算法。3 3）其它优化算法）其它优化算法17第17页，共34页。改进一：局部优化（算子改进一：局部优化（算子1 1）18第18页，共34页。n对Kroa100，算子1优化前后的路径如图所示。优化前（28596），算子1优化后（26439）19第19页，共34页。改进一：局部优化（算子改进一：局部优化（算子2）20第20
13、页，共34页。n对Kroa100，算子2优化前后的路径如图所示。算子1（26439），算子2优化后（23012）21第21页，共34页。nTSPTSP具有邻域特征，设置候选窗口，窗口大小应取一具有邻域特征，设置候选窗口，窗口大小应取一个合理值。个合理值。n蚂蚁总是优先选择候选窗口中的城市。搜索结束后，蚂蚁总是优先选择候选窗口中的城市。搜索结束后，根据候选窗口对路径进行优化，如果将候选窗口内的根据候选窗口对路径进行优化，如果将候选窗口内的节点交换到当前节点附近后距离更短，则进行变异。节点交换到当前节点附近后距离更短，则进行变异。改进一：局部优化（算子改进一：局部优化（算子3）22第22页，共34
14、页。n对Kroa100，算子3优化前后的路径如图所示。（23012），算子3优化后（21282）23第23页，共34页。收敛特性对比 24第24页，共34页。改进二：蚁群优化算法n1)ACS采用了更为大胆的行为选择规则，在城市r的蚂蚁k转移到城市s的规则为:25第25页，共34页。2.1.4蚁群优化算法第三，仅对全局最优解边上的信息素进行加强，更新如下第三，仅对全局最优解边上的信息素进行加强，更新如下:26第26页，共34页。其它改进1）精英策略2）基于排序的蚂蚁系统3）MAX-MIN蚂蚁系统27第27页，共34页。应用二：QoS多播路由问题什么是多播路由什么是多播路由？构造一棵费用最小的多播
15、树，且满足构造一棵费用最小的多播树，且满足以下限制条件：以下限制条件：(1)(1)d(T(s,D)D d(T(s,D)D （延时）（延时）(2)(2)dj(T(s,D)DJ dj(T(s,D)DJ（抖动）（抖动）(3)(3)pl(T(s,D)pl(T(s,D)PPL L（丢包率）（丢包率）(4)(4)b(T(s,D)B b(T(s,D)B.（带宽）（带宽）28第28页，共34页。路径的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)d p(s,eiii(3)(1(1)dpl(p(s,)p(s,dnii
16、npl29第29页，共34页。多播树的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,eTT30第30页，共34页。算法n方法方法1 1：用蚁群算法找到去每一个目的节：用蚁群算法找到去每一个目的节点的点的QoSQoS最优路径，再融合。最优路径，再融合。n方法方法2 2：找到一条：找到一条QoSQoS最优路径，其它目最优路径，其它目的节点再依次加入多播树中。
17、的节点再依次加入多播树中。31第31页，共34页。12356478(18,3,100,9)(8,1,110,21)(4,1,130,10)(12,2,80,12)(9,3,40,7)(12,2,120,4)(9,0,80,2)(7,2,90,6)(10,2,75,8)(3,0,80,3)(3,1,90,3)(1,1,10-5,4)(1,1,10-6,11)(3,1,10-6,2)(5,1,10-4,1)(2,0,10-7,9)(7,31,10-3,3)(2,0,10-6,7)(11,1,10-4,5)(6,1,30,8)(9,1,120,1)(6,0,70,4)32第32页，共34页。随机图实验边的概率：33第33页，共34页。Thats all.Thanks!Thanks34第34页，共34页。
