《模拟退火算法》由会员分享，可在线阅读，更多相关《模拟退火算法（13页珍藏版）》请在金锄头文库上搜索。
1、1 1模拟退火模拟退火朱海波SX15070322 2第七章第七章 模拟退火模拟退火一一. .引言引言二二. .局部搜索局部搜索三三. .模拟退火模拟退火四四. .实际应用实际应用五五. .总结总结3 3一一. .引言引言组合优化问题： 在工程、规划和制造中的许多问题都可以建模为某个费用函数在一个离散 变量集上的最小化或最大化问题 第一类问题：存在可在多项式时间内求得最优解算法第二类问题：需要超级多项式级或者指数级的时间才能求得最优解线性规划、匹配和网络问题NP-难题：复杂性理论与无免费午餐定理可以使用最优化算法来找到最优解 （可能需要很长的计算时间） 可以使用启发式算法在短时间内找到近似解局部
2、搜索算法4 4二二. .局部搜索局部搜索局部搜索算法：一类使用广泛且普适的求解复杂组合优化问题的方法，其都以一个邻域函数为基础，该邻域函数将引导搜索达 到一个好的解。最简单形式迭代改进算法：由某个初始解开始，然后不断地在邻域中搜索一个具 有更低费用的解。如果找到了该解，则该解取代当前解。该过程一直持续到无法在当前解的领域中找到更好的解为止。（局部最优解/全局最优解）可行解集（S ）全局最优解（i*） 全局最优费用函数（f*）局部最优解（i） 局部最优费用函数（f）5 5两大主要问题局部搜索算法邻域函数的选择 依赖于问题 搜索策略迭代改进算法 很容易陷入局部最优扩展模拟退火算法有限度地接受某些费
3、用函数值较差的相邻解 （neighborhood）6 6三三. .模拟退火模拟退火w算法的提出：模拟退火算法最早的思想由Metropolis等（1953） 提出，1983年Kirkpatrick等将其应用于组合优化。w算法的目的：算法的简述：模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性，从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解。解决NP复杂性问题；克服优化过程陷入局部极值；克服初值依赖性；7 7初始温度足够高初始温度足够高 （初始值）（初始值） 降温过程足够慢降温过程足够慢 （全局最优（全局最优/ /局部最优局部最优
4、）终止温度足够低终止温度足够低 （终值）（终值）算法的要求：Metropolis算法（准则）金属固体退火算法（初温- 热平衡 ）给定固体的当前状态给定固体的当前状态i i，其能量为，其能量为EiEi；后续状态为后续状态为j j，其能量为，其能量为EjEj；后续状态后续状态j j可有一个扰动机制（很小的改动）来产生，可有一个扰动机制（很小的改动）来产生，将当前状态转换到下一个状态；将当前状态转换到下一个状态；能量差能量差：Ej-EiEj-Ei 能量差能量差0 0 状态状态j j以以exp(Ei-Ej)/Kb*T)exp(Ei-Ej)/Kb*T)的概率被接受的概率被接受T：温度 Kb：玻尔兹曼常数
5、8 8Metropolis算法（准则）通过在每个温度下都进行通过在每个温度下都进行数量很大数量很大的的状态改状态改 变变来达到来达到热平衡态热平衡态热平衡态热平衡态的特征描述是的特征描述是波尔兹曼分布波尔兹曼分布，该分布给出了固体在温度，该分布给出了固体在温度T T下处于下处于 能量为能量为EiEi的状态的状态i i的概率。的概率。波尔兹曼分布波尔兹曼分布在模拟退火的在模拟退火的收敛性分析收敛性分析中起着核心作用中起着核心作用X为一个表示固体的随机 变量（i）；对所有可能的状态（j） 进行求和；9 9Metropolis算法（准则）控制参数（C） 温度多次迭代模拟退火算法在迭代过程中，控制参数
6、值逐渐减小模拟退火算法伪代码模拟退火的一个显著特性便是它不但接受改进的解，还能有限度地接受 比较差的解。在开始较大的C值下，可以接受性能明显较差的解；当C减 小时，可允许的性能退化越来越小，直至最终当C趋近于0时，完全不接 受任何性能上的退化。算法的收敛速度由参数L和C所决定；1010Procedure SIMULATED_ANNEALING;beginINITIALIZE ( i_start , C0 , L0 ) ; %赋初值k := 0 ;i := i_start ;repeatfor L := 1 to Lk dobeginGENERATE ( 来自 Si 的 j ) ; %从当前解的
7、邻域中选择某个解if f(j) random 0,1 ) then i := j end ;k := k+1;CALCULATE_LENGTH ( Lk ) ;CALCULATE_CONTROL ( Ck ); until 终止条件满足end ;% C要逐渐减小，最后趋于0，即不接受任何性能上的退化% 冷却进度表%接受一个较差的解，利用两者的概率进行比较内层循环外层循环模拟退火算法伪代码1111四四. .实际应用实际应用在递减的各控制参数值处产生有限长度的马尔可夫链的序列，即可得到模 拟退火的一个有限时间的实现。为此，必须给定一个参数集以控制算法的收敛。这些参数集组成了冷却进度表：控制参数的初
8、始值C0；一个用于减小控制参数的递减函数；由停止准则给出的一个控制参数终值；每个其次马尔科夫链的有限长度参数集冷却进度表静态冷却进度表动态冷却进度表C0: C0=Delta f_max一对相邻解之间的最大费用差（估计值） 递减函数： C_k+1 = a*C_k , k= 0,1, a为一个小于1且接近于1的常数，其典型值在0.8-0.99之间参数自适应地改变1212五五. .总结总结自1983年出现以来，模拟退火已经被用于多个不同领域中的不同问题。30余年 的经验给出了如下一些结果：高质量的解是可以获得的，不过有时需要付出大量的计算时间开销；在许多实际场合，当没有专门设计的算法可用时，该算法由于其广泛的适用性和易于实现的特点而成为一种真正的便于使用的工具；w诀窍：要将模拟退火算法有效的应用于给定问题并不总是一件易如反掌的事情 。获得合适的邻域需要对问题的深入了解，而且有时还必须重新表述问 题或将它转换到一个等价或者类似的问题，然后才能成功运用模拟退火 ；在性能方面，通常需要在解的质量和运行时间两者加以取舍；谢谢！谢谢！1313
