模擬退火算法來源于固體退火原理，是一種基于概率的算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。

模擬退火算法（Simulated Annealing，SA）最早的思想是由N． Metropolis等人于1953年提出。1983 年，S． Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領域。它是基于Monte－Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能，目前已在工程中得到了廣泛應用，諸如VLSI、生產(chǎn)調度、控制工程、機器學習、神經(jīng)網(wǎng)絡、信號處理等領域。

模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結構的優(yōu)化算法。

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e（－ΔE／（kT）），其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表（Cooling Schedule）控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。

模擬退火算法的模型

1模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。

2模擬退火的基本思想：

（1） 初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點），每個T值的迭代次數(shù)L

（2） 對k＝1， …， L做第（3）至第6步：

（3） 產(chǎn)生新解S′

（4） 計算增量ΔT＝C（S′）－C（S），其中C（S）為評價函數(shù)

（5） 若ΔT＜0則接受S′作為新的當前解，否則以概率exp（－ΔT／T）接受S′作為新的當前解．

（6） 如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。

終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。

（7） T逐漸減少，且T－＞0，然后轉第2步。

模擬退火算法的步驟

模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：

第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。

第二步是計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。

第三步是判斷新解是否被接受，判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropolis準則： 若ΔT＜0則接受S′作為新的當前解S，否則以概率exp（－ΔT／T）接受S′作為新的當前解S。

第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代�？稍诖嘶�礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。

模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S（是算法迭代的起點）無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。