基于快速模擬退火算法的地圖微縮研究

張明超 （中國(guó)地質(zhì)大學(xué) （北京）地球科學(xué)與資源學(xué)院，北京100083）

蔡永香 （長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北 荊州434023；武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢430079）

模擬退火算法思想源于物理學(xué)中固體物質(zhì) （如金屬）的退火過(guò)程。處于高能態(tài)的粒子可以自動(dòng)移動(dòng)，隨著溫度的降低，粒子將逐漸形成低能態(tài)的晶體。只要在凝固點(diǎn)附近，溫度下降的足夠慢，粒子就會(huì)擺脫應(yīng)力的束縛，從而形成最低能量的基態(tài)。在此種狀態(tài)下，晶格粒子排列最為完美。

在1982年，Kirkpatrick等受物理學(xué)中金屬退火過(guò)程的啟迪，將其引入組合優(yōu)化領(lǐng)域，超越金屬退火過(guò)程具體的物理意義，從而形成了模擬退火算法[1]。近年來(lái)，模擬退火算法在很多領(lǐng)域的大規(guī)模組合優(yōu)化問(wèn)題整體最優(yōu)解的求解中得到了廣泛的應(yīng)用，取得了很好的效果。

地圖微縮的目的就是達(dá)到大比例尺和小比例尺的自動(dòng)轉(zhuǎn)換，但是又不是簡(jiǎn)單的將地圖縮小，簡(jiǎn)單縮小會(huì)導(dǎo)致所有的地圖要素都堆積在一起，影響視覺(jué)效果[2]。地圖微縮之后要能保持城市的整體交通風(fēng)貌，如北京的交通網(wǎng)呈方正狀，莫斯科的交通呈放射狀，同時(shí)要將重要的要素保留，如歷史古跡，沙漠中的一條小河等。對(duì)于一副較大的地圖，其數(shù)據(jù)量經(jīng)常是很大的，用一般的模擬退火算法實(shí)現(xiàn)可能收斂速度太慢，甚至難以實(shí)現(xiàn)。下面，筆者采用快速模擬退火算法實(shí)現(xiàn)。與一般的模擬退火算法相比，快速模擬退火算法具有3方面的優(yōu)勢(shì)：①采用Cauchy分布生成新模型[3]，而不是用簡(jiǎn)單的均勻概率分布產(chǎn)生的模型；②接受概率函數(shù)采用新的概率方式；③溫度下降方式采用快速的降溫方式。

1 地圖微縮優(yōu)化顯示模型

假設(shè)目標(biāo)函數(shù)f（i）代表所有點(diǎn)線圖元的一種組合模式，也就是一個(gè)i值對(duì)應(yīng)著一幅地圖的可能顯示模式。假定一幅地圖有m個(gè)點(diǎn)狀要素，n個(gè)線狀要素，那么在i狀態(tài)下，地圖顯示模式[4]可表示為：

目標(biāo)函數(shù)的計(jì)算公式為：

式中，g（j）和k（j）分別是用于計(jì)算線圖元和點(diǎn)圖元的權(quán)重得分：

對(duì)于線圖元即g（j）函數(shù)而言，x1代表第j條線圖元的固定得分，如該線表示高速公路、國(guó)道、鐵路則可以賦予固定得分4分，省級(jí)道路則賦予3分，縣級(jí)道路則賦予2分，鄉(xiāng)村級(jí)道路則賦予1分；x2的得分規(guī)則是對(duì)第j條線元素，給定其一個(gè)緩沖半徑，依據(jù)落在緩沖半徑內(nèi)的線元素的條數(shù)賦予得分，每條線得0.1分，如有5條線落在緩沖半徑內(nèi)，則賦予0.1×5＝0.5分；x3的得分規(guī)則是給第j條線元素一個(gè)緩沖半徑，依據(jù)落在緩沖半徑內(nèi)的點(diǎn)元素的個(gè)數(shù)賦予得分，每個(gè)點(diǎn)賦予0.05分，如有10個(gè)點(diǎn)元素落入緩沖半徑內(nèi)，則賦予0.05×10＝0.5分。對(duì)于點(diǎn)圖元，即k（j）函數(shù)而言，y1代表第j個(gè)點(diǎn)圖元的固定得分，如給名勝景點(diǎn)賦予2分，大學(xué)、醫(yī)院、飯店，賦予1分，其他的賦予0.5分；y2的得分規(guī)則是以第j點(diǎn)位圓心做個(gè)緩沖圓，依據(jù)落入該圓內(nèi)的線圖元的條數(shù)賦予得分，每條賦予0.1分；y3的得分規(guī)則是以第j點(diǎn)為圓心做個(gè)緩沖圓，依據(jù)落入該圓內(nèi)的點(diǎn)圖元的個(gè)數(shù)賦予得分，每個(gè)點(diǎn)圖元賦予0.05分。這樣的賦分規(guī)則能有效的保證地圖微縮時(shí)，首先舍棄不重要的點(diǎn)，線元素，保留居住密集，交通發(fā)達(dá)的地區(qū)。

對(duì)地圖的微縮顯示規(guī)則采用簡(jiǎn)單的舍棄不重要圖元的方法。如對(duì)地圖縮小10%，則舍棄10%的線類圖元和10%的點(diǎn)類圖元。這種方法很簡(jiǎn)單且效果較好。

2 快速模擬退火算法的步驟

快速模擬退火算法的步驟[5]如下：

步1 求出當(dāng)前比例尺下應(yīng)該顯示的點(diǎn)線圖元數(shù)，并隨機(jī)產(chǎn)生一個(gè)初始解，以此作為當(dāng)前最優(yōu)解，并計(jì)算目標(biāo)函數(shù)值。

步2 利用Cauchy分布產(chǎn)生一個(gè)隨機(jī)擾動(dòng)，作為一個(gè)新解，并計(jì)算新解的目標(biāo)函數(shù)值。

步3 計(jì)算目標(biāo)函數(shù)的增量ΔE，若ΔE＞0，則接收新解作為當(dāng)前最優(yōu)解；若ΔE＜0，則以概率P＝[1-（1-h）ΔE／t]1／（1-h）進(jìn)行接收。

步4 程序正常運(yùn)行過(guò)程，慢慢降低溫度t。

3 算法過(guò)程詳解

3.1 狀態(tài)函數(shù)的產(chǎn)生

狀態(tài)函數(shù)就是對(duì)當(dāng)前組合的隨機(jī)擾動(dòng)，以尋求更優(yōu)組合。Ingber（1989）提出的快速SA方法[3]中，采用似Cauchy分布產(chǎn)生新?tīng)顟B(tài)，即：

式中，mj為當(dāng)前模型中的第j個(gè)變量；u為[0，1]均勻分布的隨機(jī)數(shù)；[Aj，Bj]為mj的取值范圍，且要求擾動(dòng)后的mj∈[Aj，Bj]，sgn（x）為符號(hào)函數(shù)，t為溫度。該分布的優(yōu)點(diǎn)在于低溫時(shí)易于迅速跳出局部極值，從而加快了收斂速度。

3.2 概率接收函數(shù)與接收方式

筆者采用的概率接收函數(shù)公式為：

式中，ΔE為擾動(dòng)得到的新模型的目標(biāo)函數(shù)f（j）與當(dāng)前模型的目標(biāo)函數(shù)f（i）之差，即ΔE＝f（j）-f（i）；t為溫度；h為實(shí)數(shù)。若用Pt表示狀態(tài)j置換狀態(tài)i的轉(zhuǎn)移概率，則有：

3.3 溫度更新函數(shù)

一般的模擬退火算法的溫度更新函數(shù)采用簡(jiǎn)單的線性變化，即tk＋1＝λtk，其中λ為人為給定的小于1的參數(shù)，用來(lái)控制退火速度。λ太大，則退火速度過(guò)快，容易陷入局部最優(yōu)解中，λ太小，則降溫太慢，影響程序運(yùn)行效率。Ingber（1989）給出了非常快速模擬退火方法的降溫方式[3]：

式中，t0為初始溫度；k為迭代次數(shù)；C為給定的常數(shù)；M為待計(jì)算參數(shù)個(gè)數(shù)。為計(jì)算方便，將上式改寫成：

式中，a的取值范圍通常為0.7＜a＜1。

3.4 初始溫度的計(jì)算

在某個(gè)顯示比例尺下，計(jì)算需要顯示的圖元量，通過(guò)計(jì)算若干次隨機(jī)變換目標(biāo)函數(shù)平均增量的方法，來(lái)確定初始溫度t0，即：

注意在上述計(jì)算t0過(guò)程中，取應(yīng)用Metropolis準(zhǔn)則[4]接受不改變當(dāng)前組合模式的狀態(tài)轉(zhuǎn)移概率閾值P為1／3。

4 試驗(yàn)結(jié)果

試驗(yàn)采用荊州市1∶70000的數(shù)字地圖 （見(jiàn)圖1）進(jìn)行模擬退火算法的微縮，微縮結(jié)果 （見(jiàn)圖2）表明模擬退火算法運(yùn)用于地圖微縮有較好的效果。

圖1 荊州區(qū)1∶70000數(shù)字地圖

圖2 原圖縮小后的地圖顯示

[1]康立山.非數(shù)值并行算法 （第1冊(cè)）：模擬退火算法[M].北京：科學(xué)出版社，1994：22-28.

[2]祝國(guó)瑞.高等學(xué)校測(cè)繪工程專業(yè)核心教材：地圖學(xué)[M].武漢：武漢大學(xué)出版社，2004：161-261.

[3]張霖斌，姚振興.快速模擬退火算法及應(yīng)用[J].石油地球物理勘探，1997，32（5）：654-660.

[4]羅廣祥，馬智明，田永瑞.基于模擬退火算法的自動(dòng)地圖注記配置研究[J].測(cè)繪科學(xué)，1999，2：11-16.

[5]萬(wàn)偉鋒，李云峰，張娟娟.快速模擬退火算法在含水層參數(shù)識(shí)別中的應(yīng)用[J].煤田地質(zhì)與勘探，2005，33（6）：56-60.