文档介绍：（优选）模拟退火算法详解课件
1页，共51页，星期五。
模拟退火算法及模型
物理退火过程
组合优化与物理退火的相似性
模拟退火算法的基本思想和步骤 若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：
当温度很高时，每个状态概率基本相同，接***均值1/|D|；
状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D| ；
当温度趋于0时，分子停留在最低能量状态的概率趋于1。
物理退火过程
能量最低状态 非能量最低状态
12页，共51页，星期五。
模拟退火算法及模型
现代优化计算
Metropolis准则（1953）——以概率接受新状态
固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。
物理退火过程
13页，共51页，星期五。
模拟退火算法及模型
现代优化计算
Metropolis准则（1953）——以概率接受新状态
若在温度T，当前状态i → 新状态j
若Ej<Ei，则接受 j 为当前状态；
否则，若概率 p=exp[-(Ej-Ei)/kBT] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。
物理退火过程
14页，共51页，星期五。
模拟退火算法及模型
现代优化计算
Metropolis准则（1953）——以概率接受新状态
p=exp[-(Ej-Ei)/kBT]
在高温下，可接受与当前状态能量差较大的新状态；
在低温下，只接受与当前状态能量差较小的新状态。
物理退火过程
15页，共51页，星期五。
模拟退火算法及模型
现代优化计算
相似性比较
组合优化与物理退火的相似性
组合优化问题
金属物体
解
粒子状态
最优解
能量最低的状态
设定初温
熔解过程
Metropolis抽样过程
等温过程
控制参数的下降
冷却
目标函数
能量
16页，共51页，星期五。
模拟退火算法及模型
现代优化计算
基本步骤
给定初温t=t0，随机产生初始状态s=s0，令k=0；
Repeat
Repeat
产生新状态sj=Genete(s)；
if min{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1] s=sj;
Until 抽样稳定准则满足；
退温tk+1=update(tk)并令k=k+1；
Until 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
17页，共51页，星期五。
模拟退火算法及模型
现代优化计算
影响优化结果的主要因素
给定初温t=t0，随机产生初始状态s=s0，令k=0；
Repeat
Repeat
产生新状态sj=Genete(s)；
if min{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1] s=sj;
Until 抽样稳定准则满足；
退温tk+1=update(tk)并令k=k+1；
Until 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
三函数两准则
初始温度
18页，共51页，星期五。
模拟退火算法及模型
现代优化计算
模拟退火算法的基本思想和步骤
Step1 设定初始温度t = tmax, 任选初始解r = r0
Step2 内循环
从r的邻域中随机选一个解rt, 计算r和rt对应目标函 数值, 如rt对应目标函数值较小，则令r = rt; 否则若
exp(-(E(rt)-E(r))/t)>random(0,1), 则令r=rt.
不满足内循环停止条件时，
Step3