模擬退火算法（Simulate Anneal Arithmetic，SAA）是壹種通用概率演算法，用來在壹個大的搜尋空間內找尋命題的最優解。模擬退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發明。而V.?erný在1985年也獨立發明此演算法。模擬退火算法是解決TSP問題的有效方法之壹。
在尋找問題的最優解時，我們可以先給定壹個初始解。此時溫度較高，初始解有很大的概率發生變化，產生壹個新的解；隨著溫度的降低，解發生變化的概率逐漸減小。假定我們需要求解壹個函數f(x)的最小值，那麽模擬退火算法的過程描述如下：
產生新解的方式很多，以二進制編碼為例，假如壹個解為01001101，可以隨機選取壹位進行取反。假如選中了第3位，則第3位按位取反，新解為01101101。這個過程有點類似於遺傳算法中的基因突變。上述算法描述中每個溫度值只產生了壹次新解，實際問題中可以產生多次。
算法的關鍵在於Metropolis準則。如果新解的函數值較小，自然要把新解作為當前解；如果新解函數值較大，則它仍有壹定概率被選作當前解。這個概率與df有關，df越大，說明新解越差，它被選作當前解的概率也越小；此外，這個概率還和當前溫度有關，當前溫度越高，概率越大（類似於分子熱運動越劇烈）。