一種基于信息素傳遞的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