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

智能優(yōu)化模擬退火1第1頁，共51頁，2023年，2月20日，星期五第五章 模擬退火2第2頁，共51頁，2023年，2月20日，星期五第五章模擬退火一.導言二.退火過程和Bolzman方程三.SA的算法構造及步驟四.計算舉例五.SA的收斂性分析六.SA的應用舉例3第3頁，共51頁，2023年，2月20日，星期五模擬退火的產生(SA)1953年Metropolis提出原始的SA算法，未引 起反響1982年Kirkpatrick提出現代的SA算法，得到廣泛的應用

一.導言（1）4第4頁，共51頁，2023年，2月20日，星期五基本思想模擬熱力學當中的退火過程退火過程： 物體：高溫 低溫 高能狀態(tài) 低能狀態(tài)一.導言（2）緩慢下降5第5頁，共51頁，2023年，2月20日，星期五淬火：快速冷卻，使金屬處于高能狀態(tài)，較硬易斷退火：緩慢冷卻，使金屬處于低能狀態(tài)，較為柔韌

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

時，以概率1趨于最小能量狀態(tài)二.退火過程和Bolzman方程（7）14第14頁，共51頁，2023年，2月20日，星期五SA的模擬要求初始溫度足夠高降溫過程足夠慢終止溫度足夠低

三.SA的算法構造及步驟（1）15第15頁，共51頁，2023年，2月20日，星期五問題的描述及要素 三.SA的算法構造及步驟（2）16第16頁，共51頁，2023年，2月20日，星期五SA的計算步驟初始化,任選初始解,,給定初始溫度，終止溫度，令迭代指標 。

注：選擇時，要足夠高，使隨機產生一個鄰域解， 計算目標值增量三.SA的算法構造及步驟（3）17第17頁，共51頁，2023年，2月20日，星期五若 轉步④(j比i好無條件轉移)；否則產生

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

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

三.SA的算法構造及步驟（4）18第18頁，共51頁，2023年，2月20日，星期五降低，若停止，否則轉步②。

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

四.計算舉例（1）21第21頁，共51頁，2023年，2月20日，星期五預備知識：按SPT準則，最優(yōu)順序為3-1-4-2四.計算舉例（2）22第22頁，共51頁，2023年，2月20日，星期五用SA求解這個問題狀態(tài)表達：順序編碼鄰域定義：兩兩換位定義為鄰域移動解：設 降溫過程定義為初始解：i=1-4-2-3四.計算舉例（3）23第23頁，共51頁，2023年，2月20日，星期五⑴

①②③注釋：①無條件轉移；②③為有條件轉移；在②③中，雖然目標值變壞，但搜索范圍變大；是隨機產生的

四.計算舉例（4）24第24頁，共51頁，2023年，2月20日，星期五⑵①②③注釋：①有條件轉移；②為無條件轉移；在③中，停在4-3-1-2狀態(tài)，目標值仍為109；四.計算舉例（5）25第25頁，共51頁，2023年，2月20日，星期五⑵①②③注釋：①②無條件轉移；在③中，停在3-1-4-2狀態(tài)，目標值仍為92；

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

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