本文關(guān)鍵詞：退火算法，由筆耕文化傳播整理發(fā)布。

模擬退火算法(SA,Simulated Annealing)思想

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。
模擬退火算法(Simulated Annealing，SA)最早由Kirkpatrick等應(yīng)用于組合優(yōu)化領(lǐng)域，它是基于Monte-Carlo迭代求解策略的一種隨機(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)化算法。

模擬退火算法的模型
模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。
模擬退火的基本思想:
(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L
(2) 對(duì)k=1，……，L做第(3)至第6步：
  (3) 產(chǎn)生新解S′
  (4) 計(jì)算增量Δt′=C(S′)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)
  (5) 若Δt′<0則接受S′作為新的當(dāng)前解，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解.
  (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。
        終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。
(7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。

模擬退火算法流程圖

posted @

  本文關(guān)鍵詞：退火算法，由筆耕文化傳播整理發(fā)布。