Chapter 3 模拟退火算法 tsp问题.pdf
文本预览下载声明
模拟退火算法
模拟退火算法
模拟退火算法及模型
模拟退火算法的马氏链描述
模拟退火算法的关键参数和操作的设计
模拟退火算法的改进
模拟退火算法实现与应用
引例:
引例:
模拟退火算法是基于物理中固体物质的退火过程
与一般组合优化问题之间的相似性。
比如在某种温度下,金属分子停留在能量小的状
态的概率比停留在能量大的状态的概率要大。
模拟退火算法及模型
模拟退火算法及模型
1.物理退火过程
算法的产生
模拟退火算法主要模拟热力学当中的退火过程。
模拟退火算法最早的思想由Metropolis等(1953)提出,
1983年Kirkpatrick等将其成功应用于组合优化。
模拟退火算法的目的
解决NP-hard问题
克服优化过程陷入局部极小
克服初值依赖性
模拟退火算法及模型
模拟退火算法及模型
1. 物理退火过程
物理退火过程
什么是退火?
退火是指将固体加热到足够高的温度,使分子呈随机排列状
态,然后逐步降温使之冷却,最后分子以低能状态排列,
固体达到某种稳定状态。
模拟退火算法及模型
模拟退火算法及模型
1. 物理退火过程
物理退火过程
加温过程——增强粒子的热运动,消除系统原先可能存在
的非均匀态;
等温过程——对于与环境换热而温度不变的封闭系统,系
统状态的自发变化总是朝自由能减少的方向进行,当自由
能达到最小时,系统达到平衡态;
冷却(退火)过程——使粒子热运动减弱并渐趋有序,系统能
量逐渐下降,从而得到低能的晶体结构。
模拟退火算法及模型
模拟退火算法及模型
1.物理退火过程
数学表述(Bolzman方程
在温度T,分子停留在状态r满足Boltzmann概率分布
1 E(r)
P{E E(r)} exp
Z(T) k T
B
E表示分子能量的一个随机变量,E(r)表示状态r的能量,
k 0为Boltzmann常数。Z(T)为概率分布的标准化因子:
B
E(s)
Z(T) exp
k T
sD B
模拟退火算法及模型
模拟退火算法及模型
1.物理退火过程
数学表述
在同一个温度T,选定两个能量E E ,有
1 2
1 E E E
P{E E }P{E E } exp 1 1exp 2 1
1 2
Z(T) k T k T
B B
0
显示全部