鄭春燕,郭慶勝,胡華科

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

1 引 言

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

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

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

2 多約束條件下線狀目標(biāo)簡(jiǎn)化的問題描述

約束條件是蟻群構(gòu)建路徑應(yīng)遵循的規(guī)則,滿足約束條件的螞蟻按隨機(jī)模型確定下次到達(dá)的節(jié)點(diǎn)。

2.1 約束條件

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

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

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

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

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

2.2 隨機(jī)模型

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

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

3 線狀目標(biāo)簡(jiǎn)化的ACO算法設(shè)計(jì)

3.1 目標(biāo)函數(shù)

ACO算法利用目標(biāo)函數(shù)值來(lái)評(píng)價(jià)所得解的質(zhì)量,并進(jìn)行信息素的更新,使得蟻群向較佳的路線移動(dòng)。本算法主要從幾何精度(矢量偏差、長(zhǎng)度偏差等)和節(jié)點(diǎn)數(shù)來(lái)確定目標(biāo)函數(shù),矢量偏差、長(zhǎng)度偏差和所保留節(jié)點(diǎn)數(shù)的權(quán)重為wi、w2和w3

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

3.2 信息素更新

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

3.3 啟發(fā)式信息

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

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

3.4 長(zhǎng)期禁忌表

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

3.5 局部搜索

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

(1)從當(dāng)前的路徑,依次取三個(gè)所保留的節(jié)點(diǎn) i-1、i、i+1,計(jì)算連接 Xi-1,i+1的矢量偏差 Ci-1,i+1。

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

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

3.6 主要運(yùn)算步驟

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

(2)構(gòu)建解。隨機(jī)選擇首末端點(diǎn)作為起點(diǎn),用m只螞蟻遍歷線狀目標(biāo)上的節(jié)點(diǎn),獲得 m個(gè)解。

(3)局部搜索。當(dāng)螞蟻完成了路徑構(gòu)建后,使用局部搜索進(jìn)一步優(yōu)化解。

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

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

4 線狀目標(biāo)的簡(jiǎn)化試驗(yàn)

4.1 試驗(yàn)數(shù)據(jù)

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

4.2 試驗(yàn)結(jié)果分析

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

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

本算法綜合考慮了節(jié)點(diǎn)數(shù)、偏移量等指標(biāo),用目標(biāo)函數(shù)值來(lái)度量簡(jiǎn)化效果。由試驗(yàn)結(jié)果可知:

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

(2)比較每條境界線所對(duì)應(yīng)的 FA和 FD,FA值都比 FD值小,VA都比VD小。由目標(biāo)函數(shù)值知,利用ACO算法簡(jiǎn)化線狀目標(biāo)能得到比道格拉斯算法更好的總體評(píng)價(jià)效果。

圖2 鎮(zhèn)級(jí)境界線的部分簡(jiǎn)化結(jié)果示意圖Fig.2 The schematic diagram of partial simplified result for boundary lines of township

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

5 結(jié)束語(yǔ)

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

[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. (郭慶勝,黃遠(yuǎn)林,鄭春燕,等.空間推理與漸進(jìn)式地圖綜合[M].武漢:武漢大學(xué)出版社,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.(武芳,鄧紅艷.基于遺傳算法的線要素自動(dòng)化簡(jiǎn)模型[J].測(cè)繪學(xué)報(bào),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.(段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,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.