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

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

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

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

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

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

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

目標函數(shù)的計算公式為：

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

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

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

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

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

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

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

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

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

3 算法過程詳解

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

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

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

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

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

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

3.3 溫度更新函數(shù)

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

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

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

3.4 初始溫度的計算

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

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

4 試驗結果

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

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

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

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

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

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

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

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