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

智能優(yōu)化模擬退火1第1頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月第五章 模擬退火2第2頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月第五章模擬退火一.導(dǎo)言二.退火過程和Bolzman方程三.SA的算法構(gòu)造及步驟四.計(jì)算舉例五.SA的收斂性分析六.SA的應(yīng)用舉例3第3頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月模擬退火的產(chǎn)生(SA)1953年Metropolis提出原始的SA算法，未引 起反響1982年Kirkpatrick提出現(xiàn)代的SA算法，得到廣泛的應(yīng)用

一.導(dǎo)言（1）4第4頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月基本思想模擬熱力學(xué)當(dāng)中的退火過程退火過程： 物體：高溫 低溫 高能狀態(tài) 低能狀態(tài)一.導(dǎo)言（2）緩慢下降5第5頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月淬火：快速冷卻，使金屬處于高能狀態(tài)，較硬易斷退火：緩慢冷卻，使金屬處于低能狀態(tài)，較為柔韌

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

時(shí)，以概率1趨于最小能量狀態(tài)二.退火過程和Bolzman方程（7）14第14頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月SA的模擬要求初始溫度足夠高降溫過程足夠慢終止溫度足夠低

三.SA的算法構(gòu)造及步驟（1）15第15頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月問題的描述及要素 三.SA的算法構(gòu)造及步驟（2）16第16頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月SA的計(jì)算步驟初始化,任選初始解,,給定初始溫度，終止溫度，令迭代指標(biāo) 。

注：選擇時(shí)，要足夠高，使隨機(jī)產(chǎn)生一個(gè)鄰域解， 計(jì)算目標(biāo)值增量三.SA的算法構(gòu)造及步驟（3）17第17頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月若 轉(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）18第18頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月降低，若停止，否則轉(zhuǎn)步②。

注：降低的方法有以下兩種流程框圖見下頁(yè) 三.SA的算法構(gòu)造及步驟（5）19第19頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月內(nèi)循環(huán)產(chǎn)生開始停止YNYN，降溫外循環(huán)設(shè)定產(chǎn)生計(jì)算YYNN20第20頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月問題的提出單機(jī)極小化總流水時(shí)間的排序問題四個(gè)工作： ，求的最優(yōu)順序。

四.計(jì)算舉例（1）21第21頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月預(yù)備知識(shí)：按SPT準(zhǔn)則，最優(yōu)順序?yàn)?-1-4-2四.計(jì)算舉例（2）22第22頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月用SA求解這個(gè)問題狀態(tài)表達(dá)：順序編碼鄰域定義：兩兩換位定義為鄰域移動(dòng)解：設(shè) 降溫過程定義為初始解：i=1-4-2-3四.計(jì)算舉例（3）23第23頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月⑴

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

四.計(jì)算舉例（4）24第24頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月⑵①②③注釋：①有條件轉(zhuǎn)移；②為無條件轉(zhuǎn)移；在③中，停在4-3-1-2狀態(tài)，目標(biāo)值仍為109；四.計(jì)算舉例（5）25第25頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月⑵①②③注釋：①②無條件轉(zhuǎn)移；在③中，停在3-1-4-2狀態(tài)，目標(biāo)值仍為92；

SA沒有歷史最優(yōu)，不會(huì)終止在最優(yōu)解，故算法一定要保持歷史最優(yōu)。四.計(jì)算舉例（6）26第26頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月SA終止在最優(yōu)解上的條件：初始溫度足夠高熱平衡時(shí)間足夠長(zhǎng)終止溫度足夠低降溫過程足夠慢 以上條件實(shí)際中很難滿足，所以只能記錄歷史最優(yōu)解。四.計(jì)算舉例（7）27第27頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月SA特點(diǎn)：編程最容易，理論最完善。下面基于Markov過程分析收斂性。

四.計(jì)算舉例（8）28第28頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月Markov過程的基本概念舉例說明：盲人一維游走、醉漢或青蛙在3塊石頭上隨機(jī)跳動(dòng)，這3中狀況可用來說明這個(gè)問題，他們行動(dòng)的共同特點(diǎn)是無記憶性。五.SA的收斂性分析（1）29第29頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月基本概念狀態(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的收斂性分析（2）30第30頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月以青蛙跳動(dòng)為例說明狀態(tài)轉(zhuǎn)移概率用石頭唯一的表達(dá)青蛙所處的狀態(tài)，假設(shè)青蛙跳動(dòng)具有無后效應(yīng)的特點(diǎn)。五.SA的收斂性分析（3）1/31/31/41/41/21/2青蛙跳動(dòng)圖示狀態(tài)轉(zhuǎn)移概率矩陣：1/31/41/431第31頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月t時(shí)刻處在各狀態(tài)的概率向量是行向量，假設(shè)系統(tǒng)在t+1時(shí)達(dá)到穩(wěn)態(tài)，則五.SA的收斂性分析（4）32第32頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月解方程組： 可得結(jié)果：可見青蛙是跳到第三塊石頭上的機(jī)會(huì)多一些五.SA的收斂性分析（5）33第33頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月SA的收斂性分析問題： 將狀態(tài)按目標(biāo)值進(jìn)行升序編號(hào)，即五.SA的收斂性分析（6）34第34頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月狀態(tài)間的轉(zhuǎn)移概率設(shè) 為i選j為鄰域點(diǎn)時(shí)，i j的轉(zhuǎn)移概率五.SA的收斂性分析（7）35第35頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月設(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第36頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月當(dāng)Tk很大時(shí)，則狀態(tài)轉(zhuǎn)移矩陣為：分兩種情況討論：五.SA的收斂性分析（9）37第37頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月當(dāng)五.SA的收斂性分析（10）38第38頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月當(dāng)狀態(tài)1是“捕捉的”（任何狀態(tài)到1狀態(tài)后都無法轉(zhuǎn)出）即青蛙跳到石頭1上無法跳出。五.SA的收斂性分析（11）39第39頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月推理證明：證畢即SA將以概率1停在狀態(tài)（石頭）1上。五.SA的收斂性分析（12）40第40頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月定理：當(dāng)P對(duì)稱時(shí)，當(dāng)達(dá)到熱平衡時(shí)，對(duì)所有 有：定理證明見下頁(yè)。五.SA的收斂性分析（13）41第41頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月定理證明：當(dāng)達(dá)到熱平衡時(shí)有五.SA的收斂性分析（14）42第42頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月問題：成組技術(shù)中加工中心的組成問題設(shè)有m臺(tái)機(jī)器，要組成若干個(gè)加工中心，每個(gè)加工中心可有最多q臺(tái)、最少p臺(tái)機(jī)器，有n種加工工作要在這些機(jī)器上加工。如何組織加工中心，可使總的各中心的機(jī)器相似性最好。六.SA的應(yīng)用舉例（1）43第43頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月六.SA的應(yīng)用舉例（2）44第44頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月六.SA的應(yīng)用舉例（3）45第45頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月六.SA的應(yīng)用舉例（4）46第46頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月所有相似的機(jī)器放在同一個(gè)中心，極大化成組相似性指定唯一性，一個(gè)機(jī)器只能放一個(gè)中心每一個(gè)中心的機(jī)器數(shù)小于q臺(tái)每一個(gè)中心的機(jī)器數(shù)至少有p臺(tái)六.SA的應(yīng)用舉例（5）47第47頁(yè)，課件共51頁(yè)，創(chuàng)作于2023年2月用SA求解六.SA的應(yīng)用舉例（6）48第48頁(yè)，課件共