第4章 模擬退火

第四章 模擬退火1第四章模擬退火一.導(dǎo)言二.模擬退火三.SA舉例四.SA的收斂性分析2模擬退火(SA)的產(chǎn)生原始算法是由Metropolis等(1953)提出，但未引起反響；1982年Kirkpatrick等將其應(yīng)用于組合優(yōu)化，才得到廣泛的應(yīng)用目的是為了克服優(yōu)化過程中陷入局優(yōu)和初值依賴等弊端基本思想是模擬熱力學(xué)中的退火過程一.導(dǎo)言3物理退火過程什么是退火退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。一.導(dǎo)言4物理退火過程什么是退火

加溫過程——增強(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)一.導(dǎo)言5物理退火過程什么是退火退火淬火一.導(dǎo)言高溫低溫緩慢下降高能狀態(tài)低能狀態(tài)高溫低溫快速下降高能狀態(tài)高能狀態(tài)6物理退火過程數(shù)學(xué)描述設(shè)熱力學(xué)系統(tǒng)S中有n個(gè)狀態(tài)（有限且離散的），其中狀態(tài)i的能量為Ei，在溫度Tk下，經(jīng)一段時(shí)間達(dá)到熱平衡，此時(shí)處在狀態(tài)i的概率為：

則有如下關(guān)系：Ei↓→Pi↑，Tk↓→Pi↓一.導(dǎo)言如何確定Ck?7物理退火過程數(shù)學(xué)描述通過求Ck，獲得Bolzman方程：一.導(dǎo)言8物理退火過程Bolzman方程同一溫度下，S處在能量小的狀態(tài)要比處在能量大的狀態(tài)概率大若存在E1<E2，則在同一溫度Tk下，有故P1(Tk)>P2(Tk)一.導(dǎo)言9物理退火過程Bolzman方程若i*表示S中最低能量的狀態(tài)，是關(guān)于溫度Tk單調(diào)遞減對(duì)Pi(Tk)求對(duì)溫度的導(dǎo)數(shù)，則故一.導(dǎo)言10物理退火過程Bolzman方程當(dāng)時(shí)，同理，當(dāng)時(shí)，一.導(dǎo)言11物理退火過程溫度Tk對(duì)的影響當(dāng)Tk很大時(shí)，當(dāng)時(shí)，

一.導(dǎo)言各狀態(tài)的概率幾乎相等與的小差別帶來和的巨大差別12物理退火過程溫度Tk對(duì)的影響例：當(dāng)時(shí)

一.導(dǎo)言13物理退火過程溫度Tk對(duì)的影響例：當(dāng)時(shí)此時(shí)

一.導(dǎo)言溫度趨于0時(shí)，以概率1趨于最小能量狀態(tài)14能量越低越穩(wěn)定?。?！

——真理15組合優(yōu)化與退火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)/

Tk

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

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

為當(dāng)前狀態(tài)一.導(dǎo)言在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)16組合優(yōu)化與物理退火一.導(dǎo)言組合優(yōu)化問題物理退火解狀態(tài)目標(biāo)函數(shù)能量函數(shù)最優(yōu)解最低能量狀態(tài)設(shè)定初始高溫加溫過程基于Metroplolis準(zhǔn)則的搜索等溫過程溫度參數(shù)的下降冷卻過程17構(gòu)成要素解的表達(dá)與鄰域移動(dòng)方式同TS鄰域解的產(chǎn)生在當(dāng)前解的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生選擇策略一般采用min[1,exp(-?f/t)]二.模擬退火18構(gòu)成要素初始溫度均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫利用經(jīng)驗(yàn)公式二.模擬退火實(shí)驗(yàn)表明：初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間19構(gòu)成要素降溫函數(shù)

，其中

二.模擬退火優(yōu)點(diǎn)：簡單易行，很美麗的方法20構(gòu)成要素?zé)崞胶鈼l件Metropolis抽樣穩(wěn)定準(zhǔn)則檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定連續(xù)若干步的目標(biāo)值變化較小設(shè)置內(nèi)循環(huán)迭代次數(shù)停止準(zhǔn)則設(shè)置終止溫度的閾值設(shè)置外循環(huán)迭代次數(shù)算法搜索到的最優(yōu)值連續(xù)若干步保持不變二.模擬退火21算法步驟Step1選一個(gè)初始點(diǎn)i()，給定初始溫度，終止溫度，令迭代指標(biāo)，；Step2隨機(jī)產(chǎn)生一個(gè)鄰域解，計(jì)算目標(biāo)值增量；二.模擬退火注：選擇時(shí)，要足夠高，使22算法步驟Step3若，令i=j；

(j比i好，無條件轉(zhuǎn)移)否則產(chǎn)生，若，則令i=j；(i比j好，有條件轉(zhuǎn)移)Step4若達(dá)到熱平衡（內(nèi)循環(huán)停止準(zhǔn)則），轉(zhuǎn)Step5；否則，轉(zhuǎn)Step2；二.模擬退火注：高時(shí)，廣域搜索；低時(shí)，局域搜索23算法步驟Step5若k=k+1，更新，若（外循環(huán)停止準(zhǔn)則），則停止；否則，轉(zhuǎn)Step2。二.模擬退火24問題提出單機(jī)極小化總流水時(shí)間的排序問題四個(gè)工作：求使的最優(yōu)順序三.SA舉例25問題提出預(yù)備知識(shí)：按SPT準(zhǔn)則，最優(yōu)順序?yàn)?-1-4-2三.SA舉例26算法設(shè)計(jì)編碼方式：順序編碼初始解的產(chǎn)生：隨機(jī)產(chǎn)生，如1-4-2-3鄰域移動(dòng)方式：2-OPT，即兩兩交換初始溫度終止溫度降溫函數(shù)內(nèi)循環(huán)次數(shù)三.SA舉例27初始解：i=1-4-2-3(1)

① j=1-3-2-4 ② j=4-3-2-1③ j=4-2-3-1注釋：①無條件轉(zhuǎn)移；②③為有條件轉(zhuǎn)移；在②③中，雖然目標(biāo)值變壞，但搜索范圍變大；

是隨機(jī)產(chǎn)生的

三.SA舉例28(2)① j=4-2-1-3 ② j=4-3-1-2③ j=4-2-3-1注釋：①有條件轉(zhuǎn)移；②為無條件轉(zhuǎn)移；在③中，停在4-3-1-2狀態(tài)，目標(biāo)值仍為109

三.SA舉例29(3)①②③注釋：①②無條件轉(zhuǎn)移；在③中，停在3-1-4-2狀態(tài)，目標(biāo)值仍為92；

三.SA舉例SA沒有歷史最優(yōu)，不會(huì)終止在最優(yōu)解，故算法一定要保持歷史最優(yōu)30Markov過程的基本概念例：青蛙在3塊石頭上隨機(jī)跳動(dòng)，行動(dòng)的特點(diǎn)是無記憶性四.SA的收斂性分析1/31/41/31/31/41/21/41/41/231Markov過程的基本概念狀態(tài)：處于系統(tǒng)中的一種特定狀況的表達(dá)狀態(tài)轉(zhuǎn)移概率：從狀態(tài)

i轉(zhuǎn)移到狀態(tài)j的可能性無后效性：到一個(gè)狀態(tài)后，決策只與本狀態(tài)有關(guān)，與以前的歷史狀態(tài)無關(guān)四.SA的收斂性分析32Markov過程的基本概念以青蛙跳動(dòng)為例說明狀態(tài)轉(zhuǎn)移概率用石頭唯一的表達(dá)青蛙所處的狀態(tài)，假設(shè)青蛙跳動(dòng)具有無后效應(yīng)的特點(diǎn)。四.SA的收斂性分析青