0104079模拟退火算法应用

武汉工程大学

一 参考文章

混合 SPMD 模拟退火算法及其应用

都志辉 李三立

（清华大学计算机科学与技术系 100084）

摘要 模拟退火算法由于有很好的数学特性——以概率 1 收敛于全局最优值，再加上其算法本身与特定的问题无关，因此被广泛地用于各种组合优化问题。但是，模拟退火算法又是一种 NP 类算法，具有收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点，使得它在不少应用中成为一种低效甚至是不可行的算法。收敛速度慢和参数敏感成为模拟退火算法的主要缺点。本文提出一种混合 SPMD 模拟退火算法，在克服经典模拟退火算法内在串行性的同时，进一步和下山法结合起来，并综合多种优化方法，取得大规模可扩展的并行效果，显著提高了算法的收敛速度，克服了算法性能对初始值和参数选择的过分依赖，在提高算法性能的同时，方便了算法的使用。该算法已在一个机群系统 THNPSC-1上得以实现，并在材料科学的一个定量电子晶体学研究问题中得到应用，降低了求解时间，

提高了求解质量。

关键词 模拟退火算法， 下山法， 多参数组合优化

一 介绍

模拟退火（Simulated Annealing）算法是一种随机算法，多用于复杂的组合优化问题及 NP 问题。其思想来源于物理上的退火过程，同时在数学上又有很好的模型“马尔可夫链”（Markov chain）可以对它进行严格地形式化描述，基于马尔可夫过程理论，可以证明模拟退火算法以概率 1 收敛于全局最优值，这是一条很好的数学特性。 模拟退火算法是一种解决组合优化问题的通用算法，只要优化问题能提供一个对候选方案的适应性函数或费用函数，即可使用模拟退火算法对它求解。它已成功地用于多种复杂的问题，如芯片及线路布局设计，货郎担问题（traveling salesman problem）等。

模拟退火算法存在的主要问题是运行时间太长，其性能有时甚至还不如简单的枚举算 法。模拟退火算法本身具有内在的串行化要求（下一点的选取直接依赖于上一点），不易 实现高效的大规模并行化处理；其次，模拟退火算法的性能对参数及初始值的选取十分敏 感，不同的参数可能导致算法性能的巨大差异。而优化参数设置和具体的问题是密切相关 的，这些方面都限制了模拟退火算法的应用效果。

本文针对经典模拟退火算法存在的两个主要问题进行研究，以机群系统作为算法实现 的主要并行计算平台，提出了一种混合 SPMD 模拟退火算法，在一个跨学科合作研究项目 “定量会聚束电子衍射（QCBED--Quantitative Convergence Beam Electron Diffraction） 分析方法的大规模并行实现”中得到应用，为定量会聚束电子衍射分析方法在计算时间和 计算精度上提供了保证。

283

武汉工程大学

二 相关工作

并行模拟退火算法有许多种，但它们一般都不适用于机群计算，机群计算是一种松同 步的计算模式，鼓励尽量降低通信次数和扩大通信与计算的重叠，而细粒度的并行模拟退 火算法只是在一条马尔可夫链内采取并行措施，是一种操作并行方法，经常导致高的通信 开销，因此只能得到有限的加速。粗粒度大规模并行的模拟退火算法同时保持多条马尔可 夫链，各个计算结点可以在达到同步点之前相互并行的进行计算，这种算法可以取得很高 的加速比并且具有较好的扩展性，本文的算法就是一种粗粒度大规模并行模拟退火算法， 它适合于机群计算。

提出了一种混合算法，将模拟退火和遗传算法（Genetic Algorithm）[4]融为一 体，通过利用遗传算法天然的并行性，结合模拟退火算法的全局寻优能力，是一种高效的 并行方法。但这种方法是针对 SIMD 并行计算机设计的，在机群系统上缺乏必要的硬件支 持，会产生很高的通信开销，因此不适合机群计算。不过此算法思想对我们很有启发，我 们在本算法的基础上，正在进一步研究基于机群计算的能够将模拟退火、遗传算法和下山 法有机结合的新型算法。

提出了一种阈值接受算法，该算法修改了模拟退火的接受准则，用一个阈值来替 代模拟退火中的温度，它接受任何阈值之内的解。这种接受准则比较简单，接受条件计算 量也比较小，但没有实现并行化。除了接受条件的计算有了一些简化之外，它具有原来模 拟退火算法存在的所有缺点。

通过使用推测的办法（speculative computation），对马尔可夫链接受或拒绝新3 解两个可能的分支同时计算，以提高并行速度。因为它只是设法在一条马尔可夫链内采取 并行手段，属于细粒度的并行，获得的并行加速并不高，当并行计算的结点增多时，该并 行任务二叉树也会变深，这必将产生很大的通信开销，并且根结点将成为性能的瓶颈，算 法扩展性较差，也不适合在机群上应用。

在机群计算中，一般而言，粗粒度的并行比细粒度的并行效果要好，它所需要的是 SPMD 类的并行算法而不是 SIMD 或 MIMD 类的算法，只有这样才能减少通信，扩大并行效果，

取得理想的加速。

三 本文算法的主要特点

本文提出的混合 SPMD 并行模拟退火算法，在将经典的模拟退火算法做重大的并行化 改进的同时，结合了下山法快速收敛的特点，是一种可扩展的大规模并行算法。该算法可 以在有限的时间内快速找到最优解或近似最优解，如果时间允许，可以用同样的算法进一 步对近似解进行优化。该算法是一个针对网络并行系统或机群系统的并行算法，在一定的 处理器范围之内（对 QCBED 问题是 2-16 个），参与计算的处理器越多，就可以在同样的时 间内找到更好的近似解，或用较少的时间找到同样精度的近似解。本算法的另一个优点是 避免了经典模拟退火算法对参数的依赖性，对于本算法，不需特别精心设计与选择参数， 同样能够得到满意的性能。本文算法的特点可以概括为如下几个方面：

1、 将经典的模拟退火算法中的一条马尔可夫链分裂为多条马尔可夫链 ，取得了可

284

武汉工程大学

扩展的并行性，打破了经典模拟退火算法并行化的瓶颈。

2、将具有全局优化特性的模拟退火算法和具有局部优化特性的下山法结合起来，既 可以跳出局部极值点区域，又能够加快优化速度。

3、降低了对参数选择的要求，经典模拟退火算法对初始温度和初始值有很高的要 求，不同的初始值和初始温度对算法的性能影响很大，但用本文提出的算法，最 终解的质量和找到该解所需要的时间不会因初始值的不同而有很大的波动，本算 法放宽了初始值的选择范围，从而方便了初始值的选取和算法的使用。

4、根据退火过程的不同阶段的特点，利用回火退火和引入产生函数扰动因子，来控 制搜寻全局最优值的范围，既可以提高求解速度，又不降低求解质量。

5、通过记忆马尔可夫链的最优值，并按一定的时间间隔对不同马尔可夫链得到的最 优值进行交换，从而加快了优化的过程。

6、该算法可以被中断，下次计算可以从中断点附近继续进行，而不需要一切从头开 始。

四 算法应用

1、系统环境

本算法已在一个机群系统上得以实现，该系统有 8 个计算结点，每个结点是一个双 CPU 的 SMP(Symmetric Multiple Processors)结构，CPU 是 Pentium III 500Mhz，通信网络采 用的是 100Mbps 的高速以太交换网。操作系统是 Linux Redhat 5.1，并行系统是 MPI，其实现采用的是 mpich-1.1.1。 2、关于多极值点函数的测试

在经典的模拟退火过程中嵌入下山后其收敛性如何？本算法采取的并行策略对收敛 性有何影响？下面通过四个多局部极值点函数 f1,f2,f3,f4 进行了实例测试，用本文提出 的算法来求这四个函数的最小值。这四个函数的定义如下：

f1 的最小点是 f1(0,0)=0，f2 有 169 个局部极小点，其最小点是 f2(0,0)=0，f3 有 103个

局部极小点，它的最小点是 f3(1,1,1)=0，f4 的形状比较怪，是一个狭长的山谷形状，其

285