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

張明超 （中國地質大學 （北京）地球科學與資源學院，北京100083）

蔡永香 （長江大學地球科學學院，湖北 荊州434023；武漢大學資源與環境科學學院，湖北 武漢430079）

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

在1982年，Kirkpatrick等受物理學中金屬退火過程的啟迪，將其引入組合優化領域，超越金屬退火過程具體的物理意義，從而形成了模擬退火算法[1]。近年來，模擬退火算法在很多領域的大規模組合優化問題整體最優解的求解中得到了廣泛的應用，取得了很好的效果。

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

1 地圖微縮優化顯示模型

假設目標函數f（i）代表所有點線圖元的一種組合模式，也就是一個i值對應著一幅地圖的可能顯示模式。假定一幅地圖有m個點狀要素，n個線狀要素，那么在i狀態下，地圖顯示模式[4]可表示為：

目標函數的計算公式為：

式中，g（j）和k（j）分別是用于計算線圖元和點圖元的權重得分：

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

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

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

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

步1 求出當前比例尺下應該顯示的點線圖元數，并隨機產生一個初始解，以此作為當前最優解，并計算目標函數值。

步2 利用Cauchy分布產生一個隨機擾動，作為一個新解，并計算新解的目標函數值。

步3 計算目標函數的增量ΔE，若ΔE＞0，則接收新解作為當前最優解；若ΔE＜0，則以概率P＝[1-（1-h）ΔE／t]1／（1-h）進行接收。

步4 程序正常運行過程，慢慢降低溫度t。

3 算法過程詳解

3.1 狀態函數的產生

狀態函數就是對當前組合的隨機擾動，以尋求更優組合。Ingber（1989）提出的快速SA方法[3]中，采用似Cauchy分布產生新狀態，即：

式中，mj為當前模型中的第j個變量；u為[0，1]均勻分布的隨機數；[Aj，Bj]為mj的取值范圍，且要求擾動后的mj∈[Aj，Bj]，sgn（x）為符號函數，t為溫度。該分布的優點在于低溫時易于迅速跳出局部極值，從而加快了收斂速度。

3.2 概率接收函數與接收方式

筆者采用的概率接收函數公式為：

式中，ΔE為擾動得到的新模型的目標函數f（j）與當前模型的目標函數f（i）之差，即ΔE＝f（j）-f（i）；t為溫度；h為實數。若用Pt表示狀態j置換狀態i的轉移概率，則有：

3.3 溫度更新函數

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

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

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

3.4 初始溫度的計算

在某個顯示比例尺下，計算需要顯示的圖元量，通過計算若干次隨機變換目標函數平均增量的方法，來確定初始溫度t0，即：

注意在上述計算t0過程中，取應用Metropolis準則[4]接受不改變當前組合模式的狀態轉移概率閾值P為1／3。

4 試驗結果

試驗采用荊州市1∶70000的數字地圖 （見圖1）進行模擬退火算法的微縮，微縮結果 （見圖2）表明模擬退火算法運用于地圖微縮有較好的效果。

圖1 荊州區1∶70000數字地圖

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

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

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

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

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

[5]萬偉鋒，李云峰，張娟娟.快速模擬退火算法在含水層參數識別中的應用[J].煤田地質與勘探，2005，33（6）：56-60.