《蚁群算法及其应用讲座.ppt》由会员分享,可在线阅读,更多相关《蚁群算法及其应用讲座.ppt(34页珍藏版)》请在三一办公上搜索。
1、蚁群算法及其应用,启发式算法_分类,现代优化算法:80年代初兴起禁忌搜索(tabu search)模拟退火(simulated annealing)神经网络(neural networks)遗传算法(genetic algorithms)蚂蚁算法(Ant Algorithm,群体智能,Swarm Intelligence),遗传算法,遗传算法(GeneticAlgorithm,GA)是1962年密切根大学Holland教授首次提出的一种全局优化算法,它借用了生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个体的适应性的提高,并迅速推广到优化、搜索、机器学习等方面。,遗传算法的过程,
2、蚁群算法,1 原理2 在TSP中的应用及改进3 在QoS多播路由中的应用,1 蚁群算法原理,20 世纪90 年代初,意大利学者Dorigo 等受蚂蚁觅食行为的启发,提出了蚁群算法,是一种仿生算法。蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径,为什么?(1)信息素(pheromone)(2)正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。,简化的蚂蚁寻食过程,蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚好走到C点,为一半
3、路程。,简化的蚂蚁寻食过程,经过18个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。,自然蚁群与人工蚁群,相似之处在于:都是优先选择信息素浓度大的路径。两者的区别:(1)在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。(2)人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如,在TSP问题中,可以预先知道当前城市到下一个目的地的距离。,应用一:TSP问题,旅行商问题(TSP,traveling salesman problem)1960年首先提出。问题描述:一商人去n个城市销货,所有城市走一遍再回到起点,使所走路程最短
4、。TSP在许多工程领域具有广泛的应用价值例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。,TSP问题的数学描述,TSP问题表示为一个N个城市的有向图G=(N,A),其中城市之间距离目标函数为其中,为城市1,2,n的一个排列,。,蚂蚁算法求解TSP,下面以TSP为例说明基本蚁群算法模型。首先将m只蚂蚁随机放置在n个城市,位于城市i的第k只蚂蚁选择下一个城市j的概率为:,蚂蚁算法求解TSP,其中:表示边(i,j)上的信息素浓度;是启发信息,d是城市i和j之间的距离;和反映了信息素与启发信息的相对重要性;表示蚂蚁
5、k已经访问过的城市列表。当所有蚂蚁完成周游后,按以下公式进行信息素更新。,蚂蚁算法求解TSP,其中:为小于1的常数,表示信息的持久性。,其中:Q为常数;lk表示第k只蚂蚁在本次迭代中走过的路径,Lk为路径长度。,求解TSP算法步骤,初始化随机放置蚂蚁,为每只蚂蚁建立禁忌表tabuk,将初始节点置入禁忌表中;迭代过程k=1while k=ItCount do(执行迭代)for i=1 to m do(对m只蚂蚁循环)for j=1 to n-1 do(对n个城市循环)根据式(1),采用轮盘赌方法在窗口外选择下一个城市j;将j置入禁忌表,蚂蚁转移到j;end for end for 计算每只蚂蚁的
6、路径长度;根据式(2)更新所有蚂蚁路径上的信息量;k=k+1;end while输出结果,结束算法.,蚁群的规模和停止规则,一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件 1 给定一个外循环的最大数目;2 当前最优解连续K次相同而停止,其中K是一个给定的整数,表示算法已经收敛,不再需要继续。,蚂蚁算法的缺点,蚂蚁算法的缺点:1)收敛速度慢2)易于陷入局部最优改进:1)采用局部优化,设计了三种优化算子。2)采用蚁群优化算法。3)其它优化算法,改进一:局部优化(算子1),对Kroa100,算子1优化前后的路径如图所示。优化前(28596),算子1优化后(26439
7、),改进一:局部优化(算子2),对Kroa100,算子2优化前后的路径如图所示。算子1(26439),算子2优化后(23012),TSP具有邻域特征,设置候选窗口,窗口大小应取一个合理值。蚂蚁总是优先选择候选窗口中的城市。搜索结束后,根据候选窗口对路径进行优化,如果将候选窗口内的节点交换到当前节点附近后距离更短,则进行变异。,改进一:局部优化(算子3),对Kroa100,算子3优化前后的路径如图所示。(23012),算子3优化后(21282),收敛特性对比,改进二:蚁群优化算法,1)ACS采用了更为大胆的行为选择规则,在城市r的蚂蚁k转移到城市s的规则为:,蚁群优化算法,第三,仅对全局最优解边上的信息素进行加强,更新如下:,其它改进,1)精英策略2)基于排序的蚂蚁系统3)MAX-MIN蚂蚁系统,应用二:QoS多播路由问题,什么是多播路由?构造一棵费用最小的多播树,且满足以下限制条件:(1)d(T(s,D)D(延时)(2)dj(T(s,D)DJ(抖动)(3)pl(T(s,D)PL(丢包率)(4)b(T(s,D)B.(带宽),路径的QoS参数计算,多播树的QoS参数计算,算法,方法1:用蚁群算法找到去每一个目的节点的QoS最优路径,再融合。方法2:找到一条QoS最优路径,其它目的节点再依次加入多播树中。,随机图实验,边的概率:,Thats all.Thanks!,Thanks,