基于蟻群優化算法的線狀目標簡化模型

鄭春燕,郭慶勝,胡華科

1.嘉應學院地理科學與旅游學院,廣東梅州514015;2.武漢大學資源與環境科學學院,湖北武漢430079

1 引 言

線狀目標的簡化一直是地圖綜合重點研究的問題之一,在經歷了幾十年的研究和發展后,仍有很多問題沒有解決,一方面是由于線狀目標簡化本身的理論和技術還有待完善、不成熟;另一方面是由于地圖空間中線狀目標在圖形表達上的重要性,線狀目標一般要占地圖圖形的80%以上[1]。從20世紀60年代開始發展至今,已經產生大量較為成熟的算法,如道格拉斯算法、Lang算法、Li-Openshaw算法等[2-3],但不同算法用于線狀目標的簡化所得結果有差異,說明可行解不唯一,宜將線狀目標的簡化歸結為部分選取的最優化問題[4-7],以獲取簡化效果最佳的解。

線狀目標簡化過程中要滿足多個相互制約的約束條件,優化方法則可以平衡這些約束條件之間的矛盾[6-7]。整數規劃法、遺傳算法、最小二乘平差法等的成功應用[4-6],說明優化算法是解線狀目標簡化問題的一個有效途徑。但整數規劃法的評價目標是連接數一定的情況下所有連接的偏差之和最小,節點數過于密集則可能保留冗余點[4];遺傳算法以所保留的節點數目作為適應度函數的主要矛盾,隨著壓縮率的增加則可能導致偏移量的增加[5];最小二乘平差法需要建立并解繁多的條件方程,權重設置也較為繁雜[6]。蟻群優化(ant colony optimization,ACO)算法通過模擬自然界螞蟻搜索路徑的方式來解組合優化問題,已經成功應用到旅行商問題、數據挖掘、區位選址等多個領域[8-10]。文獻[10]將ACO算法用于河流的符號化和道路網絡的專題表達,試驗表明相對禁忌搜索算法,ACO算法尋求最優解的搜索效率更高[10]。ACO算法通過蟻群構建的有序路線來獲取可行解,其搜索形式同線狀目標的簡化具有較大的相似性。

本文根據ACO算法的工作原理,提出并驗證了顧及節點壓縮率和幾何精度的線狀目標簡化模型,主要從目標函數值、幾何偏移量、所保留的節點數等方面與道格拉斯算法作了對比分析。

2 多約束條件下線狀目標簡化的問題描述

約束條件是蟻群構建路徑應遵循的規則,滿足約束條件的螞蟻按隨機模型確定下次到達的節點。

2.1 約束條件

設原線狀目標的節點數為 n個;Xij表示簡化后節點i和j是否相鄰;Pi表示節點i是否被選取。線狀目標簡化過程所需要的約束條件主要有:

(1)線狀目標的首末端點1和 n必須保留,且都只能與一個節點連接,即

(2)簡化后,中間節點 i只能與一個鄰近的前繼節點和后繼節點相連接

(3)簡化后,最相鄰的兩節點才能相連,所以Xij為1的條件是

(4)簡化后,構成線狀目標的每條直線段的矢量偏差Cij要在一定的限差δ范圍內,即Cij≤δ。

2.2 隨機模型

采用文獻[8—9]中近似非確定樹搜索中的概率選擇方式。位于節點i的螞蟻k,移動到節點 j的概率由下式給出

式中,ξ是一個參數,取值范圍0≤ξ≤1,表示信息素τij和啟發式信息ηij的相對影響力;Nki代表了位于節點 i的螞蟻 k能直接到達的節點的集合。

3 線狀目標簡化的ACO算法設計

3.1 目標函數

ACO算法利用目標函數值來評價所得解的質量,并進行信息素的更新,使得蟻群向較佳的路線移動。本算法主要從幾何精度(矢量偏差、長度偏差等)和節點數來確定目標函數,矢量偏差、長度偏差和所保留節點數的權重為wi、w2和w3

式中,l、n分別為原線狀目標的長度和節點個數; lij為節點i和j之間的距離;簡化后連接 Xij存在則Xij為1,否則為0;δ表示矢量偏差閾值;w1+ w2+w3=1。

3.2 信息素更新

信息素更新采用正反饋機制,包括信息素的蒸發和釋放。節點數越多,則螞蟻移動到某一節點上的概率越小,信息素的初始值為原線狀目標上節點數的平方根的倒數。按基于排列的螞蟻系統的信息素更新規則來釋放信息素,只有排列在最前的(w-1)只螞蟻和生成了至今最優路徑的螞蟻才允許釋放信息素。

3.3 啟發式信息

相對目標函數,啟發式信息是關于連接的一個局部信息,仍由矢量偏差、長度偏差和所保留的節點數確定。對于未被禁忌的連接 Xij,其啟發式信息ηij為

式中,Cij、δ的意義同前;dij為節點i到j的歐氏距離;dmax為可與節點 i建立連接的節點數;Dsij為節點i到j的原線狀目標長度。

3.4 長期禁忌表

ACO算法易融入禁忌搜索算法的長期禁忌表vistij,將矢量偏差大于閾值的節點 i和j的對應連接禁忌,以避開一些非可行解。當 vistij的值為true時,表示節點i和j的連接被禁忌。

3.5 局部搜索

當ACO算法與局部搜索相結合時,算法表現出來的性能最好[9]。局部搜索算法能適當局部優化螞蟻構建的解,提高運算效率。在顧及幾何精度的情況下,盡量減少節點數。主要步驟如下:

(1)從當前的路徑,依次取三個所保留的節點 i-1、i、i+1,計算連接 Xi-1,i+1的矢量偏差 Ci-1,i+1。

(2)將所求的矢量偏差按從小到大的順序排列,若最小的矢量偏差大于閾值則轉(3);反之,則刪除最小矢量偏差所對應的節點 i,并計算舍棄節點i后所得解的目標函數值,返回(1)。

(3)比較由(2)所得目標函數值,以獲取局部搜索中的最優解。

3.6 主要運算步驟

(1)初始化ACO所需的幾何度量(如線長、矢量偏差等)和參數(螞蟻數目、信息素蒸發率等)。

(2)構建解。隨機選擇首末端點作為起點,用m只螞蟻遍歷線狀目標上的節點,獲得 m個解。

(3)局部搜索。當螞蟻完成了路徑構建后,使用局部搜索進一步優化解。

(4)計算目標函數值,完成信息素的更新。

(5)若不滿足終止條件(迭代次數達到最大值等)轉步驟(2);否則結束運算,輸出最優解。

4 線狀目標的簡化試驗

4.1 試驗數據

試驗數據為廣東省某縣第二次全國土地調查成果土地利用數據庫系統中的鎮級境界線,如圖1所示,48個線狀目標,一共有43 555個節點,初始比例尺為 1∶10 000,目標比例尺為1∶100 000。

4.2 試驗結果分析

本試驗中閾值δ為30 m,權重w1和w2分別為0.15和0.1,螞蟻數量為30,信息素蒸發率ρ為0.2。圖2為對圖1中紅色矩形所標注的境界線簡化結果,其中47號為完整顯示,21號和31號為局部顯示。黑色實線、細虛線分別為ACO算法和道格拉斯算法簡化所得,重疊部分為實線,小圓點為原境界線上的節點,灰色區域是以15 m半徑為原境界線建立的緩沖區。表1列出了部分試驗結果,ID為標識號,K為原有節點數。KA、KD分別為ACO算法和道格拉斯算法所選取的節點數,VA、VD分別為它們所得平均矢量偏差,FA、FD分別為它們所得目標函數值。長度單位為米。

圖1 原地圖上的鎮級境界線Fig.1 The boundary lines of township on initial map

本算法綜合考慮了節點數、偏移量等指標,用目標函數值來度量簡化效果。由試驗結果可知:

(1)由ACO算法與道格拉斯算法所得簡化結果都能較有效的逼近原境界線,保留了重要的幾何特征點,有良好的外觀視覺效果,并取得了較高的壓縮率。

(2)比較每條境界線所對應的 FA和 FD,FA值都比 FD值小,VA都比VD小。由目標函數值知,利用ACO算法簡化線狀目標能得到比道格拉斯算法更好的總體評價效果。

圖2 鎮級境界線的部分簡化結果示意圖Fig.2 The schematic diagram of partial simplified result for boundary lines of township

表1 基于ACO算法和道格拉斯算法簡化結果對比Tab.1 The comparison on the two simplified results respectively based on ACO algorithmand Douglas algorithm

5 結束語

本文提出的簡化線狀目標的模型主要顧及了幾何精度和節點壓縮率,試驗表明該模型能取得良好的圖形簡化效果。有待深入研究的內容主要有:在線狀目標簡化中顧及空間關系一致性(避免自交、互交等);顧及成組線狀目標(如等高線簇)簡化后的協調性等。為了使算法更具普適性,還需要針對實際應用中不同語義的線狀目標(如水系、道路等)進行大量的研究,以提高算法的性能。

[1] THAPA K.Automatic Line Generalization Using Zero Crossings[J].Photogrammetric Engineering and Remote Sensing,1988,54(4):511-517.

[2] DOU GLAS D H,PEUCKER T K.Algorithms for the Reduction of the Number of Points Required to Represent a Line or Its Caricature[J].The Canadian Cartographer, 1973,10(2):112-122.

[3] GUO Qingsheng,HUANG Yuanlin,ZHENG Chunyan,et al.Spatial Reasoning and Progressive Cartographic Generalization[M].Wuhan:Wuhan University Press,2007. (郭慶勝,黃遠林,鄭春燕,等.空間推理與漸進式地圖綜合[M].武漢:武漢大學出版社,2007.)

[4] CROMLEY R G,CAMPBELL G M.Integrating Quantitative and Qualitative Aspects of Digital Line Simplification [J].The Cartographic Journal,1992,29(1):25-30.

[5] WU Fang,DENG Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification[J]. Acta Geodaetica et Cartographica Sinica,2003,32(4): 349-355.(武芳,鄧紅艷.基于遺傳算法的線要素自動化簡模型[J].測繪學報,2003,32(4):349-355.)

[6] HARRIE L,SARJAKOSKI T.Simultaneous Graphic Generallization of Vector Data Sets[J].GeoInformatica,2002, 6(3):233-261.

[7] PUNT E,WATKINS D.User-directed Generalization of Roads and Buildings for Multi-scale Cartography[C]∥Proceedings of 13th ICA Workshop on Generalisation and Multiple Representatio.Zurich:ICA,2010.

[8] DORIGO M,MANIEZZO V,COLORNI A.The Ant System:Optimization by a Colony of Cooperating Agent [J].IEEE Transactions on Systems,Man,and Cybernet: B,1996,26(1):29-41.

[9] DUAN Haibin.Principle and Application of Ant Colony Algorithm[M].Beijing:Science Press,2005.(段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005.)

[10] RICHARDS N,WARE M.Ant Colony Optimization Applied to Map Generalization[C]∥Proceedings of 13th ICA Workshop on Generalisation and Multiple Representation.Zurich:ICA,2010.