模拟退火模型.pdf

模拟退火模型模拟退火模型 主讲人 泰山教育主讲人 泰山教育小石老师小石老师 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模型背景 什么是退火 什么是退火 退火是指将固体加热到足够高的温度 使分子退火是指将固体加热到足够高的温度 使分子 呈随机排列状态 然后逐步降温使之冷却 最后分呈随机排列状态 然后逐步降温使之冷却 最后分 子以低能状态排列 固体达到某种稳定状态 子以低能状态排列 固体达到某种稳定状态 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模型背景 物理退火过程物理退火过程 加温过程加温过程 增强粒子的热运动 消除系统原先增强粒子的热运动 消除系统原先 可能存在的非均匀态 可能存在的非均匀态 等温过程等温过程 对于与环境换热而温度不变的封对于与环境换热而温度不变的封 闭系统 系统状态的自发变化总是朝自由能减少的闭系统 系统状态的自发变化总是朝自由能减少的 方向进行 当自由能达到最小时 系统达到平衡态 方向进行 当自由能达到最小时 系统达到平衡态 冷却过程冷却过程 使粒子热运动减弱并渐趋有序 使粒子热运动减弱并渐趋有序 系统能量逐渐下降 从而得到低能的晶体结构 系统能量逐渐下降 从而得到低能的晶体结构 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模型背景 热力学中的退火现象指物体逐渐降温时发生的物理现象 热力学中的退火现象指物体逐渐降温时发生的物理现象 温度越低 物体的能量状态越低 到达足够的低点时 温度越低 物体的能量状态越低 到达足够的低点时 液体开始冷凝与结晶 在结晶状态时 系统的能量状态最低 液体开始冷凝与结晶 在结晶状态时 系统的能量状态最低 缓慢降温时 可达到最低能量状态 但如果快速降温 会导缓慢降温时 可达到最低能量状态 但如果快速降温 会导 致不是最低能态的非晶形 致不是最低能态的非晶形 大自然知道慢工出细活 大自然知道慢工出细活 缓缓降温 使得物体分子在每一温度时 能够有足够缓缓降温 使得物体分子在每一温度时 能够有足够 时间找到安顿位置 则逐渐地 到最后可得到最低能态 系时间找到安顿位置 则逐渐地 到最后可得到最低能态 系 统最稳定 统最稳定 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法思想 模仿自然界退火现象而得 利用了物理中固体模仿自然界退火现象而得 利用了物理中固体 物质的退火过程与一般优化问题的相似性从某一初物质的退火过程与一般优化问题的相似性从某一初 始温度开始 伴随温度的不断下降 结合概率突跳始温度开始 伴随温度的不断下降 结合概率突跳 特性在解空间中随机寻找全局最优解特性在解空间中随机寻找全局最优解 组合优化问题组合优化问题金属物体金属物体 解解粒子状态粒子状态 最优解最优解能量最低的状态能量最低的状态 设定初温设定初温熔解过程熔解过程 Metropolis抽样过程抽样过程等温过程等温过程 控制参数的下降控制参数的下降冷却冷却 目标函数目标函数能量能量 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 i exp ik i ikk k iiki k Sn iET E P TC T EPTP C 设热力学系统中有个状态 有限个 离散的 状态 的能量为在温度下 经一段时间达到热平衡 这时处于状态 的概率为 则有如下关系 如何确定 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 BolzmanBolzman方程方程 1 1 exp exp 1 i k ikn i k i iik kki i n kkiik i k i E T P T E T EP T TPTiE TE TE P T TEE 可见 代表 最小的那一个 下的平均能量 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 背景 0 1 01 kik i k k ik ik i k k k TP T E T T P T n P T E T T T 温度对的影响 当很大时 各状态的概率几乎相等 随着温度的下降差别扩大 当很小趋于0时 当时 以概率 趋于最小能量状态 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 模拟退火算法的模拟要求 1 初始温度足够高 2 降温过程足够慢 3 终止温度足够低 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 模拟退火算法模拟退火算法的计算步骤的计算步骤 初始化初始化 任选初始解任选初始解 给定初始温度给定初始温度 终止温度终止温度 令迭代指标令迭代指标 注 选择注 选择时 要足够高 时 要足够高 使使 随机产生一个邻域解 随机产生一个邻域解 计算目标值增量计算目标值增量 iS 0 T f T 0 0 k kTT jN iN ii 表示的邻域 ffjf i 0 T0 i k E T 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 若若转步转步 j j比比i i好无条件转好无条件转 移移 否则产生 否则产生 j j比比i i好 有条件转移好 有条件转移 注 注 高时 广域搜索 高时 广域搜索 低时 局域搜索低时 局域搜索 若达到热平衡若达到热平衡 内循环次数大于内循环次数大于 转步转步 否则转步 否则转步 k n T 0 1 exp k f U T ij 若 则令 0 fij 令 k T k T 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 算法简介 12 降低降低 若 若停止 否则转步停止 否则转步 注 降低注 降低的方法有以下两种的方法有以下两种 1kk kf TT k T k T 1 1 1 0 950 99 2 kk kk TTrr TTT 较好的方法其中 优点 简单易行 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对TSP问题的求解 旅行商问题 即旅行商问题 即TSP问题 问题 Travelling Salesman Problem 又译为旅行推销员问题 货郎担问题 是 又译为旅行推销员问题 货郎担问题 是 数学领域中著名问题之一 假设有一个旅行商人要拜访数学领域中著名问题之一 假设有一个旅行商人要拜访 n个城市 他必须选择所要走的路径 路径的限制是每个城市 他必须选择所要走的路径 路径的限制是每 个城市只能拜访一次 而且最后要回到原来出发的城市 个城市只能拜访一次 而且最后要回到原来出发的城市 路径的选择目标是要求得的路径路程为所有路径之中的路径的选择目标是要求得的路径路程为所有路径之中的 最小值 最小值 迄今为止 这类问题中没有一个找到有效算法 倾向于迄今为止 这类问题中没有一个找到有效算法 倾向于 接受接受NP完全问题 完全问题 NP Complet或或NPC 和 和NP难题难题 NP Hard或或NPH 不存在有效算法这一猜想 认为 不存在有效算法这一猜想 认为 这类问题的大型实例不能用精确算法求解 必须寻求这这类问题的大型实例不能用精确算法求解 必须寻求这 类问题的有效的近似算法 类问题的有效的近似算法 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对TSP问题的求解 城市城市X坐标坐标Y坐标坐标城市城市X坐标坐标Y坐标坐标 10 66830 253660 22930 7610 20 61950 263470 51710 9414 30 40000 443980 87320 6536 40 24390 146390 68780 5219 50 17070 2293100 84880 3609 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对TSP问题的求解 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对TSP问题的求解 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对TSP问题的求解 泰山教育版权所有泰山教育版权所有 淘宝淘宝ID liuxingma123 模拟退火算法对T