一種基于信息素傳遞的GIS網(wǎng)格任務(wù)處理算法

謝文兵，戴塔根

（1. 中南大學(xué) 地學(xué)與環(huán)境工程學(xué)院，長沙 410083；2. 深圳職業(yè)技術(shù)學(xué)院，深圳 518055）

一種基于信息素傳遞的GIS網(wǎng)格任務(wù)處理算法

謝文兵1,2，戴塔根1

（1. 中南大學(xué) 地學(xué)與環(huán)境工程學(xué)院，長沙 410083；2. 深圳職業(yè)技術(shù)學(xué)院，深圳 518055）

0 引言

大型的GIS系統(tǒng)需要對海量的GIS數(shù)據(jù)進行處理、分析，然后構(gòu)建模型，并進行研究。由于大型GIS系統(tǒng)所需要處理的基礎(chǔ)數(shù)據(jù)量龐大而單機顯然不能滿足處理要求。因此如何實現(xiàn)進行高效的對大型GIS系統(tǒng)進行數(shù)據(jù)資源的處理，成為了大型GIS系統(tǒng)設(shè)計的關(guān)鍵。網(wǎng)格計算通過利用大量異構(gòu)計算機的未用資源，將其作為嵌入在分布式電信基礎(chǔ)設(shè)施中的一個虛擬的計算機集群，為解決大規(guī)模的計算問題提供了一個模型。GIS技術(shù)和網(wǎng)格技術(shù)相結(jié)合是當(dāng)今發(fā)展的必然趨勢。如何針對大數(shù)據(jù)量的GIS數(shù)據(jù)進行任務(wù)分解和調(diào)度成為一個關(guān)鍵性問題。

蟻群算法又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo于2002年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對PID控制器參數(shù)優(yōu)化設(shè)計問題，將蟻群算法設(shè)計的結(jié)果與遺傳算法設(shè)計的結(jié)果進行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進化優(yōu)化方法的有效性和應(yīng)用價值。然而蟻群算法具有收斂速度慢，全局優(yōu)化不完整等缺陷，許多學(xué)者對基本的蟻群算法進行了多方面的改進，這些改進方法對一些特定問題的求解已取得了一些效果，但是從信息系統(tǒng)角度來看，這些改進沒有很好的生物學(xué)基礎(chǔ)。本文在分析蟻群算法模型在大數(shù)據(jù)量處理缺陷的基礎(chǔ)上，提出一種與真實蟻群系統(tǒng)更加相符的基于信息素傳遞的蟻群算法，并提出了一種適合該算法的任務(wù)分配網(wǎng)格模型，該網(wǎng)格模型能對GIS海量數(shù)據(jù)進行有效的處理。

1 網(wǎng)格計算中的任務(wù)分配

1.1 網(wǎng)格計算

網(wǎng)格計算又稱為虛擬計算環(huán)境，或全球計算統(tǒng)一平臺，是在元計算的基礎(chǔ)上發(fā)展起來的，是Internet應(yīng)用的新發(fā)展，是在巨型機與互聯(lián)網(wǎng)技術(shù)的基礎(chǔ)上推出的一項新變革，是完成超級計算任務(wù)的一種新模式。網(wǎng)格計算使多組聯(lián)網(wǎng)計算機能夠組織到一起并按需進行共享，以滿足不斷變化的業(yè)務(wù)需求，網(wǎng)格計算思想來源于電力網(wǎng)系統(tǒng)，網(wǎng)格計算能把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結(jié)果綜合起來得到最終結(jié)果[1,2]。

1.2 任務(wù)分配

網(wǎng)格計算能把各種異構(gòu)的資源變成統(tǒng)一共享的虛擬計算環(huán)境，對用戶而言網(wǎng)格計算是集成各種硬件和軟件資源為用戶提供完全透明服務(wù)環(huán)境的計算平臺，網(wǎng)格計算主要具有層次管理、通信服務(wù)、信息服務(wù)、命名服務(wù)、文件系統(tǒng)管理、用戶安全認證、系統(tǒng)監(jiān)控、資源管理和調(diào)度。提供合理的資源調(diào)度方法，高效地利用各種資源[4,5]。

在網(wǎng)格計算中，一般針對下面三種應(yīng)用進行任務(wù)分配：

1）面向應(yīng)用的任務(wù)分配：根據(jù)應(yīng)用任務(wù)種類進行任務(wù)分解由各個計算節(jié)點進行處理，并將數(shù)據(jù)結(jié)果交給用戶。

2）面向服務(wù)的任務(wù)分配：根據(jù)服務(wù)的能力進行任務(wù)分解由各個計算節(jié)點進行處理，并將結(jié)果提交給用戶。

3）面向計算的任務(wù)分配：根據(jù)計算數(shù)據(jù)量和算法的復(fù)雜度進行任務(wù)的分解由各個計算節(jié)點進行處理，并將結(jié)果提交給用戶。

1.3 面向GIS數(shù)據(jù)的網(wǎng)格任務(wù)分配方式

一般針對GIS數(shù)據(jù)應(yīng)用在網(wǎng)格上可以采用以下的分解方式。

第一種是按作業(yè)流程分解。通過采用流水線的作業(yè)流程模式，將一個作業(yè)進行步驟分解，其分解的子步驟可以分配到各個網(wǎng)格計算節(jié)點上進行并行處理，整個處理過程如同工廠的流水線一樣。

第二種是功能單元分解。將網(wǎng)格計算任務(wù)按照其任務(wù)功能分解成相互基本獨立的不同功能單元。

第三種是屬性分解。根據(jù)GIS中的矢量數(shù)據(jù)、屬性數(shù)據(jù)和圖像數(shù)據(jù)的特點，依托基于信息素傳遞的蟻群任務(wù)分配算法，把網(wǎng)格中的所有節(jié)點依據(jù)GIS數(shù)據(jù)的不同類型劃分為矢量數(shù)據(jù)處理節(jié)點群，屬性數(shù)據(jù)處理節(jié)點群和圖像數(shù)據(jù)處理節(jié)點群。其中各個節(jié)點群就相當(dāng)于自然界中螞蟻的巢穴，如當(dāng)用戶提交一個GIS數(shù)據(jù)處理任務(wù)時，先由數(shù)據(jù)管理模塊將數(shù)據(jù)按照GIS的三種數(shù)據(jù)類型分解，然后各個節(jié)點群釋放出相應(yīng)的任務(wù)處理子程序（相當(dāng)于自然界中的螞蟻）來取得該節(jié)點群所需的數(shù)據(jù)資源（相當(dāng)于自然界中螞蟻的食物），其中各個螞蟻間的聯(lián)系符合信息素傳遞模型。

此外由于網(wǎng)格系統(tǒng)中各個應(yīng)用節(jié)點本身是異構(gòu)的，而異構(gòu)系統(tǒng)如果進行靜態(tài)任務(wù)調(diào)度十分困難，所以本文采用一種基于信息素傳遞的動態(tài)任務(wù)調(diào)度策略以加快系統(tǒng)的處理器速度[6]。本策略采用矢量數(shù)據(jù)處理節(jié)點群，屬性數(shù)據(jù)處理節(jié)點群和圖像數(shù)據(jù)處理節(jié)點群，分離調(diào)度處理的方式，通過在每一個可識別的靜態(tài)項之間重映射數(shù)據(jù)和計算來實現(xiàn)實現(xiàn)基于不同節(jié)點群上的cpu資源和內(nèi)存資源管理。

2 基于信息素傳遞的蟻群算法

2.1 基本蟻群算法模型分析

蟻群算法是一種隨機搜索算法[7,8]，它是由最優(yōu)候選解組成的解集，算法需要產(chǎn)生許多人工螞蟻來進行算法的收斂，每個螞蟻獨立尋找解決辦法其代表一個解空間，人工螞蟻們通過釋放信息元素來找到一個解，如果該解是最優(yōu)解，那么在該解集上的人工螞蟻留會在自己的搜尋的路徑上留下更多的信息元素[9,10]，解集的搜尋效率取決于信息元素的濃度，信息素的濃度和算法的搜尋過程同步進行，對信息元素濃度高低還能影響其它螞蟻的學(xué)習(xí)效果，隨著人工螞蟻數(shù)量的不斷增加，最佳解決方案將逐步增加，算法逐漸收斂。然而，整個蟻群算法的收斂效率總?cè)Q于信息元素的濃度[10～12]的積累效率。這種行為，容易導(dǎo)致算法的早熟和停滯。

2.2 改進后的信息素傳遞規(guī)則

螞蟻進行路徑搜索時，如果一個螞蟻找到了一條最短路徑，它釋放的信息素因相應(yīng)其它的路徑濃度要大[13]，而且信息元素濃度將以此為中心進行擴散，直接影響其它螞蟻進行路徑選擇。

圖1 算法原理示意

如圖1中，假設(shè)螞蟻A欲從E到G，其中通過E-F在到F-G為一距離很短的路徑，這條路徑比E-I-H-G路徑要短。而E-F路徑比E-I路徑要長，如果一開始路徑E-F上的信息元素濃度沒有和E-I上的信息素的高，那么經(jīng)過螞蟻A的調(diào)整,使得E-F路徑上的信息元素濃度比E-I路徑上的信息元素濃度高，而當(dāng)螞蟻B也準(zhǔn)備到G點時，如果從E點走它將不會選擇E-I這條路徑而會選擇E-F這條路徑，從而使螞蟻B選擇最短路徑E-F-G。

本文通過將螞蟻m走過的兩個節(jié)點t(e)和f(f)之間的距離定義為LTT，針對GIS數(shù)據(jù)特點對其進行矢量數(shù)據(jù)處理節(jié)點群，屬性數(shù)據(jù)處理節(jié)點群和圖像數(shù)據(jù)處理節(jié)點群處理，將處理后的ENIT和ENIF去提升相應(yīng)路徑上的信息素濃度，對于其他的任一節(jié)點l，如果它在螞蟻m所產(chǎn)生的信息素的傳遞范圍內(nèi)，則能求出傳遞到該節(jié)點的信息素的濃度ENIT和ENIF。如式(1)～(3)所示。

其中公式(1)表示如果第m只螞蟻在時刻n到n+1之間經(jīng)過節(jié)點I但不經(jīng)過節(jié)點F，其中P為對象參數(shù)公式(2)表示如果第m只螞蟻在時刻n到n+1之間經(jīng)過路徑FT，其中Q表示信息元素濃度增量值，公式(3)表示如果第m只螞蟻在時刻n到n+1之間經(jīng)過節(jié)點T但不經(jīng)過節(jié)點I，其中L表示路徑增量值。

2.3 改進后的信息素傳遞算法設(shè)計

在上述分析的基礎(chǔ)上，本文提出了一種基于信息素傳遞的蟻群算法通過。通過該算法以改進基本蟻群算法，提高路徑選擇規(guī)則，使信息素更新使用一個新的路徑選擇方法。假設(shè)所有的螞蟻都以相同的速度進行路徑搜尋。隨著時間的推移，在路徑上殘留的信息素將逐漸消失，使用參數(shù)P表示信息元素的消失率，信息元素進過N個時刻的揮發(fā)后，螞蟻完成一個周期的路徑搜索，各路徑上的信息素濃度調(diào)整如公式(4)。

通過改進基本信息素傳遞率如公式(5)。

1）初始化：設(shè)迭代次數(shù)l=0，螞蟻數(shù)為m。

2）將m個螞蟻按隨機的方式進行放置。

3）根據(jù)公式(1)來調(diào)整GIS數(shù)據(jù)對象參數(shù)。

4）根據(jù)公式(2)來調(diào)整m個螞蟻在該輪的信息元素濃度增量。

5）根據(jù)公式(3)來調(diào)整m個螞蟻在該輪的路徑增量。

6）根據(jù)公式(4)來求的總的信息元素濃度和。

7）按照每條路徑的信息元素濃度比率進行m個螞蟻的再分配

8）通過公式(5)使得后一個螞蟻通過前面螞蟻傳遞的信息素來了解那條短路徑是本次的最優(yōu)解。

9）若終止條件滿足，則結(jié)束；否則i=i+1，轉(zhuǎn)步驟2 進行下一屬性群的計算。終止條件可指定屬性的個數(shù)，也可限定運行時間，或設(shè)定最短路長的下限。

3 實驗與分析

本實驗部署了20個GIS網(wǎng)格計算工作節(jié)點，1個client節(jié)點、1個server節(jié)點和19個work節(jié)點，其結(jié)構(gòu)如圖2所示。

圖2 實驗系統(tǒng)結(jié)構(gòu)圖

圖3為基于信息素傳遞的蟻群算法的網(wǎng)格模擬實驗。通過模擬實驗可以看出，基于信息素傳遞的蟻群算法可以是蟻群繞過障礙物（紅色的塊體）快速和目標(biāo)建立最短路徑。

圖3 基于信息素傳遞的蟻群算法的信息素模擬圖

圖4為通過基于信息素傳遞的蟻群算法的網(wǎng)格模擬實驗結(jié)果，其中為一個GIS三維數(shù)據(jù)網(wǎng)格場景圖，因為其數(shù)據(jù)量具大，其任務(wù)分解機制為基于信息素傳遞的蟻群算法。

圖4 基于信息素傳遞的蟻群算法的網(wǎng)格GIS實驗效果圖

實驗曲線圖5說明在本實驗中基于信息素傳遞的蟻群算法的網(wǎng)格GIS任務(wù)處理速度要優(yōu)于普通蟻群算法的網(wǎng)格GIS任務(wù)處理速度。

圖5 基于信息素傳遞的蟻群算法和普通蟻群算法的數(shù)據(jù)處理速度比較圖

4 結(jié)論

信息素傳遞的蟻群算吸取了螞蟻算法在尋優(yōu)問題上的優(yōu)勢，并克服了其的許多不足。通過實驗顯示該算法在針對大數(shù)海量GIS數(shù)據(jù)處理時比普通的任務(wù)分解算法速度更快，效率更高。由于該算法僅僅只面向簡單結(jié)構(gòu)的GIS海量數(shù)據(jù)（其中未包含空間數(shù)據(jù)和屬性數(shù)據(jù)的混合數(shù)據(jù)，也未包含多尺度數(shù)據(jù)）進行實驗，該算法對復(fù)雜結(jié)構(gòu)的多尺度GIS海量數(shù)據(jù)的效率還需進一步研究。

[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].長春:吉林大學(xué)出版社,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]凌云,陳毓芬,王英杰.基于用戶認知特征的地圖可視化系統(tǒng)自適應(yīng)用戶界面研究[J].測繪學(xué)報,2005,8(34):278-282.

An GIS gird task processing algorithm base on pheromone transfer

XIE Wen-bing1,2, DAI Ta-gen1

本文在分析蟻群算法模型缺陷的基礎(chǔ)上，提出一種與真實蟻群系統(tǒng)更加相符的基于信息素傳遞

的蟻群算法，并提出了一種適合該算法的任務(wù)分配網(wǎng)格模型，該網(wǎng)格模型能對GIS海量數(shù)據(jù)進行有效的處理。并進行實驗分析驗證了其獨特的效果。

GIS；網(wǎng)格任務(wù)；信息素傳遞；蟻群算法

謝文兵（1977 -），男，四川鄰水人，副教授，在讀博士，研究方向為國土資源與信息工程。

TH166；TP391.7

A

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

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

2010-11-13