模擬退火算法.ppt

《模擬退火算法.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、模擬退火算法（SimulatedAnnealing）1、引子2、SA算法的起源3、SA算法的基本思想4、SA算法的步驟5、SA算法應用范圍與一般要求6、SA算法的優(yōu)缺點1、引子在科學與工程計算中，經(jīng)常發(fā)生的一個問題是在Rn中或者是在一個有界區(qū)域上求某個非線性函數(shù)f(x)的極小點。在f(x)可導時，一個最基本的算法就是最速下降法。這一方法從某一選定的初值開始，利用如下公式進行迭代，即然而以速降法為代表的傳統(tǒng)算法具有共同的缺點，它們都不保證求得全局極小，只能保證收斂到一個由初值決定的局部極小點。每次都鼠目寸光的選擇一個當前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火

2、其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。2、SA算法的起源SA算法起源于對固體退火過程的模擬。簡單而言，在固體退火時，先將固體加熱使其溫度充分高，再讓其徐徐冷卻，其物理退火過程由以下三部分組成：加溫過程、等溫過程、冷卻過程。SA算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機搜索技術。模擬退火物理退火解粒子狀態(tài)最優(yōu)解能量最低態(tài)設定初溫熔解過程Metropolis采樣過程等溫過程控制參數(shù)的下降冷卻目標函數(shù)能量模擬退火算法與物理退火過程的相似關系3

3、、SA算法的基本思想在搜索最優(yōu)解的過程中，SA算法除了可以接受優(yōu)化解外，還基于隨機接受準則（Metropolis準則）有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于0。（這使得算法有可能從局部最優(yōu)中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂）SA的思想最早是由Metropolis等在1953年提出的，Metropolis等提出了重要性采樣法，即以概率接受新狀態(tài)。SA算法的思想為：由初始解i和控制參數(shù)初值t開始，對當前解重復產生新解→計算目標函數(shù)差→接受或舍棄的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)

4、式隨機搜索過程。SA算法與其它搜索方法相比，具有如下的特點：以一定的概率接受惡化解；引進算法控制參數(shù)；使用對象函數(shù)值進行搜索；隱含并行性；搜索復雜區(qū)域。4、SA算法的基本步驟1)隨機產生一個初始解x0，令xbest＝x0并計算目標函數(shù)值E(x0);2)設置初始溫度T(0)=To，迭代次數(shù)i=1;3)DowhileT(i)>Tmin1)forj=1~k2)對當前最優(yōu)解xbest按照某一鄰域函數(shù)，產生一新的解xnew。計算新的目標函數(shù)值E(xnew)，并計算目標函數(shù)值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，則xbest=xnew；4)如果ΔE

5、＞0，則p=exp(-ΔE/T(i));1)如果c=random[0,1]

6、制；（3）冷卻進度表。冷卻進度表是指從某一高溫狀態(tài)T0向低溫狀態(tài)冷卻時的降溫管理表。假設時刻t的溫度用T(t)來表示，則經(jīng)典模擬退火算法的降溫方式為：而快速模擬退火算法的降溫方式為：這兩種方式都能夠使得模擬退火算法收斂于全局最小點。5、SA算法應用范圍與一般要求5、SA算法應用范圍與一般要求初始溫度T0的設定：實驗表明，初溫越大，獲得高質量解的幾率越大，但花費的計算時間將增加。因此，初溫的確定應折衷考慮優(yōu)化質量和優(yōu)化效率，常用方法包括：(1)均勻抽樣一組狀態(tài)，以各狀態(tài)目標值的方差為初溫。(2)隨機產生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標值差

7、Δmax

8、，然后依據(jù)差

9、值，利用一定的函數(shù)確定初溫。比如，t0=－Δmax/pr，其中pr為初始接受概率。(3)利用經(jīng)驗公式給出。5、SA算法應用范圍與一般要求算法終止準則，常用的包括：(1)設置終止溫度的閾值；(2)設置外循環(huán)迭代次數(shù)；(3)算法搜索到的最優(yōu)值連續(xù)若干步保持不變；(4)檢驗系統(tǒng)熵是否穩(wěn)定。6、SA算法的優(yōu)缺點與同類方法相比，SA算法具有以下優(yōu)缺點：優(yōu)點：高效，靈活，通用，初值魯棒性強，適用于并行處理，可用于求解復雜的非線性優(yōu)化問題。缺點：由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此其收斂速度慢，執(zhí)行時間長，算法性能與初始值有

10、關及參數(shù)敏感等缺點。Th