退火算法在地下结构中的特点

模拟退火算法在搜索策略上和传统的随机搜索策略存在很大不同，它不仅引入了适当随机搜索的因素，而且还借鉴了在物理系统中退火过程的自然机理。引入这种自然机理后，使得模拟退火算法在迭代过程中不仅保留使目标函数变“好”的试探点，而且还能以一定的概率保留使目标函数值变“差”的试探点，并且接受率随着温度的下降而减小。模拟退火算法引入的这种搜索策略有效地避免了在搜索过程中因陷入局部最优解而无法跳出的不足，明显地提高了得到全局最优解的可靠性。综上所述，模拟退火算法的特性不仅在理论上解决了传统搜索算法难以解决的问题，而且具有很高的科学价值和实际应用价值，因此，被各国学者誉为解决高难度优化问题的救星。

1.常见的传统搜索方法

1）解析法。它通常是通过求解使目标函数梯度为零的一组非线性方程来进行搜索的。一般而言，该方法只适用于目标函数连续可微、解的空间方程比较简单的情况。但是，若方程的变量增加到几十个甚至几百个时，该方法就无能为力了。

2）爬山法。它和解析法一样都是属于搜索局部最优解的方法。对于爬山法来说，只有当更好的解位于当前解附近的时候，才能继续进行最优解的搜索。显然，这种方法只适用于具有单峰分布性质的解空间，而对具有多峰解空间的目标函数无能为力。

3）穷举法。该方法的思想很简单，即在一个连续有限搜索空间或离散无限搜索空间中，计算空间中每个点的目标函数，并且每次只计算一次。显而易见，这种方法效率低且鲁棒性不强，现实中的实际问题所对应的搜索空间都很大，一点一点地慢慢求解实现起来是不现实的。

4）随机搜索方法。这一方法比上述三种搜索方法有所改进，是一种比较常用的方法，但它的搜索效率不高。一般而言，它只适用于解在搜索空间中形成紧致分布的情况。但这种条件在实际应用中是很难满足的。这里需要指出的是，随机搜索（Random Search）方法和随机化技术（Randomized Technique）是有很大区别的。模拟退火算法是利用随机化技术来指导最小能量状态搜索的。遗传算法是另一个利用随机化技术来指导对一个被编码的参数空间进行高效搜索的方法。因此，随机化技术并不意味着无方向搜索，这一点与随机搜索有所不同。

前述的几种传统搜索方法虽然鲁棒性不强，但这些方法在一定的条件下，尤其是将它们混合使用也是有效的。当面临更为复杂的问题时，必须采用像模拟退火算法这样更好的方法。

2.模拟退火算法

模拟退火算法具有十分顽强的鲁棒性，这是因为与传统的优化搜索方法相比，它采用了许多自有的、独特的方法和技术，主要有以下六个方面。

1）根据一定概率接受恶化解。模拟退火算法在搜索策略上不仅引入了适当的随机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅可以保留使目标函数变“好”的试探点，而且还能根据概率保留一定数量的使目标函数值变“差”的试探点，并且在迭代过程中出现的状态是随机产生的，即不强求后一个状态一定优于前一个状态，以一定的概率容忍退化状态的出现，接受率随着温度的下降而逐渐减小。传统的优化搜索算法通常是从目标函数解空间的一个初始点开始迭代搜索最优解的过程。比如上面提到的爬山法，该方法的思想是，若一个细微变动能提高目标函数值的质量，则沿该方向前进，否则取相反方向前进。然而，在现实生活中，问题是相当复杂的，解空间中通常会出现若干局部最优解，传统的搜素优化方法很容易陷入局部最优解而无法跳出的困境。此外，很多传统的优化算法往往是确定性的，即从各搜索点到另一个搜索点的转移方法和转移关系都是确定的，这种确定性往往可能使得搜索永远达不到最优点，因而限制了算法的应用范围。模拟退火算法是以一种概率的方式进行的，从而增加了其搜索过程的灵活性。

2）简化性。模拟退火算法求得解的质量的好坏与初始解的选择无关，因此模拟退火算法在选取初始解和随机数序列方面较为灵活。在应用该算法求解组合优化问题时，可以省掉大量的前期工作。

3）加入算法控制参数。模拟退火算法仿照固体退火过程中的退火温度在算法中加入了算法控制参数，按照算法控制参数将优化过程分成若干阶段，并以此决定各阶段下随机状态的取舍标准，接受函数是由Metropolis算法给出的一个简单的数学模型。模拟退火算法的两个重要步骤中都涉及算法控制参数的使用：(www.xing528.com)

（1）在每个算法控制参数下，从前迭代点出发，产生邻近的随机状态，根据算法控制参数确定的接受准则来决定得到的新状态的取舍，并据此形成一定长度的随机马尔可夫链。

（2）缓慢降低算法控制参数，提高接受准则，直至算法控制参数趋向于0，状态链稳定于优化问题的最优状态，提高模拟退火算法得到的全局最优解的可靠性。

4）仅使用适应度函数值进行搜索。传统搜索算法不仅需要利用目标函数的函数值，而且大多需要目标函数的导数值等其他辅助的数学信息才能确定算法的搜索方向。当这些信息不存在时，传统的算法也就无法进行了。模拟退火算法仅使用由目标函数变换得到的适应度函数的值，来确定进一步搜索的方向和搜索的范围，无须借助其他的一些辅助信息。需要特别指出的是，模拟退火算法的适应度函数不需要是连续可微的，而且其定义域也可以在任意范围。这一特性对于很多无法或很难求导数的函数，或者对于根本不存在导数的函数的优化问题、组合优化问题等，使用模拟退火算法就显得比较方便。另外，直接利用目标函数的值或个体适应度函数，也可以将搜索范围集中在适应度较高的搜索空间中，以此来提高搜索效率。

5）隐含并行性。并行算法是20世纪60年代发展起来的，发展速度非常迅速。有些专家甚至认为“大量并行”是目前提高计算机系统性能的唯一方法。到现在为止，并行算法的设计主要采用两种方法：

（1）对现有的串行算法进行改造，使之成为较好的并行算法。

（2）结合现有并行计算机的结构特点，直接设计出新的并行算法。

将模拟退火算法改造为并行算法相对还是比较容易的。目前常见的并行策略有以下几种：①操作并行策略；②试演并行策略；③区域分裂策略；④混乱松弛策略。

这几种并行算法不同程度上在解的质量、收敛速度方面优于模拟退火算法。由此可以预见，大规模的并行计算模式将成为研究全局优化问题的主流。模拟退火算法隐含着并行性，这是优于其他优化搜索算法求解过程的关键所在。另外，模拟退火算法的隐含并行性还有助于进行非线性问题的处理。

6）善于搜索复杂区域。模拟退火算法最善于对复杂地区进行搜索，从中找出期望值高的区域。但该算法在求解简单问题时效率却不高。正如遗传算法创始人Holland H.所指出的“如果只对几个变量做微小的改动就能进一步改进解，则最好使用一些更普通的方法，来为遗传算法助一臂之力”。SA算法在这一点上与遗传算法类似，但比遗传算法更加适合搜索复杂区域。

上述具有特色的技术和方法使得模拟退火算法使用简单、鲁棒性强、易于并行化，从而应用范围甚广。