文档介绍：第三章模拟退火算法演示文稿
第一页，共五十一页。
优选第三章模拟退火算法
第二页，共五十一页。
智能算法及应用
第三页，共五十一页。
智能算法及应用
第四页，共五十一页。
智能算法
相似性比较
组合优化与物理退火的相似性
组合优化问题
金属物体
解
粒子状态
最优解
能量最低的状态
设定初温
熔解过程
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 算法终止准则满足；
输出算法搜索结果。
模拟退火算法的基本思想和步骤
三函数两准则
初始温度
第十九页，共五十一页。
智能算法及应用
定义
马尔科夫性（无后效性）：
由时刻t0系统或过程所处的状态，可以决定系统或过程在时刻t>0所处的状态，而无需借助于t0以前系统或过程所处状态的历史资料。
马尔科夫性过程分布函数的描述：
X(tn-1)=xn-1,即：
P{X(tn)<=xn|x(t1=x1),X(t2)=x2,......,X(tn-1)=xn-1}
=P{X(tn)<=xn|X(tn-1)<=xn-1}, xn€R.
马尔科夫链
第二十页，共五十一页。
智能算法及应用
定义
马尔科夫链
第二十一页，共五十一页。
模拟退火算法的马氏链描述
智能算法及应用
定义
一步转移概率：
n步转移概率：
若解空间有限，称马尔可夫链为有限状态；
若 ，称马尔可夫链为时齐的。
马尔科夫链
第二十二页，共五十一页。
智能算法及应用
模拟退火算法对应了一个马尔可夫链
模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。
若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；
若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。
分析收敛性
模拟退火算法与马尔科夫链
第二十三页，共五十一页。
智能算法及应用
原则
产生的候选解应遍布全部解空间
方法
在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生
状态产生函数
第二十四页，共五十一页。
智能算法及应用
原则
(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；
(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；
(3)当温度趋于零时，只能接受目标函数下降的解。
方法
具体形式对算法影响不大
一般采用min[1,exp(-∆C/t)]
状态接受函数
第二十五页，共五十一页。
智能算法及应用
收敛性分析
通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数