模拟退火算法.ppt

《模拟退火算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模拟退火算法（SimulatedAnnealing）1、引子2、SA算法的起源3、SA算法的基本思想4、SA算法的步骤5、SA算法应用范围与一般要求6、SA算法的优缺点1、引子在科学与工程计算中，经常发生的一个问题是在Rn中或者是在一个有界区域上求某个非线性函数f(x)的极小点。在f(x)可导时，一个最基本的算法就是最速下降法。这一方法从某一选定的初值开始，利用如下公式进行迭代，即然而以速降法为代表的传统算法具有共同的缺点，它们都不保证求得全局极小，只能保证收敛到一个由初值决定的局部极小点。每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火

2、其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。2、SA算法的起源SA算法起源于对固体退火过程的模拟。简单而言，在固体退火时，先将固体加热使其温度充分高，再让其徐徐冷却，其物理退火过程由以下三部分组成：加温过程、等温过程、冷却过程。SA算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术。模拟退火物理退火解粒子状态最优解能量最低态设定初温熔解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法与物理退火过程的相似关系3

3、、SA算法的基本思想在搜索最优解的过程中，SA算法除了可以接受优化解外，还基于随机接受准则（Metropolis准则）有限度地接受恶化解，并且接受恶化解的概率慢慢趋向于0。（这使得算法有可能从局部最优中跳出，尽可能找到全局最优解，并保证了算法的收敛）SA的思想最早是由Metropolis等在1953年提出的，Metropolis等提出了重要性采样法，即以概率接受新状态。SA算法的思想为：由初始解i和控制参数初值t开始，对当前解重复产生新解→计算目标函数差→接受或舍弃的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发

4、式随机搜索过程。SA算法与其它搜索方法相比，具有如下的特点：以一定的概率接受恶化解；引进算法控制参数；使用对象函数值进行搜索；隐含并行性；搜索复杂区域。4、SA算法的基本步骤1)随机产生一个初始解x0，令xbest＝x0并计算目标函数值E(x0);2)设置初始温度T(0)=To，迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，则xbest=xnew；4)如果ΔE

5、＞0，则p=exp(-ΔE/T(i));1)如果c=random[0,1]

6、制；（3）冷却进度表。冷却进度表是指从某一高温状态T0向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。5、SA算法应用范围与一般要求5、SA算法应用范围与一般要求初始温度T0的设定：实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：(1)均匀抽样一组状态，以各状态目标值的方差为初温。(2)随机产生一组状态，确定两两状态间的最大目标值差

7、Δmax

8、，然后依据差

9、值，利用一定的函数确定初温。比如，t0=－Δmax/pr，其中pr为初始接受概率。(3)利用经验公式给出。5、SA算法应用范围与一般要求算法终止准则，常用的包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。6、SA算法的优缺点与同类方法相比，SA算法具有以下优缺点：优点：高效，灵活，通用，初值鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。缺点：由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此其收敛速度慢，执行时间长，算法性能与初始值有

10、关及参数敏感等缺点。Th