《优化综述报告》word版

《《优化综述报告》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、模拟退火算法综述一、模拟退火算法的研究进展模拟退火算法（SimulatedAnnealingAlgorithm,简称SAA）是一种基于对金属退火过程的模拟发展起来的随机搜索算法。1953年，MetropolisN.等人在研究二维相变时提出了Metropolis准则。随着对固体退火过程研究的的深入，KirkpatrickS（1980）等人和CernyV（1981）首先意识到其与组合优化问题之间存在的类似性并相继独立的提出了SA思想。不久，他们将Metropolis准则引入到组合优化过程当中，形成了最早的常规模拟退火算法（1983年）并首先将

2、这种算法应用到了VLSI的设计。但对于类似的大规模的组合优化问题而言，它的收敛速度很慢。由此，1986年Szu.H提出了一种退火率与时间成反比的快速模拟退火算法（FSA）。1987年，LaarhovenP.和Aarts出版了《模拟退火理论与应用》，对SA算法做了比较系统的阐述、总结。极大地促进了之后SA算法的理论研究与实际应用，在SA发展史上具有里程碑式的意义。在其后的二十几年里，针对模拟退火算法实际应用中出现的各种问题，许多人有侧重性的进行了不同程度的研究和实验，对工程实际问题的解决起到了较好指导和借鉴作用，取得了不错的效果。如：199

3、0年GunteD.和TobiasS.对算法中的Ts（初始温度）的确定方法进行了研究；1995年TarekM.对算法进行了并行优化计算的研究，以求提高计算效率，用以解决比较复杂的科学和工程计算问题。1993年KirkpatrickS.将SA算法用于优化总是，取得了不错的效果。2002年耿平等人采用人工神经网络方法建立多变量与多目标函数之间的关系，并将模拟退火算法与人工神经网络BP算法相结合，解决了这类复杂系统中多函数变量与多目标函数之间没有确定的解析关系因而无法进行直接优化的难题，并为解决多变元非线性复杂系统的优化问题提供了一种新的有效的方

4、法。当然，这同计算机技术、数学，以及相关学科的发展是分不开的。总体表现为：从理论研究上来讲，业已证明SA算法可以达到全局极小值。它是基于有限状态奇异Markov链的有关理论，给出SA算法的某些关于理想收敛模型的充分条件或必要条件，这些条件在理论上证明了退火三原则（初始温度足够高、降温速度足够慢、终止温度足够低）满足时，SA算法能够以概率1获取全局最优解。因而也就表明在局部层次上，针对算法的参数、结构等的各种研究对于算法的整体把握和工程应用是有意义的。从实际应用上来讲，理论研究的深入和多样性，使得模拟退火算法已从经典的常规模拟退火算法发展成

5、为一种混合型或复合型的模拟退火算法。比如：遗传-模拟退火算法，它是将遗传算法良好的收敛性和模拟退火解变换的自适性有效结合起来；带返回搜索的模拟退火算法，它是一种将传统算法快速、良好的局部搜索能力以及针对退火内循环迭代过程中可能先前4已获得了最优解却必须经过暂时恶化的“山脊梁”使得最终解不一定是最优解的情况对解予以记忆处理结合起来一种算法。当然，他们的应用受限于具体的实际问题，没有完全的通用性可言，只是针对某一类。这对算法研究者提供了解决空间和挑战。目前，正处于模拟退火算法兴盛期，无论是理论研究和应用研究都是十分热门的课题，有待于我们去探索

6、和实践。二、模拟退火算法的特点(1)以一定的概率接受劣解。传统算法在搜索进程中只接受好解，不接爱劣解。而模拟退火算法以一定的概率随机接受劣解，有利于改善解的质量，增强新解迭代过程中的自适应性和灵活性，可避免陷于局部最优的“陷阱”，确保缩短算法运行时间，确保获得较好的近似最优解。（2)引入算法控制参数T。T始终贯穿于算法的整个进程，具体表现为它对外循环的直接控制和内循环的间接控制。就内循环而言，在每个控制参数T下，借用前一迭代解和摄动装置可产生新的随机迭代解，T对其中的好解（df<0）无任何影响，只对劣解（df>0）以态概率exp(-df/

7、T)是否大于由随机矩阵rand产生的随机数决定是否接受劣解。很明显，状态概率的大小主要由T决定，并且在很大程度上决定着Markov链的长度。就外循环而言，直接控制参数T缓慢降低，提高接收准则，直至T趋向0，状态链稳定于优化问题的最优状态，提高SA算法获得全局最优解的可靠性。(3)使用目标函数值(即适应值)进行搜索。传统搜索算法不仅需要利用目标函数值，而且往往需要且标函数的导数值等其它一些辅助信息才能确定搜索方向。当这些信息不存在时，算法就会无效。而SA算法仅使用由目标函数变换来的适应度函数值就可完成。此外，SA算法的适应度函数不仅不受连续

8、可微的约束，而且其定义域可以任意设定。对适应度函数唯一要求是，对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导数的函数，或导数不存在的函数的优化以及组合优化等问题，应用SA算法