一种基于信息素传递的GIS网格任务处理算法

谢文兵，戴塔根

（1. 中南大学 地学与环境工程学院，长沙 410083；2. 深圳职业技术学院，深圳 518055）

一种基于信息素传递的GIS网格任务处理算法

谢文兵1,2，戴塔根1

（1. 中南大学 地学与环境工程学院，长沙 410083；2. 深圳职业技术学院，深圳 518055）

0 引言

大型的GIS系统需要对海量的GIS数据进行处理、分析，然后构建模型，并进行研究。由于大型GIS系统所需要处理的基础数据量庞大而单机显然不能满足处理要求。因此如何实现进行高效的对大型GIS系统进行数据资源的处理，成为了大型GIS系统设计的关键。网格计算通过利用大量异构计算机的未用资源，将其作为嵌入在分布式电信基础设施中的一个虚拟的计算机集群，为解决大规模的计算问题提供了一个模型。GIS技术和网格技术相结合是当今发展的必然趋势。如何针对大数据量的GIS数据进行任务分解和调度成为一个关键性问题。

蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于2002年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。然而蚁群算法具有收敛速度慢，全局优化不完整等缺陷，许多学者对基本的蚁群算法进行了多方面的改进，这些改进方法对一些特定问题的求解已取得了一些效果，但是从信息系统角度来看，这些改进没有很好的生物学基础。本文在分析蚁群算法模型在大数据量处理缺陷的基础上，提出一种与真实蚁群系统更加相符的基于信息素传递的蚁群算法，并提出了一种适合该算法的任务分配网格模型，该网格模型能对GIS海量数据进行有效的处理。

1 网格计算中的任务分配

1.1 网格计算

网格计算又称为虚拟计算环境，或全球计算统一平台，是在元计算的基础上发展起来的，是Internet应用的新发展，是在巨型机与互联网技术的基础上推出的一项新变革，是完成超级计算任务的一种新模式。网格计算使多组联网计算机能够组织到一起并按需进行共享，以满足不断变化的业务需求，网格计算思想来源于电力网系统，网格计算能把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终结果[1,2]。

1.2 任务分配

网格计算能把各种异构的资源变成统一共享的虚拟计算环境，对用户而言网格计算是集成各种硬件和软件资源为用户提供完全透明服务环境的计算平台，网格计算主要具有层次管理、通信服务、信息服务、命名服务、文件系统管理、用户安全认证、系统监控、资源管理和调度。提供合理的资源调度方法，高效地利用各种资源[4,5]。

在网格计算中，一般针对下面三种应用进行任务分配：

1）面向应用的任务分配：根据应用任务种类进行任务分解由各个计算节点进行处理，并将数据结果交给用户。

2）面向服务的任务分配：根据服务的能力进行任务分解由各个计算节点进行处理，并将结果提交给用户。

3）面向计算的任务分配：根据计算数据量和算法的复杂度进行任务的分解由各个计算节点进行处理，并将结果提交给用户。

1.3 面向GIS数据的网格任务分配方式

一般针对GIS数据应用在网格上可以采用以下的分解方式。

第一种是按作业流程分解。通过采用流水线的作业流程模式，将一个作业进行步骤分解，其分解的子步骤可以分配到各个网格计算节点上进行并行处理，整个处理过程如同工厂的流水线一样。

第二种是功能单元分解。将网格计算任务按照其任务功能分解成相互基本独立的不同功能单元。

第三种是属性分解。根据GIS中的矢量数据、属性数据和图像数据的特点，依托基于信息素传递的蚁群任务分配算法，把网格中的所有节点依据GIS数据的不同类型划分为矢量数据处理节点群，属性数据处理节点群和图像数据处理节点群。其中各个节点群就相当于自然界中蚂蚁的巢穴，如当用户提交一个GIS数据处理任务时，先由数据管理模块将数据按照GIS的三种数据类型分解，然后各个节点群释放出相应的任务处理子程序（相当于自然界中的蚂蚁）来取得该节点群所需的数据资源（相当于自然界中蚂蚁的食物），其中各个蚂蚁间的联系符合信息素传递模型。

此外由于网格系统中各个应用节点本身是异构的，而异构系统如果进行静态任务调度十分困难，所以本文采用一种基于信息素传递的动态任务调度策略以加快系统的处理器速度[6]。本策略采用矢量数据处理节点群，属性数据处理节点群和图像数据处理节点群，分离调度处理的方式，通过在每一个可识别的静态项之间重映射数据和计算来实现实现基于不同节点群上的cpu资源和内存资源管理。

2 基于信息素传递的蚁群算法

2.1 基本蚁群算法模型分析

蚁群算法是一种随机搜索算法[7,8]，它是由最优候选解组成的解集，算法需要产生许多人工蚂蚁来进行算法的收敛，每个蚂蚁独立寻找解决办法其代表一个解空间，人工蚂蚁们通过释放信息元素来找到一个解，如果该解是最优解，那么在该解集上的人工蚂蚁留会在自己的搜寻的路径上留下更多的信息元素[9,10]，解集的搜寻效率取决于信息元素的浓度，信息素的浓度和算法的搜寻过程同步进行，对信息元素浓度高低还能影响其它蚂蚁的学习效果，随着人工蚂蚁数量的不断增加，最佳解决方案将逐步增加，算法逐渐收敛。然而，整个蚁群算法的收敛效率总取决于信息元素的浓度[10～12]的积累效率。这种行为，容易导致算法的早熟和停滞。

2.2 改进后的信息素传递规则

蚂蚁进行路径搜索时，如果一个蚂蚁找到了一条最短路径，它释放的信息素因相应其它的路径浓度要大[13]，而且信息元素浓度将以此为中心进行扩散，直接影响其它蚂蚁进行路径选择。

图1 算法原理示意

如图1中，假设蚂蚁A欲从E到G，其中通过E-F在到F-G为一距离很短的路径，这条路径比E-I-H-G路径要短。而E-F路径比E-I路径要长，如果一开始路径E-F上的信息元素浓度没有和E-I上的信息素的高，那么经过蚂蚁A的调整,使得E-F路径上的信息元素浓度比E-I路径上的信息元素浓度高，而当蚂蚁B也准备到G点时，如果从E点走它将不会选择E-I这条路径而会选择E-F这条路径，从而使蚂蚁B选择最短路径E-F-G。

本文通过将蚂蚁m走过的两个节点t(e)和f(f)之间的距离定义为LTT，针对GIS数据特点对其进行矢量数据处理节点群，属性数据处理节点群和图像数据处理节点群处理，将处理后的ENIT和ENIF去提升相应路径上的信息素浓度，对于其他的任一节点l，如果它在蚂蚁m所产生的信息素的传递范围内，则能求出传递到该节点的信息素的浓度ENIT和ENIF。如式(1)～(3)所示。

其中公式(1)表示如果第m只蚂蚁在时刻n到n+1之间经过节点I但不经过节点F，其中P为对象参数公式(2)表示如果第m只蚂蚁在时刻n到n+1之间经过路径FT，其中Q表示信息元素浓度增量值，公式(3)表示如果第m只蚂蚁在时刻n到n+1之间经过节点T但不经过节点I，其中L表示路径增量值。

2.3 改进后的信息素传递算法设计

在上述分析的基础上，本文提出了一种基于信息素传递的蚁群算法通过。通过该算法以改进基本蚁群算法，提高路径选择规则，使信息素更新使用一个新的路径选择方法。假设所有的蚂蚁都以相同的速度进行路径搜寻。随着时间的推移，在路径上残留的信息素将逐渐消失，使用参数P表示信息元素的消失率，信息元素进过N个时刻的挥发后，蚂蚁完成一个周期的路径搜索，各路径上的信息素浓度调整如公式(4)。

通过改进基本信息素传递率如公式(5)。

1）初始化：设迭代次数l=0，蚂蚁数为m。

2）将m个蚂蚁按随机的方式进行放置。

3）根据公式(1)来调整GIS数据对象参数。

4）根据公式(2)来调整m个蚂蚁在该轮的信息元素浓度增量。

5）根据公式(3)来调整m个蚂蚁在该轮的路径增量。

6）根据公式(4)来求的总的信息元素浓度和。

7）按照每条路径的信息元素浓度比率进行m个蚂蚁的再分配

8）通过公式(5)使得后一个蚂蚁通过前面蚂蚁传递的信息素来了解那条短路径是本次的最优解。

9）若终止条件满足，则结束；否则i=i+1，转步骤2 进行下一属性群的计算。终止条件可指定属性的个数，也可限定运行时间，或设定最短路长的下限。

3 实验与分析

本实验部署了20个GIS网格计算工作节点，1个client节点、1个server节点和19个work节点，其结构如图2所示。

图2 实验系统结构图

图3为基于信息素传递的蚁群算法的网格模拟实验。通过模拟实验可以看出，基于信息素传递的蚁群算法可以是蚁群绕过障碍物（红色的块体）快速和目标建立最短路径。

图3 基于信息素传递的蚁群算法的信息素模拟图

图4为通过基于信息素传递的蚁群算法的网格模拟实验结果，其中为一个GIS三维数据网格场景图，因为其数据量具大，其任务分解机制为基于信息素传递的蚁群算法。

图4 基于信息素传递的蚁群算法的网格GIS实验效果图

实验曲线图5说明在本实验中基于信息素传递的蚁群算法的网格GIS任务处理速度要优于普通蚁群算法的网格GIS任务处理速度。

图5 基于信息素传递的蚁群算法和普通蚁群算法的数据处理速度比较图

4 结论

信息素传递的蚁群算吸取了蚂蚁算法在寻优问题上的优势，并克服了其的许多不足。通过实验显示该算法在针对大数海量GIS数据处理时比普通的任务分解算法速度更快，效率更高。由于该算法仅仅只面向简单结构的GIS海量数据（其中未包含空间数据和属性数据的混合数据，也未包含多尺度数据）进行实验，该算法对复杂结构的多尺度GIS海量数据的效率还需进一步研究。

[1]ColorniA,DorigoM,Maniezzo V.Distributed Optimization by Ant Colonics[C].In:Varela F,BourgineP,Eds.Proceedings of 1st European Conference on Artificial Life(ECAL'91).Paris:Elsevier Publishing,1991:134-142.

[2]周春光,梁艳春.计算智能[M].长春:吉林大学出版社,2001:102-104,277-280.

[3]DorigoM,GambardellaLM.Ant Colony System:A Cooperative L earning App roach to the T raveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[4]GutjahrW J.A Graph2based Ant System and Its Convergence[J].Future Generation Computing Systems,2000,16:873-888.

[5]Bullnheimer B,Hartl R F,Strauss Ch.A n Imp roved Ant System Algorithm for the Vehicle Routing Problem [J].Annals of Operations Research,1999,89:319-328.

[6]Dorigo M.,Maniezzo V.,Colorni A.Ant system:Optimization by a colony of coorperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.

[7]Dorigo M.,Gambardella L.M.Ant colonies for the traveling salesman problem[J].BioSystems,1997,43(2):73-81.

[8]Stützle T.,Hoos H.H.MAX-MIN Ant System[J].Future Generation Computer Systems Journal.2000,16(8):889-914.

[9]Botee H.M, Bonabeau E. Evolving ant colony optimization[J].Complex Systems,1998,1(2):149-159.

[10]Dorigo M,Gambardella LM.Ant Colonied for the Travelling Salesman Problem [J].Biosystems,1997,43(2):73-81.

[11]凌云,陈毓芬,王英杰.基于用户认知特征的地图可视化系统自适应用户界面研究[J].测绘学报,2005,8(34):278-282.

An GIS gird task processing algorithm base on pheromone transfer

XIE Wen-bing1,2, DAI Ta-gen1

本文在分析蚁群算法模型缺陷的基础上，提出一种与真实蚁群系统更加相符的基于信息素传递

的蚁群算法，并提出了一种适合该算法的任务分配网格模型，该网格模型能对GIS海量数据进行有效的处理。并进行实验分析验证了其独特的效果。

GIS；网格任务；信息素传递；蚁群算法

谢文兵（1977 -），男，四川邻水人，副教授，在读博士，研究方向为国土资源与信息工程。

TH166；TP391.7

A

1009-0134(2011)4(上)-0151-04

10.3969/j.issn.1009-0134.2011.4(上).47

2010-11-13