模式識(shí)別：禁忌搜索與模擬退火算法20151019

模式識(shí)別：模擬退火算法&禁忌搜索算法PatternRecognition主講人：胡雪梅導(dǎo)師：黃嵐指導(dǎo)老師：王巖時(shí)間：2015/10/192023/9/21模擬退火算法&禁忌搜索算法模擬退火算法禁忌搜索算法

模擬退火算法&禁忌搜索算法模擬退火算法源自于物理學(xué)鍛造技術(shù)和退火現(xiàn)象，在1953年由Metropolis所提出來(lái)的。固體物質(zhì)退火過(guò)程與一般組合優(yōu)化問(wèn)題相似。算法起源在圖2.1之中，開始狀態(tài)下物體的分子狀態(tài)是無(wú)序的，然后進(jìn)行高溫處理，物體分子變得活躍并分散開來(lái)，到達(dá)最高溫時(shí)內(nèi)能最大，逐漸冷卻時(shí)各個(gè)物體分子漸漸變得有序并開始尋找一個(gè)最佳平衡點(diǎn)，如果溫度降得足夠慢，那么到達(dá)最終態(tài)時(shí)內(nèi)能將最小，分子將排列的最為有序。退火過(guò)程模擬退火算法就是模仿鍛造技術(shù)的退火方法來(lái)找到整個(gè)解空間下的最終收斂狀態(tài)以達(dá)到尋找最優(yōu)解的目的。算法基本思想由初始解和控制參數(shù)的初值開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解

計(jì)算目標(biāo)函數(shù)差

判斷是否接受

接受或舍棄”的迭代，并逐漸衰減t值，算法終止時(shí)的當(dāng)前解即為近似最優(yōu)解。算法步驟(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)前解，否則以Metropolis準(zhǔn)則接受S′作為新的當(dāng)前解；

(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序；

(7)T逐漸減少，且T->0，然后轉(zhuǎn)第2步；模擬退火算法&禁忌搜索算法算法特點(diǎn)與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S無(wú)關(guān)；以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性；模擬退火算法&禁忌搜索算法算法應(yīng)用實(shí)例兔子醉酒

兔子喝醉了。它隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。旅行商問(wèn)題(TSP,TravelingSalesmanProblem)有N個(gè)城市，要求從其中某個(gè)問(wèn)題出發(fā)，唯一遍歷所有城市，再回到出發(fā)的城市，求最短的路線。旅行商問(wèn)題屬于所謂的NP完全問(wèn)題，精確的解決TSP只能通過(guò)窮舉所有的路徑組合，其時(shí)間復(fù)雜度是O(N!