基于蟻群算法的道路選取模型研究

鐘 東，郭慶勝，林 青，靳家寶

(武漢大學 資源與環(huán)境科學學院，湖北 武漢 430070)

基于蟻群算法的道路選取模型研究

鐘 東，郭慶勝，林 青，靳家寶

(武漢大學 資源與環(huán)境科學學院，湖北 武漢 430070)

在制圖綜合中，道路選取是非常重要的內容之一，研究道路選取的智能化方法是非常必要的。文中在研究道路語義、幾何特征、拓撲關系和結構特征的基礎上，充分考慮居民點對道路選取過程的影響，建立道路選取的蟻群算法模型。通過實驗證明該模型算法的可行性和有效性。

制圖綜合;道路;選取;蟻群算法

在道路網綜合中，道路的選取是最根本的一步，是在化簡、移位等操作之前的首要步驟。針對道路網選取的研究有很多，依據是否采用智能化算法可以將現(xiàn)有研究分為兩類：非智能選取模型和智能化選取模型[1]。

非智能選取模型分為三類：基于道路語義的選取方法，基于圖論研究和基于Stroke的選取方法[2]。基于語義的道路選取是最早也是最常見的選取方法。用道路屬性信息描述道路重要性，如道路名稱、等級、路寬、車道數、路面類型等，將各個屬性按照一定規(guī)則賦予權值，計算每條道路的總權值并按從大到小順序進行排序，從權值最大的道路開始選取直到選取數目達到預定值[3]。圖論方法是將道路網看成圖，以圖的節(jié)點代表道路交點，圖的邊代表路段，通過拓撲關系、網眼、最短路徑等概念來設計算法。Thomson等[4]根據人類視覺感知原理和良好關聯(lián)性(Good Continuation)提出構建Stroke對道路進行選取。Stroke被稱為“路劃”，是綜合考慮道路本身的屬性信息和感知重要性所提取的道路網中的一部分道路?；赟troke的選取方法將道路網分成多個Stroke，每一條路段都屬于某個Stroke，對路段的選取變成對Stroke的選取。

基于智能化的道路選取模型主要有：基于遺傳算法的選取[5]、基于知識的選取[6]等?；谶z傳算法選取道路的基本原理：首先生成道路數據的拓撲關系和幾何分布特性，再根據道路的幾何分布特性生成M種染色體，接下來根據適應度函數進行經濟實用價值的評估，最后利用遺傳算法的各種遺傳算子，不斷遺傳，獲取在空間分布特性和經濟實用價值上保持良好的結果[5]?；谥R進行選取道路的研究較多，其中錢海忠提出了一種基于自動綜合鏈來進行自動綜合過程控制的模型，實現(xiàn)了自動綜合的智能控制[6]。

本文綜合考慮道路選取的多種原則和約束，研究道路選取的蟻群算法模型。

1 道路選取約束

道路選取的約束可以分為幾何約束、拓撲約束和結構約束[7-10]。幾何約束是要保持道路網的幾何特征，過短的路段要舍去，足夠長的路段必須選取。拓撲約束要保持道路的拓撲連通性以及與居民點的聯(lián)系，即本來連通的道路選取后不能斷開，也不應該有新的不合理的懸掛路段產生，道路網的選取要和居民點相適應。結構約束要保證道路網密度不能過大，要保證不同區(qū)域的密度對比，保持道路網的整體結構。

針對道路選取的蟻群算法模型，具體的道路選取約束會有所不同。本文主要考慮數量約束、等級約束、密度約束、連通性約束和居民點約束。

1.1 數量約束

大比例尺地圖綜合到小比例尺地圖上時，道路的數量要減少到一定的值，這個值就是小比例尺地圖上道路選取的總數，用N表示，本文把這種約束稱為數量約束。確定N的方法主要有資格法和定額法[11]。資格法是以一定的數量或質量標志作為選取的標準(資格)而進行選取的方法。定額法是規(guī)定出單位面積內應選取的制圖物體的數量而進行選取的方法。這兩種方法各有優(yōu)缺點，可以互補。本文先采用資格法確定道路選取的總數量，將在下文采用定額法確定優(yōu)先選取的數量。使用定額法常常給出一個臨界指標，即規(guī)定一個高指標和一個低指標[11]。通俗的講，也就是N可以有一定的區(qū)間，即N±n。n值的大小并沒有特定的要求，可根據實際情況給出，本文需要給定n，使用道路螞蟻選取路段，判斷居民點給定緩沖區(qū)內是否有路段被選取，若沒有，則需要將居民點連到選定的路段上，這種情況主要出現(xiàn)在小比例尺上，選取的路段比較稀少時。由于沒有特定的標準，并且n依賴于具體的情況，假定：

n=N×10%.

使用定額法確定N時，采用德國制圖學家特普菲爾的中方根模型[11]：

式中：N為小比例尺地圖上要選取的道路總數；Na為原地圖的道路條數；Ma為原地圖的比例尺分母；Mb為小比例尺地圖的比例尺分母；x是地圖符號和地物重要性的影響系數。

1.2 等級約束

道路選取時，可以依據道路的等級[11]來確定道路的優(yōu)先級。道路可以依據等級從高到低分為高速公路、國道、省道、縣道、鄉(xiāng)道、農村硬化道路和機耕道[11]，將這些等級用1～7的整數表示，等級對道路選取的約束定義為等級約束?！秶一颈壤叩貓D編繪規(guī)范》[12]對道路選取的等級問題有明確的規(guī)定。例如，1∶5萬和1∶10萬的地形圖(本文以這兩種比例尺為例)，高速、國、省、縣、鄉(xiāng)等城際間的各等級公路均應選取。這樣，蟻群算法只是針對農村硬化道路和機耕路進行選取的。

1.3 幾何約束

假設l表示路段長度，δmax和δmin均表示長度閾值，根據上文所述，幾何約束要求道路選取時必須選取l≥δmax的路段和刪除l≤δmin的路段，但是δmax和δmin的值并沒有直接給出?！秶一颈壤叩貓D編繪規(guī)范》規(guī)定，對于1∶5萬和1∶10萬的地形圖，圖上長度不足1 cm的鄉(xiāng)村路、機耕道應酌情刪去。但是有些路段雖然長度不足，但是位于Stroke上，這些路段不能刪除。另外，非城市地區(qū)的道路長度普遍偏短，可根據實際情況降低閾值。至于δmax可以根據實際情況取圖上長度1 cm的倍數。得到δmax和δmin的計算式：

δmax=μ1×M/100，

δmin=μ2×M/100.

式中：μ1為倍數，μ1> 1；μ2為閾值降低的倍數，μ2< 1；M為地形圖比例尺的分母。

本文可以把l≥δmax的路段定義為必須刪除的路段，把l≤δmin且不在Stroke上的路段定義為必須選取的路段。另外，為了便于下文描述，定義以下變量：

Nselect1：農村硬化道路中必須選取的路段數；

Nselect2：機耕道中必須選取的路段數；

Ndelete1：農村硬化道路中必須刪除的路段數；

Ndelete2：機耕道中必須刪除的路段數；

Nrest1：農村硬化道路中還可以選取的路段數；

Nrest2：機耕道中還可以選取的路段數；

N2：由幾何約束選取的道路總和，N2=Nselect1+Nselect2。

1.4 密度約束

道路選取要求保持不同地區(qū)道路密度的對比，同時道路選取的結果本身不能過密。為保證此選取原則，本文采用Chen.J(2009)提出的網眼密度[13]作為標準，在不同比例尺下，不同等級路段組成的網眼密度閾值不同，由閾值來判斷網眼是否過密。

1.5 連通性約束

在使用蟻群算法時，為了保證連通的道路網不能斷開，螞蟻在走到某一節(jié)點處，若沒有路段可以選取而需要跳轉時，就規(guī)定只能跳轉到已被選取的路段所對應的節(jié)點上，以保證道路網的連通。

1.6 居民點約束

道路的取舍必須與居民點的取舍相適應，非城市區(qū)域中，道路選取的決定性因素之一就是居民點之間的最短路徑[14]。在文獻[6]中利用遺傳算法進行道路選取時，采用居民點之間的最短路徑作為目標函數。但是，智能算法每次選擇的道路是隨機的，若將所有居民點之間的最短路徑設為目標函數，螞蟻每選取一次就需要計算居民點之間的最短路徑，計算量過大。本文的做法是在執(zhí)行道路螞蟻選取路段后，判斷在各個居民點的一定范圍內是否有路段被選取，若沒有，則需要使用居民點螞蟻將居民點連入道路網。具體方式：從距離居民點最近的路段出發(fā)，用最短的路程找到已經被選取的道路。

以上約束的優(yōu)先級可能不同，例如，等級約束需要在密度約束之前考慮；而且，某一種約束并不都是先于或者后于另一種約束的，例如，1～5等級的道路需要全部選取，這時等級約束先于幾何約束，但是對于6和7等級的道路，長度大于一定閾值的必須選取，長度小于一定閾值的必須刪除，這時的幾何約束就先于等級約束。

2 道路選取的蟻群算法模型

2.1 基本蟻群算法原理

蟻群算法模型是模擬現(xiàn)實中螞蟻總能夠在巢穴和食物之間找到最短路徑的現(xiàn)象，從而求解實際問題的一種智能化算法。其基本思想是：如果一只螞蟻要在某個路口選擇多條路徑，那么那些螞蟻先行螞蟻大量選擇的路徑(也就是信息素留存較濃的路徑)被選中的概率就最大，較多的信息素意味著較短的路徑。

著名的旅行商問題(TSP)：一個商人到M個城市賣商品，已知每兩個城市之間的距離，如何選取一條路徑使得商人走遍所有城市并回到原點且路程最短。旅行商人問題可以用圖論中的無向加權圖G=(M，E)來表示。M代表城市節(jié)點，E代表所有城市之間的道路，兩個城市i，j之間分配權值dij表示城市i和城市j之間的距離。借用TSP問題描述蟻群算法的步驟:

1)初始化，設置時間、循環(huán)次數，將X只螞蟻放到Y個城市中，設置好各個參數。

2)循環(huán)次數加1，禁忌表即螞蟻走過的路段加上對應索引號碼，已經行進的螞蟻數量加1。

3)單個螞蟻根據已經設置好的概率轉移函數計算所有可以前進的城市概率，根據輪盤算法等概率選擇算法選取并移動到一個城市，將其加入禁忌表。判斷是否經過了所有城市，若沒有則重復本步驟，直到遍歷完所有城市，進入下一步。

4)更新信息素，在螞蟻完成對所有城市的訪問后，更新道路上的信息素濃度，包括原來信息素的揮發(fā)以及本次循環(huán)新加入的信息素。

5)判斷算法是否停止，若滿足設置好的結束條件或者循環(huán)次數到達上限，則停止。否則清空禁忌表轉到第二步。

2.2 道路選取的蟻群算法模型

模仿TSP問題，能夠容易的將道路選取問題用蟻群算法來建模。道路網是由眾多的路段和交點組成的，因此使用圖論能夠很好的模擬道路網。用圖來模擬道路網，可以從圖中知道每個節(jié)點連接哪些路段，每條路段的始末節(jié)點是什么。蟻群算法解決的是組合優(yōu)化問題，組合優(yōu)化問題的核心概念是找到一組離散變量的合理組合，使得所設定的目標函數的解達到最優(yōu)。對應到道路選取，即找到所有路段的合理組合，選取哪些路段，舍棄哪些路段使選取結果最符合所設定的原則與約束。

本文在蟻群算法模型中設計兩類螞蟻：道路螞蟻和居民點螞蟻。道路螞蟻用于在優(yōu)先選取N1+N2條道路后選取另外的Nroad條路段，Nroad=N-N1-N2；居民點螞蟻用于將未連入所選取的道路網的居民點連入道路網，設居民點螞蟻選取的道路數為Npoi。

目標函數是蟻群算法的實現(xiàn)目標，是不確定但是要盡量達到的目標。由于本算法中兩類螞蟻，因此對應的目標函數也有兩個：

L1=R1+R2+ …+Ri+ …+Ra，

L2=R1+R2+ …+Rj+ …+Rb.

式中：L1為道路螞蟻選取的路段總長度；L2為居民點螞蟻選取的路段總長度；Ri為道路螞蟻走過的某一路段；Rj為居民點螞蟻走過的某一路段；a的值為Nroad；b的值為Npoi。

2.3 啟發(fā)函數

啟發(fā)函數是為了盡快達到目標而人為設置的函數。螞蟻選取路段的隨機性太大，當螞蟻走到道路節(jié)點有幾條路段可以選取時，通過啟發(fā)函數可以令螞蟻選取重要路段的可能性更大。目標函數為道路長度，那么啟發(fā)函數也一定和道路長度相關，而且越長越好，這樣才會令目標函數在盡可能短的時間內達到最優(yōu)。經過對地圖的研究，采用路段本身長度與路段所在Stroke長度相結合的方式設置啟發(fā)函數。若某條Storke足夠長，則表示組成Stroke的路段很重要，這些路段需要優(yōu)先選取。啟發(fā)函數式：

fη=L+Ls.

式中：fη為啟發(fā)函數，L在路段長度，Ls為路段所在Stroke長度。

2.4 信息素相關函數

蟻群算法一次迭代完畢后，將完成目標函數最優(yōu)的螞蟻記錄下來，同時要更新信息素。每條路段的信息素總量為殘留的信息素與本次螞蟻新生成的信息素。信息素函數為

τx(t+1)=τx(t)×ρ+Δτx.

式中：τ為信息素含量，t為時刻，t+1為新一次迭代完畢的時刻，ρ為揮發(fā)因子，x為某一路段，Δτ為本次迭代中蟻群算法產生的新信息素，Δτ的形式類似目標函數，需要考慮Stroke因素。具體表現(xiàn)形式：

其中，Q為常量，會影響生成信息素的量。

已知信息素函數和啟發(fā)函數，可以得到隨機模型。當螞蟻走到節(jié)點處有多條路段可以選擇時，由隨機模型決定該條路段被選取的概率。隨機模型的函數為

3 實 驗

使用蟻群算法模型進行道路選取的基本策略：

1)根據使用蟻群算法模型選取道路的相應要求，對道路網和居民點數據進行預處理。首先進行拓撲檢查，改正拓撲錯誤，創(chuàng)建拓撲關系。然后，明確節(jié)點連接的路段，每條路段的始末節(jié)點和左右網眼，每個網眼的組成路段。最后需構建道路Stroke，并建立居民點位置點圖層。

2)按等級約束，將選取全部等級為1～5的路段，選取數量為N1。

3)道路等級為6和7的道路必須刪除。

4)針對道路等級為6和7的道路選取必須選取的路段，選取數量為N2。

5)使用道路螞蟻選取路段。如果N1+N2+Nrest1≥N，則只需在等級為6的農村硬化道路上使用道路螞蟻進行選取，否則就在農村硬化道路和機耕道上進行選取，選取的路段數為Nroad。

6)檢查密度約束。當道路螞蟻每完成一次路徑的訪問，提取所有被選取的路段，重建拓撲關系，找出密度過大的網眼，舍棄網眼的一條路段，舍棄的原則：①舍棄等級最低的路段；②若等級最低的路段有多條，舍棄所在Stroke最短的路段，若Stroke長度相同，舍棄自身長度最短的路段；③若所在Stroke足夠長，則此Stroke上的所有選取的路段都要保留。

7)居民點約束處理。當道路螞蟻選取結束后，判斷居民點是否都已經接入道路網，若沒有，則執(zhí)行居民點螞蟻。

當Npoi>n，說明有很多居民點都沒有連入道路網，則需要調整Nroad，Nroad=Nroad-n，重新執(zhí)行⑤～⑦步。算法的整體流程如圖1所示。

圖1 算法流程

在理論基礎上，進行蟻群算法模型的道路選取實驗。該實驗基于Visual Studio2012和AE10.2平，使用空間數據庫GDB文件存儲的實驗數據(如圖2所示)，實驗數據包含道路數據(各等級的道路數見表1)和居民點數據，區(qū)域為非城市地區(qū)，比例尺為1∶1萬。

表1 每個等級的道路數量

由于該數據所代表的區(qū)域是非城市地區(qū)，包含短路段，所以取中方根模型中的x=2，用來平衡選取的路段數，這樣，對1∶5萬地形圖進行道路選取時算得N=84。再由表1得到因等級約束優(yōu)先選取的路段數為N1=1+0+2+1+30=34條。取μ1=2，μ2=0.8，M=50 000，δmax=1 000 m，δmin=400 m，另外得到Nselect1=8，Ndelete1=145，Nrest1=27，Nselect2=4，Ndelete2=156，Nrest2=44，所以N2=8+4=12，N1+N2+Nrest1

同理針對1∶10萬的地形圖，取x=2，算得N=42，N1=34，取μ1=2，μ2=0.8，M=100 000，δmax=2 000 m，δmin=800 m，另外統(tǒng)計得到Nselect1=2，Ndelete1=162，Nrest1=16，Nselect2=0，Ndelete2=182，Nrest2=22，所以N2=2，N1+N2+Nrest1>N，也就是說只需在農村硬化道路中剩下的16條道路中使用蟻群算法選取6條，機耕道中的路段均不選取。

從圖3實驗結果和圖2原始數據的對比可以看出：原始數據中具有大量的短路段，在1∶5萬和1∶10萬選取的地形圖中均未選取，只選取了主要的道路。另外，本文所指的道路條數并不是圖上直觀看到的道路條數，這是因為有些道路由多個路段組成，這些路段在一個Stroke上，刪除這條道路的分支后，直觀的看起來就是一條道路，而實際上是由多個路段組成的。

圖2 原始數據

圖3 實驗結果

4 結束語

本文討論道路選取的策略，并將蟻群算法模型應用于道路選取。設計了基于蟻群算法的道路選取模型，將螞蟻分為道路螞蟻和居民點螞蟻兩類，道路螞蟻進行初步選取，使用居民點螞蟻將居民點連接到道路網內部。選取結果可以滿足道路選取的原則和約束。

當然，本文也存在一定的不足，最主要的不足是閾值的確定，如道路網密度閾值，n,δmax,δmin的取值。這主要是因為這些閾值的確定帶有很多的經驗因素，并且受具體的環(huán)境影響較大，所以難以確定。

[1] 郭敏, 錢海忠, 黃智深,等. 采用案例歸納推理進行道路網智能選取[J]. 中國圖像圖形學報, 2013, 18(10):1343-1353.

[2] LIU Y，MOLENAAR M，AI T，et al. Categorical database generalization[J]. GeoSpatial Information Science，2003，6：1-9.

[3] 李曉軒.面向制圖綜合的道路信息表達研究與實踐[D].鄭州:信息工程大學，2010.

[4] THOMSON R C，RICHARDSON D E. The “good continuation” principle of perceptual organization applied to the generalization of road network[J]. Proceedings of the 19th International Cartographic Conference [C]. Ottawa: [s. n.]，1999：1215-1223.

[5] 鄧紅艷. 基于遺傳算法的制圖綜合研究[D]. 鄭州：信息工程大學, 2003.

[6] 錢海忠, 武芳, 王家耀. 自動制圖綜合鏈與綜合過程控制模型[J]. 中國礦業(yè)大學學報, 2006, 35(6):787-791.

[7] 王家耀.地圖學與地理信息工程研究[M]. 北京：科學出版社,2005.

[8] 王家耀，李志林，武芳.數字地圖綜合發(fā)展[M].北京：科學出版社,2011.

[9] 商其亞.道路自動綜合算法的比較與應用研究[D]. 蘭州：蘭州交通大學，2013.

[10] 田茂義，李鵬飛，俞家勇，等.格網鄰域濾波在車載激光點云道路邊線提取中的方法研究[J].測繪與空間地理信息，2016,39(5)：8-10，16.

[11] 祝國瑞. 地圖學[M]. 武漢：武漢大學出版社，2004.

[責任編輯：李銘娜]

Research of ant colony algorithm model of road selection

ZHONG Dong，GUO Qingsheng，LIN Qing，JIN Jiabao

(School of Resource and Environmental Science, Wuhan University, Wuhan 430070,China)

In cartographic generalization,roads selection is one of the most important aspects,and it is very necessary to study the intelligent methods of roads selection.In this paper,based on the semantic,geometry features,topology relationships,and structure features of roads,an ant colony algorithm is proposed for the road selection before considering the effect of settlement places in roads selection.At the end,the result of a test proves the practicability and effectiveness of the given algorithm.

cartographic generalization; road; selection; ant colony algorithm

引用著錄：鐘東，郭慶勝，林青,等.基于蟻群算法的道路選取模型研究[J].測繪工程，2017，26(4)：47-52.

10.19349/j.cnki.issn1006-7949.2017.04.009

2016-05-03

國家自然科學基金資助項目(41471384)

鐘 東(1992-)，男，碩士研究生.

TP273.4

A

1006-7949(2017)04-0047-06