基于蟻群優(yōu)化算法的線狀目標簡化模型

鄭春燕,郭慶勝,胡華科

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

1 引 言

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

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

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

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

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

2.1 約束條件

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

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

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

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

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

2.2 隨機模型

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

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

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

3.1 目標函數(shù)

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

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

3.2 信息素更新

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

3.3 啟發(fā)式信息

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

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

3.4 長期禁忌表

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

3.5 局部搜索

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

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

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

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

3.6 主要運算步驟

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

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

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

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

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

4 線狀目標的簡化試驗

4.1 試驗數(shù)據(jù)

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

4.2 試驗結果分析

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

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

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

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

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

圖2 鎮(zhèn)級境界線的部分簡化結果示意圖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 結束語

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

[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.