第4章 模拟退火.ppt

今天是九.一八纪念日! 2 第四章 模拟退火 3 第四章 模拟退火 一.导言 二.模拟退火 三.SA举例 四.SA的收敛性分析 4 模拟退火(SA)的产生 原始算法是由Metropolis等(1953)提出，但未引起反响； 1982年Kirkpatrick等将其应用于组合优化，才得到广泛的应用 目的是为了克服优化过程中陷入局优和初值依赖等弊端 基本思想是模拟热力学中的退火过程 一.导言 5 金属退火过程 什么是退火 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。 一.导言 6 金属退火过程 什么是退火 加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态 等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态 冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构 一.导言 7 金属退火过程 什么是退火 退火 淬火 一.导言 8 金属退火过程 数学描述 设热力学系统S中有n个状态（有限且离散的），其中状态i的能量为Ei ，在温度Tk下，经一段时间达到热平衡，此时处在状态i的概率为： 则有如下关系：Ei↓→ Pi ↑， Tk↓→ Pi ↓ 一.导言 如何确定Ck? 9 金属退火过程 数学描述 通过求Ck，获得Bolzman方程： 一.导言 10 金属退火过程 Bolzman方程 同一温度下，S处在能量小的状态要比处在能量大的状态概率大 若存在E1E2，则在同一温度Tk下，有 故P1(Tk)P2(Tk) 一.导言 11 金属退火过程 Bolzman方程 若i*表示S中唯一的最低能量的状态， 是关于温度Tk单调递减 对Pi(Tk)求对温度的导数，则 故 一.导言 12 金属退火过程 Bolzman方程 当 时， 同理，当 时， 一.导言 13 金属退火过程 温度Tk对 的影响 当Tk 很大时， 当 时， 一.导言 各状态的概率几乎相等 与 的小差别带来 和 的巨大差别 14 金属退火过程 温度Tk对 的影响 例： 当 时 一.导言 15 金属退火过程 温度Tk对 的影响 例： 当 时 此时 一.导言 温度趋于0时，以概率1趋于最小能量状态 16 能量越低越稳定！！！ ——自然界的普遍规律 17 组合优化与退火 Metropolis准则—以概率接受新状态 若在温度Tk ，当前状态i → 新状态j 若EjEi，则接受 j 为当前状态 否则，若概率 p=exp[-(Ej-Ei)/ Tk ] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态 一.导言 在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态 18 组合优化与退火 一.导言 组合优化问题 物理退火 解 状态 目标函数 能量函数 最优解 最低能量状态 设定初始高温 加温过程 基于Metropolis准则的有哪些信誉好的足球投注网站 等温过程 温度参数的下降 冷却过程 19 构成要素 解的表达与邻域移动方式同TS 邻域解的产生 在当前解的邻域结构内以一定概率方式（均匀分布、 正态分布、指数分布等）产生 选择策略 一般采用min[1,exp(-∆f/t)] 二.模拟退火 20 构成要素 初始温度 均匀抽样一组状态，以各状态目标值的方差为初温 随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温 利用经验公式 二.模拟退火 实验表明：初温越大，获得高质量解的机率越大，但花费较多的计算时间 21 构成要素 降温函数 ，其中 二.模拟退火 优点：简单易行，很美丽的方法 22 构成要素 热平衡条件 Metropolis抽样稳定准则 检验目标函数的均值是否稳定 连续若干步的目标值变化较小 设置内循环迭代次数 停止准则 设置终止温度的阈值 设置外循环迭代次数 算法有哪些信誉好的足球投注网站到的最优值连续若干步保持不变 二.模拟退火 23 算法步骤 Step 1 选一个初始点i( )，给定初始温度 ，终止温度 ，令迭代指标 ， ； Step 2 随机产生一个