文档介绍：第三章模拟退火算法智能算法导论浙江大学 模拟退火算法及模型 物理退火过程 组合优化与物理退火的相似性 模拟退火算法的基本思想和步骤 模拟退火算法的马氏链描述 马尔可夫链 模拟退火算法与马尔可夫链 模拟退火算法的关键参数和操作的设计 状态产生函数 状态接受函数 初温 温度更新函数 内循环终止准则 外循环终止准则智能算法导论浙江大学 模拟退火算法的改进 模拟退火算法的优缺点 改进内容 一种改进的模拟退火算法 模拟退火算法实现与应用 30城市TSP问题(d*= by D B Fogel) 模拟退火算法在管壳式换热器优化设计中的应用智能算法导论浙江大学 模拟退火算法及模型智能算法导论浙江大学?算法的提出模拟退火算法最早的思想由Metropolis等(1953) 提出,1983年Kirkpatrick等将其应用于组合优化。?算法的目的解决NP复杂性问题; 克服优化过程陷入局部极小; 克服初值依赖性。 物理退火过程 模拟退火算法及模型智能算法导论浙江大学?物理退火过程什么是退火: 退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。 物理退火过程 模拟退火算法及模型智能算法导论浙江大学?物理退火过程加温过程——增强粒子的热运动,消除系统原先可能存在的非均匀态; 等温过程——对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态; 冷却过程——使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。 物理退火过程 模拟退火算法及模型智能算法导论浙江大学?数学表述在温度T,分子停留在状态r满足Boltzmann概率分布 物理退火过程???????????????????????? D s B B B T k s E T Z T Z k r r E E T k r E T Z r E E P ) ( exp ) ( ) ( Boltzmann 0 ) ( ) ( exp ) ( 1 )} ( { 子: 为概率分布的标准化因常数。为的能量, 表示状态机变量, 表示分子能量的一个随 模拟退火算法及模型智能算法导论浙江大学?数学表述在同一个温度T,选定两个能量E 1<E 2,有在同一个温度,分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。 物理退火过程?????????????????????????????? T k E E T k E T Z E E P E E P B B 1 2 1 2 1 exp 1 exp ) ( 1 } { } { <1 >0 模拟退火算法及模型智能算法导论浙江大学?数学表述|D|为状态空间D中状态的个数,D 0是具有最低能量的状态集合: 当温度很高时,每个状态概率基本相同,接***均值1/|D|; 状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值1/|D| ; 当温度趋于0时,分子停留在最低能量状态的概率趋于1,非最低能量状态的概率趋于0。 物理退火过程能量最低状态非能量最低状态 模拟退火算法及模型智能算法导论浙江大学?Metropolis准则(1953)——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。 物理退火过程