文档介绍：模拟退火算法综述
一、模拟退火算法的研究进展
模拟退火算法(Simulated Annealing Algorithm,简称SAA)是一种基于对金 属退火过程的模拟发展起来的随机搜索算法。1953年，Metropolis 温速度足够慢、终止温度足够低)满足时，SA算法能够以概率1获取全局最优解。 因而也就表明在局部层次上，针对算法的参数、结构等的各种研究对于算法的整 体把握和工程应用是有意义的。从实际应用上来讲，理论研究的深入和多样性， 使得模拟退火算法已从经典的常规模拟退火算法发展成为一种混合型或复合型 的模拟退火算法。比如：遗传-模拟退火算法，它是将遗传算法良好的收敛性和 模拟退火解变换的自适性有效结合起来；带返回搜索的模拟退火算法，它是一种 将传统算法快速、良好的局部搜索能力以及针对退火内循环迭代过程中可能先前 已获得了最优解却必须经过暂时恶化的“山脊梁”使得最终解不一定是最优解的 情况对解予以记忆处理结合起来一种算法。当然，他们的应用受限于具体的实际
问题，没有完全的通用性可言，只是针对某一类。这对算法研究者提供了解决空 间和挑战。目前，正处于模拟退火算法兴盛期，无论是理论研究和应用研究都是 十分热门的课题，有待于我们去探索和实践。
二、 模拟退火算法的特点
以一定的概率接受劣解。传统算法在搜索进程中只接受好解，不接爱劣解。 而模拟退火算法以一定的概率随机接受劣解，有利于改善解的质量，增强新解迭 代过程中的自适应性和灵活性，可避免陷于局部最优的“陷阱”，确保缩短算法 运行时间，确保获得较好的近似最优解。
引入算法控制参数T。T始终贯穿于算法的整个进程，具体表现为它对外循 环的直接控制和内循环的间接控制。就内循环而言，在每个控制参数T下，借用 前一迭代解和摄动装置可产生新的随机迭代解，T对其中的好解(df<0)无任何 影响，只对劣解(df>0)以态概率exp (-df/T)是否大于由随机矩阵rand产生的随 机数决定是否接受劣解。很明显，状态概率的大小主要由T决定，并且在很大程 度上决定着Markov链的长度。就外循环而言，直接控制参数T缓慢降低，提高接 收准则，直至T趋向0,状态链稳定于优化问题的最优状态，提高SA算法获得全 局最优解的可靠性。
使用目标函数值(即适应值)进行搜索。传统搜索算法不仅需要利用目标函 数值，而且往往需要且标函数的导数值等其它一些辅助信息才能确定搜索方向。 当这些信息不存在时，算法就会无效。而SA算法仅使用由目标函数变换来的适应 度函数值就可完成。此外，SA算法的适应度函数不仅不受连续可微的约束，而且 其定义域可以任意设定。对适应度函数唯一要求是，对于输入可计算出加以比较 的正的输出。这个特性对很多无法或很难求导数的函数，或导数不存在的函数的 优化以及组合优化等问题，应用SA算法就显得比较方便。
隐含并行性。并行算法是60年代发展起来的，发展迅速。它的特点是收敛 速度较其它算法要快。SA算法隐含并行性的特点启示我们：如果能将并行策略加 入到SA算法中，将会提高解的质量和收敛速度。这也是它优于其它算法求解过程 的关键所在。另外，SA算法的隐含并行性还有助于处理非线性问题。
搜索复杂区域。由于SA算法不受初始解的限制并且能够以一定的概率接受 新解，因而最善于搜索复杂区域，从中找出期望值高