文档介绍：第三章模拟退火算法
第1页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法及模型
物理退火过程
组合优化与物理退火的相似性
（1953）——以概率接受新状态
若在温度T，当前状态i → 新状态j
若Ej<Ei，则接受 j 为当前状态；
否则，若概率 p=exp[-(Ej-Ei)/kBT] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。
物理退火过程
第11页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法及模型
智能优化计算
Metropolis准则（1953）——以概率接受新状态
p=exp[-(Ej-Ei)/kBT]
在高温下，可接受与当前状态能量差较大的新状态；
在低温下，只接受与当前状态能量差较小的新状态。
物理退火过程
第12页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法及模型
智能优化计算
相似性比较
组合优化与物理退火的相似性
组合优化问题
金属物体
解
粒子状态
最优解
能量最低的状态
设定初温
熔解过程
Metropolis抽样过程
等温过程
控制参数的下降
冷却
目标函数
能量
第13页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法及模型
智能优化计算
基本步骤
给定初温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 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
第14页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法及模型
智能优化计算
影响优化结果的主要因素
给定初温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 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
三函数两准则
初始温度
第15页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法的马氏链描述
智能优化计算
定义
马尔科夫链
第16页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法的马氏链描述
智能优化计算
定义
一步转移概率：
n步转移概率：
若解空间有限，称马尔可夫链为有限状态；
若，称马尔可夫链为时齐的。
马尔科夫链
第17页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法的马氏链描述
智能优化计算
模拟退火算法对应了一个马尔可夫链
模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。
若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；
若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。
分析收敛性
模拟退火算法与马尔科夫链
第18页，共48页，2022年，5月20日，1点37分，星期日
模拟退火算法关键参数和操作的设计
智能优化计算
原则