【蚁群算法在网格资源查找中的应用】蚁群算法相关论文
[摘要]提出基于蚁群算法的移动Agent在网格中的资源发现方法,利用蚁群算法的并行性,全局优化性和离散性等特点,初步研究将蚁群算法应用到网格资源查找,为今后的研究提出新的思路。
[关键词]网格计算网格监控蚁群算法
中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)1110066-01
网格是伴随着互联网技术迅速发展起来的,最初是专门针对复杂科学计算应用的一种新型计算模式,这种计算模式把整个网络整合成一台巨大的超级计算机。网格中的资源规模巨大,更新频繁,如何实时准确地监控网格中的资源情况就成了网格技术中的一个重要问题。
一、蚁群系统概述
蚂蚁是通过感知信息素(pheromone)的浓度来选择路径的。从巢穴通往食物源的各条路径上,最开始是没有任何信息素留下的,第一批蚂蚁首次选择路径时并不知道哪条路径最短,它们的选择是盲目的。随后出发的蚂蚁则可以把第一批蚂蚁留下的信息素作为参考信息,根据信息素浓度选择路径。而将食物搬回巢穴的蚂蚁,再次前往食物源时,不会再顺原路走了,而是重新选择路径,当然这次它会根据蚂蚁以前留下的信息素的浓度来选择路径。蚂蚁在行进过程中,只会根据信息素来选择路径,有时会走回头路,而它不会因为曾经走过就不走了。这些现象都说明,蚂蚁没有记忆能力,并不记得自己以前走过的路径。自然界是存在于一个连续的时空当中的,信息素会因为时间的流逝而逐渐挥发,蚂蚁的行径和留下信息素也都是一个连续的过程。蚂蚁之间通过信息素进行交流,路径上信息素浓度越高,表明路径越短,走过的蚂蚁也越多,从而吸引更多的蚂蚁选择这条路,路径上信息素的浓度随之增加,如此反复,最短路径上的信息素浓度将高于其它路径上的信息素浓度,整个蚁群最终会聚集到最短的路径上。这种用信息素的浓度来反映路径的长短,并通过正反馈机制强化这些信息,引导蚁群找到最短路径的群体智能特性,是蚁群算法在设计中要模仿的。真实蚁群除了信息素外不会去学习任何关于路径长短的先验知识,蚂蚁也没有记忆力,这使得蚁群的行为体现出一定的盲目性,缺乏效率。这是蚁群算法需要进行改进的方面。
因为人工蚁群和真实蚁群存在联系和区别,所以实现人工蚁群模拟真是蚁群进行问题求解就成为可能,实践证明这种仿生方法是行之有效的。如路径DF,BF和BCD的路程长度d为1;C是路径BCD的中点;假设在每个单位时间内,有30只蚂蚁从A来到B,30只蚂蚁从E来到D;每只蚂蚁单位时间内行进路程为1;蚂蚁在行进过程中在单位时间内留下1个浓度单位献信息素,1个浓度单位的信息素在一个时间段(t,t+l)结束后瞬间完全挥发。t=0时,在B和D点各有30只蚂蚁,由于此前路径上没有信息素,它们随机地选择路径,在DF,DC,BF和BC上各有15只蚂蚁。t=1时,又有30只蚂蚁到达B,它们发现在BF上的信息素浓度为15,BC上信息素浓度为30(是由15只BC走向和15只CB走向的蚂蚁共同留下的),因此选择BC路径的蚂蚁数的期望值是选择BF路径蚂蚁数的2倍。所以,20只蚂蚁选择BC,10只蚂蚁选择BF。同样的情况发生在D点。这个过程一直持续下去,直到所有人工蚂蚁最终选择最短路径BCD(或DCB)。可以看出人工蚂蚁生活在离散的时空中。经过改进,人工蚂蚁与真实蚂蚁相比主要有以下几点区别:(l)人工蚂蚁具有记忆能力,而真实蚂蚁没有记忆能力。人工蚂蚁可以记住曾经走过的路径或访问过的节点,这样对提高算法效率是有益的。(2)人工蚂蚁不像真实蚂蚁那样是完全“瞎”的。人工蚂蚁可以根据一些启发信息来指导自己的选择。(3)人工蚂蚁“生活”在一个离散时间的环境中,而真实蚂蚁生活在连续时间的环境中。这一点对于解决分步骤的优化问题是十分重要的。人工蚁群系统正是有了这些不同于真实蚂蚁的特性,才使得该系统具有更高的智能性,在寻优过程中具有更高的效率,适合于解决更多类型的问题。
二、基于蚁群算法的网格资源查找
现在大量的工作是围绕组合优化问题进行的,因为蚁群模型的定义要受到问题结构的影响,故而选择一种标准的问题是衡量算法好坏,并与其它算法进行比较的前提,通常选择的问题是旅行商问题(TSP),下面简要地介绍一下用于TSP的蚁群算法。蚁群算法的求解方法是这样的:将m只蚂蚁均匀地分布在n个城市中。每只蚂蚁根据前往相邻城市的距离长短和每条路径上的信息素浓度选择一条路径前往新的城市,所有蚂蚁周游完n座城市形成一条闭合回路。再根据各条路线的优劣对信息素浓度进行调整,然后m只蚂蚁进行下一轮寻优的旅行。经过多轮搜索,蚂蚁逐渐集中到一条最优的路线上,就完成了寻优的过程。人工蚂蚁的特性在这里得到了应用:人工蚂蚁具有记忆特性,能够记住自己走过了那些城市。蚂蚁经过的城市不能再被选择,这一点靠禁忌表来控制。人工蚂蚁能够将路径的距离作为启发信息来选择路线,这样可以避免开始阶段在没有信息素的情况下随机选择出较差的路线。当所有蚂蚁完成旅行后,统一对走过的路径进行信息素更新,这反映了人工蚂蚁离散的生活空间。下面是具体的算法模型:
我们这里设m是蚁群中的蚂蚁总数,dij(i,j=1,2,...,n)表示城
其中,allowedx{0,1,…,n-1}-tabuk表示蚂蚁k下一步允许走过的城市的集合,与真实蚁群不同,人工蚁群系统具有记忆功能,tabuk(k=1,2,…,m)用以记录蚂蚁k当前所走过的城市,集合tabuk随着进化过程作动态调整。a表示路径上的信息量对蚂蚁选择路径所起的作用大小,为由城市i转移到城市j的期望程度,经过n个时刻,蚂蚁可走完所有的城市,完成一次循环,每只蚂蚁所走过的路径就是一个解。
三、结论
蚁群优化算法对于解决TSP问题并不是目前最好的方法,但是,首先它提出了解决此问题的新思路;其次由于这种算法特有的解决方法,已经被成功应用于解决其他组合优化问题,例如武器目标分配、多播路由问题、图的着色(GraphColoring)等问题。国内也在有学者在用蚂蚁算法求解全国144个城市的最短回路问题,求得的解同其他方法一样精确,这说明蚂蚁算法不但是求解组合优化问题的可行方法,而且是一种很有竞争力的算法。
参考文献:
[1]黄肠、李伟、徐志伟,国家高性能计算环境中的资源目录管理,计算机研究和发展,2001.
[2]徐宁、李春光、张健,几种现代优化算法的比较研究,系统工程与电子技术,2002,24(12):100-103.
[3]伍文城、肖健,基于蚁群算法的中国旅行商问题满意解,计算机与现代化,2002,8:6-9.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文