第八讲 模拟退火.ppt

1、1,第五章 模拟退火,一.导言 二.退火过程和Bolzman方程 三.SA的算法构造及步骤 四.计算举例 五.SA的收敛性分析 六.SA的应用举例,2,前言,为了找出地球上最高的山，一群有志气的兔子们开始想办法。,3,前言(C.),方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。 遗传算法,4,前言(C.),方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能

2、保证局部最优值就是全局最优值。 局部搜索法,5,前言,方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。 禁忌搜索法,6,前言,方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。 模拟退火法,7,模拟退火的产生(SA) 1953年 Metropolis提出原始的SA算法，未引起反响； 1982年 Kirkpatrick提出现代的SA算法,成功用于解决大规模组合优化问题，得到广泛

3、的应用； SA的基本思想源于热力学中的退火过程。,一.导言（1）,8,一.导言（2）,金属物体被加热到一定的温度后，它的所有分子在状态空间自由运动。 随着温度逐渐下降，分子停留在不同的状态，分子运动趋于有序，并以一定结构排列。 这种由高温向低温逐渐降温的热处理过程称为退火，是一个物理过程。 退火是一个物理过程，该过程中系统的熵值不断减小，系统的能量也由于温度的降低趋于最小值。,9,一.导言（3）,退火过程有三部分组成： 加温过程：目的是增强分子的热运动，使其偏离平衡位置，温度很高时，固体变液体，分子分布由有序的结晶态变为无序的液态，消除了系统原先可能存在的非均匀态，随后的冷却过程从一个平衡态为

4、起点。 等温过程：保证系统在每一个温度下都达到平衡态，对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的变化总是朝着自由能减少的方向进行，自由能达到最小时，系统达到平衡态。 冷却过程：使分子热运动减弱并趋于有序，系统能量逐渐下降。,10,基本思想 模拟热力学当中的退火过程 退火过程： 物体： 高温低温 高能状态低能状态,一.导言（4）,缓慢下降,淬火：快速冷却，使金属处于高能状态，较硬易断 退火：缓慢冷却，使金属处于低能状态，较为柔韧,11,退火在SA中的应用 在SA中将目标函数作为能量函数 模拟： 初始高温 温度缓慢下降 终止在低温 这时能量函数达到极小，目标函数最小,一.导言（4）

5、,12,13,14,对于一个典型的优化问题，核心思想是找到一个最好解，使得系统的目标函数达到最小。 若采用爬山算法，在搜索过程中容易陷入局部极小，因为爬山算法只接受好解。 利用模拟退火算法，以一定的概率接受劣解，可以避免陷入局部最优，从而找到全局最优解。 模拟退火算法是一种全局优化算法。,15,热力学中的退火过程 退火过程是一个变温物体缓慢降温从而达到分子之间能量最低的状态的过程。,二.退火过程和Bolzman方程（1）,16,二.退火过程和Bolzman方程（2）,17,18,19,20,Bolzman方程,二.退火过程和Bolzman方程（3）,21,温度 对 的影响 当 很大时， ，各状

6、态的概率几乎相等 SA开始做广域搜索，随着温度的下降 差别 扩大,二.退火过程和Bolzman方程（4）,22,当 时， 与 的小差别带来 和 的巨大差别 例如： =90， =100，,二.退火过程和Bolzman方程（5）,23,当=100时,二.退火过程和Bolzman方程（6）,24,当 =1时 此时 结论: 时，以概率1趋于最小能量状态,二.退火过程和Bolzman方程（7）,25,能量越低越稳定！ 真理 物理现象人的生命现象 自然科学哲学 自然语言数学语言,二.退火过程和Bolzman方程（8）,26,SA的模拟要求 初始温度足够高 降温过程足够慢 终止温度足够低,三.SA的算法构造

7、及步骤（1）,27,问题的描述及要素,三.SA的算法构造及步骤（2）,28,SA的计算步骤 初始化,任选初始解, ,给定初始温度 ，终止温度 ，令迭代指标 。 注：选择 时，要足够高，使 随机产生一个邻域解， 计算目标值增量,三.SA的算法构造及步骤（3）,29,若 转步 (j比i好无条件转移) ；否则产生 (有条件转移)。 注：高时，广域搜索； 低时，局域搜索 若达到热平衡(内循环次数大于 )转步，否则转步。,三.SA的算法构造及步骤（4）,30,降低 ，若 停止，否则转步。 注：降低 的方法有以下两种 流程框图见下页,三.SA的算法构造及步骤（5）,31,32,模拟退火算法应用（1）,0-

8、1背包问题 一个旅行者有一个最多能装M公斤的背包，现在有N件物品， 它们的重量分别是W1，W2，.,Wn, 它们的价值分别为P1,P2,.,Pn.若每种物品只有一件。 求旅行者能获得的最大总价值。,33,模拟退火算法应用,例：已知背包的装载量为m=10,现在有n=5个物品，它们的重量和价值分别是 (2,3,5,1,4)和(2,5,8,3,6)。试使用模拟退火算法求解该背包问题。,34,模拟退火算法应用,问题的一个可行解用0和1的序列表示，例如i=(10101)表示选择第1、第3和第5个物品，而不选择第2和第4个物品。 第一步：初始化，假设初始解为i=(11001)，初始温度为T=10，计算 f

9、(i)=2+5+6=13,35,模拟退火算法应用,第二步：在T温度下局部搜索，直到“平衡”。 降温時机用在同一温度下所应反复进行Metropolis 演算的次数，假设次数为3。 搜寻法则：随机改变某一位的0,1值或交换某两位的0,1值。,36,模拟退火算法应用,假设产生的新解j=(11100)，f(j)=2+5+8=1513，所以接受新解。 假设产生的新解j=(11010)， f(j)=2+5+3=1013，计算接受概率 P(T)=exp(10-13)/10)0.741， 产生一个随机数random(0,1)，如果 random(0,1) P(T)，则接受j为新解，否则不接受。,37,模拟退火

10、算法应用,第三步：降温。假设温度降为T=T-1，如果没有达到结束标准，则返回第二步继续执行。 注意： （1）产生的新解的合法性。要舍弃那些总重量超过背包装载量的非法解。 （2）在搜索过程中，要保存最优解。,38,模拟退火算法应用（2）,Traveling Salesman Problem (TSP) Given 6 cities and the traveling cost between any two cities A salesman need to start from city 1 and travel all other cities then back to city 1 Min

11、imize the total traveling cost,39,TSP算例,40,SA parameter setting,Th=2000 t=10 r=0.6 N=2 生成新的解：随机选择两个位置，交换其表示的城市,41,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,42,求得初始解 BS=

12、初始解,BS,初始解,温度T2000 n=0,新的解,43,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,44,当前解,新的解,Exp(新的解当前解)/T)=exp(-2/2000) Random0,1=0.7,45,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接

13、受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,46,BS,当前解,温度T2000 n=1,47,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一

14、温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,48,当前解,新的解,Exp(新的解当前解)/T)=exp(-5/2000) Random0,1=0.99，拒绝新的解,49,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,50,当前解,新的解,Exp(新的解当前解)/T)=exp(

15、-1/2000) Random0,1=0.6,51,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,52,BS,当前解,温度T1200 n=2,53,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,54,当前解,新的解,接受新的解,温度T1200 n=0,55,T=Th,求得初始解 BS=初始解,n=0,求得新的解