國科大中科院算法講義 模擬退火

啟發(fā)式算法

二、模擬退火固體退火將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)（規(guī)整晶體）的熱力學(xué)過程。固體退火過程加溫過程：增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置，目的是消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程：退火過程中要讓溫度慢慢降低，在每一個(gè)溫度下要達(dá)到熱平衡狀態(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)。當(dāng)液體凝固為固體的晶態(tài)時(shí)退火過程完成。模擬退火算法SimulatedAnnealing由MetropolisN.

于1953年提出，Kirkpatrick1983年成功地應(yīng)用于組合優(yōu)化問題。模擬退火（SA）是基于MonteCarlo迭代求解策略的一種隨機(jī)優(yōu)化算法，其思想來源于復(fù)雜組合優(yōu)化問題與固體的退火過程之間的相似之處。模擬退火算法的基本思想SA開始于一個(gè)很高的初始溫度（隨機(jī)行走），伴隨溫度參數(shù)的不斷下降，在每一溫度下（算法的狀態(tài)轉(zhuǎn)移）慢慢達(dá)到熱平衡（爬山法），最終達(dá)到物理基態(tài)（全局最優(yōu)）。SA在系統(tǒng)向著能量減小的趨勢(shì)變化過程中，允許系統(tǒng)按一定概率（以溫度為參數(shù)）跳到能量較高的狀態(tài)，以避開局部最優(yōu)，最終穩(wěn)定在全局最優(yōu)。

退火過程和Bolzman方程

統(tǒng)計(jì)力學(xué)研究表明，在溫度T，分子停留在狀態(tài)i（能量為Ei）滿足波茲曼(Boltsmann)分布：Bolzman方程

退火過程和Bolzman方程溫度對(duì)的影響當(dāng)很大時(shí)， 各狀態(tài)的概率幾乎相等，SA開始做廣域搜索，隨著溫度的下降 差別擴(kuò)大。

退火過程和Bolzman方程當(dāng) 時(shí)，與的小差別帶來和的巨大差別例如：=90， =100，

退火過程和Bolzman方程當(dāng) =100時(shí)

退火過程和Bolzman方程當(dāng)=1時(shí)此時(shí)結(jié)論:

時(shí)，以概率1趨于最小能量狀態(tài)

退火過程和Bolzman方程SA的模擬要求初始溫度足夠高降溫過程足夠慢終止溫度足夠低

SA的算法構(gòu)造及步驟（1）問題的描述及要素 SA的算法構(gòu)造及步驟（2）Metropolis準(zhǔn)則(以概率接受新狀態(tài))在溫度Tk，當(dāng)前狀態(tài)i→新狀態(tài)j若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/T]大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)。SA的計(jì)算步驟初始化,任選初始解,,給定初始溫度，終止溫度，令迭代指標(biāo) 。

注：選擇時(shí)，要足夠高，使隨機(jī)產(chǎn)生一個(gè)鄰域解， 計(jì)算目標(biāo)值增量SA的算法構(gòu)造及步驟（3）若 轉(zhuǎn)步④(j比i好無條件轉(zhuǎn)移)；否則產(chǎn)生

(j比i好，有條件轉(zhuǎn)移)。

注： 高時(shí)，廣域搜索；低時(shí)，局域搜索若達(dá)到熱平衡(內(nèi)循環(huán)次數(shù)大于)轉(zhuǎn)步⑤，否則轉(zhuǎn)步②。

SA的算法構(gòu)造及步驟（4）

降低，若停止，否則轉(zhuǎn)步②。

注：降低的方法有以下兩種流程框圖見下頁 SA的算法構(gòu)造及步驟（5）18內(nèi)循環(huán)產(chǎn)生開始停止YNYN，降溫外循環(huán)設(shè)定產(chǎn)生計(jì)算YYNN組合優(yōu)化問題金屬物體退火解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過程Metropolis抽樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量組合優(yōu)化和固體退火的相似性問題的提出單機(jī)極小化總流水時(shí)間的排序問題四個(gè)工作： ，求的最優(yōu)順序。

簡單舉例（1）預(yù)備知識(shí)：按SPT準(zhǔn)則，最優(yōu)順序?yàn)?-1-4-2簡單舉例（2）用SA求解這個(gè)問題狀態(tài)表達(dá)：順序編碼鄰域定義：兩兩換位定義為鄰域移動(dòng)解：設(shè) 降溫過程定義為初始解：i=1-4-2-3簡單舉例（3）⑴

①②③注釋：①無條件轉(zhuǎn)移；②③為有條件轉(zhuǎn)移；在②③中，雖然目標(biāo)值變壞，但搜索范圍變大；是隨機(jī)產(chǎn)生的

簡單舉例（4）⑵①②③注釋：①有條件轉(zhuǎn)移；②為無條件轉(zhuǎn)移；在③中，停在4-3-1-2狀態(tài)，目標(biāo)值仍為109；簡單舉例（5）⑵①②③注釋：①②無條件轉(zhuǎn)移；在③中，停在3-1-4-2狀態(tài)，目標(biāo)值仍為92；

SA算法中一定要保存歷史最優(yōu)解。簡單舉例（6）初始溫度足夠高熱平衡時(shí)間足夠長終止溫度足夠低降溫過程足夠慢 以上條件實(shí)際中很難滿足，所以只能記錄歷史最優(yōu)解。SA終止在最優(yōu)解上的條件：

27編程最容易，理論最完善。下面基于Markov過程分析收斂性。

SA特點(diǎn)Markov過程的基本概念基本概念狀態(tài)： 處于系統(tǒng)中的一種特定狀態(tài)表達(dá)。狀態(tài)轉(zhuǎn)移概率： 從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的可能性。無后效應(yīng)： 到一個(gè)狀態(tài)后，決策只與本狀態(tài)有關(guān)，與以前的歷史狀態(tài)無關(guān)。SA的Markov鏈描述及收斂性分析（1）三個(gè)狀態(tài)轉(zhuǎn)移概率SA的Markov鏈描述及收斂性分析（2）1/31/31/41/41/21/2狀態(tài)轉(zhuǎn)移概率矩陣：1/31/41/4t時(shí)刻處在各狀態(tài)的概率向量是行向量，假設(shè)系統(tǒng)在t時(shí)達(dá)到穩(wěn)態(tài)，則對(duì)前面3狀態(tài)實(shí)例，解方程可得Π(t)=[21/57,20/57,16/57]

SA的Markov鏈描述及收斂性分析（3）SA的收斂性分析問題： 將狀態(tài)按目標(biāo)值進(jìn)行升序編號(hào)，即SA的Markov鏈描述及收斂性分析（4）狀態(tài)間的轉(zhuǎn)移概率設(shè) 為i選j為鄰域點(diǎn)時(shí)，i j的轉(zhuǎn)移概率SA的Markov鏈描述及收斂性分析（5）設(shè) 是系統(tǒng)處于狀態(tài)i時(shí)選擇j為鄰域移動(dòng)點(diǎn)的概率， 為狀態(tài)i的鄰域點(diǎn)的個(gè)數(shù)，則若j是i的鄰居，有，否則則狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率為SA的Markov鏈描述及收斂性分析（6）狀態(tài)轉(zhuǎn)移