退火算法在地下结构中的研究进展

在自然科学、社会科学以及人们的日常生活中，广泛存在着大量的求最大、最小值的问题，即最优化的问题。特别是自20世纪80年代以来，在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路设计、代码设计、图像处理和电子工程等科技领域中，大量的组合优化问题需要解決。模拟退火算法（Simulated Annealing，SA）是一种近年被广泛应用于实际工程中的全局最优算法，也是局部搜索算法的扩展。

模拟退火算法的核心思想——Metropolis准则最早是在1953年由Metropolis等人在研究二维相变时发现的，1983年由kirkpatrick等成功地引入到组合优化领域中。从此，模拟退火算法开始被大规模、广泛地应用于组合优化求解的问题中。

German S.和German D.于1984年在其文章Equations of State Calculation by Fast Computing Machines中给出了退火率与退火时间的对数成反比的模拟退火算法。Cerny V.于1985年运用模拟退火算法求解旅行商问题（Traveling S alesman Problem，简称TSP问题）获得成功。H.Szu于1986年提出了一种退火率与时间成反比的快速模拟退火算法（Fast Simulated Annealing，FSA）。此后，模拟退火算法进入了各个领域的应用研究阶段。1987年，Corana A.在求解多目标连续变量优化问题中应用了模拟退火算法；同年，Laarhoven P.和Aarts E.在其出版的《模拟退火的理论和应用》一书中，系统地对模拟退火算法做了总结，促进了模拟退火算法在理论研究和实际应用等方面的发展，是模拟退火算法发展史上伟大的里程碑。

1989年，Charnes A.和Wolfe M.进行了模拟退火算法的收敛性研究；同年，Aarts E.等将模拟退火算法同人工神经网络结合起来分析玻耳兹曼机。1990年，Gunte D.和Tobias S.对模拟退火算法中初始温度临界值的确定方法进行了研究。1992年，Laarhoven P.等人将模拟退火算法用于解决Jobshop这一NP完全问题；同年，Ingber L.等人提出了VFSA（Very Fast Simulated Annealing）算法，并将其应用于数学连续函数优化问题中，而且与遗传算法进行了比较。结果表明VFSA算法的计算精度和计算效率都明显高于标准的遗传算法。Kirkpatrick S.等人于1993年将模拟退火算法应用于优化问题中，并取得了不错的效果；同年，Lin F.等人为解决一些NP完全问题中比较困难的问题，将模拟退火算法和遗传算法进行结合，并将这一方面的研究做了总结。1995年，Tarek M.等人提出了并行的模拟退火算法，该算法较标准的模拟退火算法在计算效率方面有明显的提高，更适合用来解决复杂的科学和工程问题。Ali和Storey对连续变量的优化问题进行了深入研究，并于1997年发展出ASA（Aspiration based Simulated Annealing）算法；随后，Ali又在此基础上提出了DSA（Direct search Simulated Annealing）算法，这两个算法都具有较好的时间逼近的多项式。

国内也有许多优秀的学者正在进行模拟退火算法的理论和应用研究。徐雷于1989年成功地将模拟退火算法应用于模式识別中，并取得了不错的效果；1997年，胡山鹰等人在无约束非线性规划问题全局优化的模拟退火算法基础上，进一步进行了求解有约束问题的探讨，对约束条件为不等式的情况，提出了检验法和罚函数法两种处理方法，对约束条件为等式的情况，开发了罚函数法和解方程法的求解步骤，并进行了分析比较，形成了完整的求取非线性规划问题全局优化的模拟退火算法。

张玉祥等人于1998年在采矿工程领域最优化设计过程中，应用模拟退火算法初步探索了该领域求解全局最优解的问题，他们给算法增加了一个“记忆器”，使它能够记住搜索过程中曾经达到过的最好结果，从而可以在许多情况下提高最终所得到的解的质量。

1998年，蔡文学等人对应用于平面析架结构拓扑优化设计中的模拟退火算法进行了研究，构造了一个双重控制Metropolis准则处理应力约束，提出了一个基于力平衡的启发式准则，以实现优化过程中单元的自动增删，该方法能够克服析架结构拓扑优化中因存在非凸星形可行域而造成的拓扑优化求解困难。康立山等于1999年出版了《非数值并行算法》（第一册），其中对并行的模拟退火算法做了比较概括、系统的总结和归纳；同年，王子才等人提出基于混沌变量的一种混沌模拟退火优化算法，并给出了初始温度的确定方法。改进后算法的主要思想是：利用混沌变量对当前点进行扰动，随着搜索的深入逐渐减小扰动的幅度，该方法显著提高了全局优化问题求解过程中的计算效率；同年，王雅琳等人对模拟退火算法的搜索过程进行了深入的研究，对模拟退火算法在搜索初期和后期两种情况下算法可能长期陷入局部点无法跳出的原因进行了分析，并分别采用变异操作和扩大搜索空间的方法对一种単循环模拟退火算法进行了改进的。

2000年，向阳等人对推广模拟退火方法的基本思想及其统计基础进行了介绍，使用一系列标准函数对推广模拟退火算法的性能进行了测试，讨论了推广模拟退火方法的效率随体系复杂性的变化规律；同年，席自强针对模拟退火算法本身存在的收敛慢、费时较多和效率较低等不足，将模拟退火算法与单纯型法有机地结合在一起，形成了一种新的改进的优化算法——单纯形模拟退火算法，改进后的算法收敛速度明显加快，解的质量明显提高，融合了单纯形法和模拟退火算法各自的优点。

2001年，都志辉等人提出一种新的模拟退火算法——混合SPMD模拟退火算法，该算法在克服标准模拟退火算法内在串行性的同时，进一步和下山法结合起来，综合多种优化方法的特点，在一定的处理机规模内取得了可扩展的并行效果，改进后算法的收敛速度有了显著提高，降低了算法性能对初始值和参数选择的依赖性，不仅提高了算法性能，同时还方便了算法的使用；同年，江加等人对模拟退火算法在连续变量全局优化问题中的应用进行了研究，并给出了具体的实现步骤，介绍了实用的选择控制参数的方法，针对连续变量的特殊性，也给出了实用的新解产生方法；同年，杨庆之等人为了解决标准模拟退火算法搜索空间过大，难以利用领域知识等问题，提出了具有约束指导的模糊退火算法，并给出了关于抽样次数选择、新解产生等问题的一些新方法，以间歇过程生产调度为背景进行的算法仿真实验表明，应用该算法后，收敛速度有了较大的提高。

高齐圣等人于2002年基于均匀设计的思想，针对参数设计中的一类非线性规划问题，提出了一种用于全局优化的模拟退火并行算法：同年，耿平等人使用人工神经网络的方法建立多变量与多目标函数之间的关系，并将模拟退火算法与人工神经网络BP（Error Back Propagation）算法相结合，解决了这类复杂系统中多函数变量与多目标函数之间没有确定的解析关系而无法直接优化的难题，并为解决多变元非线性复杂系统的优化问题提供了一种新的、有效的方法。目前，模拟退火算法迎来了兴盛时期，无论是理论研究还是应用研究都成为了十分热门的课题。尤其是模拟退火算法的应用研究显得格外活跃，已被用于经济、电信、超大规模集成电路的计算机的辅助设计、模式识别和图像处理、求解“NP完全问题”、图的分配问题、人工智能和人工神经网络、离散/连续变量的结构优化问题等，在化学工程、系统科学和管理、光学工程、地球物理反演等领域都得到了应用。在它得到实际应用后，由于其在解決局部极小问题上的突出表现而迅速得到人们的青睐，也引起了众多学者广泛的研究兴趣，使模拟退火算法得到了突飞猛进的发展。国内引进模拟退火算法的历史较短，相比于遗传算法、蚁群算法所进行的研究也不是很多，而且大多数都是关于模拟退火在工程等方面的实际应用以及考察算法的实际效果和效率，较少对其理论性有深入的研究。

下面重点介绍经常在实际中被应用的模拟退火算法的改进算法。

1.有记忆的模拟退火算法

模拟退火算法在迭代过程中不但能够接受目标函数向好的方向前进的解，而且能够在一定限度内接受使目标函数恶化的解，这使得算法能够有效地跳出局部极小的陷阱，但对于具有多个极值的工程问题，该算法就很难保证最终得到的最优解是整个搜索过程中曾经到达过的最优解。为了解决这一问题，可以为算法增加一个“记忆器”，通过“记忆器”来记住搜索过程中曾经出现过的好结果，从而可以提高最终得到的最优解的质量。

具有记忆能力的模拟退火算法的详细实现过程如下所述：

1）设置一个变量x，以此来记录到目前为止所出现过的最好的解，并以f（x）同时记录到目前为止所出现过的最好的目标函数值。

2）在实现算法的初始阶段，设x和f（x）的初始值分别为x0和f（x0），并以此初始值为基础进行迭代，即在每次得到一个新解时用新解所对应的f（xk）值和现有的最优解对应的f（x）进行比较，选其优者作为现阶段最优解f（x）。

3）完成算法的迭代过程后，将当前得到的解和变量x中存储的解相互比较，选择其中较为优秀的作为目标函数f（x）近似的全局最优解。

2.单调升温的模拟退火算法

模拟退火算法可以按一定的概率接受目标函数值不太好的状态，当温度控制参数充分大的时候，接受概率接近于1，即算法此时是在进行全局搜索；当温度控制参数充分小的时候，接受概率几乎接近于0，如果此时搜索陷入局部最优状态，则该算法跳出局部最优解的时间将会非常长。显然，跳出局部最优解花费时间长是由差解的接受概率过低造成的，那么可以通过在搜索陷入局部最优时人为提高温度控制参数，借此提高对差解的接受概率，以此来缩短跳出局部最优解的时间。上述内容即为单调升温模拟退火算法的主要思想。判定捜索进入局部最优的方法如下：假设搜索进入局部最优点，那么在当前解的优化程度小于当前最优解的优化程度时，差解的接受概率几乎为1，但是，当温度足够低时，差解的接受概率接近0。因此，可以总结得出搜索陷入局部最优时的特征如下：(www.xing528.com)

1）由于局部最优点邻域内的所有点的优化程度都小于局部最优点的优化程度，所以在最近的若干次搜索中都没有出现过优化程度更高的解。

2）由于搜索已经陷入局部最优，所以局部最优解以及在局部最优解邻域内与局部最优解的优化程度相同的少数若干个点可能会在最近的几次搜索所接受的新解中反复出现。

如果具备以上两个特征，则说明搜索已经进入局部最优，并且温度过低，想要尽快跳出局部最优，就需要提高温度控制参数。如何确定升温幅度呢？升温是为了跳出局部最优的陷阱。如果升温幅度过小，则不能达到效果；但若升温幅度过大，捜索可能会进入全局搜索，等于重新开始模拟退火搜索。一般来说，可将温度控制参数升高到接受概率为60%～70%的范围内，这样既可以保证搜索快速跳出局部最优，又可以避免重新开始全局搜索。

3.并行的模拟退火算法

模拟退火算法是在某一当前状态的邻域中随机产生一个新的状态并以一定概率接受的一种随机搜索算法。可见，接受概率仅依赖于新状态和当前状态，即下一个状态的产生只和上一个状态有关，从而从本质上决定了模拟退火算法是一种串行的随机优化过程，这对算法的优化效率产生了影响，选取合适的冷却进度表能使算法得到满意的结果，但并不足以从根本上提高算法的效率。解决这一问题的办法是，将原有的模拟退火算法并行实现以提高算法性能。

4.单纯型模拟退火算法

单纯型模拟退火算法是将单纯型法与模拟退火算法相结合的一种混合算法。

单纯型法是由Nelder和Mead提出的一种多变量函数的寻优算法。该算法应用规则的几何图形，计算规则几何图形顶点的函数值，根据计算得到的函数值的大小分布来进一步确定函数变化的趋势，然后按照一定的规则逐渐搜索出最优解。因为该算法不是沿着某一方向进行搜索，所以并不用计算目标函数的梯度。这种算法是通过对N维空间的N+1个点上的函数值进行比较，丢弃其中最差的点，从而构成一个新的单纯型，这样逐步迭代直到找到极小值点。

模拟退火算法是一种随机搜索算法，它能跳出局部极小的陷阱并最终得到全局极小值，但在搜索的过程中做了很多的无用功，浪费了时间，效率还有待改进。单纯型算法的优点是，能够直接快速地搜索到极小值，对于大型、复杂的函数求极值问题，不会出现收敛性不稳定的情况。因此，可以把模拟退火算法与单纯型进行结合，融合两种算法的优点，求解函数的极小值。融合后的算法的基本思想是，对任一给定的初始解，首先用单纯型法快速求得一个极小值点，然后改用模拟退火算法进行随机捜索，跳出该局部枚小值，一旦找到一个比该局部极小值更小的点，则以该局部极小值点为初始值使用单纯型法搜索该点附近的另一个极小值点，如此交叉进行，直至满足算法结束条件，得到的结果即为全局极小值。

5.推广的模拟退火算法

模拟退火算法的根本思想是，使用当前解根据某种规则生成一个新的解，并根据一定规则判断是否接受此新解。在这个过程中，产生新解的步骤也可称为跃迁分布，即随机地从Xn跃迁到Xn+1。推广模拟退火算法是以Tsallis统计的一些知识（包括Tsallis熵、Tsallis概率分布等）为基础提出的，它将模拟退火算法中原有的跃迁方式和接受概率的计算方法进行改进，利用得到的推广跃迁分布和推广接受概率来进行全局最优解的搜索。

模拟退火算法的思想和原理比较清晰，实际实现起来也比较简单，而且它的效果和其他很多算法比较起来也是相当优秀的，不但能找到所需的全局最优解，而且花费的时间也比较少。因此，模拟退火算法获得了很多人的关注，人们也在不断地对它进行着完善和改进。上面所提到的对模拟退火算法的改进都是在模拟退火算法的原理基础上或通过添加规则，或通过转为并行设计，或与其他算法相结合等，都具有很强的适应性，在实际应用中也都取得了很好的效果。总之，模拟退火算法是一种实用性很强的算法，能够应用到很多实际问题中，而且也很容易构建出合理的数学模型进行求解，很值得进一步对其进行研究和改进。

目前，模拟退火算法在理论上已经证明了该算法可以达到全局极小值，所以它开始广泛受到专家与学者们的青睐和重视。事实上，正是由于专家和学者们对该算法的钻研，才使该算法从经典的模拟退火算法走到了今天具有多样性的模拟退火算法，比如快速模拟退火算法（Fast Simulated Annealing，FSA），该改进算法的搜索速度和收敛性都得到较大提高；再比如具有适应性的模拟退火算法，该改进算法具有一定的智能性；还比如现在有学者提到的遗传模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起来。不能忽略的是，每种算法的提出都与其应用范围紧密结合，这样才使得改进的算法在其应用领域具有较好的适用性。由于模拟退火算法从理论上可以达到全局极小值，所以对该算法的研究才更具有实际意义。现阶段，关于模拟退火算法的研究通常分为两类。第一类，基于有限状态奇异马尔可夫（Markov）链的有关理论，给出模拟退火算法的某些关于理想收敛模型的充分条件或充要条件，这些条件在理论上证明了当退火三原则（初始温度足够高、降温速率足够慢、终止温度足够低）满足时，模拟退火算法能以100%的概率达到全局最优解。第二类，针对某些具体问题，给出了模拟退火算法的成功应用。前者在指导应用方面作用有限，在算法的定参过程中，往往很难给出有益的定量关系。后者在各自的领域中有应用价值，但过分依赖于问题，不具有普遍意义。事实上，在现有情况下给出关于SA的、具有普遍意义的定量关系式是不现实的。因此，对SA进行的有意义的研究应集中在引入新思想，在此基础上提出在应用中实现新思想的可能途径，并通过典型实验对其效果进行验证。SA的未来发展方向应着重解决以下几个问题：

1）把传统的启发式搜索方法与模拟退火随机搜索算法结合起来。

2）把模拟退火算法与遗传算法有机结合起来，开发出一种更具有理论意义和应用价值的随机搜索算法。

3）期望给出一种在理想情況下判定搜索进入局部极小点的充要条件。

4）作为一种随机搜索算法，模拟退火算法在理论上并不存在时间上限的概念。应给出一种模拟退火算法所通用的时间评价标准。

5）由于模拟退火算法及其改进算法所固有的特点，它们在解决某些特殊领域的问题时具有很好的性能。应寻找更多的能够使用模拟退火算法的领域，并给出在这些领域中成功的应用系统，这也是一个颇具理论研究价值和应用价值的研究方向。