第八讲 模拟退火

第五章模拟退火一.导言二.退火过程和Bolzman方程三.SA的算法构造及步骤四.计算举例五.SA的收敛性分析六.SA的应用举例1前言为了找出地球上最高的山，一群有志气的兔子们开始想办法。

2前言(C.)方案一：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。遗传算法

3前言(C.)方案二：兔子们朝着比现在高的地方跳去，它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实，它们这种做法只是自己心理上认为找到了最高的山，并不能保证局部最优值就是全局最优值。局部搜索法

4前言方案三：兔子们知道一个兔子的力量是渺小的。于是，它们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。这样，它们制定了下一步去哪里寻找的策略。禁忌搜索法

5前言方案四：兔子们用酒将自己灌醉了。它们随机地跳了很长时间。在这期间，它们可能走向高处，也可能踏入平地。但是，随着时间的流逝，它们渐渐清醒了并朝最高方向跳去。模拟退火法

6模拟退火的产生(SA)1953年Metropolis提出原始的SA算法，未引起反响；1982年Kirkpatrick提出现代的SA算法,成功用于解决大规模组合优化问题，得到广泛的应用；SA的基本思想源于热力学中的退火过程。

一.导言（1）7一.导言（2）金属物体被加热到一定的温度后，它的所有分子在状态空间自由运动。随着温度逐渐下降，分子停留在不同的状态，分子运动趋于有序，并以一定结构排列。这种由高温向低温逐渐降温的热处理过程称为退火，是一个物理过程。退火是一个物理过程，该过程中系统的熵值不断减小，系统的能量也由于温度的降低趋于最小值。8一.导言（3）退火过程有三部分组成：加温过程：目的是增强分子的热运动，使其偏离平衡位置，温度很高时，固体变液体，分子分布由有序的结晶态变为无序的液态，消除了系统原先可能存在的非均匀态，随后的冷却过程从一个平衡态为起点。等温过程：保证系统在每一个温度下都达到平衡态，对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的变化总是朝着自由能减少的方向进行，自由能达到最小时，系统达到平衡态。冷却过程：使分子热运动减弱并趋于有序，系统能量逐渐下降。9基本思想模拟热力学当中的退火过程退火过程： 物体：高温 低温 高能状态 低能状态一.导言（4）缓慢下降淬火：快速冷却，使金属处于高能状态，较硬易断退火：缓慢冷却，使金属处于低能状态，较为柔韧

10退火在SA中的应用在SA中将目标函数作为能量函数模拟：初始高温 温度缓慢下降 终止在低温这时能量函数达到极小，目标函数最小一.导言（4）111213对于一个典型的优化问题，核心思想是找到一个最好解，使得系统的目标函数达到最小。若采用爬山算法，在搜索过程中容易陷入局部极小，因为爬山算法只接受好解。利用模拟退火算法，以一定的概率接受劣解，可以避免陷入局部最优，从而找到全局最优解。模拟退火算法是一种全局优化算法。14热力学中的退火过程 退火过程是一个变温物体缓慢降温从而达到分子之间能量最低的状态的过程。

二.退火过程和Bolzman方程（1）15二.退火过程和Bolzman方程（2）16171819Bolzman方程二.退火过程和Bolzman方程（3）20温度对的影响当很大时， ，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降 差别扩大二.退火过程和Bolzman方程（4）21当 时，与的小差别带来和的巨大差别例如：=90， =100，二.退火过程和Bolzman方程（5）22当 =100时二.退火过程和Bolzman方程（6）23当=1时此时结论:

时，以概率1趋于最小能量状态二.退火过程和Bolzman方程（7）24能量越低越稳定！！！——真理物理现象人的生命现象自然科学哲学自然语言数学语言二.退火过程和Bolzman方程（8）25SA的模拟要求初始温度足够高降温过程足够慢终止温度足够低

三.SA的算法构造及步骤（1）26问题的描述及要素

三.SA的算法构造及步骤（2）27SA的计算步骤初始化,任选初始解,,给定初始温度，终止温度，令迭代指标 。

注：选择时，要足够高，使随机产生一个邻域解， 计算目标值增量三.SA的算法构造及步骤（3）28若 转步④(j比i好无条件转移)；否则产生

(有条件转移)。

注： 高时，广域搜索；低时，局域搜索若达到热平衡(内循环次数大于)转步⑤，否则转步②。

三.SA的算法构造及步骤（4）29降低，若停止，否则转步②。

注：降低的方法有以下两种流程框图见下页

三.SA的算法构造及步骤（5）30内循环产生开始停止YNYN，降温外循环设定产生计算YYNN31模拟退火算法应用（1）0-1背包问题一个旅行者有一个最多能装M公斤的背包，现在有N件物品，

它们的重量分别是W1，W2，...,Wn,

它们的价值分别为P1,P2,...,Pn.

若每种物品只有一件。求旅行者能获得的最大总价值。32模拟退火算法应用例：已知背包的装载量为m=10,现在有n=5个物品，它们的重量和价值分别是(2,3,5,1,4)和(2,5,8,3,6)。试使用模拟退火算法求解该背包问题。33模拟退火算法应用问题的一个可行解用0和1的序列表示，例如i=(10101)表示选择第1、第3和第5个物品，而不选择第2和第4个物品。第一步：初始化，假设初始解为i=(11001)，初始温度为T=10，计算f(i)=2+5+6=1334模拟退火算法应用第二步：在T温度下局部搜索，直到“平衡”。降温時机用在同一温度下所应反复进行Metropolis演算的次数，假设次数为3。搜寻法则：随机改变某一位的0,1值或交换某两位的0,1值。35模拟退火算法应用假设产生的新解j=(11100)，f(j)=2+5+8=15>13，所以接受新解。假设产生的新解j=(11010)，f(j)=2+5+3=10<13，计算接受概率P(T)=exp((10-13)/10)≈0.741，产生一个随机数rando