1、4.模擬退火算法,4.1 模擬退火算法概述,模擬退火算法：基本思想是把某類優(yōu)化問題的求解過程與統(tǒng)計熱力學中的熱平衡問題進行對比，試圖通過模擬高溫物體退火過程的方法，來找到優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解。,4.1 模擬退火算法概述,一個物體（例如金屬）的退火過程大體上是這樣的：首先對該物體加熱（熔化），那么物體內的原子就可高速自由運行，處于較高的能量狀態(tài)。但是作為一個實際的物理系統(tǒng)，原子的運行總是最低的能態(tài)。一開始溫度較高時，高溫使系統(tǒng)具有較高的內能，而隨著溫度的下降，原子越來越趨向于低能態(tài)，最后整個物體形成最低能量的基態(tài)。,4.1 模擬退火算法概述,模擬退火算法（ Simulated An

2、nealing；SA） 最早的想法是由N.Metropolis 等人于1953 年所提出，在當時并沒有受到重視。 直到1983 年由Kirkpatrick et al. 提出蒙特卡羅模擬（MonteCarlo Simulated）概念的隨機搜尋技巧，利用此方法來求解的組合優(yōu)化問題時，才使此算法受到重視。,4.1 模擬退火算法概述,SA的觀念主要來自于固體加熱至一定的溫度后，固體間的分子結構會被打散瓦解變?yōu)橐簯B(tài)結構， 接著再對其降溫過程加以控制，當完全冷卻能使其分子在液態(tài)結構轉變?yōu)楣腆w結構時，重新排列成我們所預期的穩(wěn)定狀態(tài),4.1 模擬退火算法概述,當目前狀況是落于區(qū)域的最佳解時，模擬退火法會藉

3、由重新加熱的動作，透過隨機的過程，以幾率性質來接受一個暫劣解使其演算法能跳脫目前的區(qū)域最佳解，而有機會能達到另一個最佳解,4.1 模擬退火算法概述,接受法則（Accepting Rule） 并用退火程序（Annealing Schedule）的參數演算法的進行 而Metroplis 接受法則的概念則在于能使求解時跳脫陷入區(qū)域最佳解 而模擬退火法能否成功應用在于退火程序的合理選擇,4.1 模擬退火算法概述,若令i 代表在時間k 的現有解，其成本為C(i) 下一個搜尋到的解，其成本為C(j) D E = C(j) - C(i)為兩個解之間的成本差 當j 的成本大于i 時，SA 會根據一幾率決定是否

4、要接受j來取代i 成為時間k+1 的新解,4.1 模擬退火算法概述,因此當搜尋到的新解比現有解之成本大時，會有一個幾率值來決定是否接受交換。 SA 基本上是以Metrolopis 接受法則為基楚，再配合退火程序，藉由溫度逐漸的降低來調整是否接受成本較差新解的幾率，當溫度越低時，幾率值也跟著降低,4.2 模擬退火算法流程,四個基本要素 系統(tǒng)狀態(tài)（Configuration）：即在某一個溫度下，系統(tǒng)產生的初始解，并當作目前的現行解 搜尋法則（Search rule）：在退火的過程中，由目前系統(tǒng)狀態(tài)經由隨機擾動而產生變化跳至另一種狀態(tài) 一般而言，SA 較常用的有梯度搜尋法（ Gradient Typ

5、e） 和迭代改善法（ IterativeImprovement,4.2 模擬退火算法流程,成本函數（Cost Function）：用來衡量某一系統(tǒng)狀態(tài)下之能量函數 退火程序（Annealing Process）：退火程序中包含的參數有初始溫度、降溫機制、冷卻率和終止溫度。在退火的過程中，在溫度高的時候，雖然是較差的目標值，但有可能被接受當成目前的目標值，但隨著溫度慢慢的降低，接受較差目標值的概率逐漸降低。,4.2 模擬退火算法流程,4.2 模擬退火算法流程,參數設定 初始溫度 為了防止落入區(qū)域極小的陷阱，在模擬退火法中初始溫度的設定必須使得大部份的轉移均可被接受 初始溫度的設定可以是一個定值，

6、 如Kirkpatrick等學者 ( 1983 ) 將初始溫度定為10 Heragu 以及 Alfa ( 1992 )將初始溫度定為999 初始溫度亦可由所設定接受概率的門檻值 P 0來反推求得，如Kouvelis 以及 Chiang( 1992 ) 將初始溫度定為,4.2 模擬退火算法流程,終止條件 終止條件最簡單的設定方式是指定一個固定的終止溫度，一般是一個接近於零較小的數，或是限制降溫次數不超過預定值 其它方式則為檢查所求得的解是否有所改善，如在1992 年Kouvelis 與 Chiang設定若經過數次降溫後所得的解仍未改善或移轉接受比率低於一個定值，則將終止模擬退火法的運算。,4.2

7、 模擬退火算法流程,降溫時機 降溫時機是指在同一溫度下所應反復進行Metropolis 演算的次數 最直接的方式是設定一個固定長度，但此長度與問題規(guī)模有關，如在1992 年Kouvelis 與Chiang 將其設定為鄰近解個數之比率。 此外亦可設定降溫時機為移轉接受次數已達一定值，如Heragu 以及 Alfa（1992）所使用的方式便是 但此一方式當溫度降至很低時，移轉接受之機率將會很小，進而導致馬可夫鏈過長，因此必須同時限定馬可夫鏈的長度，以免造成求解時間過長,4.2 模擬退火算法流程,溫度控制參數 溫度控制參數是指在演算過程中，若達到降溫時機時，由目前溫度減少到次一溫度的下降比率 若溫度

8、控制參數愈小，則溫度下降的差距愈大，那麼會造成在次一溫度達成均衡所需的馬可夫鏈長度愈長，使得求解時間增加。 因此，為了避免在新溫度下的馬可夫鏈長度過長，溫度控制參數不應過小，Kirkpatrick 等學者（1983）將其設定為0.9，而一般則設定在0.5至0.9 之間。,4.2 模擬退火算法應用,0-1背包問題 一個旅行者有一個最多能裝M公斤的背包，現在有N件物品， 它們的重量分別是W1，W2，.,Wn, 它們的價值分別為P1,P2,.,Pn.若每種物品只有一件。 求旅行者能獲得的最大總價值。,4.2 模擬退火算法應用,例：已知背包的裝載量為m=10,現在有n=5個物品，它們的重量和價值分別是

9、 (2,3,5,1,4)和(2,5,8,3,6)。試使用模擬退火算法求解該背包問題。,4.2 模擬退火算法應用,問題的一個可行解用0和1的序列表示，例如i=(10101)表示選擇第1、第3和第5個物品，而不選擇第2和第4個物品。 第一步：初始化，假設初始解為i=(11001)，初始溫度為T=10，計算 f(i)=2+5+6=13,4.2 模擬退火算法應用,第二步：在T溫度下局部搜索，直到“平衡”。 降溫時機用在同一溫度下所應反復進行Metropolis 演算的次數，假設次數為3。 搜尋法則：隨機改變某一位的0,1值或交換某兩位的0,1值。,4.2 模擬退火算法應用,假設產生的新解j=(11100)，f(j)=2+5+8=1513，所以接受新解。 假設產生的新解j=(11010)， f(j)=2+5+3=1013，計算接受概率 P(T)=exp(10-13)/10)0.741， 產生一個隨機數random(0,1)