兔窩

啟發式演算法 – 模擬退火演算法 Simulate Anneal

閒言：

　　大學時一個非常照顧我的師長曾經說過，知識的完整性比它的深度來的重要，很多時候我們必須停下來整理自己所學的東西。然而我這半年就是完全沒有這樣做才導致部落格一直處在荒廢狀態，想想自己也已經要升上碩二了，沒有意外的話明年就要找工作，確實是該來一邊整理知識一邊準備作品集了，所以之後部落格更新的頻率會高一點。

　　順帶一題我發現之前的文章常常中英文交替用，之後專有名詞除了第一次出現以外都會採用英文或英文簡稱為主，《II篇》我也有稍作修正，有興趣的人可以去複習一下再看這篇。原因是雖然啟發式演算法的應用真的很廣，是滿好玩的領域，但是在台灣討論的人比較少，如果大家真的有興趣繼續研究也都是英文資源較多。

簡介：

　　上回的 II 介紹我們已經說明了它的原理，同時我們也了解到其最大的缺點就是處於一個 local optimum 時他就會停下，但是又不能把 neighborhood function 無限上綱的開大。而今天要介紹的模擬退火演算法（Simulate Anneal），簡稱 SA，就是使用 neighborhood function 擴張以外的方法解決這個缺點。local optimum，換句話說就是我現在的解使用 neighborhood function 所生出來的新解的 fitness 都比較差，導致我無法選擇他們，而 SA 就是讓演算法有一定的機率去接受這個解，在時間許可下嘗試往不好的地方繼續搜索，期許可以找到另外一個更好的 local optimum 甚至是 global optimum。如下圖，假設現在要求的是最低點、而演算法正搜尋到 A 點，這時若是我們願意接受較差勁的 B 點，這樣 B 點在生出新的解時就會生出更加好的 C 點，帶我們脫離 A 點這個 local optimum。

　　光是這樣簡介我們就可以知道這個接受的機率控制就是 SA 最大的重點，其控制參考冶金學或材料工程的退火（Anneal）所設計，故命名為 Simulate Anneal。

說明：

　　基本上 SA 在流程上與 II 是一樣的，初始解、生出新的解、接受新的解、是否達標終止條件，其中只有接受新的解這點會不一樣，所以將重點放在他身上。在丟出控制公式之前我們先簡易的說明它控制的想法，當我們不知道 global optimum 在哪、同時演算法遇到一個 optimum 時，在甚麼情況我們會認為它可能是 local optimum 並願意花費時間接受一個比較差的解，期許它帶領我們脫離這個 local optimum 找到更好的解來？

　　為了回答這個問題，我們將演算法遇到 optimum 的狀況根據時間分成早期跟晚期，如上表我們可以很直覺地說，早期的 optimum 很可能是 local optimum，畢竟也還沒看過幾個解，其他地方有更好解的機率非常高，同時在時間上的花費也還很少，在這兩個前提下我們比較願意先接受較差的解，並期待它會幫助我們搜尋到更加的解。反之亦然，當後期找到好解的機率不高、花費過多時間又會失去啟發式演算法優點時，比起繼續期待下去我們更傾向就結束演算法輸出這個已經足夠優秀的 local optimum。

　　SA的想法就是這麼運作的，當演算法遇到 optimum 時會有一定的機率接受較差的解，而這個機率會隨著搜索過程逐漸降低，如下公式所示。

現在我們來解釋這個公式

• P：P 就是我接受較差解的機率，而不管從機率的定義來看還是從等號右邊的指數函數都可以得出 P 是恆正。

• T：再來我們談談 T，T 是用來控制前後期機率的，同時他不可以是負數，當 T 大，次方就越接近 -0，P 越接近 1，接受的機率越大；反之 T 小，次方接近 -∞，P 越接近 0，接受的機率越小。所以 T 就是我們在演算法中必須調整的值，讓 T 一開始夠大並隨著時間降低來達到剛剛提及的前期接受機率高、後期低的效果。

• ∆ C：最後是 ∆ C，它代表這個較差解跟我現在有的好解的 fitness 差距，同時差距在這邊的概念就如同數學的絕對值，他恆正。當解很差時，差距大，∆ C 大，次方就小，P 也就小，接受機率就小。所以 SA 除了我們剛剛提到的時間外他也會考慮這個較差解有多差，越差接受率越低。

假設剛剛的公式都看不懂也關係，圖畫出來就清楚了

圖的 y 軸是 P，x 軸是 T，而不同的曲線對應不同的 ∆ C，我們可以看到如果是一樣的 ∆ C，P 是會跟著 T 的增加而下降的，所以時間越長 P 越小。而 ∆ C 越大意味著這個解越差，P 也較低，所以可以看到 ∆ C 設成 1000 的紫色曲線即使在 T 很大（1000）的時候，由於解太差，它依舊只有 4 成左右的機率會被接受。同時提醒在實作時 T 的初始值、下降速度都是我們需要自己設定的，它不一定如圖中是線性下降也不一定是 1000 ~ 0。

　　現在我們可以將整個 SA 的流程圖畫出來

　　重點就在於沒有更好的解時會做額外的操作，利用綠色部分的機率控制，一定機率進入橘色部分使用新的差解替換現有解來解決 II 卡在 local optimum 的缺點。我們也可以從流程圖看出當 SA 的 T 很小時，它就會跟 II 一樣幾乎不可能再繼續搜索其他區域，只會一直執行最右邊藍色的維持現有解的動作，所以 SA 中止條件很常被設定為 T 低到一定程度時停止，又或是一樣採用常見的固定 MaxFES，但是其 T 的下降一樣要去配合這個 MaxFES 數量，讓他快結束時剛好是低的。

　　當然 idea 聽起來都是很美好的，真正使用 SA 時也是會有坑存在，比如說我們剛剛提到要設定參數，SA 的效能很依賴這些參數，同時遇到不同問題、不同資料集、不同 fitness function 時都會影響參數的效能。當然，幾乎所有含有隨機、複雜的演算法都有參數設定，但是其參數好不好設定、影響大不大就是另外一回事了，而 SA 的參數就是屬於比較難設定的。

　　例如這個問題本身不同解的 fitness 的差異性就很高，neighborhood function 生出來的解的 fitness 差距都會在 2000 左右，然後我才用剛剛前面提及的一樣的 T，初始為 1000 線性下降到 0。其公式曲線如下，可以看到 P 從頭到尾都很低，SA 根本幾乎接受較差的解，它就跟 II 沒兩樣了。

　　有許多研究在針對這類較難設定參數的演算法做自適應參數控制，讓這些原本需要人為依靠經驗去設定的參數交由演算法自己根據現在的狀況調整，不過那是另外一個章節了，在這邊我們只需要知道 SA 的參數是需要依賴於你自己要解的問題，再反覆嘗試後根據經驗做設定。

總結：

　　本次介紹了 SA 這種一定程度改良 II 的演算法，其優點在於利用機率的控制使得演算法在我們設定的許可範圍內可以盡力搜索，提升找到  global optimum 的機率，同時我們也提到缺點在於 SA 的 T 參數的初始跟下降速度都相當影響效能又依賴於問題，所以它不是這麼好調教的。下一次會再介紹一種同樣不擴張 neighborhood function 又改善 II 缺點的演算法，當然也不可能一直都是純理論，三個基本單點式算法都講解完後會再出一篇實作篇，利用這三個演算法解決實際上的問題，同時帶出一些實作上應該注意的事項。本次的啟發式演算法系列就到此為止，謝謝正在觀看的你。