基于快速模拟退火算法的地图微缩研究

张明超 （中国地质大学 （北京）地球科学与资源学院，北京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.