模擬退火算法

上傳人：卓*** IP屬地：廣東上傳時間：2024-04-12 格式：PPT 頁數：23 大?。?.85MB 積分：15 舉報 版權申訴

已閱讀5頁，還剩18頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

關于模擬退火算法一、模擬退火算法的基本思想啟發(fā)注意到一個自然規(guī)則：物質總是趨于最低的能態(tài)。水總是向低處流。電子總是向最低能級的軌道排布。最低能態(tài)是最穩(wěn)定的狀態(tài)。物質會”自動”地趨向的最低能態(tài)。第2頁,共31頁，2024年2月25日，星期天模擬退火算法的設計與原理

猜想物質自動趨向的最低能態(tài)與函數最小值之間有相似性！?。∥覀兡懿荒茉O計一種算法求函數最小值，就像物質”自動”地趨向最低能態(tài)？降溫圖像離散函數圖像相似性?最小值最低能態(tài)第3頁,共31頁，2024年2月25日，星期天模擬退火算法的設計與原理

物理模型——固體退火退火俗稱固體降溫先把固體加熱至足夠高溫，使固體中所有粒子處于無序的狀態(tài)（最高的熵值），然后將溫度緩慢下降，粒子漸漸有序（熵值下降），這樣只要溫度上升得足夠高，冷卻過程足夠慢，則所有粒子最終會處于最低能態(tài)（最低的熵值）。最低能態(tài)時間溫度第4頁,共31頁，2024年2月25日，星期天模擬退火算法的設計與原理類比根據Metropolis準則，粒子在溫度T時趨于熱平衡的概率為

其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數?？梢栽O計算法：將系統(tǒng)熵值類比為函數值F，來模擬這個退火過程。第5頁,共31頁，2024年2月25日，星期天Metropolis準則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當前狀態(tài)能量差較小的新狀態(tài)。第6頁,共31頁，2024年2月25日，星期天模擬退火算法的設計與原理提出模擬退火算法(SA)就是這樣一個將退火過程中系統(tǒng)熵值類比為目標函數值F，來模擬這個退火系統(tǒng)的算法。第7頁,共31頁，2024年2月25日，星期天模擬退火算法的設計與原理

數學模型——馬爾可夫過程模擬退火算法在概率理論上有一個很好的數學模型的來解釋：馬爾可夫(Markov)過程。第8頁,共31頁，2024年2月25日，星期天馬爾可夫過程及馬爾可夫鏈簡介馬爾可夫過程是一個隨機過程，它具備這樣的性質，即可知tm時刻過程處在狀態(tài)的條件下，在時刻tm以后過程將要到達的狀態(tài)的情況與該時刻以前過程所處的狀態(tài)無關。這個性質也稱為過程的無后效性或過程的馬爾可夫性。對一個狀態(tài)空間(I)離散、參數為非負整數的隨機過程，若它滿足條件: 這樣的隨機過程稱為馬爾可夫鏈。馬爾可夫鏈在t時刻的一步條件轉移概率也稱作t時刻的狀態(tài)轉移(i→j)

概率。顯然有：第9頁,共31頁，2024年2月25日，星期天二、模擬退火算法的實現

SA算法在Markov鏈長度內持續(xù)進行“產生新解—判斷—接受/舍棄”的迭代過程，對應著固體在某一恒定溫度下趨于熱平衡的過程。算法終止時的當前解即為所得近似最優(yōu)解。這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。第10頁,共31頁，2024年2月25日，星期天模擬退火算法的實現思想SA算法的計算過程可視為重復遞減控制參數值（溫度）并進行Metropolis算法的迭代過程。一次Metropolis算法是指，對于控制參數t的每一取值，算法在Markov鏈長度內持續(xù)進行“產生新解—判斷—接受/舍棄”的迭代過程，對應著固體在某一恒定溫度下趨于熱平衡的過程。算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。第11頁,共31頁，2024年2月25日，星期天相似性比較

優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設定初溫熔解過程Metropolis抽樣過程等溫過程控制參數的下降冷卻目標函數能量組合優(yōu)化與物理退火的相似性第12頁,共31頁，2024年2月25日，星期天模擬退火算法的實現

算法描述SimulatedAnnealing(SA)Algorithm:1初始化：系統(tǒng)初溫T，初始狀態(tài)S0，馬爾可夫鏈長L，終止條件AIM2while(true) 2.1對于k=1..L,執(zhí)行2.1.1到2.1.4 2.1.1從當前解S,產生新解SN

，他們之間的差值為D. 2.1.2若(D<0或滿足概率exp(-D/T)),則S:=SN. 2.1.3若(當前解S<當前最優(yōu)解SB),則SB:=S. 2.1.4if(T趨于0或連續(xù)AIM次迭代物最優(yōu)值),則可近似認為SB為最優(yōu)，轉3. 2.2降溫 2.3S=SB3輸出SB第13頁,共31頁，2024年2月25日，星期天模擬退火算法的實現

實現技術冷卻進度表、鄰域結構和新解產生器、接受準則和隨機數產生器一起構成算法的三大支柱。從算法結構可知，新狀態(tài)產生函數、新狀態(tài)接受函數、退溫函數、退火結束準則以及初始溫度是直接影響算法優(yōu)化結果的主要環(huán)節(jié)。第14頁,共31頁，2024年2月25日，星期天模擬退火算法的實現

冷卻進度表冷卻進度表包含：初始溫度，退溫速率，退火結束準則，Markov鏈長。它直接決定了算法的效率，需要大量試驗才能得出其最佳的組合。第15頁,共31頁，2024年2月25日，星期天模擬退火算法的優(yōu)化

回火技術如圖所示，若粒子開始處于D狀態(tài)，若讓能量逐漸減小，則粒子最終到達的是A點(局部最低點)而不是B(全局最低點)點，這是我們所不希望的。解決的辦法是對系統(tǒng)經常地”搖動”一下，就很可能把粒子從D點越過C點搖到B點，而把它搖到A點的可能性減小。這就是回火技術：降溫后以一定概率升溫，引入產生函數擾動因子，來控制搜尋全局最優(yōu)值的范圍。ABCD第16頁,共31頁，2024年2月25日，星期天模擬退火算法的應用前景

NP問題與計算復雜性理論計算復雜性理論通俗的解釋：多項式時間:運行時間最多是輸入量的多項式函數。P類問題是可被“在多項式時間運行”一個算法解決的問題，換句話說這種解決是好的，快的。NP完全類問題即是目前沒有一個“可用多項式時間解決”的問題，這種問題是稱為”難的”。如TSP問題，若有144個城市，求最優(yōu)解，則要運行144!次，這是要幾萬年的時間。該類問題排位“新千年急待解決的7大數學問題”之首！NP完全問題都是相互多項式等價的，就是說，解決了其中一個問題，所有的NP完全問題都被“好的”解決。第17頁,共31頁，2024年2月25日，星期天模擬退火算法的應用前景

算法特性優(yōu)點可并行性擴展性和通用性

它可以高效的解決幾乎所有的組合優(yōu)化問題。高效率，高性價比逼近速度快，可極快的求得很好的近似值SA算法比傳統(tǒng)算法速度快的多了，解也以1的概率趨于最優(yōu)解。在解的質量與時間的比上效果良好。

傳統(tǒng)算法要運行幾年的情況，SA只需幾秒。具有全局優(yōu)化特性

第18頁,共31頁，2024年2月25日，星期天

三、模擬退火算法的應用