文档介绍：模拟退火算法
本讲稿第一页，共四十七页
模拟退火算法及模型
物理退火过程
组合优化与物理退火的相似性
模拟退火算法的基本思想和步骤
模拟退火算法及模型
智能优化计算
Metropolis准则（1953）——以概率接受新状态
p=exp[-(Ej-Ei)/kBT]
在高温下，可接受与当前状态能量差较大的新状态；
在低温下，只接受与当前状态能量差较小的新状态。
物理退火过程
本讲稿第十二页，共四十七页
模拟退火算法及模型
智能优化计算
相似性比较
组合优化与物理退火的相似性
组合优化问题
金属物体
解
粒子状态
最优解
能量最低的状态
设定初温
熔解过程
Metropolis抽样过程
等温过程
控制参数的下降
冷却
目标函数
能量
本讲稿第十三页，共四十七页
模拟退火算法及模型
智能优化计算
基本步骤
给定初温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 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
本讲稿第十四页，共四十七页
模拟退火算法及模型
智能优化计算
影响优化结果的主要因素
给定初温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 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
三函数两准则
初始温度
本讲稿第十五页，共四十七页
模拟退火算法的马氏链描述
智能优化计算
定义
马尔科夫链
本讲稿第十六页，共四十七页
模拟退火算法的马氏链描述
智能优化计算
定义
一步转移概率：
n步转移概率：
若解空间有限，称马尔可夫链为有限状态；
若 ，称马尔可夫链为时齐的。
马尔科夫链
本讲稿第十七页，共四十七页
模拟退火算法的马氏链描述
智能优化计算
模拟退火算法对应了一个马尔可夫链
模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。
若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；
若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。
分析收敛性
模拟退火算法与马尔科夫链
本讲稿第十八页，共四十七页
模拟退火算法关键参数和操作的设计
智能优化计算
原则
产生的候选解应遍布全部解空间
方法
在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生
状态产生函数
本讲稿第十九页，共四十七页
模拟退火算法关键参数和操作的设计
智能优化计算
原则
(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；
(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；
(3)当温度趋于零时，只能接受目标函数下降的解。
方法
具体形式对算法影响不大
一般采用min[1,exp(-∆C/t)]
状态接受