模擬退火算法講解課件

模擬退火算法模擬退火算法算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極小；克服初值依賴性。算法的提出什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。什么是退火：物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可

熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：溫度越低，物體的能量狀態(tài)越低，到達(dá)足夠的低點(diǎn)時(shí)，液體開始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。緩慢降溫（退火，annealing）時(shí)，可達(dá)到最低能量狀態(tài)；但如果快速降溫（淬火，quenching），會(huì)導(dǎo)致不是最低能態(tài)的非晶形。

熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性

從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布數(shù)學(xué)表述

模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率1停留在最優(yōu)解。在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變Boltzman概率分布告訴我們：

（1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率（2）溫度越高，不同能量狀態(tài)對(duì)應(yīng)的概率相差越小；溫度足夠高時(shí)，各狀態(tài)對(duì)應(yīng)概率基本相同。（3）隨著溫度的下降，能量最低狀態(tài)對(duì)應(yīng)概率越來越大；溫度趨于0時(shí)，其狀態(tài)趨于1Boltzman概率分布告訴我們：Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)固體在恒定溫度下達(dá)到熱平衡的過程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)若在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i

為當(dāng)前狀態(tài)。Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。p=exp[-(Ej-Ei)/kBT]相似性比較組合優(yōu)化問題金屬物體解離子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫溶解過程Metropolis抽樣過程控制參數(shù)的下降等溫過程冷卻過程目標(biāo)函數(shù)能量相似性比較組合優(yōu)化問題金屬物體解離子狀態(tài)最優(yōu)解能量最低的狀態(tài)基本步驟給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果?；静襟E算法程序核心內(nèi)容三個(gè)函數(shù)新狀態(tài)sj=Genete(s)ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;tk+1=update(tk)兩個(gè)準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則（內(nèi)循環(huán)終止準(zhǔn)則）算法終止準(zhǔn)則（外循環(huán)終止準(zhǔn)則）算法程序核心內(nèi)容狀態(tài)產(chǎn)生函數(shù)原則

產(chǎn)生的候選解應(yīng)遍布全部解空間方法

在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生狀態(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)的產(chǎn)生原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；

(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；

(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法具體形式對(duì)算法影響不大一般采用min[1,exp(-?C/t)]狀態(tài)接受函數(shù)的產(chǎn)生初溫的設(shè)定收斂性分析通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)；初溫應(yīng)充分大；實(shí)驗(yàn)表明初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間；初溫的設(shè)定初溫產(chǎn)生方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。初溫產(chǎn)生方法溫度更新函數(shù)時(shí)齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。溫度更新函數(shù)內(nèi)循環(huán)終止準(zhǔn)則，即Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。常用的抽樣穩(wěn)定準(zhǔn)則包括：(1)檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；(2)連續(xù)若干步的目標(biāo)值變化較?。?3)按一定的步數(shù)抽樣。內(nèi)循環(huán)終止準(zhǔn)則，即Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定外循環(huán)終止準(zhǔn)則，即算法的終止準(zhǔn)則模擬退火算法從初始溫度開始，通過在每一溫度的迭代和溫度的下降，最后達(dá)到終止原則而停止。盡管有些原則有一定的理論指導(dǎo)，終止原則大多數(shù)是直觀的。下面分幾類討論。外循環(huán)終止準(zhǔn)則，即算法的終止準(zhǔn)則(1)零度法模擬退火算法的最終溫度為零，因而最為簡(jiǎn)單的原則是：給出一個(gè)較小的正數(shù)，當(dāng)溫度小于這個(gè)數(shù)時(shí)，算法停止，表示已經(jīng)達(dá)到最低溫度。模擬退火算法講解課件(2)循環(huán)總數(shù)控制法這一原則為：總的下降次數(shù)為一定值K，當(dāng)溫度迭代次數(shù)達(dá)到K值時(shí)，停止運(yùn)算。(3)基于不改進(jìn)規(guī)則的控制法在一個(gè)溫度和給定的迭代次數(shù)內(nèi)設(shè)有改進(jìn)當(dāng)前的局部最優(yōu)解，則停止運(yùn)算。模擬退火算法的一個(gè)基本思想是跳出局部最優(yōu)解，直觀的結(jié)論是在較高的溫度沒能跳出局部最小解，則在低的溫度跳出最優(yōu)解的可能也比較小，由此產(chǎn)生上面的停止原則。(2)循環(huán)總數(shù)控制法(4)接受概率控制法該方法與(3)相同的思想。給定一個(gè)指針P>0是一個(gè)比較小的數(shù)。除當(dāng)前局部最優(yōu)解以外，其它狀態(tài)的接受概率都小于P時(shí)，停止計(jì)算。實(shí)現(xiàn)(3)和(4)時(shí)，記錄當(dāng)前局部最優(yōu)解，給定一個(gè)固定的迭代次數(shù)，在規(guī)定的次數(shù)里沒有離開局部最優(yōu)解或每一次計(jì)算的接受概率都小于隨機(jī)數(shù)X，就在這個(gè)溫度停止迭代。(4)接受概率控制法模擬退火算法的優(yōu)點(diǎn)質(zhì)量高；初值魯棒性強(qiáng)；簡(jiǎn)單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn)由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過程較長。模擬退火算法的優(yōu)點(diǎn)TSP城市坐標(biāo)

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450TSP城市坐標(biāo)模擬退火算法講解課件模擬退火算法講解課件模擬退火算法講解課件模擬退火算法模擬退火算法算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極小；克服初值依賴性。算法的提出什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。什么是退火：物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。物理退火過程

加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可

熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：溫度越低，物體的能量狀態(tài)越低，到達(dá)足夠的低點(diǎn)時(shí)，液體開始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。緩慢降溫（退火，annealing）時(shí)，可達(dá)到最低能量狀態(tài)；但如果快速降溫（淬火，quenching），會(huì)導(dǎo)致不是最低能態(tài)的非晶形。

熱力學(xué)中的退火現(xiàn)象指物體逐漸降溫時(shí)發(fā)生的物理現(xiàn)象：模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性

從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布數(shù)學(xué)表述

模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率1停留在最優(yōu)解。在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有模擬退火算法基本思想：在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變Boltzman概率分布告訴我們：

（1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)的概率（2）溫度越高，不同能量狀態(tài)對(duì)應(yīng)的概率相差越?。粶囟茸銐蚋邥r(shí)，各狀態(tài)對(duì)應(yīng)概率基本相同。（3）隨著溫度的下降，能量最低狀態(tài)對(duì)應(yīng)概率越來越大；溫度趨于0時(shí)，其狀態(tài)趨于1Boltzman概率分布告訴我們：Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)固體在恒定溫度下達(dá)到熱平衡的過程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)若在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i

為當(dāng)前狀態(tài)。Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。p=exp[-(Ej-Ei)/kBT]相似性比較組合優(yōu)化問題金屬物體解離子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫溶解過程Metropolis抽樣過程控制參數(shù)的下降等溫過程冷卻過程目標(biāo)函數(shù)能量相似性比較組合優(yōu)化問題金屬物體解離子狀態(tài)最優(yōu)解能量最低的狀態(tài)基本步驟給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果?；静襟E算法程序核心內(nèi)容三個(gè)函數(shù)新狀態(tài)sj=Genete(s)ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;tk+1=update(tk)兩個(gè)準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則（內(nèi)循環(huán)終止準(zhǔn)則）算法終止準(zhǔn)則（外循環(huán)終止準(zhǔn)則）算法程序核心內(nèi)容狀態(tài)產(chǎn)生函數(shù)原則

產(chǎn)生的候選解應(yīng)遍布全部解空間方法

在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生狀態(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)的產(chǎn)生原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；

(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；

(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法具體形式對(duì)算法影響不大一般采用min[1,exp(-?C/t)]狀態(tài)接受函數(shù)的產(chǎn)生初溫的設(shè)定收斂性分析通過理論分析可以得到初溫的解析式，但解決實(shí)際問題時(shí)難以得到精確的參數(shù)；初溫應(yīng)充分大；實(shí)驗(yàn)表明初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間；初溫的設(shè)定初溫產(chǎn)生方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗(yàn)公式。初溫產(chǎn)生方法溫度更新函數(shù)時(shí)齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。溫度更新函數(shù)內(nèi)循環(huán)終止準(zhǔn)則，即Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。常用的抽樣穩(wěn)定準(zhǔn)則包括：(1)檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；(2)連續(xù)若干步的目標(biāo)值變化較?。?3)按一定的步數(shù)抽樣。內(nèi)循環(huán)終止準(zhǔn)則，即Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定外循環(huán)終止準(zhǔn)則，即算法的終止準(zhǔn)則模擬退火算法從初始溫度開始，通過在每一溫度的迭代和溫度的下降，最后達(dá)到終止原則而停止。盡管有些原則有一定的理論指導(dǎo)，終止原則大多數(shù)是直觀的。下面分幾類討論。外循環(huán)終止準(zhǔn)則，即算法的終止準(zhǔn)則(1)零度法模擬退火算法的最終溫度為零，因而最為簡(jiǎn)單的原則是：給出一個(gè)較小的正數(shù)，當(dāng)溫度小于這個(gè)數(shù)時(shí)，算法停止，表示已經(jīng)達(dá)到最低溫度。