模擬退火演算法(SA)
引言
模擬退火演算法（Simulation annealing )是一個在1983年發表的演算法，而該演算法在發表時有一些爭議，原因為 Kirkpatrick 以及 Černý 在差不多時間都發表了模擬退火演算法，該演算法從爬山演算法延伸而來。雖然年代久遠，但至今還是有許多的研究使用模擬退火的概念，將模擬退火結合其他演算法或是將其應用至各種問題。此演算法的概念十分簡單卻有效，是一個頗為經典的超啓發式演算法。
概念
在超啓發式演算法中，區域最佳解(Local optimum)是此領域常遇到的一個問題，在迭代(iteration)過程中若是陷入區域最佳解，可能導致程式卡在此解，無法跳脫找到更佳的解，這邊以一個經典的函數最佳化問題來做說明，大家可能會比較好理解。
下圖是一個經典的測試函數-Rastrigin，所謂的區域最佳解就是那些山谷，從地形圖來看就是各種顏色的圈圈，而我們可以看出中間的位置(藍色)才有較好的解，但若演算法跳脫區域最佳解的能力不佳，很有可能沒辦法找到中間的區域。
而模擬退火演算法則是會讓程式以一定的機率接受較差的解，以此增加跳脫出區域最佳解的機會。接下來我們就來看看模擬退火演算法的細節吧!
想更了解測試函數可以參考
程式流程
模擬退火演算法的運行流程與爬山演算法大致相同，有以下五步，一開始先設定退火溫度以及迭代次數(Iteration)，再進行隨機初始化(2)，接著會不斷的進行TED(3–5)的步驟，直到設定的迭代次數才終止。為了方便大家了解這邊還是以 One max problem 來進行解說。
※01問題定義、超啟發式演算法運行流程可以看上一篇對爬山演算法的介紹
- 設定
設定迭代次數(Iteration)、初始溫度(T)和退火係數(Rₜ)。
2.初始化(Initial)
以隨機方式進行初始化，接著再評估該組解的好壞。
3.Transition
將第一步產生出的解，隨機挑選一個位置進行更動。
4.Evaluation
評估適應值(Fitness value)大小。
5.Determination
將第四步評估出的適應值與先前的進行比較。
若優於或等於先前解則更新。
若無則進行退火環節，退火的進行方式是使用退火溫度(T)和適應值的差值(Δf)計算出允許機率，接著隨機一個0–1的浮點數(r)，若該隨機值(r)≤允許機率則進行更新。
每次迭代的最後皆需進行降溫動作，會將溫度T乘上一個小於1的數值(Rₜ)，Rₜ的數值大小取決於想要的收斂速度。
- r為一個0–1的隨機浮點數
- Δf為當前的適應值減去先前的適應值
- T則為退火溫度，一般初始值設為1
- 在這邊要注意因為01問題是要找出最大的適應值，所以Δf的計算是當前-先前，若為最小化的問題，Δf的計算要改為先前-當前。
簡而言之，必須要讓Δf的值小於0!
公式解析
這邊會逐步的說明公式特性
此迭代產生出的解若是優於先前解，則會直接更新，不會進入退火環節，也就是說進入到退火環節的當前解一定會比先前解差，所以Δf一定會是負值！
接下來先假設T為1，暫時可以忽略不看。若當前解與先前解差異過大的話，會產生出一個很大的負值，若差異小的話則產生出的負值會較小。
e的指數若是一個很大的負值，計算後的值會很接近0；e的指數若是一個很小的負值，計算後的值會較接近1，所以此公式在差值較小的情形能有比較大的機率接受更新，在差值較大的情況更新機率會較低。
接下來我們將T也考慮進來，根據公式2，T會隨著迭代的進行而越來越小，從初始值1開始，隨著迭代不斷下降；回到公式1，Δf 除上一個小於1的值，會將 Δf 的值放大，變成一個更大的負數，成功更新的機率變得更低了！
附上簡單的舉例說明，希望可以讓大家了解的更快速！
這邊做個小結論，差值越大更新機率越低，隨著迭代進行，更新的次數也會下降，也就是演算法將漸趨收斂。
程式結果
設定的參數為
T : 1.0
Rₜ : 0.95
Length : 100、1000
Iteration : 100、500、1000、5000
Run : 51
以下的實驗結果皆為51次的平均結果，初始溫度和降溫係數可以依據問題設定不同的值；但01問題較為簡單，比較沒辦法看出不同值的差異性，所以在這邊只設定一組參數來進行實驗。
接下來介紹收斂圖，收斂圖可以讓我們很直觀的了解演算法的收斂情形，有利於我們了解演算法在各個迭代次數下的狀況。
下圖為模擬退火演算法在長度1000且最大迭代次數為5000的收斂圖，可以看出此方法是以一個斜率漸減的拋物線往好的解前進。
結論
模擬退火演算法以溫度下降的方式在一定機率下接受較差的解，能夠藉此方式跳出區域最佳解，雖然在01問題的實驗結果與上一篇介紹的爬山演算法差異不大，但在更複雜問題上，模擬退火演算法是能夠有更好效果的！
最後附上程式碼。
