文档介绍：该【蚁群算法及其应用讲座】是由【wxq362】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【蚁群算法及其应用讲座】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。蚁群算法及其应用
1
第一页,共三十五页。
启发式算法_分类
现代优化算法:
80年代初兴起
禁忌搜索(tabusearch)
模拟退火(simulatedannealing)
神经网络(neuralnetworks)
遗传算法(geneticalgorithms)
蚂蚁算法(AntAlgorithm,群体智能,SwarmIntelligence)
2
第二页,共三十五页。
遗传算法
遗传算法(Genetic Algorithm, GA)是1962年密切根大学Holland教授首次提出的一种全局优化算法,它借用了生物遗传学的观点,通过自然选择、遗传、变异等作用机制,实现各个体的适应性的提高,并迅速推广到优化、搜索、机器学****等方面。
3
第三页,共三十五页。
遗传算法的过程
编码和初始群体生成
个体适应度的评测(适值函数)
选择
交叉
变异
4
第四页,共三十五页。
蚁群算法
1原理
2在TSP中的应用及改进
3在QoS多播路由中的应用
5
第五页,共三十五页。
1蚁群算法原理
20世纪90年代初,意大利学者Dorigo等受蚂蚁觅食行为的启发,提出了蚁群算法,是一种仿生算法。
蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径,为什么?
(1)信息素(pheromone)
(2)正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
6
第六页,共三十五页。
简化的蚂蚁寻食过程
蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚好走到C点,为一半路程。
7
第七页,共三十五页。
简化的蚂蚁寻食过程
经过18个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。
8
第八页,共三十五页。
自然蚁群与人工蚁群
相似之处在于:都是优先选择信息素浓度大的路径。
两者的区别:
(1)在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。
(2)人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如,在TSP问题中,可以预先知道当前城市到下一个目的地的距离。
9
第九页,共三十五页。
应用一:TSP问题
旅行商问题(TSP,travelingsalesmanproblem)1960年首先提出。
问题描述:
一商人去n个城市销货,所有城市走一遍再回到起点,使所走路程最短。
TSP在许多工程领域具有广泛的应用价值
例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。
TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。
10
第十页,共三十五页。