模拟退火讲解.ppt

《模拟退火讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、一.导言优化问题物理退火解状态目标函数能量函数最优解最低能量状态设定初始高温加温过程基于Metroplolis准则的搜索等温过程温度参数的下降冷却过程5退火过程的数学描述设热力学系统S中有n个状态（有限且离散的），其中状态i的能量为Ei，在温度Tk下，经一段时间达到热平衡，此时处在状态i的概率为：则有如下关系：Ei↓→Pi↑，Tk↓→Pi↓二.退火过程和Bolzman方程如何确定Ck?6Bolzman方程通过求Ck，获得Bolzman方程：二.退火过程和Bolzman方程7Bolzman方程同一温度下，S处在

3、能量小的状态要比处在能量大的状态概率大若存在E1P2(Tk)二.退火过程和Bolzman方程8Bolzman方程若i*表示S中最低能量的状态，是关于温度Tk单调递减的对Pi(Tk)求对温度的导数，则故二.退火过程和Bolzman方程9Bolzman方程当Tk→0时，同理，当Tk→0时，二.退火过程和Bolzman方程10温度对的影响当很大时，，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降差别扩大二.退火过程和Bolzman方程11当时，与的小差别带来和的

4、巨大差别例如：二.退火过程和Bolzman方程12当时二.退火过程和Bolzman方程13当时此时结论:时，以概率1趋于最小能量状态二.退火过程和Bolzman方程14能量越低越稳定！！！——真理二.退火过程和Bolzman方程15问题的描述及要素三.SA的算法构造及步骤16SA的计算步骤初始化,任选初始解,,给定初始温度，终止温度，令迭代指标。注：选择时，要足够高，使随机产生一个邻域解，计算目标值增量三.SA的算法构造及步骤17若转步④(j比i好无条件转移)；否则产生(i比j好，有条件转移)。注：高时，广域

5、搜索；低时，局域搜索若达到热平衡(内循环次数大于)转步⑤，否则转步②。三.SA的算法构造及步骤18降低，若停止，否则转步②。注：降低的方法有以下两种流程框图见下页三.SA的算法构造及步骤19内循环产生开始停止YNYN，降低外循环设定产生计算YYNN20问题的提出单机极小化总流水时间的排序问题四个工作：，求的最优顺序。四.计算举例21预备知识：按SPT准则，最优顺序为3-1-4-2四.计算举例22用SA求解这个问题状态表达：顺序编码邻域定义：两两换位定义为邻域移动解：设降温过程定义为初始解：i=1-4-2-3四

6、.计算举例23⑴①②③注释：①无条件转移；②③为有条件转移；在②③中，虽然目标值变坏，但搜索范围变大；是随机产生的四.计算举例24⑵①②③注释：①有条件转移；②为无条件转移；在③中，停在4-3-1-2状态，目标值仍为109；四.计算举例25⑵①②③注释：①②无条件转移；在③中，停在3-1-4-2状态，目标值仍为92；SA没有历史最优，不会终止在最优解，故算法一定要保持历史最优。四.计算举例26SA终止在最优解上的条件：初始温度足够高热平衡时间足够长终止温度足够低降温过程足够慢以上条件实际中很难满足，所以只能记

7、录历史最优解。四.计算举例27练习工作指派问题可以简述如下：n个工作可以由n个工人分别完成。工人i完成工作j的时间为dij，问如何安排可是总的工作时间达到最小。试按SA算法设计一个求解该问题的算法（包括状态表达，领域定义，算法步骤），并画出程序框图。28Markov过程的基本概念举例说明：青蛙在3块石头上随机跳动行动的特点是无记忆性。五.SA的收敛性分析1/31/41/31/31/41/21/41/41/229基本概念状态：处于系统中的一种特定状况的表达状态转移概率：从状态i转移到状态j的可能性无后效性：到一

8、个状态后，决策只与本状态有关，与以前的历史状态无关五.SA的收敛性分析30以青蛙跳动为例说明状态转移概率用石头唯一的表达青蛙所处的状态，假设青蛙跳动具有无后效应的特点。五.SA的收敛性分析青蛙跳动图示状态转移概率矩阵：1/31/41/41/31/31/41/41/21/231表示t时刻青蛙处在各状态的概率分布向量，是行向量，则在t+1时刻有：若，则五.SA的收敛性分析32假设系统在t+1时达到稳态，