模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，在常溫時達(dá)到基態(tài)，內(nèi)能減為。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。
3.5.1 模擬退火算法的模型
　　模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。
　模擬退火的基本思想:
　　(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′作為新的當(dāng)前解，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解.
　　(6) 如果滿足終止條件則輸出當(dāng)前解作為解，結(jié)束程序。
終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。
　　(7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。
算法對應(yīng)動態(tài)演示圖：
模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：
　　步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。
　　第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計算按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的快方法。
　　第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準(zhǔn)則，常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若Δt′<0則接受S′作為新的當(dāng)前解S，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解S。
　　第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。此時，當(dāng)前解實現(xiàn)了迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當(dāng)新解被判定為舍棄時，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。
　　模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局解的全局優(yōu)化算法；模擬退火算法具有并行性。