模擬退火算法課件.ppt

《模擬退火算法課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、模擬退火算法SimulatedAnnealingAlgorithmSAA模擬退火算法是什么？是怎樣提出來的？模擬退火算法（SimulatedAnnealing，SA）是一種模擬物理退火的過程而設(shè)計(jì)的優(yōu)化算法。它的基本思想最早在1953年就被Metropolis提出，但直到1983年Kirkpatrick等人才設(shè)計(jì)出真正意義上的模擬退火算法并進(jìn)行應(yīng)用。模擬退火算法的基本思想是怎樣的？模擬退火算法采用類似于物理退火的過程，先在一個(gè)高溫狀態(tài)下（相當(dāng)于算法隨機(jī)搜索），然后逐漸退火，在每個(gè)溫度下（相當(dāng)于算法的每一次狀態(tài)轉(zhuǎn)移）徐徐冷卻（相當(dāng)于算法局部搜索

2、），最終達(dá)到物理基態(tài)（相當(dāng)于算法找到最優(yōu)解）。簡介模擬退火算法的來源是根據(jù)復(fù)雜組合優(yōu)化問題與固體的退火過程之間的相似之處。該算法在系統(tǒng)向著能量減小的趨勢變化過程中，偶爾允許系統(tǒng)跳到能量較高的狀態(tài)，以避開局部最小，最終穩(wěn)定在全局最小。簡介SAA屬于隨機(jī)模擬算法模擬統(tǒng)計(jì)物理學(xué)中物體加熱后冷卻這一退火過程而建立的隨機(jī)優(yōu)化算法，意圖是避免陷入局部極小解，早期用于組合優(yōu)化，后來發(fā)展成一種通用的優(yōu)化算法?；舅枷隨AA是基于MenteCarlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。另一方面，

3、結(jié)合爬山法和隨機(jī)行走。SAA在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。基本思路首先在高溫下進(jìn)行搜索，此時(shí)各狀態(tài)出現(xiàn)概率相差不大，可以很快進(jìn)入“熱平衡狀態(tài)”，這時(shí)進(jìn)行的是一種“粗搜索”，也就是大致找到系統(tǒng)的低能區(qū)域；隨著溫度的逐漸降低，各狀態(tài)出現(xiàn)概率的差距逐漸被擴(kuò)大，搜索精度不斷提高。這就可以越來越準(zhǔn)確的找到網(wǎng)絡(luò)能量函數(shù)的全局最小點(diǎn)。一、模擬退火算法概述二、模擬退火算法的馬氏鏈描述及收

4、斂性三、模擬退火算法關(guān)鍵參數(shù)和操作設(shè)計(jì)四、模擬退火算法的改進(jìn)及其并行性五、模擬退火算法的實(shí)現(xiàn)及應(yīng)用固體退火過程Metropolis準(zhǔn)則組合優(yōu)化與物理退火的相似性模擬退火算法的步驟第一節(jié)模擬退火算法概述1模擬退火算法概述算法的提出模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。—Optimizationbysimulatedannealing,IBMResearchReport算法的目的解決NP復(fù)雜性問題提供有效近似算法；克服優(yōu)化過程陷入局部極?。豢朔踔狄蕾囆?。1.1固體退

5、火過程1、源于對(duì)固體退火過程的模擬；2、采用Metropolis接受準(zhǔn)則；3、用冷卻進(jìn)度表控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似解。固體退火過程的物理圖像和統(tǒng)計(jì)性質(zhì)是SAA的物理背景；Metropolis接受準(zhǔn)則使算法跳離局部最優(yōu)“險(xiǎn)井”；而冷卻進(jìn)度表的合理選擇是算法應(yīng)用的前提。1模擬退火算法概述1.1固體退火過程算法的基礎(chǔ)1模擬退火算法概述固體退火過程什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。1.1固體退火過程固體退火是將固體加熱至融化，再

6、徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過程，屬于熱力學(xué)與統(tǒng)計(jì)物理研究的范疇。由以下三部分組成：加溫過程等溫過程冷卻過程固體在恒定溫度下達(dá)到熱平衡的過程！1模擬退火算法概述固體退火過程加溫過程——增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置，目的是消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——退火過程中要讓溫度慢慢降低，在每一個(gè)溫度下要達(dá)到熱平衡狀態(tài)，對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)滿足自由能較少定律，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體

7、結(jié)構(gòu)。當(dāng)液體凝固為固體的晶態(tài)時(shí)退火過程完成。1.1固體退火過程1模擬退火算法概述數(shù)學(xué)表述在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布溫度低時(shí)能量低的微觀狀態(tài)概率大，溫度趨于零時(shí)，固體幾乎處于概率最大能量最小的基態(tài)。1.1固體退火過程1模擬退火算法概述數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E101模擬退火算法概述數(shù)學(xué)表述若

8、D

9、為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：(1)當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近

10、平均值1/

11、D

12、；(2)狀態(tài)空間存在超過兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/

13、D

14、；(3)當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。1.1