馬瀟雅，郭慶勝，2

（1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢 430079；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢 430079）

一、引 言

作為占地圖圖形80%以上的地圖目標(biāo)，線狀要素的自動(dòng)綜合自然成為地圖綜合的一個(gè)重要方面。圖形簡(jiǎn)化作為其綜合的重要手段之一，已得到國(guó)內(nèi)外有關(guān)學(xué)者的持續(xù)關(guān)注，并研究實(shí)現(xiàn)了大量自動(dòng)化算法［1-4］，如著名的道格拉斯算法、Li-Openshaw算法等。隨著智能優(yōu)化算法的廣泛應(yīng)用，有關(guān)學(xué)者在線狀要素圖形簡(jiǎn)化的智能優(yōu)化算法探索中也已取得一定成效，提出了基于遺傳算法［5］和蟻群優(yōu)化算法［6］的線狀要素圖形簡(jiǎn)化模型，并證明了智能優(yōu)化算法是解決線狀要素圖形簡(jiǎn)化問題的一個(gè)有效途徑。

免疫遺傳算法是人工免疫系統(tǒng)模型的重要組成部分，該算法將免疫系統(tǒng)生理學(xué)機(jī)制和自然生物進(jìn)化機(jī)制相結(jié)合，具有強(qiáng)大的空間搜索能力［7-8］，在優(yōu)化問題的解決上具有很大優(yōu)勢(shì)。本文在現(xiàn)有線狀要素圖形簡(jiǎn)化的研究基礎(chǔ)上，提出一種基于免疫遺傳算法的線狀要素圖形自動(dòng)簡(jiǎn)化方法。并將試驗(yàn)結(jié)果與單純免疫算法、遺傳算法和道格拉斯算法進(jìn)行對(duì)比，試驗(yàn)表明基于免疫遺傳算法的線狀要素圖形簡(jiǎn)化方法在保持線狀要素圖形形狀方面表現(xiàn)更佳。

二、基于免疫遺傳算法的線狀要素圖形簡(jiǎn)化方法

基于免疫遺傳算法的線狀要素圖形簡(jiǎn)化的本質(zhì)是將線狀要素圖形簡(jiǎn)化問題轉(zhuǎn)化為抗原，線狀要素圖形簡(jiǎn)化方案轉(zhuǎn)化為抗體，抗原和抗體間的親和力值則是衡量抗體與抗原的親和度，圖形簡(jiǎn)化即為尋找與抗原親和度最高的抗體的過程。為達(dá)到保證數(shù)據(jù)質(zhì)量和可視化要求的同時(shí)，盡可能減少曲線上的點(diǎn)數(shù)，并保留關(guān)鍵點(diǎn)（包括曲線的端點(diǎn)、極值點(diǎn)、拐點(diǎn)等）的圖形簡(jiǎn)化目標(biāo)［9］，本文依據(jù)免疫遺傳算法的基本原理，顧及線狀要素的幾何精度和形狀特征點(diǎn)保留的約束條件，引入不可行解的修復(fù)機(jī)制，提出線狀要素圖形簡(jiǎn)化方法。

1.編 碼

編碼的本質(zhì)是將線狀要素圖形簡(jiǎn)化方案轉(zhuǎn)換成免疫系統(tǒng)中的抗體，并且每個(gè)抗體對(duì)應(yīng)一種圖形簡(jiǎn)化方案。本文采用二進(jìn)制編碼構(gòu)造算法的抗體，編碼的長(zhǎng)度為線狀要素上節(jié)點(diǎn)的數(shù)目，每個(gè)基因位儲(chǔ)存該節(jié)點(diǎn)的狀態(tài)，0為舍棄，1為保留。同時(shí)，線狀要素的首尾兩個(gè)節(jié)點(diǎn)為必須保留點(diǎn)。

2.親和度函數(shù)設(shè)計(jì)

在采用免疫遺傳算法進(jìn)行問題求解時(shí)，通?？贵w的親和度高低反映了抗體（問題的解）滿足抗原（問題）的程度，即抗體的親和度值越大，抗體（問題對(duì)應(yīng)的解）越優(yōu)。在對(duì)線狀要素圖形簡(jiǎn)化結(jié)果進(jìn)行評(píng)價(jià)時(shí)，親和度函數(shù)的設(shè)計(jì)僅考慮保留點(diǎn)個(gè)數(shù)及特征點(diǎn)保留兩個(gè)約束條件，幾何精度的保證則通過引入不可行解的修復(fù)機(jī)制解決。

本文把對(duì)線狀要素圖形形狀的保持起重要作用的節(jié)點(diǎn)認(rèn)為是線狀要素的形狀特征點(diǎn)，各節(jié)點(diǎn)的重要程度，由其貢獻(xiàn)值體現(xiàn)。根據(jù)文獻(xiàn)［10］的方法，各節(jié)點(diǎn)的貢獻(xiàn)值可通過該節(jié)點(diǎn)兩相鄰的直線段長(zhǎng)度L（S1）、L（S2）及兩線段的轉(zhuǎn)角β（S1，S2）綜合計(jì)算得到［10］，計(jì)算公式如下

基于免疫遺傳算法是一個(gè)尋求保留節(jié)點(diǎn)的貢獻(xiàn)值最大、圖形表示節(jié)點(diǎn)個(gè)數(shù)最少，以及圖形簡(jiǎn)化后在距離限差內(nèi)應(yīng)舍棄的保留節(jié)點(diǎn)個(gè)數(shù)最少的抗體的過程。該算法中抗體親和度值可通過式（2）計(jì)算得到

式中，Ki為線狀要素第i個(gè)保留節(jié)點(diǎn)的貢獻(xiàn)值；Nr為保留節(jié)點(diǎn)的個(gè)數(shù)；Nd為圖形簡(jiǎn)化后距離限差內(nèi)應(yīng)舍棄的保留節(jié)點(diǎn)個(gè)數(shù)。其中，Nd的探測(cè)方法為:解碼抗體，沿線狀要素的數(shù)字化方向依次遍歷并計(jì)算各保留節(jié)點(diǎn)與其相鄰兩保留節(jié)點(diǎn)連線的垂直距離，且判斷該距離是否小于指定限差，是則說明該節(jié)點(diǎn)應(yīng)被舍棄。

3.算法流程及主要算子設(shè)計(jì)

基于免疫遺傳算法線狀要素圖形簡(jiǎn)化方法的流程如下:

1）隨機(jī)產(chǎn)生初始抗體種群Ab（0），令當(dāng)前算法迭代次數(shù)為T=0。

2）對(duì)抗體種群Ab（k）執(zhí)行克隆操作，得到新抗體種群Abc（k）。

3）對(duì)抗體種群Abc（k）執(zhí)行高頻變異操作，得到新抗體種群Ab'c（k）。

4）對(duì)抗體種群Ab'c（k）執(zhí)行交叉操作，得到新抗體種群Ab*（k）。

5）對(duì)抗體種群Ab*（k）中的抗體執(zhí)行修復(fù)操作，得到新抗體種群Ab'*（k）。

6）根據(jù)式（2）計(jì)算所有抗體的親和度。

7）對(duì)抗體種群Ab（k）和Ab'*（k）執(zhí)行克隆選擇操作，得到新抗體種群Ab（k+1）。

8）令T=T+1，若滿足終止條件，算法停止，將抗體種群中最優(yōu)的抗體解碼為線狀要素圖形簡(jiǎn)化方案；否則，返回步驟2）。

該算法中主要算子操作如下:

（1）克隆操作

克隆倍數(shù)決定算法的局部搜索能力及計(jì)算量。為獲得較好的圖形簡(jiǎn)化效果，簡(jiǎn)化方案對(duì)應(yīng)抗體的親和度越高則抗體被復(fù)制的倍數(shù)應(yīng)越大。其中，抗體被克隆的倍數(shù)可通過式（3）計(jì)算得到［7］

式中，Nc為抗體被克隆的倍數(shù)；β為增值系數(shù)，由用戶預(yù)設(shè)；N為種群規(guī)模；round（）為取整數(shù)操作。如N=10，β=1，則親和力最高的抗體（i=1）將被克隆10倍，親和度次高的抗體將被克隆5倍。

（2）高頻變異

變異是免疫遺傳算法中抗體親和度成熟和抗體多樣性產(chǎn)生的主要手段，決定著算法的全局搜索能力，變異概率決定算法收斂性能。本算法中抗體的變異是將抗體上某個(gè)基因位的值取反的過程，如圖1所示。在進(jìn)行變異操作時(shí)，各抗體上的基因值均按照一定的概率Pm隨機(jī)確定該基因位是否進(jìn)行變異。

圖1 抗體變異原理

（3）交叉操作

交叉是免疫遺傳算法保持種群進(jìn)化過程中抗體多樣性的輔助方式，決定算法的局部搜索能力。常用的交叉方式有單點(diǎn)交叉、兩點(diǎn)交叉和均勻交叉。本算法采用單點(diǎn)交叉方式，即將2個(gè)被選中抗體的基因鏈按照一定概率Pc進(jìn)行交叉，生成2個(gè)新的子抗體，交叉位置是隨機(jī)的（如圖2所示）。

圖2 抗體交叉原理

（4）不可行解的修復(fù)

不可行解修復(fù)機(jī)制的引入是為了保證線狀要素圖形簡(jiǎn)化過程中的幾何精度，其本質(zhì)是將抗體解碼為線狀要素圖形簡(jiǎn)化方案，以判斷線狀要素上各節(jié)點(diǎn)的保留及舍棄是否合理。具體操作步驟如下［6］:

1）判斷節(jié)點(diǎn)的舍棄是否合理。沿線狀要素方向依次取2個(gè)相鄰的保留節(jié)點(diǎn)，若該兩節(jié)點(diǎn)間存在已被舍棄的點(diǎn)，則尋找出與此兩節(jié)點(diǎn)連線距離最遠(yuǎn)的節(jié)點(diǎn)，計(jì)算該距離。若該距離小于指定的距離限差，則說明此兩節(jié)點(diǎn)間其他節(jié)點(diǎn)的舍棄均合理。繼續(xù)搜索判斷節(jié)點(diǎn)舍棄的合理性，若搜索至最后一個(gè)節(jié)點(diǎn)則轉(zhuǎn)到步驟2），否則繼續(xù)轉(zhuǎn)到步驟1）執(zhí)行；若該距離大于指定距離限差，說明搜索到的節(jié)點(diǎn)為不應(yīng)舍棄的點(diǎn)，將該點(diǎn)的抗體基因位的值由0變成1，繼續(xù)轉(zhuǎn)到步驟1）執(zhí)行。

2）判斷線狀要素上各保留節(jié)點(diǎn)的選取是否恰當(dāng)。沿線的方向依次取3個(gè)相鄰保留節(jié)點(diǎn)，計(jì)算中間節(jié)點(diǎn)到前后兩相鄰保留節(jié)點(diǎn)連線的垂直距離。若該距離小于指定距離限差，則說明該節(jié)點(diǎn)是應(yīng)舍棄的點(diǎn)，將其抗體上該節(jié)點(diǎn)基因位上的值由1變?yōu)?，繼續(xù)轉(zhuǎn)到步驟1）執(zhí)行；若該距離大于指定距離限差，說明該節(jié)點(diǎn)的保留是恰當(dāng)?shù)摹?/p>

三、試驗(yàn)與分析

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

本文采用的試驗(yàn)數(shù)據(jù)為某縣級(jí)境界線的部分?jǐn)?shù)據(jù)，原始線狀要素如圖3所示，線上有726個(gè)節(jié)點(diǎn)。本文將用不同的算法以不同的距離限差作為線狀要素?cái)?shù)據(jù)壓縮的條件進(jìn)行試驗(yàn)。

圖3 原始線狀要素

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

試驗(yàn)采用的距離精度限差為1～3 m。當(dāng)距離為1 m時(shí)，設(shè)置免疫遺傳算法的種群規(guī)模為100，增值系數(shù)為0.08，變異率為0.01，交叉率為0.002，運(yùn)行代數(shù)為200代。圖4是距離限差為1 m時(shí)免疫遺傳算法、免疫算法、遺傳算法和道格拉斯算法4種算法簡(jiǎn)化后的圖形；圖5是算法收斂曲線。各算法在不同距離限差條件下簡(jiǎn)化結(jié)果指標(biāo)值見表1。

圖4 距離限差為1 m的圖形簡(jiǎn)化結(jié)果

由試驗(yàn)結(jié)果可得到以下結(jié)論:

1）圖形上。4種算法的簡(jiǎn)化結(jié)果均能較好地保持線狀要素的形狀。道格拉斯算法在保持極值點(diǎn)方面表現(xiàn)較好；智能優(yōu)化算法在保持對(duì)線狀要素形狀保持貢獻(xiàn)更大的點(diǎn)方面表現(xiàn)更佳，簡(jiǎn)化后的圖形效果更好；免疫遺傳算法和單純免疫算法的簡(jiǎn)化結(jié)果一致，優(yōu)于遺傳算法的簡(jiǎn)化結(jié)果。

2）優(yōu)化算法效率。從算法收斂圖看，當(dāng)距離限差為1時(shí)，免疫遺傳算法在運(yùn)行118代后找到最優(yōu)解；免疫算法運(yùn)行185代后解達(dá)到最優(yōu)；遺傳算運(yùn)行200代仍未找到最優(yōu)解。免疫遺傳算法的收斂速度明顯快于單純的免疫算法和遺傳算法，算法效率更高。

3）綜合指標(biāo)。從表1可看出，免疫遺傳算法相對(duì)其他3種算法，在表示節(jié)點(diǎn)數(shù)相近的情況下，總的節(jié)點(diǎn)貢獻(xiàn)值最大，親和度函數(shù)值最大，算法保留了對(duì)圖形形狀貢獻(xiàn)較大的點(diǎn)。免疫遺傳算法在平衡保持線狀要素圖形特征點(diǎn)、減少保留節(jié)點(diǎn)數(shù)量和幾何精度控制上表現(xiàn)更佳。

圖5 算法收斂曲線圖

表1 不同距離限差下各算法的線狀要素圖形簡(jiǎn)化指標(biāo)對(duì)比

四、結(jié)束語

本文顧及線狀要素的幾何精度和圖形特征點(diǎn)，并結(jié)合不可行解修復(fù)機(jī)制，提出一種基于免疫遺傳算法的線狀要素圖形簡(jiǎn)化方法，在線狀要素圖形形狀特征的保持方面取得良好的效果，為智能算法應(yīng)用于地圖綜合領(lǐng)域提供了一定的理論和實(shí)踐基礎(chǔ)。研究成果也能為地圖生產(chǎn)提供相應(yīng)的理論指導(dǎo)和技術(shù)支持。同時(shí)，線狀要素簡(jiǎn)化過程中隨著比例尺的縮小可能產(chǎn)生的空間沖突、地理信息語義不一等問題的處理仍有待作進(jìn)一步研究。

［1］ DOUGLAS D，PEUCKER T.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature［J］.The Canadian Cartographer，1973，10（2）:112-122.

［2］ LI Z L，OPENSHAW S.Algorithms for Antomated Line Generalization Based on a Natural Principle of Objective Generation［J］.INT.J.Geographical Information Systems，1992，6（5）:373-389.

［3］ CROMLEY R G，GAMPBELL G M.Integrating Quantitative and Qualitative Aspects of Digital Line Simplification［J］.The Cartographic Journal，1992，29（1）:25-30.

［4］ 郭慶勝.線狀要素圖形綜合的漸進(jìn)方法研究［J］.武漢大學(xué)學(xué)報(bào):信息科學(xué)版，1998，23（1）:54-58.

［5］ 武芳，鄧紅艷.基于遺傳算法的線要素自動(dòng)化簡(jiǎn)模型［J］.測(cè)繪學(xué)報(bào)，2003，32（4）:349-355.

［6］ 鄭春燕，郭慶勝，胡華科.基于蟻群優(yōu)化算法的線狀目標(biāo)簡(jiǎn)化模型［J］.測(cè)繪學(xué)報(bào)，2011，40（5）:635-638.

［7］ 梁勤歐.人工免疫系統(tǒng)與GIS空間分析應(yīng)用［M］.武漢:武漢大學(xué)出版社，2011.

［8］ DE CASTRO L N，VONZUBEN F J.Artificial Immune System:Part I——Basic Theory and Applications［M］.Campinas，SP:State University of Campinas，1999.

［9］ 郭慶勝，黃遠(yuǎn)林，鄭春燕，等.空間推理與漸進(jìn)式地圖綜合［M］.武漢:武漢大學(xué)出版社，2007.

［10］ FREKSA C，BRAUER W，HABEL C，et al.Spatial Cognition II:Integrating Abstract Theories，Empirical Studies，F(xiàn)ormal Methods，and Practical Application［M］.Berlin:Springer，2000.