模擬退火是一個通用的全域性最最佳化演算法。要理解它的思想，可以從 Gibbs Distribution 入手：這定義了一個機率分佈，其中 x 表示系統的狀態，P(x) 表示系統取 x 狀態的機率，E(x) 表示系統處於 x 狀態的能量，T表示溫度。在物理上，E(.)的定義取決於系統本質，在最最佳化上，我們需要虛擬一個系統，讓這個系統的 E(.) 對應到我們的最佳化目標。這個分佈有兩個特點：1. E(x) 越小，P(x) 則越大；反之亦然。2. T 越大，P(.) 分佈越 uniform，反之 P(.) 越 sharp。根據(1)，我們做最小化的時候，比如我們要最小化函式 f(x) 的值，就可以直接讓 E(x) = f(x)；如果是最大化 f(x)，可以設 E(x) = -f(x)。總之，這樣一來原始的最最佳化問題就變成了在 P 分佈下尋找機率最大的狀態 x。對於(2)，可以畫個不太嚴謹的圖解釋如下：可以看到，當T=0的時候，只有對於讓 E(x) 最小的 x*，我們有 P(x*)=1，其他的x均為 P(x)=0。而當T=∞時，對於所有的x，P(x)均相等，於是就構成了一個均勻分佈（從上面的機率公式看，此時對於任何x都有E(x)/T=E(x)/∞=0，跟E(x)等於幾已經無關了）。當T取其他值的時候呢，就是介於0和∞之間的狀態。於是我們得出結論：T越大，P(.)越均勻，T越小，P(.)越陡峭。為了更直觀，本物理盲在這裡瞎扯幾句：假設一些水分子組成了一個系統，系統的變數是水分子的空間座標。當T很大的時候，P(.)變得均勻，於是整個系統變得非常的不穩定，所有的水分子都亂飄（因為取任何座標的機率都均等嘛），宏觀上就是水蒸發成了氣體。當T變成0時，P(.)變得非常陡峭，於是整個系統的狀態穩定在P(x)=1的x上，宏觀上看就是水凝成了固體。現在假設我們有一個演算法，可以在給定的 P(.) 上面取樣。那麼，當 T=0 時，由於只有最優的 x* 滿足 P(x*) = 1，其餘的 x 均為 P(x) = 0。所以只要我們採集的樣本滿足此時 P(.) 的分佈，那麼它一定就是 x*。這個演算法就是模擬退火。學過C語言的人都知道rand()，它會以相等的機率返回一個介於0到RAND_MAX之間的隨機數。這對應的是在[0,RAND_MAX]的均勻分佈上取樣。假設我們需要在更加複雜的分佈上取樣，比如上面的P(.)，我們應該怎麼做呢？解決方法就是MCMC（Markov chain Monte Carlo）。MCMC簡單來講就是，從一個初始狀態開始，經過若干步狀態轉移，最後達到一個狀態，這個就是採集出來的樣本。在每次狀態轉移時（到，到等），首先需要 propose 一個可能的新狀態 x"，然後根據 P(.) 的特點決定是否要接受（accept）這個新的狀態：如果接受了，那麼下一次的狀態就變為 x"，否則保持不變。這實際上是為了維護細緻平衡（Detailed balance）。對於MCMC而言，正是這個關鍵的步驟保證了取樣的結果符合目標分佈。在模擬退火的演算法中，有一個很詭異的rejection操作，其實就是這個原因。但是，維護細緻平衡是有代價的，如果目標分佈 P(.) 過於陡峭，那麼，很有可能 propose 的 x’ 能量遠大於當前的 x（E(x") >> E(x)），根據 rejection 公式，可以看到這樣的 x" 幾乎總是會被拒絕。於是系統的收斂速度會變得巨慢：簡言之，你需要非常多的狀態轉移才能採集到一個合格的樣本。但如果 P(.) 比較均勻呢，這時新的 x" 就很容易被接受，相對來說就更容易拿到合格的樣本。所以在模擬退火中，從來不直接從T=0（或者其他低溫狀態）開始取樣，儘管理論上這樣採集到的樣本也是最優解，但為了拿到一個樣本，你恐怕要永遠地等下去。模擬退火採用的方法是：從高溫開始取樣，使得演算法可以快速拿到下的樣本，然後緩慢地降低一點溫度到，這時以為起點，在溫度下采樣，由於和很接近，於是也很接近下面的合格樣本，經過少數幾輪狀態轉移，就可以期望拿到下面的樣本，於是繼續稍微降低溫度到，重複這個過程……直到抵達了一個極低溫度，這時的樣本就是全域性最優解。可以看到T有一個減小的過程，這大概就是“退火”這個說法的由來。S. Kirkpatrick在1983年證明了模擬退火這個想法確實是可行的。並且（理論上）它最牛逼的地方在於：這是一個通用演算法。也就是說幾乎可以吃掉所有的最最佳化問題，而且得到的結果還是全域性最優的！但實際應用中，全域性最優基本上是不能保證的，這是因為 S. Kirkpatrick 同時也證明了要達到全域性最優需要實現的退火速度（也就是T減小的速度）——這個速度基本上是慢到人類無法承受的。不過好在實際應用中，我們通常可以採用一個快速的降溫策略，再配合一些heuristic演算法，這樣最後得到的結果雖不是全域性最優，但基本上也是全域性不錯的。關於MCMC講的比較intuitive，請有興趣的同學自行參考相關資料：）
模擬退火是一個通用的全域性最最佳化演算法。要理解它的思想，可以從 Gibbs Distribution 入手：這定義了一個機率分佈，其中 x 表示系統的狀態，P(x) 表示系統取 x 狀態的機率，E(x) 表示系統處於 x 狀態的能量，T表示溫度。在物理上，E(.)的定義取決於系統本質，在最最佳化上，我們需要虛擬一個系統，讓這個系統的 E(.) 對應到我們的最佳化目標。這個分佈有兩個特點：1. E(x) 越小，P(x) 則越大；反之亦然。2. T 越大，P(.) 分佈越 uniform，反之 P(.) 越 sharp。根據(1)，我們做最小化的時候，比如我們要最小化函式 f(x) 的值，就可以直接讓 E(x) = f(x)；如果是最大化 f(x)，可以設 E(x) = -f(x)。總之，這樣一來原始的最最佳化問題就變成了在 P 分佈下尋找機率最大的狀態 x。對於(2)，可以畫個不太嚴謹的圖解釋如下：可以看到，當T=0的時候，只有對於讓 E(x) 最小的 x*，我們有 P(x*)=1，其他的x均為 P(x)=0。而當T=∞時，對於所有的x，P(x)均相等，於是就構成了一個均勻分佈（從上面的機率公式看，此時對於任何x都有E(x)/T=E(x)/∞=0，跟E(x)等於幾已經無關了）。當T取其他值的時候呢，就是介於0和∞之間的狀態。於是我們得出結論：T越大，P(.)越均勻，T越小，P(.)越陡峭。為了更直觀，本物理盲在這裡瞎扯幾句：假設一些水分子組成了一個系統，系統的變數是水分子的空間座標。當T很大的時候，P(.)變得均勻，於是整個系統變得非常的不穩定，所有的水分子都亂飄（因為取任何座標的機率都均等嘛），宏觀上就是水蒸發成了氣體。當T變成0時，P(.)變得非常陡峭，於是整個系統的狀態穩定在P(x)=1的x上，宏觀上看就是水凝成了固體。現在假設我們有一個演算法，可以在給定的 P(.) 上面取樣。那麼，當 T=0 時，由於只有最優的 x* 滿足 P(x*) = 1，其餘的 x 均為 P(x) = 0。所以只要我們採集的樣本滿足此時 P(.) 的分佈，那麼它一定就是 x*。這個演算法就是模擬退火。學過C語言的人都知道rand()，它會以相等的機率返回一個介於0到RAND_MAX之間的隨機數。這對應的是在[0,RAND_MAX]的均勻分佈上取樣。假設我們需要在更加複雜的分佈上取樣，比如上面的P(.)，我們應該怎麼做呢？解決方法就是MCMC（Markov chain Monte Carlo）。MCMC簡單來講就是，從一個初始狀態開始，經過若干步狀態轉移，最後達到一個狀態，這個就是採集出來的樣本。在每次狀態轉移時（到，到等），首先需要 propose 一個可能的新狀態 x"，然後根據 P(.) 的特點決定是否要接受（accept）這個新的狀態：如果接受了，那麼下一次的狀態就變為 x"，否則保持不變。這實際上是為了維護細緻平衡（Detailed balance）。對於MCMC而言，正是這個關鍵的步驟保證了取樣的結果符合目標分佈。在模擬退火的演算法中，有一個很詭異的rejection操作，其實就是這個原因。但是，維護細緻平衡是有代價的，如果目標分佈 P(.) 過於陡峭，那麼，很有可能 propose 的 x’ 能量遠大於當前的 x（E(x") >> E(x)），根據 rejection 公式，可以看到這樣的 x" 幾乎總是會被拒絕。於是系統的收斂速度會變得巨慢：簡言之，你需要非常多的狀態轉移才能採集到一個合格的樣本。但如果 P(.) 比較均勻呢，這時新的 x" 就很容易被接受，相對來說就更容易拿到合格的樣本。所以在模擬退火中，從來不直接從T=0（或者其他低溫狀態）開始取樣，儘管理論上這樣採集到的樣本也是最優解，但為了拿到一個樣本，你恐怕要永遠地等下去。模擬退火採用的方法是：從高溫開始取樣，使得演算法可以快速拿到下的樣本，然後緩慢地降低一點溫度到，這時以為起點，在溫度下采樣，由於和很接近，於是也很接近下面的合格樣本，經過少數幾輪狀態轉移，就可以期望拿到下面的樣本，於是繼續稍微降低溫度到，重複這個過程……直到抵達了一個極低溫度，這時的樣本就是全域性最優解。可以看到T有一個減小的過程，這大概就是“退火”這個說法的由來。S. Kirkpatrick在1983年證明了模擬退火這個想法確實是可行的。並且（理論上）它最牛逼的地方在於：這是一個通用演算法。也就是說幾乎可以吃掉所有的最最佳化問題，而且得到的結果還是全域性最優的！但實際應用中，全域性最優基本上是不能保證的，這是因為 S. Kirkpatrick 同時也證明了要達到全域性最優需要實現的退火速度（也就是T減小的速度）——這個速度基本上是慢到人類無法承受的。不過好在實際應用中，我們通常可以採用一個快速的降溫策略，再配合一些heuristic演算法，這樣最後得到的結果雖不是全域性最優，但基本上也是全域性不錯的。關於MCMC講的比較intuitive，請有興趣的同學自行參考相關資料：）