IOA-北大未名BBS-北京大学校园论坛，北大人的网上精神家园.ppt

1、by 谢广明 ， 20052006学年度第一学期,1,Simulated Annealing Algorithm，SAA,第三章 模拟退火算法 (I),by 谢广明 ， 20052006学年度第一学期,2,简介,SAA属于随机模拟算法模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。,by 谢广明 ， 20052006学年度第一学期,3,内 容,SAA起源与发展SAA提出依据SAA机理SAA流程图SAA特点SAA实现SAA基础理论研究SAA应用领域SAA简单演示,by 谢广明 ， 20052006学年度第一

2、学期,4,SAA起源与发展,N. Metropolis 1953年 最早提出S. Kirkpatrick , 1983年 应用于组合优化Optimization by simulated annealing，IBM Research Report,by 谢广明 ， 20052006学年度第一学期,5,SAA提出依据,固体退火过程加热熔解：增强粒子热运动，使其偏离平衡位置，目的是消除系统原先的非均匀态。冷却凝固：使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，当液体凝固为固体的晶态时退火过程完成。等温过程：退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，对于与周围环境交换热量而温度不

3、变的封闭系统满足自由能减少定律，系统状态的自发变化总是朝自由能减少的方向进行，直至达到平衡态。,by 谢广明 ， 20052006学年度第一学期,6,SAA提出依据,固体处于微观状态 i 的概率服从Gibbs分布：Pi=exp(-Ei/k/T)/Z， 其中Ei 温是物体处于微观状态 i 下的总能量， T是温度， k，Z是常数。温度低时能量低的微观状态概率大，温度趋于零时，固体几乎处于概率最大能量最小的基态。,by 谢广明 ， 20052006学年度第一学期,7,SAA提出依据,Monte Carlo模拟退火过程方法简单，但是需要大量的计算蒙特卡罗(Monte Carlo)方法，或称计算机随机模

4、拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯诺伊曼用驰名世界的赌城摩纳哥的Monte Carlo来命名这种方法，为它蒙上了一层神秘色彩。,by 谢广明 ， 20052006学年度第一学期,8,SAA提出依据,Monte Carlo方法Monte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。Buffon试验：19世纪人们用投针试验的方法来求解圆周率。本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机

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

6、， 20052006学年度第一学期,12,SAA提出依据,固体模拟退火与组合优化问题的相似性退火过程的状态 组合优化问题的解 能量目标值 能量的取舍目标值的取舍 能量的最小值目标值的最小值根据这种相似性，并依据Metropolis准则进行迭代就形成了模拟退火算法,by 谢广明 ， 20052006学年度第一学期,13,SAA机理,优化问题的解视为固体的状态随机给定优化问题的初始解给定初始温度根据当前的解产生新的解依据Metropolis准则对两个解进行取舍选择降低温度继续上述过程直到温度降到最低，最后的状态就是问题的解,by 谢广明 ， 20052006学年度第一学期,14,SAA流程,关键环

7、节1 初温、初始解2 状态产生函数3 状态接受函数4 退温函数5 抽样稳定准则6 收敛准则,by 谢广明 ， 20052006学年度第一学期,15,SAA特点,可以保证全局最优特别适合组合优化问题可以随机选择初始解对问题本身没有特别要求，不会因为问题实例的改变影响性能简单易行，通用性好,by 谢广明 ， 20052006学年度第一学期,16,SAA实现,通用框架确定问题编码方案设计初始温度、终止温度和温度下降策略设计能量函数设计变异算子：产生新的解设计选择算子： Metropolis准则生成初始状态,by 谢广明 ， 20052006学年度第一学期,17,SAA基础理论,马氏链模型,by 谢广

8、明 ， 20052006学年度第一学期,18,SAA基础理论,非时齐马氏链模型的收敛定理,by 谢广明 ， 20052006学年度第一学期,19,SAA基础理论,收敛可以保证，但是时间性能不好收敛速度有待研究,by 谢广明 ， 20052006学年度第一学期,20,SAA应用领域,目前已经推广到函数优化等方面，特别适合其它算法结合以后可以获得更好的性能。,by 谢广明 ， 20052006学年度第一学期,21,SAA简单演示,问题：求（1）编码：解自身 （2）初始温度 100 终止温度 0，降温策略 -1（3）能量函数：,by 谢广明 ， 20052006学年度第一学期,22,SAA简单演示,（4） Metropolis准则 Pi/ Pj =exp(Ej -Ei) /T), k=1, r=0.6（5）初始状态： 13 能量： 1024-169=855 （6）变异产生新状态：大范围高斯变异 新状态： 10 能量: 924,by 谢广明 ， 20052006学年度第一学期,23,（7）选择：选择新状态 10（8）温度降低1度，重复上述操作直到温度降到最低 ,或许就能够得到最优解！,SAA简单演示,