智能優(yōu)化-模擬退火

1、智能優(yōu)化方法AI-Based Optimization Methods1第五章模擬退火2第五章 模擬退火一.導(dǎo)言二.退火過(guò)程和Bolzman方程三.SA的算法構(gòu)造及步驟四.計(jì)算舉例五.SA的收斂性分析六.SA的應(yīng)用舉例3模擬退火的產(chǎn)生(SA) 1953年 Metropolis提出原始的SA算法，未引起反響1982年 Kirkpatrick提出現(xiàn)代的SA算法，得到廣泛的應(yīng)用一.導(dǎo)言（1）4基本思想模擬熱力學(xué)當(dāng)中的退火過(guò)程退火過(guò)程：物體： 高溫低溫 高能狀態(tài)低能狀態(tài)一.導(dǎo)言（2）緩慢下降5淬火：快速冷卻，使金屬處于高能狀態(tài)，較硬易斷退火：緩慢冷卻，使金屬處于低能狀態(tài)，較為柔韌一.導(dǎo)言（3）6模擬退

2、火在SA中的應(yīng)用在SA中將目標(biāo)函數(shù)作為能量函數(shù)模擬：初始高溫 溫度緩慢下降 終止在低溫這時(shí)能量函數(shù)達(dá)到極小，目標(biāo)函數(shù)最小一.導(dǎo)言（4）7熱力學(xué)中的退火過(guò)程變溫物體緩慢降溫從而達(dá)到分子之間能量最低的狀態(tài)二.退火過(guò)程和Bolzman方程（1）8二.退火過(guò)程和Bolzman方程（2）9Bolzman方程二.退火過(guò)程和Bolzman方程（3）10溫度 對(duì) 的影響當(dāng) 很大時(shí)，各狀態(tài)的概率幾乎相等SA開(kāi)始做廣域搜索，隨著溫度的下降 差別擴(kuò)大二.退火過(guò)程和Bolzman方程（4）11當(dāng) 時(shí)， 與 的小差別帶來(lái) 和 的巨大差別例如： =90， =100，二.退火過(guò)程和Bolzman方程（5）12當(dāng)=100時(shí)二

3、.退火過(guò)程和Bolzman方程（6）13當(dāng) =1時(shí)此時(shí)結(jié)論: 時(shí)，以概率1趨于最小能量狀態(tài)二.退火過(guò)程和Bolzman方程（7）14SA的模擬要求初始溫度足夠高降溫過(guò)程足夠慢終止溫度足夠低三.SA的算法構(gòu)造及步驟（1）15問(wèn)題的描述及要素三.SA的算法構(gòu)造及步驟（2）16SA的計(jì)算步驟初始化,任選初始解, ,給定初始溫度 ，終止溫度 ，令迭代指標(biāo) 。注：選擇 時(shí)，要足夠高，使隨機(jī)產(chǎn)生一個(gè)鄰域解， 計(jì)算目標(biāo)值增量三.SA的算法構(gòu)造及步驟（3）17若 轉(zhuǎn)步 (j比i好無(wú)條件轉(zhuǎn)移) ；否則產(chǎn)生 (j比i好，有條件轉(zhuǎn)移)。 注：高時(shí)，廣域搜索； 低時(shí)，局域搜索若達(dá)到熱平衡(內(nèi)循環(huán)次數(shù)大于 )轉(zhuǎn)步，否則

4、轉(zhuǎn)步。三.SA的算法構(gòu)造及步驟（4）18 降低 ，若 停止，否則轉(zhuǎn)步。注：降低 的方法有以下兩種流程框圖見(jiàn)下頁(yè)三.SA的算法構(gòu)造及步驟（5）19內(nèi)循環(huán)產(chǎn)生開(kāi)始停止YNYN，降溫外循環(huán)設(shè)定產(chǎn)生 計(jì)算YYNN20問(wèn)題的提出單機(jī)極小化總流水時(shí)間的排序問(wèn)題四個(gè)工作： ，求 的最優(yōu)順序。四.計(jì)算舉例 （1）21預(yù)備知識(shí)：按SPT準(zhǔn)則，最優(yōu)順序?yàn)?-1-4-2四.計(jì)算舉例 （2）22用SA求解這個(gè)問(wèn)題狀態(tài)表達(dá)：順序編碼鄰域定義：兩兩換位定義為鄰域移動(dòng)解：設(shè)降溫過(guò)程定義為初始解：i=1-4-2-3四.計(jì)算舉例 （3）23 注釋?zhuān)簾o(wú)條件轉(zhuǎn)移；為有條件轉(zhuǎn)移；在中，雖然目標(biāo)值變壞，但搜索范圍變大； 是隨機(jī)產(chǎn)生的

5、四.計(jì)算舉例 （4）24注釋?zhuān)河袟l件轉(zhuǎn)移；為無(wú)條件轉(zhuǎn)移；在中，停在4-3-1-2狀態(tài)，目標(biāo)值仍為109；四.計(jì)算舉例 （5）25注釋?zhuān)?無(wú)條件轉(zhuǎn)移；在中，停在3-1-4-2狀態(tài)，目標(biāo)值仍為92；SA沒(méi)有歷史最優(yōu)，不會(huì)終止在最優(yōu)解，故算法一定要保持歷史最優(yōu)。四.計(jì)算舉例 （6）26SA終止在最優(yōu)解上的條件：初始溫度足夠高熱平衡時(shí)間足夠長(zhǎng)終止溫度足夠低降溫過(guò)程足夠慢以上條件實(shí)際中很難滿(mǎn)足，所以只能記錄歷史最優(yōu)解。四.計(jì)算舉例 （7）27SA特點(diǎn)：編程最容易，理論最完善。下面基于Markov過(guò)程分析收斂性。四.計(jì)算舉例 （8）28Markov過(guò)程的基本概念舉例說(shuō)明：盲人一維游走、醉漢或青蛙在3塊石頭

6、上隨機(jī)跳動(dòng)，這3中狀況可用來(lái)說(shuō)明這個(gè)問(wèn)題，他們行動(dòng)的共同特點(diǎn)是無(wú)記憶性。五.SA的收斂性分析 （1）29基本概念狀態(tài)：處于系統(tǒng)中的一種特定狀態(tài)表達(dá)。狀態(tài)轉(zhuǎn)移概率：從狀態(tài) i 轉(zhuǎn)移到狀態(tài) j 的可能性。無(wú)后效應(yīng)：到一個(gè)狀態(tài)后，決策只與本狀態(tài)有關(guān)，與以前的歷史狀態(tài)無(wú)關(guān)。五.SA的收斂性分析 （2）30以青蛙跳動(dòng)為例說(shuō)明狀態(tài)轉(zhuǎn)移概率用石頭唯一的表達(dá)青蛙所處的狀態(tài)，假設(shè)青蛙跳動(dòng)具有無(wú)后效應(yīng)的特點(diǎn)。五.SA的收斂性分析 （3）1/31/31/41/41/21/2青蛙跳動(dòng)圖示狀態(tài)轉(zhuǎn)移概率矩陣：1/31/41/431t時(shí)刻處在各狀態(tài)的概率向量是行向量，假設(shè)系統(tǒng)在t+1時(shí)達(dá)到穩(wěn)態(tài)，則五.SA的收斂性分析 （4

7、）32解方程組：可得結(jié)果：可見(jiàn)青蛙是跳到第三塊石頭上的機(jī)會(huì)多一些五.SA的收斂性分析 （5）33SA的收斂性分析問(wèn)題： 將狀態(tài)按目標(biāo)值進(jìn)行升序編號(hào)，即五.SA的收斂性分析 （6）34狀態(tài)間的轉(zhuǎn)移概率設(shè) 為 i 選 j 為鄰域點(diǎn)時(shí)，i j的轉(zhuǎn)移概率五.SA的收斂性分析 （7）35設(shè)是系統(tǒng)處于狀態(tài) i 時(shí)選擇 j 為鄰域移動(dòng)點(diǎn)的概率， 為狀態(tài) i 的鄰域點(diǎn)的個(gè)數(shù)，則則狀態(tài) i 到狀態(tài) j 的轉(zhuǎn)移概率為五.SA的收斂性分析 （8）36當(dāng)Tk很大時(shí)，則狀態(tài)轉(zhuǎn)移矩陣為：分兩種情況討論：五.SA的收斂性分析 （9）37當(dāng)五.SA的收斂性分析 （10）38當(dāng)狀態(tài)1是 “捕捉的”（任何狀態(tài)到1狀態(tài)后都無(wú)法轉(zhuǎn)出

8、）即青蛙跳到石頭1上無(wú)法跳出。五.SA的收斂性分析 （11）39推理證明： 證畢即SA將以概率1停在狀態(tài)（石頭）1上。五.SA的收斂性分析 （12）40定理：當(dāng)P對(duì)稱(chēng)時(shí)，當(dāng)達(dá)到熱平衡時(shí)，對(duì)所有有：定理證明見(jiàn)下頁(yè)。五.SA的收斂性分析 （13）41定理證明：當(dāng)達(dá)到熱平衡時(shí)有五.SA的收斂性分析 （14）42問(wèn)題：成組技術(shù)中加工中心的組成問(wèn)題設(shè)有m臺(tái)機(jī)器，要組成若干個(gè)加工中心，每個(gè)加工中心可有最多q臺(tái)、最少p臺(tái)機(jī)器，有n種加工工作要在這些機(jī)器上加工。如何組織加工中心，可使總的各中心的機(jī)器相似性最好。六.SA的應(yīng)用舉例（1）43六.SA的應(yīng)用舉例（2）44六.SA的應(yīng)用舉例（3）45六.SA的應(yīng)用舉例（4）46所有相似的機(jī)器放在同一個(gè)中心，極大化成組相似性指定唯一性，一個(gè)機(jī)器只能放一個(gè)中心每一個(gè)中心的機(jī)器數(shù)小于q臺(tái)每一個(gè)中心的機(jī)器數(shù)至少有p臺(tái)六.SA的應(yīng)用舉例（5）47用SA求解