資源描述：
《《模擬退火算法》PPT課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、模擬退火算法（SimulatedAnnealing）1、引子2、SA算法的起源3、SA算法的基本思想4、SA算法的步驟5、SA算法應(yīng)用范圍與一般要求6、SA算法的優(yōu)缺點(diǎn)1、引子在科學(xué)與工程計(jì)算中，經(jīng)常發(fā)生的一個(gè)問題是在Rn中或者是在一個(gè)有界區(qū)域上求某個(gè)非線性函數(shù)f(x)的極小點(diǎn)。在f(x)可導(dǎo)時(shí)，一個(gè)最基本的算法就是最速下降法。這一方法從某一選定的初值開始，利用如下公式進(jìn)行迭代，即然而以速降法為代表的傳統(tǒng)算法具有共同的缺點(diǎn)，它們都不保證求得全局極小，只能保證收斂到一個(gè)由初值決定的局部極小點(diǎn)。每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此
2、只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。2、SA算法的起源SA算法起源于對固體退火過程的模擬。簡單而言，在固體退火時(shí)，先將固體加熱使其溫度充分高，再讓其徐徐冷卻，其物理退火過程由以下三部分組成：加溫過程、等溫過程、冷卻過程。SA算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機(jī)搜索技術(shù)。模擬退火物理退火解粒子狀態(tài)最優(yōu)解能量最低態(tài)設(shè)定初溫熔解過程Metropolis采樣過程等溫過程控制
3、參數(shù)的下降冷卻目標(biāo)函數(shù)能量模擬退火算法與物理退火過程的相似關(guān)系3、SA算法的基本思想在搜索最優(yōu)解的過程中，SA算法除了可以接受優(yōu)化解外，還基于隨機(jī)接受準(zhǔn)則（Metropolis準(zhǔn)則）有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于0。（這使得算法有可能從局部最優(yōu)中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂）SA的思想最早是由Metropolis等在1953年提出的，Metropolis等提出了重要性采樣法，即以概率接受新狀態(tài)。SA算法的思想為：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄的
4、迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。SA算法與其它搜索方法相比，具有如下的特點(diǎn)：以一定的概率接受惡化解；引進(jìn)算法控制參數(shù)；使用對象函數(shù)值進(jìn)行搜索；隱含并行性；搜索復(fù)雜區(qū)域。4、SA算法的基本步驟1)隨機(jī)產(chǎn)生一個(gè)初始解x0，令xbest＝x0并計(jì)算目標(biāo)函數(shù)值E(x0);2)設(shè)置初始溫度T(0)=To，迭代次數(shù)i=1;3)DowhileT(i)>Tmin1)forj=1~k2)對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計(jì)算新的目標(biāo)函數(shù)值E(
5、xnew)，并計(jì)算目標(biāo)函數(shù)值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，則xbest=xnew；4)如果ΔE＞0，則p=exp(-ΔE/T(i));1)如果c=random[0,1]
6、域得到廣泛的研究。SA算法的應(yīng)用需滿足如下三個(gè)方面的要求：（1）對問題的簡明形式的描述即數(shù)學(xué)模型，由解空間、目標(biāo)函數(shù)和初始解三部分構(gòu)成；（2）新解的產(chǎn)生和接受機(jī)制；（3）冷卻進(jìn)度表。冷卻進(jìn)度表是指從某一高溫狀態(tài)T0向低溫狀態(tài)冷卻時(shí)的降溫管理表。假設(shè)時(shí)刻t的溫度用T(t)來表示，則經(jīng)典模擬退火算法的降溫方式為：而快速模擬退火算法的降溫方式為：這兩種方式都能夠使得模擬退火算法收斂于全局最小點(diǎn)。5、SA算法應(yīng)用范圍與一般要求5、SA算法應(yīng)用范圍與一般要求初始溫度T0的設(shè)定：實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計(jì)算時(shí)間將增
7、加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：(1)均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。(2)隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差
8、Δmax
9、，然后依據(jù)差值，利用一定的函數(shù)確定初溫。比如，t0=－Δmax/pr，其中pr為初始接受概率。(3)利用經(jīng)驗(yàn)公式給出。5、SA算法應(yīng)用范圍與一般要求算法終止準(zhǔn)則，常用的包括：(1)設(shè)置終止溫度的閾值；(2)設(shè)置外循環(huán)迭代次數(shù)；(3)算法搜索到的最優(yōu)值連續(xù)若干步保持不變；(4)檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。6、SA算法的優(yōu)缺點(diǎn)與同類方法相比，SA算法具有以下優(yōu)缺點(diǎn)：
10、優(yōu)點(diǎn)：高效，靈活，通用，初值魯棒性強(qiáng)，適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問題。缺點(diǎn)：由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此其收斂速度慢，執(zhí)行時(shí)間長，算法性能與初始值有關(guān)及參數(shù)敏感等缺點(diǎn)。Th
