模拟退火

1第五章模拟退火一.导言二.退火过程和Bolzman方程三.SA的算法构造及步骤四.计算举例五.SA的收敛性分析六.SA的应用举例2前言为了找出地球上最高的山，一群有志气的兔子们开始想办法。3前言(C.)方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法4前言(C.)方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。局部搜索法5前言方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法6前言方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。模拟退火法71.模拟退火的产生(SA)1953年Metropolis提出原始的SA算法，未引起反响；1982年Kirkpatrick提出现代的SA算法,成功用于解决大规模组合优化问题，得到广泛的应用；SA的基本思想源于热力学中的退火过程。一.导言（1）8一.导言（2）金属物体被加热到一定的温度后，它的所有分子在状态空间自由运动。随着温度逐渐下降，分子停留在不同的状态，分子运动趋于有序，并以一定结构排列。这种由高温向低温逐渐降温的热处理过程称为退火，是一个物理过程。退火是一个物理过程，该过程中系统的熵值不断减小，系统的能量也由于温度的降低趋于最小值。9一.导言（3）退火过程有三部分组成：加温过程：目的是增强分子的热运动，使其偏离平衡位置，温度很高时，固体变液体，分子分布由有序的结晶态变为无序的液态，消除了系统原先可能存在的非均匀态，随后的冷却过程从一个平衡态为起点。等温过程：保证系统在每一个温度下都达到平衡态，对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的变化总是朝着自由能减少的方向进行，自由能达到最小时，系统达到平衡态。冷却过程：使分子热运动减弱并趋于有序，系统能量逐渐下降。102.基本思想3.模拟热力学当中的退火过程退火过程：物体：高温低温高能状态低能状态一.导言（4）缓慢下降淬火：快速冷却，使金属处于高能状态，较硬易断退火：缓慢冷却，使金属处于低能状态，较为柔韧113.退火在SA中的应用4.在SA中将目标函数作为能量函数模拟：初始高温温度缓慢下降终止在低温这时能量函数达到极小，目标函数最小一.导言（4）121314对于一个典型的优化问题，核心思想是找到一个最好解，使得系统的目标函数达到最小。若采用爬山算法，在搜索过程中容易陷入局部极小，因为爬山算法只接受好解。利用模拟退火算法，以一定的概率接受劣解，可以避免陷入局部最优，从而找到全局最优解。模拟退火算法是一种全局优化算法。151.热力学中的退火过程2.退火过程是一个变温物体缓慢降温从而达到分子之间能量最低的状态的过程。3.二.退火过程和Bolzman方程（1）16二.退火过程和Bolzman方程（2）ikiikikkikiPTPETECTPiTEinS)(exp,高能量较小的状态概率要则有如下关系：的概率为：这时处于状态平衡，下，经一段时间达到热在温度的能量为，状态有限个，离散的个状态中有设热力学系统171819202.Bolzman方程二.退火过程和Bolzman方程（3）iknikiikkikikkiinikikikiEETTPETETEiTPTTPETETETP,1expexp11下的平均能量：最小的那一个代表可见：213.温度对的影响①当很大时，②，各状态的概率几乎相等③SA开始做广域搜索，随着温度的下降差别④扩大二.退火过程和Bolzman方程（4）kTkiTPkT0kiTEnTPki1kiTP22②当时，③与的小差别带来和的巨大差别④例如：=90，=100，二.退火过程和Bolzman方程（5）kiTP0kTkiTEiEjEkjTPiEjE23I.当=100时二.退火过程和Bolzman方程（6）kT367.0406.0367.0406.010010010090kkkkkjkiCCueCeCTPTP24II.当=1时此时结论:时，以概率1趋于最小能量状态二.退火过程和Bolzman方程（7）200001072.310194.84440kkkjkiCCTPTPkinikiTPTP1kT0kT25能量越低越稳定！！！——真理物理现象人的生命现象自然科学哲学自然语言数学语言二.退火过程和Bolzman方程（8）261.SA的模拟要求①初始温度足够高②降温过程足够慢③终止温度足够低④三.SA的算法构造及步骤（1）272.问题的描述及要素三.SA的算法构造及步骤（2）内循环热平衡的达到外循环算法的特点冷却控制搜索：随机的邻域移动移动同要素：状态表达和邻域代表状态是离散有限状态空间，,,minSATSiSSiif283.SA的计算步骤①初始化,任选初始解,,给定初始温度，终止温度，令迭代指标。②注：选择时，要足够高，使②随机产生一个邻域解，计算目标值增量三.SA的算法构造及步骤（3）Si0TfT0,0TTkk的邻域表示iiNiNj,ifjff0T0kiTE29③若转步④(j比i好无条件转移)；否则产生④(有条件转移)。⑤注：高时，广域搜索；低时，局域搜索④若达到热平衡(内循环次数大于)转步⑤，否则转步②。三.SA的算法构造及步骤（4）kTnjiTfUk,exp,1,0则令若,0jif令kTkT30⑤降低，若停止，否则转步②。注：降低的方法有以下两种流程框图见下页三.SA的算法构造及步骤（5）1kkfkTTkTkT111.0.950.992.kkkkTTrrTTT较好的方法其中。优点：简单易行—很美丽的表达方式31内循环产生开始停止YNYN，降温外循环0,0TTkkSi设定kTn0n产生计算ifjffiNj1nn1kkkT0f1,0expUTfkjikTnnYfkTTYNN32模拟退火算法应用（1）0-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(i)=2+5+6=1335模拟退火算法应用第二步：在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模拟退火算法应用第三步：降温。假设温度降为T=T-1，如果没有达到结束标准，则返回第二步继续执行。注意：（1）产生的新解的合法性。要舍弃那些总重量超过背包装载量的非法解。（2）在搜索过程中，要保存最优解。38模拟退火算法应用（2）TravelingSalesmanProblem(TSP)–Given6citiesandthetravelingcostbetweenanytwocities–Asalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1–Minimizethetotaltravelingcost39TSP算例Citytocity1234561124791021120138361713469515640SAparametersettingTh=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市41T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否42求得初始解BS=初始解SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解温度T＝2000n=0SequenceThelengthoftheroute12345630新的解43T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否44SequenceThelengthoftheroute13245628当前解SequenceThelengthoftheroute12345630新的解Exp((新的解－当前解)/T)=exp(-2/2000)Random[0,1]=0.745T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否46SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝2000n=147T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否48SequenceThelengthoftheroute12345630当前解SequenceThelengthoftheroute12354636新的解Exp((新的解－当前解)/T)=exp(-5/2000)Random[0,1]=0.99，拒绝新的解49T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的