演算法原理 – 模拟退火法(sa)

演算法原理演算法原理 模擬退火法模擬退火法(SA)(SA) 模擬退火法(Simulated Annealing)是貪婪演算法的一種，但其大大改善了貪婪演算 法容易陷入區域最佳解的狀況，因為模擬退火法在貪婪演算法的基礎上，加入了治金 中退火的概念。 在治金的過程中，會先將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積， 並且減少晶格中的缺陷。自然界中的原子原本就會自行停留在局部最小能量的位置， 加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動，在降溫的過程中， 原子們會趨向低能量、高亂度。退火模擬法即是將治金中，求最小能態之自冷過程的 概念抽象化，用來一非線性函數的全域最佳解。 貪婪演算法之所以容易陷於區域最佳解，就是因為其無法接受找到的值變差的情 形，但在區域最佳解與全域最佳解中，經常解會先變差，如下圖 圖 1 貪婪演算法易陷於區域最佳解 而模擬退火法則是使用了波茲曼分佈一非線性函數來決定現是否接受目前變 壞的情形，以防陷入區域最佳解。 模擬退火法的執行模擬退火法的執行 以下為模擬退火法大概的流程： 輸入一個目標繞射圖形後，產生一個與目標繞射圖形相同大小的矩陣，並計算其能量 (評價函數)。接著，擾動一個或多個像素(pixel)，並計算擾動後的能量，若能量的變 化為負，則接受此變化；若能量的變化為正，則利用波茲曼分佈計算此時接受此變化 的機率，再隨機產生一個隨機值，若隨機值比接受此變化的機率高，則接受此變化， 反之，則不接受。重複上述步驟，待達到我們設定的穩態條件，則依我們設定的降溫 方式降溫，直至冰點。 最適合用來描述模擬退火法的數學模型就是馬克夫鏈(Markov chain)，所謂的馬克 夫鏈是描述一連串連續嘗試的過程，且當前的狀態只與上一個狀態相關，與上一個狀 態之前狀態無關1。 溫度的設定溫度的設定 初溫的設定的問題，可大可小。我們可以隨意設一個溫度為初溫，但如此一 來，我們不容易控制模擬退火法，我們不能確定在初溫時，程式接受結構變壞的機率。 若我們初溫設太低，雖然程式在一開始較容易接受結構變差的情形，但其總接受的次 數亦將較少；若我們初溫設太高，則程式在一開始就不易接受結構變壞的情況，換句 話說，前面都做白工，浪費時間。 最常用的方法是統計的方式，在程式開始前先設定在程式執行之初，我們希望程 式接愛變壞的機率 一般都設定 85% 接著寫一個模擬退火法，計算平均的能量變化 (評價函數的變化)，並取能量變化 (評價函數的變化)為正者，最後藉由波茲EE 曼分布 ，反推溫度，計算出來的溫度即為初溫。順帶一提，在模擬=exp/ B PE k T 退火法中，我們會忽略波茲曼常數 。 B k 另一個初溫的方式是嘗試錯誤，我們在程式一開始，擇一較高之初溫，並視程 式接受結構變差的機率，決定是否要下修或上調初溫。若發現一開始接受的機率小於 我們的預設值，則加倍初溫並重新執行程式，反覆這兩個步驟，直至接受機率到達我 們的預設值。在本文所執行的模擬退火法，其初溫的訂定是使用統計的方式。 末溫(即冰點)的設定，最直觀的做法是設末溫為 0 度，但 White 與 Huang 等人分 別提出了較為嚴格的定義。White 提出，當某一個馬克夫鏈的結構及接續的數個馬克夫 鏈的結構相同，我們視此系統已達冰點。Huang 等人2則提出在每個馬克夫鏈的最後， 比較接受改變的結構中，能量最大與能量最小者的改變量，若兩者相同，則改變量為 零，意即當前之馬克夫鏈中，所有結構均擁有相同的能量。故模擬退火法已可不再需 要，令末溫為零以終止演算。 在討論初溫及末溫的制訂後，接下來要討論如何降溫降溫計劃表。降溫計劃表 有許多型式，不勝枚舉，筆者列出三種被廣泛應用的退火方式，即對數型(Exponential)、 柯西(cauchy)、指數型(Logarithmic)退火，指數型又稱為幾何型，它們的數學表達式分 別如下： 對數型： /ln ki TTk 柯西型：/ ki TTk 指數型：或 ck ki TTe k ki TT 由於本文的降溫計表是使用柯西型退火，設定，再加上設定上的方便，所以 1 i k T T k 末溫設定為 0.04。 第一穩態條件第一穩態條件 輸入一個目標繞射圖形後，產生一個與目標繞射圖形相同大小的矩陣，並計算其 能量(評價函數)。接著，擾動一個或多個像素(pixel)，並計算擾動後的能量，若能量 的變化為負，則接受此變化；若能量的變化為正，則利用波茲曼分佈計算此時接受此 變化的機率，再隨機產生一個隨機值，若隨機值比接受此變化的機率高，則接受此變 化，反之，則不接受。重複上述步驟，待不被接受的次數達到我們設定的次數，則依 我們設定的降溫方式降溫，直至冰點。在本文中，第一穩態所設定的不被接受的次 數為 1000000 次。 第二穩態條件第二穩態條件 輸入一個目標繞射圖形後，產生一個與目標繞射圖形相同大小的矩陣，並計算其 能量(評價函數)。接著，擾動一個或多個像素(pixel)，並計算擾動後的能量，若能量 的變化為負，則接受此變化；若能量的變化為正，則利用波茲曼分佈計算此時接受此 變化的機率，再隨機產生一個隨機值，若隨機值比接受此變化的機率高，則接受此變 化，反之，則不接受。我們給定一個馬克夫鍊的長度，並重複上述步驟，待達到我們 設定的馬克夫鍊之長度，則依我們設定的降溫方式降溫，直至冰點；換句話說，我們 設定不斷地給予擾動幾次後降溫。在本文中，第二穩態所設定的一個馬克夫鍊的 長度為 500000 次。 第二穩態條件尚有一改進的版本重新模擬退火法，此法與第二穩態一樣，但在 每次降溫達冰點時，會再以一定的比例回溫，以防模擬退火法陷入局部最佳解，但礙 於此法在繞射光學元件的領域上成效不彰，所以本文不予討論。3 第三穩態條件第三穩態條件 輸入一個目標繞射圖形後，產生一個與目標繞射圖形相同大小的矩陣，並計算其 能量(評價函數)。接著，擾動一個或多個像素(pixel)，並計算擾動後的能量，若能量 的變化為負，則接受此變化；若能量的變化為正，則利用波茲曼分佈計算此時接受此 變化的機率，再隨機產生一個隨機值，若隨機值比接受此變化的機率高，則接受此變 化，反之，則不接受。當能量差 小於初始能量的百分之五；也就是初始相位的能E 量，即達穩態條件，此時，得降溫一次。在開始執行模擬退火法第三穩態條件前，先 以一個程式不斷地對此繞射光學元件微擾，並回傳其平均的能量變化，接著我們將此 能量變化乘以一定的比例做為穩態條件(在 Yoshikawa 的論文中，是乘以百分之五4)， 然後在程式中，我們也以一個向量評估函數計算其平均能量量差，當此平均能量差小 於穩態條件，則依我們設定的降溫方式降溫，直至冰點，而且在每次降溫後，平均能 量差必需重新計算。在程式開始前所計算出的平均能量差所需乘的比例，是依繞射光 學元件的需要而設定，在本文中，第三穩態的穩態條件所乘的比例為 0.9。 執行結果討論執行結果討論 穩態條件穩態條件耗費時間耗費時間(s)(s)總迴圈次數總迴圈次數接受的回圈接受的回圈 次數次數 繞射效率繞射效率方均根誤差方均根誤差訊雜比訊雜比 第一穩態條件 17701.512592600284628460.12100.21750.00074924 第二穩態條件 7543.332795350000062460.21480.23140.0032 第三穩態條件 雖然模擬退火法較容易找到最佳解，也是比較好掌控的，但其花費的時間將會比 較多，這也是我們在討論最佳化問題NP-Complete 的問題時，我們不會去討論其時 間複雜度，因為我們找的是最佳解 ，而非最佳時間 ；必竟魚與熊掌難以兼得。 參考資料 1W.Feller, “An introduction to probability theory and its applications”, Wiley, New York, vol. 1, 1950. 2M. D. Huang, F.Romeo and A. L. Sang