第4章 模拟退火

第四章 模拟退火1第四章模拟退火一.导言二.模拟退火三.SA举例四.SA的收敛性分析2模拟退火(SA)的产生原始算法是由Metropolis等(1953)提出，但未引起反响；1982年Kirkpatrick等将其应用于组合优化，才得到广泛的应用目的是为了克服优化过程中陷入局优和初值依赖等弊端基本思想是模拟热力学中的退火过程一.导言3物理退火过程什么是退火退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。一.导言4物理退火过程什么是退火

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态

等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态

冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构一.导言5物理退火过程什么是退火退火淬火一.导言高温低温缓慢下降高能状态低能状态高温低温快速下降高能状态高能状态6物理退火过程数学描述设热力学系统S中有n个状态（有限且离散的），其中状态i的能量为Ei，在温度Tk下，经一段时间达到热平衡，此时处在状态i的概率为：

则有如下关系：Ei↓→Pi↑，Tk↓→Pi↓一.导言如何确定Ck?7物理退火过程数学描述通过求Ck，获得Bolzman方程：一.导言8物理退火过程Bolzman方程同一温度下，S处在能量小的状态要比处在能量大的状态概率大若存在E1<E2，则在同一温度Tk下，有故P1(Tk)>P2(Tk)一.导言9物理退火过程Bolzman方程若i*表示S中最低能量的状态，是关于温度Tk单调递减对Pi(Tk)求对温度的导数，则故一.导言10物理退火过程Bolzman方程当时，同理，当时，一.导言11物理退火过程温度Tk对的影响当Tk很大时，当时，

一.导言各状态的概率几乎相等与的小差别带来和的巨大差别12物理退火过程温度Tk对的影响例：当时

一.导言13物理退火过程温度Tk对的影响例：当时此时

一.导言温度趋于0时，以概率1趋于最小能量状态14能量越低越稳定！！！

——真理15组合优化与退火Metropolis准则—以概率接受新状态若在温度Tk，当前状态i

→

新状态j若Ej<Ei，则接受j为当前状态否则，若概率p=exp[-(Ej-Ei)/

Tk

]大于[0,1)区间的随机数，则仍接受状态j

为当前状态；若不成立则保留状态i

为当前状态一.导言在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态16组合优化与物理退火一.导言组合优化问题物理退火解状态目标函数能量函数最优解最低能量状态设定初始高温加温过程基于Metroplolis准则的搜索等温过程温度参数的下降冷却过程17构成要素解的表达与邻域移动方式同TS邻域解的产生在当前解的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生选择策略一般采用min[1,exp(-∆f/t)]二.模拟退火18构成要素初始温度均匀抽样一组状态，以各状态目标值得方差为初温随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温利用经验公式二.模拟退火实验表明：初温越大，获得高质量解的机率越大，但花费较多的计算时间19构成要素降温函数

，其中

二.模拟退火优点：简单易行，很美丽的方法20构成要素热平衡条件Metropolis抽样稳定准则检验目标函数的均值是否稳定连续若干步的目标值变化较小设置内循环迭代次数停止准则设置终止温度的阈值设置外循环迭代次数算法搜索到的最优值连续若干步保持不变二.模拟退火21算法步骤Step1选一个初始点i()，给定初始温度，终止温度，令迭代指标，；Step2随机产生一个邻域解，计算目标值增量；二.模拟退火注：选择时，要足够高，使22算法步骤Step3若，令i=j；

(j比i好，无条件转移)否则产生，若，则令i=j；(i比j好，有条件转移)Step4若达到热平衡（内循环停止准则），转Step5；否则，转Step2；二.模拟退火注：高时，广域搜索；低时，局域搜索23算法步骤Step5若k=k+1，更新，若（外循环停止准则），则停止；否则，转Step2。二.模拟退火24问题提出单机极小化总流水时间的排序问题四个工作：求使的最优顺序三.SA举例25问题提出预备知识：按SPT准则，最优顺序为3-1-4-2三.SA举例26算法设计编码方式：顺序编码初始解的产生：随机产生，如1-4-2-3邻域移动方式：2-OPT，即两两交换初始温度终止温度降温函数内循环次数三.SA举例27初始解：i=1-4-2-3(1)

① j=1-3-2-4 ② j=4-3-2-1③ j=4-2-3-1注释：①无条件转移；②③为有条件转移；在②③中，虽然目标值变坏，但搜索范围变大；

是随机产生的

三.SA举例28(2)① j=4-2-1-3 ② j=4-3-1-2③ j=4-2-3-1注释：①有条件转移；②为无条件转移；在③中，停在4-3-1-2状态，目标值仍为109

三.SA举例29(3)①②③注释：①②无条件转移；在③中，停在3-1-4-2状态，目标值仍为92；

三.SA举例SA没有历史最优，不会终止在最优解，故算法一定要保持历史最优30Markov过程的基本概念例：青蛙在3块石头上随机跳动，行动的特点是无记忆性四.SA的收敛性分析1/31/41/31/31/41/21/41/41/231Markov过程的基本概念状态：处于系统中的一种特定状况的表达状态转移概率：从状态

i转移到状态j的可能性无后效性：到一个状态后，决策只与本状态有关，与以前的历史状态无关四.SA的收敛性分析32Markov过程的基本概念以青蛙跳动为例说明状态转移概率用石头唯一的表达青蛙所处的状态，假设青蛙跳动具有无后效应的特点。四.SA的收敛性分析青