模拟退火算法新(共49张PPT)精选

模拟退火算法(suànfǎ)新第一页，共49页。2第五章模拟退火一.导言二.退火过程和Bolzman方程(fāngchéng)三.SA的算法构造及步骤四.计算举例五.SA的收敛性分析六.SA的应用举例第二页，共49页。3模拟退火的产生(SA)1953年Metropolis提出原始的SA算法(suànfǎ)，未引 起反响1982年Kirkpatrick提出现代的SA算法(suànfǎ)，得到广泛的应用 一.导言(dǎoyán)〔1〕第三页，共49页。4根本思想模拟热力学当中(dāngzhōng)的退火过程退火过程： 物体：高温 低温 高能状态 低能状态一.导言(dǎoyán)〔2〕缓慢(huǎnmàn)下降第四页，共49页。设 为i选j为邻域点时，i j的转移(zhuǎnyí)概率问题(wèntí)的提出变温物体缓慢(huǎnmàn)降温从而到达分子之间能量最第三十九页，共49页。第四十一页，共49页。结论(jiélùn):第三十四页，共49页。第四十一页，共49页。第四十二页，共49页。降低，假设(jiǎshè)停止，否那么转步②。单机极小化总流水时间的排序问题(wèntí)在SA中将目标函数作为能量函数注：选择时，要足够高，使处于系统中的一种特定状态表达。第三十二页，共49页。举例说明：盲人(mánɡrén)一维游走、醉汉或青蛙在3块石SA没有历史最优，不会终止在最优解，故算法(suànfǎ)一5淬火：快速冷却，使金属(jīnshǔ)处于高能状态，较硬易断退火：缓慢冷却，使金属(jīnshǔ)处于低能状态，较为柔韧

一.导言(dǎoyán)〔3〕第五页，共49页。6模拟退火在SA中的应用在SA中将目标函数作为能量函数模拟：初始高温 温度缓慢下降(xiàjiàng) 终止在低温这时能量函数到达极小，目标函数最小一.导言(dǎoyán)〔4〕第六页，共49页。7热力学中的退火过程 变温物体缓慢(huǎnmàn)降温从而到达分子之间能量最低的状态 二.退火(tuìhuǒ)过程和Bolzman方程〔1〕第七页，共49页。8二.退火(tuìhuǒ)过程和Bolzman方程〔2〕第八页，共49页。9Bolzman方程(fāngchéng)二.退火(tuìhuǒ)过程和Bolzman方程〔3〕第九页，共49页。10温度对的影响当很大时， ，各状态(zhuàngtài)的概率几乎相等SA开始做广域搜索，随着温度的下降 差异扩大二.退火(tuìhuǒ)过程和Bolzman方程〔4〕第十页，共49页。11当 时，与的小差异带来和的巨大(jùdà)差异例如：=90， =100，二.退火过程(guòchéng)和Bolzman方程〔5〕第十一页，共49页。12当 =100时二.退火(tuìhuǒ)过程和Bolzman方程〔6〕第十二页，共49页。13当=1时此时结论(jiélùn): 时，以概率1趋于最小能量状态二.退火过程(guòchéng)和Bolzman方程〔7〕第十三页，共49页。14SA的模拟要求初始温度足够(zúgòu)高降温过程足够(zúgòu)慢终止温度足够(zúgòu)低

三.SA的算法构造(gòuzào)及步骤〔1〕第十四页，共49页。15问题的描述(miáoshù)及要素 三.SA的算法(suànfǎ)构造及步骤〔2〕第十五页，共49页。16SA的计算步骤初始化,任选初始解,,给定初始温度，终止温度，令迭代指标(zhǐbiāo) 。 注：选择时，要足够高，使随机产生一个邻域解， 计算目标值增量三.SA的算法(suànfǎ)构造及步骤〔3〕第十六页，共49页。17假设 转步④(j比i好无条件(tiáojiàn)转移)；否那么产生 (j比i好，有条件(tiáojiàn)转移)。 注： 高时，广域搜索；低时，局域搜索假设到达热平衡(内循环次数大于)转步⑤，否那么转步②。 三.SA的算法构造(gòuzào)及步骤〔4〕第十七页，共49页。18降低，假设(jiǎshè)停止，否那么转步②。 注：降低的方法有以下两种流程框图见下页 三.SA的算法(suànfǎ)构造及步骤〔5〕第十八页，共49页。19内循环产生开始停止YNYN，降温外循环设定产生计算YYNN第十九页，共49页。SA开始做广域搜索，随着温度的下降 差异第三十八页，共49页。例如：=90， =100，定理(dìnglǐ)证明：定理(dìnglǐ)证明：SA的收敛性分析(fēnxī)〔10〕第三十八页，共49页。SA开始做广域搜索，随着温度的下降 差异第二十三页，共49页。温度对的影响模拟退火的产生(SA)预备知识(zhīshi)：按SPT准那么，最优顺序为3-1-4-2模拟热力学当中(dāngzhōng)的退火过程题，他们行动的共同特点是无记忆性。退火(tuìhuǒ)过程和Bolzman方程〔6〕20问题(wèntí)的提出单机极小化总流水时间的排序问题(wèntí)四个工作： ，求的最优顺序。 四.计算(jìsuàn)举例〔1〕第二十页，共49页。21预备知识(zhīshi)：按SPT准那么，最优顺序为3-1-4-2四.计算(jìsuàn)举例〔2〕第二十一页，共49页。22用SA求解这个问题状态(zhuàngtài)表达：顺序编码邻域定义：两两换位定义为邻域移动解：设 降温过程定义为初始解：i=1-4-2-3四.计算(jìsuàn)举例〔3〕第二十二页，共49页。23⑴①②③注释：①无条件转移；②③为有条件转移；在②③中，虽然目标值变坏(biànhuài)，但搜索范围变大；是随机产生的 四.计算(jìsuàn)举例〔4〕第二十三页，共49页。24⑵①②③注释：①有条件转移(zhuǎnyí)；②为无条件转移(zhuǎnyí)；在③中，停在4-3-1-2状态，目标值仍为109；四.计算(jìsuàn)举例〔5〕第二十四页，共49页。25⑵①②③注释：①②无条件转移；在③中，停在3-1-4-2状态，目标值仍为92； SA没有历史最优，不会终止在最优解，故算法(suànfǎ)一定要保持历史最优。四.计算(jìsuàn)举例〔6〕第二十五页，共49页。26SA终止在最优解上的条件(tiáojiàn)：初始温度足够高热平衡时间足够长终止温度足够低降温过程足够慢 以上条件(tiáojiàn)实际中很难满足，所以只能记录历史最优解。四.计算(jìsuàn)举例〔7〕第二十六页，共49页。27SA特点：编程最容易，理论最完善。下面基于(jīyú)Markov过程分析收敛性。

四.计算(jìsuàn)举例〔8〕第二十七页，共49页。28Markov过程的根本概念举例说明：盲人(mánɡrén)一维游走、醉汉或青蛙在3块石头上随机跳动，这3中状况可用来说明这个问题，他们行动的共同特点是无记忆性。五.SA的收敛性分析(fēnxī)〔1〕第二十八页，共49页。29根本概念状态： 处于系统中的一种特定状态表达。状态转移概率： 从状态i转移到状态j的可能性。无后效应： 到一个状态后，决策只与本状态有关，与以前的历史(lìshǐ)状态无关。五.SA的收敛性分析(fēnxī)〔2〕第二十九页，共49页。30以青蛙跳动为例说明状态转移概率(gàilǜ)用石头唯一的表达青蛙所处的状态，假设青蛙跳动具有无后效应的特点。五.SA的收敛性分析(fēnxī)〔3〕1/31/31/41/41/21/2青蛙跳动图示状态转移概率矩阵：1/31/41/4第三十页，共49页。31t时刻处在各状态(zhuàngtài)的概率向量是行向量，假设系统在t+1时到达稳态，那么五.SA的收敛性分析(fēnxī)〔4〕第三十一页，共49页。32解方程组： 可得结果：可见青蛙是跳到第三块石头(shítou)上的时机多一些五.SA的收敛性分析(fēnxī)〔5〕第三十二页，共49页。33SA的收敛性分析问题： 将状态(zhuàngtài)按目标值进行升序编号，即五.SA的收敛性分析(fēnxī)〔6〕第三十三页，共49页。34状态间的转移(zhuǎnyí)概率设 为i选j为邻域点时，i j的转移(zhuǎnyí)概率五.SA的收敛性分析(fēnxī)〔7〕第三十四页，共49页。35设 是系统处于状态i时选择j为邻域移动点的概率(gàilǜ)， 为状态i的邻域点的个数，那么那么状态i到状态j的转移概率(gàilǜ)为五.SA的收敛性分析(fēnxī)〔8〕第三十五页，共49页。36当Tk很大时，那么(nàme)状态转移矩阵为：分两种情况讨论：五.SA的收敛性分析(fēnxī)〔9〕第三十六页，共49页。37当五.SA的收敛性分析(fēnxī)〔10〕第三十七页，共49页。38当状态1是“捕捉的〞〔任何(rènhé)状态到1状态后都无法转出〕即青蛙跳到石头1上无法跳出。五.SA的收敛性分析(fēnxī)〔11〕第三十八页，共49页。39推理(tuīlǐ)证明：证毕即SA将以概率1停在状态〔石头〕1上。五.SA的收敛性分析(fēnxī)〔12〕第三十九页，共49页。40定理(dìnglǐ)：当P对称时，当到达热平衡时，对所有 有：定理(dìnglǐ)证明见下页。五.SA的收敛性分析(fēnxī)〔13〕第四十页，共49页。41定理(dìnglǐ)证明：当到达热平衡时有五.SA的收敛性分析(fēnxī)〔14〕第四十一页，共49页。42问题：成组技术中加工(jiāgōng)中心的组成问题设有m台机器，要组成假设干个加工(jiāgōng)中心，每个加工(jiāgōng)中心可有最多q台、最少p台机器，有n种加工(jiāgōng)工作要在这些机器上加工(jiāgōng)。如何组织加工(jiāgōng)中心，可使总的各中心的机器相似性最好。六.SA的应用(yìngyòng)举例〔1〕第四十二页，共49页。43六.SA的应用(yìngyòng)举例〔2〕第四十三页，共49页。44六.SA的应用(yìngyòng)举例〔3〕第四十四页，共49页。45六.SA的应用(yìngyòng)举例〔4〕第四十五页，共49页。46所有相似的机器(jīqì)放在同一个中心，极大化成组相似