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 并行模拟退火算法，在将经典的模拟退火算法做重大的并行化 改进的同时，结合了下山法快速收敛的特点，是一种可扩展的大规模并行算法。该算法可 以在有限的时间内快速找到最优解或近似最优 …… 此处隐藏：6027字，全部文档内容请下载后查看。喜欢就下载吧 ……