【概述】

模擬退火（Simulated Annealing，SA），其類似于物理學上金屬退火的過程，故稱為模擬退火，其是一個隨機化與貪心結合的算法，在你 RP 較好或數據范圍比較小的時候，可以輕松解決許多難題。

模擬退火的原理與金屬退火的原理近似：

• 將熱力學的理論套用到統計學上
• 將搜尋空間內每一點想像成空氣內的分子
• 搜尋空間內的每一點，也像空氣分子一樣帶有動能，其用于表示該點對命題的合適程度
• 演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個相鄰的點，然后再計算從現有位置到達相鄰點的概率

【主要思路】

我們模擬物理退火的三個過程：加溫、等溫、冷卻，來歸納一下模擬退火算法的主要思路：

首先，確定一個初始溫度 T，這個參數是隨機選擇的，初始溫度選擇的越好，算法表現就越好，但具體該選何值，沒有一個明確的界定方法，只能依靠 RP 來選，不過據說有些大佬可以根據題目推出最優初始溫度

然后，當溫度大于一個邊界值時，我們將當前狀態的答案與下一狀態的答案進行比較：

• 如果 res<newRes，轉移答案
• 如果 res>newRes，有一定概率轉移答案

在擴展狀態時有一個小方法：nextSta=nowSta+(rand()?2?RAND_MAX)?T，這樣的原理是：(rand()?2?RANDMAX) 的范圍是從負數到正數的，這樣在擴展坐標的時候就可以多方向擴展，不會只在一個方向上更新。

其次，確定轉移答案的概率，由于轉移答案的概率需要隨著時間的推移與 res 和 newRes 差值的增大而增大，因此常表示為：，其中

最后，我們模擬降溫過程，對 T 乘以一個小于但十分接近于 1 的數 delta，以體現時間對答案的影響。

這樣，隨著溫度不斷降低，變化幅度也越來越小，接受一個更劣的解的概率也越來越小。

void SA(double nowSta){int T = ****; //初始溫度double delta=0.99;int res=getRes(nowSta);//初始狀態能得到的答案while (T > EPS) { // EPS是一個大于0的極小值，用于精度的比較，一般取1E-9~1E-15int nextSta = nowSta + (rand() * 2 - RAND_MAX)*T; //擴展狀態int newRes = getRes(nextSta); //記錄下一個狀態能得到的答案double pr = exp((res - newRes) / T) * RAND_MAX;//一定的概率if (res < newRes || pr > rand()){//新的代價小于當前代價，或在一定概率下nowSta = nextSta;//更新當前狀態res = newRes;//更新新狀態的答案}T *= delta; //降溫的過程，將溫度減小} }

?

總結

以上是生活随笔為你收集整理的搜索 —— 启发式搜索 —— 模拟退火的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。