模擬退火算法是基於Monte Carlo疊代求解法後種啟發式隨機搜尋算法，它模擬固體物質退火過程的熱平衡問題與隨機搜尋尋優問題的相似性來達到尋找全局最優或近似全局最優的目的。
基本介紹
- 中文名：模擬退火遺傳算法
- 定義：模擬退火算法過程中溶入遺傳算法
- 基礎：Monte Carlo疊代求解法
- 目的：尋找全局最優或近似全局最優
在模擬退火算法的運行過程中溶入遺傳算法，稱為模擬退火遺傳算法。
在搜尋最優解的過程中，模擬退火法除了可以接受最佳化解外，還有一個隨機接受準則（Metropolis準則）有限度地接受惡化解，並且接受惡化解的機率慢慢趨向於0，這使得算法有可能從局部極值區域中跳出，即可能找到全局最優解，並保證了算法的收斂性。
模擬退火算法的求解過程如下：
（1）隨機產生初始解x0；
（2）初始化退火溫度T0；
（3）在溫度TK下執行如下操作：
·產生新的可行解x',x'為x的鄰解；
·計算評價函式f(x')和f(x)的差值Δf=f(x')-f(x);
·以min{1,exp(-Δf/Tk)}>random[0,1]的機率接收新解，其中random[0,1]是[0，1]之間的隨機數。若達到溫度Tk的平衡狀態轉（4），否則轉（3）；
（4）按一定方式降低溫度，可定義下降函式為Tk+1=αTk,k+1→,其中α∈[0，1]；
（5）若滿足收斂判據，退火過程結束；否則轉（3）。
通過以上分析可知，在模擬退火過程中，其退火溫度控制著求解過程向最小值的最佳化方向進行，同時它又以機率exp(-Δf/Tk)接收劣質解，因此算法可以跳出局部極值點。只要初始溫度足夠高，退火過程足夠慢，算法能夠收斂到全局最優解。
