张俊豪张晓玉刘苏娜——人工蚁群算法介绍分析.pptx

人工蚁群算法; 人工蚁群算法是人们对自然界中蚁群行为的研究结果而提出的一种新型仿生类算法。最早是由意大利学者M.Dorigo等人首先提出, 并且成功地用于求解TSP问题, 引起了人们的关注。;一种用来寻找最优解决方案的机率型技术 蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径,其选择一条路径的概率与该路径上分泌物的强度成正比, 即信息素(pheromone)强度越高的路径, 选择它的蚂蚁会越多。反之, 路径上经过的蚂蚁越多, 则在该路径上留下的信息素的其强度就更大;考虑一个简单的例子;为什么小小的蚂蚁能完成如此复杂的工作呢？ 简单规则的涌现 事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来;TSP问题可以表示为一幅图（N,E)，其中N是城市的集合，E是城市之间路径的集合;最初的蚁群算法被称为“蚂蚁系统”。 算法初始阶段，每个城市都放置一定数量的蚂蚁，在算法的每一阶段，每个蚂蚁都根据一定的规则从一个城市移动到另外一个城市。规则介绍如下： 1.在一轮寻优完成之前，每个蚂蚁都经过每个城市一次 2.在每一阶段，距离远的城市被选择作为下一目的地的概率很小 3.两个城市之间的路径上的信息素量越多，则该路径被选择的概率就越大 4.在特定的时间，每个蚂蚁都会在经过的路径上添加信息素 5.路径上已存在的信息素会随着时间的推移而挥发 ; 算法中一些重要的变量和公式： ;在最初的“蚂蚁系统”中;为了保证每个蚂蚁能够访问到所有的城市一次，必须设置一个“禁忌列表-tabu”，这个列表保存某个蚂蚁已经访问过的城市，根据这个列表就可以防止某个城市被重复访问 规则中明确表示，距离远的城市成为下一个目的地的概率会比较小。设置变量: ;从城市i移动到城市j的概率： ;算法的流程;蚁群算法以其分布式并发性, 正反馈, 鲁棒性强, 收敛速度快, 易获得全局最优解等特点, 成为目前国内启发式算法研究的热点, 但是蚁群算法也存在如下缺点: 容易出现停滞现象( stagnation behaviour) , 算法运算时间过长。针对这些缺陷, 近年来众多国内外的学者在蚁群的改进方面做了大量的研究工作, 其目的是在合理时间复杂度的限制条件下, 尽可能提高蚁群算法在一定的空间复杂度下的寻优能力, 从而改善蚁群算法的全局收敛性, 扩宽蚁群算法的应用领域。; M.Dorigo等人提出一种修正的蚁群算法为Ant- Q System,该算法和基本蚁群算法有如下不同: 状态转移规则不同: 仅让信息量最大的路径以较大的概率选中。 全局更新规则不同: 仅对一次循环中的最优的蚂蚁使用。 增加更新规则: 在所有蚂蚁完成一次转移后执行。;德国学者Thomastuzle和Holerhoos提出了一种改进的算法即最大最小系统(MAX-MINant system, MMAS) 。为了防止算法过早的停滞, MMAS限定了信息量允许的上下限, 并且采用了平滑机制对蚂蚁系统的解进行了改进。;基于蚁群算法的数据挖掘方法;数据挖掘 ——知识提取技术;数据挖掘的步骤;蚁群算法在数据挖掘中的应用;蚁群算法在分类中的应用;蚁群算法在分类中的应用;构造规则;蚁群算法在聚类中的应用;基于蚁群聚类模型; LF算法;基于信息熵的蚁群聚类算法 ——引入信息熵的LF??进算法 ; TSP和文本分聚类的异同;文本的聚类算法;;;分类算法;实验分析;蚁群算法在网络路由、流量控制及访问控制中的应用;组播路由调度方法 2001;算法过程：;资源发现算法2006;分级路由网络中;网络流量控制2008;启发信息量: 带宽利用率和时延;动态与基本的蚁群算法性能的对比;1.使用带宽资源最少 2.负载分布均匀;P2P访问控制 2008;根据获得资源的质量，更新信任值;系统收集信任值的过程如下： (1)请求资源节点在发送请求信息时，产生一个有哪些信誉好的足球投注网站蚂蚁Fant，携带必要的资源请求信息。 (2)Fant根据途中各个节点的信任矩阵T中资源C的信息素强度选择下一个节点； (3)当找到拥有资源的节点后，Fant自动消失，产生一个返回蚂蚁Bant； (4) Bant沿原路返回并按式(4)对途中各个节点的信任矩阵中资源C的信息素进行更新，直至返回到请求资源节点;用于P2P网络有哪些信誉好的足球投注网站2009