蚁群算法及其应用讲座课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《蚁群算法及其应用讲座课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 及其 应用 讲座 课件
- 资源描述:
-
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页。蚂蚁算法求
展开阅读全文