地下结构的方法-退火算法概述

模拟退火（Simulated Annealing，SA）算法将组合优化问题与统计力学中的热平衡问题类比，另辟了求解组合优化问题的新途径。通过模拟退火过程可找到全局（或近似）最优解。模拟退火算法是基于Monte Carlo迭代求解法的一种启发式随机搜索算法。SA算法用于解决组合优化问题的出发点是基于物理中固体物质的退火过程与一般组合优化问题间的相似性。在对固体物质进行退火处理时，通常先将它加温熔化，使其中的粒子可自由运动，然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。对于组合优化问题来说，它也有这样类似的过程。组合优化问题解空间中的每一点都代表一个解，不同的解有着不同的代价函数值。所谓优化，就是在解空间中寻找代价函数（亦称目标函数）的最小（或最大）解。

模拟退火算法可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：

1）温度T的初始值设置问题。温度T的初始值设置是影响模拟退火法全局搜索性能的重要因素之一。初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。

2）退火速度问题。模拟退火法的全局搜索性能也与退火速度密切相关，一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。在实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。

3）温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用T（t+1）=k×T（t）的迭代降温方式，式中k为正的略小于1.00的常数，t为降温的次数。

假定给定的以粒子相对位置为表征的初始状态表示为i；物质当前状态为固态，则物质在该状态下的能量表示为E（i），然后用摄动装置随机选择一个粒子并使该粒子的位置随机地发生微小的变化，以此来得到一个新的状态：新状态的能量可表示为E（j），如果E（j）＜E（i），则新状态j就可作为“重要”状态；反之，若E（j）＞E（i），考虑到热运动对能量的影响，则要根据固体处于该状态的概率来决定该新状态是否作为“重要”状态。概率的计算方法如下：(www.xing528.com)

式中，r表示该状态的概率，它是一个大于0的数，用随机数产生器产生一个[0，1）区间的随机数，若r大于这个随机数，则将新状态j作为重要状态，否则将其舍去。T表示新状态下的温度。k为玻耳兹曼（Boltzmann）常数。若新状态j是重要状态，就以新状态j取代原有状态成为当前状态，否则依然以原有状态i作为当前状态。然后不断重复上述产生新状态的过程。以此来保证在大规模固体状态变换后，系统仍处于能量较低的平衡状态。

根据上述r的计算公式可知，在高温状态下可接受与当前状态能量差别较大的新状态作为重要状态，而在较低温度状态下只能接受与当前状态能量差别较小的新状态作为重要状态。这与实际生活中不同温度下热运动的影响完全一致。在温度值趋近于零时，就不能接受任何E（j）＞E（i）的新状态j了。

根据Metropolis准则，用固体退火过程模拟组合优化问题，设组合优化问题的一个解i对应固体退火过程中的一个微观状态，组合优化问题的目标函数f（i）对应固体退火过程中的一个微观状态i的能量E（i），将固体退火过程中的温度T演化为称为冷却进度表的控制参数t，这样就得到了求解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解不断地重复“产生新解→计算目标函数差→接受/舍弃”的迭代，这个迭代的过程对应着固体在某一温度下趋于热平衡的过程，并逐步衰减控制参数t的值，算法终止时的当前解即为所求最优解的近似值。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。由于固体退火的过程必须是“徐徐”降温，才能使固体在每个温度下都能够达到热平衡，最终才能趋于能量最小的基态。由此可见，控制参数的值也必须是缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。

综上所述，模拟退火算法是通过模拟物理学中固体物质退火的过程来解决一般组合优化问题的一种组合优化算法，即在某一初始温度下，随着控制参数值的不断下降，结合Metropolis准则在解空间中随机寻找目标函数的全局最优解。也就是说，局部最优解能按照一定的概率跳出并最终趋于全局最优解。