文档介绍：1、模拟退火算法(起源) 模拟退火算法起源于物理退火。物理退火过程: (1) 加温过程(2) 等温过程(3) 冷却过程物理退火原理 1953 年, Metropolis 提出重要性采样法,即以概率接受新状态,称 Metropolis 准则,计算量相对 Monte Carlo 方法显著减少。 1983 年, Kirkpatrick 等提出模拟退火算法,并将其应用于组合优化问题的求解。 2、模拟退火算法 Metropolis 准则 1) Metropolis 准则提出固体在恒定温度下达到热平衡的过程可以用 MorteCarol 算法方法加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,因而计算量很大。鉴于物理系统倾向于能量较低的状态,而热运动又妨碍它准确落到最低态。采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。因此, Metropolis 等在 1953 年提出了重要的采样法, 即以概率接受新状态。 2) Metropolis 准则假设在状态 x old 时,系统受到某种扰动而使其状态变为 x new 。与此相对应,系统的能量也从 E(x old)变成 E(x new) ,系统由状态 xold 变为状态 xnew 的接受概率 p: 模拟退火算法------- 步骤 1) 随机产生一个初始解 x0,令 xbest = x0, 并计算目标函数值 E(x0); 2) 设置初始温度 T(0)=To ,迭代次数 i= 1; 3) Do while T(i) > Tmin 1) for j= 1~k 2) 对当前最优解 xbest 按照某一邻域函数,产生一新的解 x new 。计算新的目标函数值 E(x new) ,并计算目标函数值的增量ΔE= E(xnew) - E(xbest) 。 3) 如果ΔE<0 ,则 x best=x new; 4) 如果ΔE>0 ,则 p= exp(- ΔE /T(i)); 1) 如果 c= random[0,1] <p, xbest = xnew; 否则 xbest = xbest 。 5) End for 4)i=i+1; 5) End Do 6) 输出当前最优点,计算结束下图为模拟退火算法流程图: 模拟退火算法------ 参数的选择冷却进度表我们称调整模拟退火法的一系列重要参数为冷却进度表。它控制参数 T 的初值及其衰减函数,对应的 MARKOV 链长度和停止条件,非常重要。一个冷却进度表应当规定下述参数: 1 .控制参数 t 的初值 t0; 2 .控制参数 t 的衰减函数; 3. 马尔可夫链的长度 Lk。( 即每一次随机游走过程, 要迭代多少次, 才能趋于一个准平衡分布,即一个局部收敛解位置) 4 .结束条件的选择有效的冷却进度表判据: ::最终解的质量和 CPU 的时间参数的选取: 一)控制参数初值 T0 的选取一般要求初始值 t0 的值要充分大,即一开始即处于高温状态, 且 Metropolis 的接收率约为 1。(1) 均匀抽样一组状态,以各状态目标值的方差为初温。(2) 随机产生一组状态,确定两两状态间的最大目标值差|Δ max| ,然后依据差值,利用一定的函数确定初温。比如, t0= -Δ max/pr ,其中