模擬退火(simu1atcd Amea1ing,sA)算法最早的思想是由N,Mc饣opOlis等人于1953年提出。1983年,s.Kirkpatrick等成功地將退火思想引入組合優(yōu)化領(lǐng)域。 LPO2506I-682LC它是基于 Montc-C刪0迭代求解策略的一種隨機(jī)尋優(yōu)算法,其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與―般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā),伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解,即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法,理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用,如VLsI生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性,從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法�？梢詫⒛M退火算法應(yīng)用于求解組合優(yōu)化問題,將組合優(yōu)化問題解空間中的一個(gè)解對(duì)應(yīng)于固體降溫過程中的一個(gè)狀態(tài),將目標(biāo)函數(shù)對(duì)應(yīng)于該狀態(tài)下的能量。

   以控制參數(shù)Γ來模擬固體的溫度。對(duì)于每一個(gè)Γ,進(jìn)行迭代過程,即“解變換產(chǎn)生新解,判別準(zhǔn)則,新解的取舍”,并采用Mctrop01is準(zhǔn)則來決定解的取舍。隨著溫度的降低,該算法有可能從局部極值區(qū)域跳出,從而達(dá)到全局最優(yōu)解。模擬退火算法流程圖如圖3-11所示。