Simulated Annealing Algorithm，SAA

Presentation on theme: "Simulated Annealing Algorithm，SAA"— Presentation transcript:

1 Simulated Annealing Algorithm，SAA
by 谢广明 ， ~2006学年度第一学期

2 简介 SAA属于随机模拟算法 模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。 by 谢广明 ， ~2006学年度第一学期

3 内 容 SAA起源与发展 SAA提出依据 SAA机理 SAA流程图 SAA特点 SAA实现 SAA基础理论研究 SAA应用领域
内 容 SAA起源与发展 SAA提出依据 SAA机理 SAA流程图 SAA特点 SAA实现 SAA基础理论研究 SAA应用领域 SAA简单演示 by 谢广明 ， ~2006学年度第一学期

4 SAA起源与发展 N. Metropolis 1953年 最早提出 S. Kirkpatrick , 1983年 应用于组合优化
Optimization by simulated annealing，IBM Research Report by 谢广明 ， ~2006学年度第一学期

5 SAA提出依据 固体退火过程 加热熔解：增强粒子热运动，使其偏离平衡位置，目的是消除系统原先的非均匀态。
冷却凝固：使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，当液体凝固为固体的晶态时退火过程完成。 等温过程：退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与周围环境交换热量而温度不变的封闭系统满足自由能减少定律，系统状态的自发变化总是朝自由能减少的方向进行，直至达到平衡态。 by 谢广明 ， ~2006学年度第一学期

6 SAA提出依据 固体处于微观状态 i 的概率 服从Gibbs分布：Pi=exp(-Ei/k/T)/Z， 其中Ei 温是物体处于微观状态 i 下的总能量， T是温度， k，Z是常数。 温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。 by 谢广明 ， ~2006学年度第一学期

7 SAA提出依据 Monte Carlo模拟退火过程 方法简单，但是需要大量的计算
蒙特卡罗(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。 by 谢广明 ， ~2006学年度第一学期

8 SAA提出依据 Monte Carlo方法 Monte Carlo方法的基本思想很早以前就被人们所发现和利用。
早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。 Buffon试验：19世纪人们用投针试验的方法来求解圆周率π。 本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。 by 谢广明 ， ~2006学年度第一学期

9 SAA提出依据 Monte Carlo方法 用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。 它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。 by 谢广明 ， ~2006学年度第一学期

10 SAA提出依据 Metropolis准则 by 谢广明 ， ~2006学年度第一学期

11 SAA提出依据 Metropolis准则 by 谢广明 ， ~2006学年度第一学期

12 SAA提出依据 固体模拟退火与组合优化问题的相似性 根据这种相似性，并依据Metropolis准则进行迭代就形成了模拟退火算法
退火过程的状态 组合优化问题的解 能量目标值 能量的取舍目标值的取舍 能量的最小值目标值的最小值 根据这种相似性，并依据Metropolis准则进行迭代就形成了模拟退火算法 by 谢广明 ， ~2006学年度第一学期

13 SAA机理 优化问题的解视为固体的状态 随机给定优化问题的初始解 给定初始温度 根据当前的解产生新的解
依据Metropolis准则对两个解进行取舍选择 降低温度继续上述过程直到温度降到最低，最后的状态就是问题的解 by 谢广明 ， ~2006学年度第一学期

14 SAA流程 关键环节 1 初温、初始解 2 状态产生函数 3 状态接受函数 4 退温函数 5 抽样稳定准则 6 收敛准则 接受函数 成立否？
确定初温 随机给定初始解 收敛准则满足否？ 输出结果 Y 抽样稳定准则 满足否？ 由当前状态产生新状态 接受函数 成立否？ 替换当前状态 N 退温 保持当前状态不变 关键环节 1 初温、初始解 2 状态产生函数 3 状态接受函数 4 退温函数 5 抽样稳定准则 6 收敛准则 by 谢广明 ， ~2006学年度第一学期

15 SAA特点 可以保证全局最优 特别适合组合优化问题 可以随机选择初始解 对问题本身没有特别要求，不会因为问题实例的改变影响性能
简单易行，通用性好 by 谢广明 ， ~2006学年度第一学期

16 SAA实现 通用框架 确定问题编码方案 设计初始温度、终止温度和温度下降策略 设计能量函数 设计变异算子：产生新的解
设计选择算子： Metropolis准则 生成初始状态 by 谢广明 ， ~2006学年度第一学期

17 SAA基础理论 马氏链模型 by 谢广明 ， ~2006学年度第一学期

18 SAA基础理论 非时齐马氏链模型的收敛定理 by 谢广明 ， ~2006学年度第一学期

19 SAA基础理论 收敛可以保证，但是时间性能不好 收敛速度有待研究 by 谢广明 ， ~2006学年度第一学期

20 SAA应用领域 目前已经推广到函数优化等方面，特别适合其它算法结合以后可以获得更好的性能。
by 谢广明 ， ~2006学年度第一学期

21 SAA简单演示 问题：求 （1）编码：解自身 （2）初始温度 100 终止温度 0，降温策略 -1 （3）能量函数：
by 谢广明 ， ~2006学年度第一学期

22 SAA简单演示 Pi/ Pj =exp((Ej -Ei) /T), k=1, r=0.6 （4） Metropolis准则
（5）初始状态： 13 能量： =855 （6）变异产生新状态：大范围高斯变异 新状态： 10 能量: by 谢广明 ， ~2006学年度第一学期

23 SAA简单演示 （7）选择：选择新状态 10 （8）温度降低1度，重复上述操作直到温度降到最低 ,或许就能够得到最优解！
by 谢广明 ， ~2006学年度第一学期