模拟退火讲解.ppt

1、1,一.导言 二.退火过程和Bolzman方程 三.SA的算法构造及步骤 四.计算举例 五.SA的收敛性分析 六.SA的应用举例,模拟退火,2,模拟退火的产生(SA) 1953年原始的SA算法被提出，未引起反响 1982年现代的SA算法被提出，得到广泛的应用 SA采用一种概率转移的策略来实现全局最优,一.导言,3,基本思想 模拟热力学当中的退火过程 金属退火过程：,一.导言,加热过程,等温过程,降温过程,消除非均匀态,达到平衡态,最低能量状态,4,基本思想 退火： 淬火：,一.导言,5,退火与模拟退火(SA),一.导言,6,退火过程的数学描述 设热力学系统S中有n个状态（有限且离散的），其中

2、状态i的能量为Ei，在温度Tk下，经一段时间达到热平 衡，此时处在状态i的概率为： 则有如下关系： Ei Pi ， Tk Pi ,二.退火过程和Bolzman方程,如何确定Ck?,7,Bolzman方程 通过求Ck，获得Bolzman方程：,二.退火过程和Bolzman方程,8,Bolzman方程 同一温度下，S处在能量小的状态要比处在能量大的状态概率大 若存在E1P2(Tk),二.退火过程和Bolzman方程,9,Bolzman方程 若i*表示S中最低能量的状态， 是关于温度Tk单调递减的 对Pi(Tk)求对温度的导数，则 故,二.退火过程和Bolzman方程,10,Bolzman方程 当T

3、k0时， 同理，当Tk0时，,二.退火过程和Bolzman方程,11,温度 对 的影响 当 很大时， ，各状态的概率几乎相等 SA开始做广域搜索，随着温度的下降 差别扩大,二.退火过程和Bolzman方程,12,当 时， 与 的小差别带来 和 的巨大差别 例如：,二.退火过程和Bolzman方程,13,当 时,二.退火过程和Bolzman方程,14,当 时 此时 结论: 时，以概率1趋于最小能量状态,二.退火过程和Bolzman方程,15,能量越低越稳定！ 真理,二.退火过程和Bolzman方程,16,问题的描述及要素,三.SA的算法构造及步骤,17,SA的计算步骤 初始化,任选初始解, ,给

4、定初始温度 ，终止温度 ，令迭代指标 。 注：选择 时，要足够高，使 随机产生一个邻域解， 计算目标值增量,三.SA的算法构造及步骤,18,若 转步 (j比i好无条件转移) ；否则产生 (i比j好，有条件转移)。 注：高时，广域搜索； 低时，局域搜索 若达到热平衡(内循环次数大于 )转步，否则转步。,三.SA的算法构造及步骤,19,降低 ，若 停止，否则转步。 注：降低 的方法有以下两种 流程框图见下页,三.SA的算法构造及步骤,20,21,问题的提出 单机极小化总流水时间的排序问题 四个工作： ，求 的最优顺序。,四.计算举例,22,预备知识：按SPT准则，最优顺序为3-1-4-2,四.计算

5、举例,23,用SA求解这个问题 状态表达：顺序编码 邻域定义：两两换位定义为邻域移动 解： 设 降温过程定义为 初始解：i=1-4-2-3,四.计算举例,24, 注释： 无条件转移； 为有条件转移； 在中，虽然目标值变坏，但搜索范围变大； 是随机产生的,四.计算举例,25, 注释： 有条件转移； 为无条件转移； 在中，停在4-3-1-2状态，目标值仍为109；,四.计算举例,26, 注释： 无条件转移； 在中，停在3-1-4-2状态，目标值仍为92； SA没有历史最优，不会终止在最优解，故算法一 定要保持历史最优。,四.计算举例,27,SA终止在最优解上的条件： 初始温度足够高 热平衡时间足够

6、长 终止温度足够低 降温过程足够慢 以上条件实际中很难满足，所以只能记录历 史最优解。,四.计算举例,28,练 习,工作指派问题可以简述如下：n个工作可以由n个工人分别完成。工人i完成工作j的时间为dij，问如何安排可是总的工作时间达到最小。试按SA算法设计一个求解该问题的算法（包括状态表达，领域定义，算法步骤），并画出程序框图。,29,Markov过程的基本概念 举例说明：青蛙在3块石头上随机跳动 行动的特点是无记忆性。,五.SA的收敛性分析,1/3,1/4,1/3,1/3,1/4,1/2,1/4,1/4,1/2,30,基本概念 状态： 处于系统中的一种特定状况的表达 状态转移概率： 从状态

7、 i 转移到状态 j 的可能性 无后效性： 到一个状态后，决策只与本状态有关，与以前的历史状态无关,五.SA的收敛性分析,31,以青蛙跳动为例说明状态转移概率 用石头唯一的表达青蛙所处的状态，假设青蛙 跳动具有无后效应的特点。,五.SA的收敛性分析,青蛙跳动图示,状态转移概率矩阵：,1/3,1/4,1/4,32,表示t时刻青蛙处在各状 态的概率分布向量， 是行向量，则在t+1时刻 有： 若 ，则,五.SA的收敛性分析,33,假设系统在t+1时达到稳态，则 又 故 存在唯一解,五.SA的收敛性分析,34,在上面的小例子中解方程组： 可得结果： 可见系统达到稳态时，青蛙是在第三块石头上 的机会多一

8、些,五.SA的收敛性分析,35,SA的Markov描述 问题： 将状态按目标值进行升序编号， 即,五.SA的收敛性分析,36,状态间的转移概率 设 为 i 选 j 为邻域点时，i j的转移概率,五.SA的收敛性分析,37,设是系统处于状态 i 时选择 j 为邻域移动点 的概率， 为状态 i 的邻域点的个数，则 则状态 i 到状态 j 的转移概率为,五.SA的收敛性分析,38,则状态转移矩阵为： 分两种情况讨论：,五.SA的收敛性分析,39,当 时 若ji，则 若ji，则 又,五.SA的收敛性分析,40,五.SA的收敛性分析,41,当 时 若ji，则 若ji，则,五.SA的收敛性分析,42,五.

9、SA的收敛性分析,状态1是 “捕捉的”（任何状态到1状态后都 无法转出）即青蛙跳到石头1上无法跳出。,43,SA实现全局收敛的条件： 状态可达 初值鲁棒 极限分布的存在,五.SA的收敛性分析,44,引理：当 时，系统达到稳态时的状态概 率分布向量 证明： 当系统达到稳态时，存在,五.SA的收敛性分析,45,又 则,五.SA的收敛性分析,46,五.SA的收敛性分析,又 ， 故当 时， 当 时， 得证。,47,定理：G对称，当达到热平衡时，对所有 有： 注释： 表示状态概率分布向量 表示系统处在状态1的概率 表示从1移向状态i的概率,五.SA的收敛性分析,48,五.SA的收敛性分析,证明：在温度T

10、k下达到热平衡时，有 当i=1时， 又 故,49,五.SA的收敛性分析,因此，对于所有 ，当达到热平衡时 得证。,由以上定理可知，当Tk趋近于0时，对于所有状态 i1，有 趋近于0， 趋近于1，即SA对应的 Markov过程将以概率1收敛于状态1。,50,问题：成组技术中加工中心的组成问题设有m 台机器，要组成若干个加工中心，每个加工中 心可有最多q台、最少p台机器，有n种加工工 作要在这些机器上加工。 如何组织加工中心，可使总的各中心的机器相 似性最好。,六.SA的应用举例,51,六.SA的应用举例,52,六.SA的应用举例,53,六.SA的应用举例,54,所有相似的机器放在同一个中心，极大化成组相似性,指定唯一性，一个机器只能放一个中心,每一个中心的机器数小于q台,每一个中心的机器数至少有p台,六.SA的应用举例,55,用SA求解 状态表达： ，表示