文档详情

Chapter 3 模拟退火算法 tsp问题.pdf

发布:2017-09-28约1.08万字共44页下载文档
文本预览下载声明
模拟退火算法 模拟退火算法 模拟退火算法及模型 模拟退火算法的马氏链描述 模拟退火算法的关键参数和操作的设计 模拟退火算法的改进 模拟退火算法实现与应用 引例: 引例: 模拟退火算法是基于物理中固体物质的退火过程 与一般组合优化问题之间的相似性。 比如在某种温度下,金属分子停留在能量小的状 态的概率比停留在能量大的状态的概率要大。 模拟退火算法及模型 模拟退火算法及模型 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  sD  B  模拟退火算法及模型 模拟退火算法及模型 1.物理退火过程  数学表述 在同一个温度T,选定两个能量E E ,有 1 2 1  E   E E  P{E E }P{E E }  exp  1 1exp  2 1  1 2     Z(T) k T k T  B   B  0
显示全部
相似文档