智能优化模拟退火.ppt

基本概念状态： 处于系统中的一种特定状态表达。状态转移概率： 从状态i转移到状态j的可能性。无后效应： 到一个状态后，决策只与本状态有关，与以前的历史状态无关。五.SA的收敛性分析（2）*第30页，共51页，星期日，2025年，2月5日以青蛙跳动为例说明状态转移概率用石头唯一的表达青蛙所处的状态，假设青蛙跳动具有无后效应的特点。五.SA的收敛性分析（3）1/31/31/41/41/21/2青蛙跳动图示状态转移概率矩阵：1/31/41/4*第31页，共51页，星期日，2025年，2月5日t时刻处在各状态的概率向量是行向量，假设系统在t+1时达到稳态，则五.SA的收敛性分析（4）*第32页，共51页，星期日，2025年，2月5日解方程组： 可得结果：可见青蛙是跳到第三块石头上的机会多一些五.SA的收敛性分析（5）*第33页，共51页，星期日，2025年，2月5日SA的收敛性分析问题： 将状态按目标值进行升序编号，即五.SA的收敛性分析（6）*第34页，共51页，星期日，2025年，2月5日状态间的转移概率设 为i选j为邻域点时，i j的转移概率五.SA的收敛性分析（7）*第35页，共51页，星期日，2025年，2月5日设 是系统处于状态i时选择j为邻域移动点的概率， 为状态i的邻域点的个数，则则状态i到状态j的转移概率为五.SA的收敛性分析（8）*第36页，共51页，星期日，2025年，2月5日*第1页，共51页，星期日，2025年，2月5日第五章 模拟退火*第2页，共51页，星期日，2025年，2月5日第五章模拟退火一.导言二.退火过程和Bolzman方程三.SA的算法构造及步骤四.计算举例五.SA的收敛性分析六.SA的应用举例*第3页，共51页，星期日，2025年，2月5日模拟退火的产生(SA)1953年Metropolis提出原始的SA算法，未引 起反响1982年Kirkpatrick提出现代的SA算法，得到广泛的应用 一.导言（1）*第4页，共51页，星期日，2025年，2月5日基本思想模拟热力学当中的退火过程退火过程： 物体：高温 低温 高能状态 低能状态一.导言（2）缓慢下降*第5页，共51页，星期日，2025年，2月5日淬火：快速冷却，使金属处于高能状态，较硬易断退火：缓慢冷却，使金属处于低能状态，较为柔韧 一.导言（3）*第6页，共51页，星期日，2025年，2月5日模拟退火在SA中的应用在SA中将目标函数作为能量函数模拟：初始高温 温度缓慢下降 终止在低温这时能量函数达到极小，目标函数最小一.导言（4）*第7页，共51页，星期日，2025年，2月5日热力学中的退火过程 变温物体缓慢降温从而达到分子之间能量最低的状态 二.退火过程和Bolzman方程（1）*第8页，共51页，星期日，2025年，2月5日二.退火过程和Bolzman方程（2）*第9页，共51页，星期日，2025年，2月5日Bolzman方程二.退火过程和Bolzman方程（3）*第10页，共51页，星期日，2025年，2月5日温度对的影响当很大时， ，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降 差别扩大二.退火过程和Bolzman方程（4）*第11页，共51页，星期日，2025年，2月5日当 时，与的小差别带来和的巨大差别例如：=90， =100，二.退火过程和Bolzman方程（5）*第12页，共51页，星期日，2025年，2月5日当 =100时二.退火过程和Bolzman方程（6）*第13页，共51页，星期日，2025年，2月5日当=1时此时结论: 时，以概率1趋于最小能量状态二.退火过程和Bolzman方程（7）*第14页，共51页，星期日，2025年，2月5日SA的模拟要求初始温度足够高降温过程足够慢终止温度足够低 三.SA的算法构造及步骤（1）*第15页，共51页，星期日，2025年，2月5日问题的描述及要素 三.SA的算法构造及步骤（2）*第16页，共51页，星期日，2025年，2月5日SA的计算步骤初始化,任选初