1、模擬退火算法模擬退火算法Simulated Annealing AlgorithmSAA模擬退火算法是什么？是怎樣提出來(lái)的？模擬退火算法是什么？是怎樣提出來(lái)的？模擬退火算法（模擬退火算法（Simulated Annealing，SA）是一種模擬物理退火的過(guò)程而設(shè)計(jì)的優(yōu)化算法。是一種模擬物理退火的過(guò)程而設(shè)計(jì)的優(yōu)化算法。它的基本思想最早在它的基本思想最早在1953年就被年就被Metropolis提出，提出，但直到但直到1983年年Kirkpatrick等人才設(shè)計(jì)出真正等人才設(shè)計(jì)出真正意義上的模擬退火算法并進(jìn)行應(yīng)用。意義上的模擬退火算法并進(jìn)行應(yīng)用。 模擬退火算法的基本思想是怎樣的？模擬退火算法的基本

2、思想是怎樣的？模擬退火算法采用類似于物理退火的過(guò)程，模擬退火算法采用類似于物理退火的過(guò)程，先在一個(gè)高溫狀態(tài)下（相當(dāng)于算法隨機(jī)搜索），然后逐漸退火，先在一個(gè)高溫狀態(tài)下（相當(dāng)于算法隨機(jī)搜索），然后逐漸退火，在每個(gè)溫度下（相當(dāng)于算法的每一次狀態(tài)轉(zhuǎn)移）徐徐冷卻在每個(gè)溫度下（相當(dāng)于算法的每一次狀態(tài)轉(zhuǎn)移）徐徐冷卻（相當(dāng)于算法局部搜索），最終達(dá)到物理基態(tài)（相當(dāng)于算法局部搜索），最終達(dá)到物理基態(tài)（相當(dāng)于算法找到最優(yōu)解）。（相當(dāng)于算法找到最優(yōu)解）。 簡(jiǎn)介簡(jiǎn)介l模擬退火算法的來(lái)源是根據(jù)復(fù)雜組合優(yōu)化問(wèn)題模擬退火算法的來(lái)源是根據(jù)復(fù)雜組合優(yōu)化問(wèn)題與固體的退火過(guò)程之間的相似之處。與固體的退火過(guò)程之間的相似之處。l該算法在

3、系統(tǒng)向著能量減小的趨勢(shì)變化過(guò)程中，該算法在系統(tǒng)向著能量減小的趨勢(shì)變化過(guò)程中，偶爾允許系統(tǒng)跳到能量較高的狀態(tài)，以避開(kāi)局偶爾允許系統(tǒng)跳到能量較高的狀態(tài)，以避開(kāi)局部最小，最終穩(wěn)定在全局最小。部最小，最終穩(wěn)定在全局最小。簡(jiǎn)介簡(jiǎn)介lSAA屬于隨機(jī)模擬算法屬于隨機(jī)模擬算法l模擬統(tǒng)計(jì)物理學(xué)中物體加熱后冷卻這一退火模擬統(tǒng)計(jì)物理學(xué)中物體加熱后冷卻這一退火過(guò)程而建立的過(guò)程而建立的隨機(jī)優(yōu)化算法隨機(jī)優(yōu)化算法，意圖是避免陷，意圖是避免陷入局部極小解，早期用于組合優(yōu)化，后來(lái)發(fā)入局部極小解，早期用于組合優(yōu)化，后來(lái)發(fā)展成一種通用的優(yōu)化算法。展成一種通用的優(yōu)化算法?；舅枷牖舅枷雔SAA是是基于基于Mente Carlo迭代

4、求解策略的一種迭代求解策略的一種隨機(jī)尋優(yōu)算法，其隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)出發(fā)點(diǎn)是基于物理中固體物是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。另一方面，性。另一方面，結(jié)合爬山法和隨機(jī)行走。結(jié)合爬山法和隨機(jī)行走。lSAA在某一初溫下，伴隨溫度參數(shù)的不斷下降，在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部?jī)?yōu)解能概率性地跳數(shù)的全局最優(yōu)解，即在局部?jī)?yōu)解能概率性地跳出并最終趨于全局最優(yōu)。出并最終趨于全局最優(yōu)。 模擬退火算法是一種通用的優(yōu)化算法，目模擬退火算

5、法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。前已在工程中得到了廣泛應(yīng)用。 基本思路基本思路l首先在高溫下進(jìn)行搜索，此時(shí)各狀態(tài)出現(xiàn)概率首先在高溫下進(jìn)行搜索，此時(shí)各狀態(tài)出現(xiàn)概率相差不大，可以很快進(jìn)入相差不大，可以很快進(jìn)入“熱平衡狀態(tài)熱平衡狀態(tài)”，這，這時(shí)進(jìn)行的是一種時(shí)進(jìn)行的是一種“粗搜索粗搜索”，也就是大致找到，也就是大致找到系統(tǒng)的低能區(qū)域；系統(tǒng)的低能區(qū)域；l隨著溫度的逐漸降低，各狀態(tài)出現(xiàn)概率的差距隨著溫度的逐漸降低，各狀態(tài)出現(xiàn)概率的差距逐漸被擴(kuò)大，搜索精度不斷提高。這就可以越逐漸被擴(kuò)大，搜索精度不斷提高。這就可以越來(lái)越準(zhǔn)確的找到網(wǎng)絡(luò)能量函數(shù)的全局最小點(diǎn)。來(lái)越準(zhǔn)確的找到網(wǎng)絡(luò)能量函數(shù)的全局

6、最小點(diǎn)。一、模擬退火算法概述一、模擬退火算法概述二、模擬退火算法的馬氏鏈描述及收斂性二、模擬退火算法的馬氏鏈描述及收斂性三、模擬退火算法關(guān)鍵參數(shù)和操作設(shè)計(jì)三、模擬退火算法關(guān)鍵參數(shù)和操作設(shè)計(jì)四、模擬退火算法的改進(jìn)及其并行性四、模擬退火算法的改進(jìn)及其并行性五、模擬退火算法的實(shí)現(xiàn)及應(yīng)用五、模擬退火算法的實(shí)現(xiàn)及應(yīng)用固體退火過(guò)程固體退火過(guò)程Metropolis準(zhǔn)則準(zhǔn)則組合優(yōu)化與物理退火的相似性組合優(yōu)化與物理退火的相似性模擬退火算法的步驟模擬退火算法的步驟第一節(jié)第一節(jié) 模擬退火算法概述模擬退火算法概述 l算法的提出算法的提出 模擬退火算法最早的思想由模擬退火算法最早的思想由Metropolis等（等（19

7、53）提出，提出，1983年年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。等將其應(yīng)用于組合優(yōu)化。 Optimization by simulated annealing, IBM Research Reportl算法的目的算法的目的 解決解決NP復(fù)雜性復(fù)雜性問(wèn)題問(wèn)題提供有效近似算法提供有效近似算法； 克服優(yōu)化過(guò)程陷入局部極小；克服優(yōu)化過(guò)程陷入局部極?。?克服初值依賴性。克服初值依賴性。1、源于對(duì)固體退火過(guò)程的模擬；、源于對(duì)固體退火過(guò)程的模擬；2、采用、采用Metropolis接受準(zhǔn)則；接受準(zhǔn)則；3、用冷卻進(jìn)度表控制算法進(jìn)程，使算法在多、用冷卻進(jìn)度表控制算法進(jìn)程，使算法在多項(xiàng)式時(shí)間里給出一個(gè)近似

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

9、體達(dá)到某種穩(wěn)定狀態(tài)。態(tài)。 固體退火是將固體加熱至融化，再徐固體退火是將固體加熱至融化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程，徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程，屬于熱力學(xué)與統(tǒng)計(jì)物理研究的范疇。屬于熱力學(xué)與統(tǒng)計(jì)物理研究的范疇。由以下三部分組成：由以下三部分組成：加溫過(guò)程加溫過(guò)程等溫過(guò)程等溫過(guò)程冷卻過(guò)程冷卻過(guò)程固體在恒定溫度下達(dá)固體在恒定溫度下達(dá)到熱平衡的過(guò)程！到熱平衡的過(guò)程！ l固體固體退火過(guò)程退火過(guò)程 加溫過(guò)程加溫過(guò)程增強(qiáng)粒子的熱運(yùn)動(dòng)，增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置，使其偏離平衡位置，目的是目的是消除系統(tǒng)原先可能存在的非均勻態(tài)；消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過(guò)程等溫過(guò)程退火過(guò)

10、程中要讓溫度慢慢降低，在每一個(gè)退火過(guò)程中要讓溫度慢慢降低，在每一個(gè)溫度下要達(dá)到熱平衡狀態(tài)，溫度下要達(dá)到熱平衡狀態(tài)，對(duì)于與環(huán)境換熱而溫度不變對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)的封閉系統(tǒng)滿足自由能較少定律滿足自由能較少定律，系統(tǒng)狀態(tài)的自發(fā)變化，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；系統(tǒng)達(dá)到平衡態(tài)； 冷卻過(guò)程冷卻過(guò)程使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)逐漸下降，從而得到低能的晶體結(jié)構(gòu)。當(dāng)液體凝固為固當(dāng)液體凝固為固體的晶態(tài)時(shí)退火過(guò)程完成。體的晶

11、態(tài)時(shí)退火過(guò)程完成。 l數(shù)學(xué)表述數(shù)學(xué)表述 在溫度在溫度T，分子停留在狀態(tài)，分子停留在狀態(tài)r滿足滿足Boltzmann概率分布概率分布 溫度低時(shí)能量低的微觀狀態(tài)概率大，溫度趨于零時(shí)，溫度低時(shí)能量低的微觀狀態(tài)概率大，溫度趨于零時(shí)，固體幾乎處于概率最大能量最小的基態(tài)。固體幾乎處于概率最大能量最小的基態(tài)。DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子：為概率分布的標(biāo)準(zhǔn)化因常數(shù)。為的能量，表示狀態(tài)機(jī)變量，表示分子能量的一個(gè)隨 l數(shù)學(xué)表述數(shù)學(xué)表述 在在同一個(gè)溫度同一個(gè)溫度T，選定兩個(gè)能量，選定兩個(gè)能量E1E2，有，有 在同一個(gè)溫度，分

12、子停留在能量小的狀態(tài)的概在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。率比停留在能量大的狀態(tài)的概率要大。TkEETkETZEEPEEPBB12121exp1exp)(10l數(shù)學(xué)表述數(shù)學(xué)表述 若若|D|為狀態(tài)空間為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：是具有最低能量的狀態(tài)集合： (1) 當(dāng)當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，本相同，接近平均值接近平均值1/|D|； (2) 狀態(tài)空間狀態(tài)空間存在超過(guò)兩個(gè)不同能量存在超過(guò)兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平時(shí)，具有最低能量狀態(tài)的概率超出平均值均值1/|D| ；

13、 (3) 當(dāng)當(dāng)溫度趨于溫度趨于0時(shí)，分子停留在最低時(shí)，分子停留在最低能量狀態(tài)的概率趨于能量狀態(tài)的概率趨于1。能量能量最低狀態(tài)最低狀態(tài)非非能量最低狀態(tài)能量最低狀態(tài) lMetropolis準(zhǔn)則（準(zhǔn)則（1953）以概率接受新?tīng)顟B(tài)以概率接受新?tīng)顟B(tài) 固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用Monte Carlo方法方法（計(jì)算機(jī)隨機(jī)模擬方法）加以（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。得到比較精確的結(jié)果，計(jì)算量很大。lMonte Carlo模擬退火過(guò)程模擬退火過(guò)程l蒙特卡羅

14、蒙特卡羅(Monte Carlo)方法，或稱計(jì)算機(jī)隨機(jī)方法，或稱計(jì)算機(jī)隨機(jī)模擬方法，是一種基于模擬方法，是一種基于“隨機(jī)數(shù)隨機(jī)數(shù)”的計(jì)算方法。的計(jì)算方法。這一方法源于美國(guó)在第一次世界大戰(zhàn)中研制原這一方法源于美國(guó)在第一次世界大戰(zhàn)中研制原子彈的子彈的“曼哈頓計(jì)劃曼哈頓計(jì)劃”。該計(jì)劃的主持人之一、。該計(jì)劃的主持人之一、數(shù)學(xué)家馮數(shù)學(xué)家馮諾伊曼用馳名世界的賭城諾伊曼用馳名世界的賭城摩納哥摩納哥的的Monte Carlo來(lái)命名這種方法，為它蒙上來(lái)命名這種方法，為它蒙上了一層神秘色彩。了一層神秘色彩。lMonte Carlo方法方法lMonte Carlo方法的基本思想很早以前就被人方法的基本思想很早以前就

15、被人們所發(fā)現(xiàn)和利用。們所發(fā)現(xiàn)和利用。l早在早在17世紀(jì)，人們就知道用事件發(fā)生的世紀(jì)，人們就知道用事件發(fā)生的“頻率頻率”來(lái)決定事件的來(lái)決定事件的“概率概率”。lBuffon試驗(yàn)：試驗(yàn)：19世紀(jì)人們用投針試驗(yàn)的方法來(lái)世紀(jì)人們用投針試驗(yàn)的方法來(lái)求解圓周率求解圓周率。l本世紀(jì)本世紀(jì)40年代電子計(jì)算機(jī)的出現(xiàn)，特別是近年年代電子計(jì)算機(jī)的出現(xiàn)，特別是近年來(lái)高速電子計(jì)算機(jī)的出現(xiàn)，使得用數(shù)學(xué)方法在來(lái)高速電子計(jì)算機(jī)的出現(xiàn)，使得用數(shù)學(xué)方法在計(jì)算機(jī)上大量、快速地模擬這樣的試驗(yàn)成為可計(jì)算機(jī)上大量、快速地模擬這樣的試驗(yàn)成為可能。能。lMonte Carlo方法方法l用民意測(cè)驗(yàn)來(lái)作一個(gè)不嚴(yán)格的比喻。民意測(cè)驗(yàn)用民意測(cè)驗(yàn)來(lái)作一

16、個(gè)不嚴(yán)格的比喻。民意測(cè)驗(yàn)的人不是征詢每一個(gè)登記選民的意見(jiàn)，而是通的人不是征詢每一個(gè)登記選民的意見(jiàn)，而是通過(guò)對(duì)選民進(jìn)行小規(guī)模的抽樣調(diào)查來(lái)確定可能的過(guò)對(duì)選民進(jìn)行小規(guī)模的抽樣調(diào)查來(lái)確定可能的優(yōu)勝者。其基本思想是一樣的。優(yōu)勝者。其基本思想是一樣的。l它需要一個(gè)良好的隨機(jī)數(shù)源。這種方法往往包它需要一個(gè)良好的隨機(jī)數(shù)源。這種方法往往包含一些誤差，但是隨著隨機(jī)抽取樣本數(shù)量的增含一些誤差，但是隨著隨機(jī)抽取樣本數(shù)量的增加，結(jié)果也會(huì)越來(lái)越精確。加，結(jié)果也會(huì)越來(lái)越精確。 lMetropolis準(zhǔn)則（準(zhǔn)則（1953）以概率接受新?tīng)顟B(tài)以概率接受新?tīng)顟B(tài) 若在溫度若在溫度T，當(dāng)前狀態(tài)，當(dāng)前狀態(tài)i 新?tīng)顟B(tài)新?tīng)顟B(tài)j 若若Ej=r

17、androm0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足；抽樣穩(wěn)定準(zhǔn)則滿足； 退溫退溫tk+1=update(tk)并令并令k=k+1； Until 算法終止準(zhǔn)則滿足；算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。輸出算法搜索結(jié)果。 l影響優(yōu)化結(jié)果的主要因素影響優(yōu)化結(jié)果的主要因素 給定初溫給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令，令k=0； Repeat Repeat 產(chǎn)生新?tīng)顟B(tài)產(chǎn)生新?tīng)顟B(tài)sj=Genete(s)； if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足；抽樣穩(wěn)定準(zhǔn)則滿足； 退溫退溫tk+1=up

18、date(tk)并令并令k=k+1； Until 算法終止準(zhǔn)則滿足；算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。輸出算法搜索結(jié)果。三函數(shù)兩準(zhǔn)則三函數(shù)兩準(zhǔn)則初始溫度初始溫度三函數(shù)兩準(zhǔn)則三函數(shù)兩準(zhǔn)則狀態(tài)產(chǎn)生函數(shù)狀態(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)退溫函數(shù)退溫函數(shù)抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則退火結(jié)束準(zhǔn)則退火結(jié)束準(zhǔn)則SAA流程流程確定確定初溫初溫隨機(jī)給定隨機(jī)給定初始解初始解收斂準(zhǔn)收斂準(zhǔn)則則滿足滿足否？否？輸出結(jié)果輸出結(jié)果Y抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則滿足否？滿足否？由當(dāng)前由當(dāng)前狀態(tài)產(chǎn)生狀態(tài)產(chǎn)生新?tīng)顟B(tài)新?tīng)顟B(tài)接受函數(shù)接受函數(shù)成立否？成立否？替換當(dāng)前狀態(tài)替換當(dāng)前狀態(tài)YYNNN退溫退溫保持當(dāng)前狀態(tài)不變保持當(dāng)前狀態(tài)不變 關(guān)鍵

19、環(huán)節(jié)關(guān)鍵環(huán)節(jié)1 1 初溫、初始解初溫、初始解2 2 狀態(tài)產(chǎn)生函數(shù)狀態(tài)產(chǎn)生函數(shù)3 3 狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)4 4 退溫函數(shù)退溫函數(shù)5 5 抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則6 6 收斂準(zhǔn)則收斂準(zhǔn)則SAA特點(diǎn)特點(diǎn)l可以保證全局最優(yōu)可以保證全局最優(yōu)l特別適合組合優(yōu)化問(wèn)題特別適合組合優(yōu)化問(wèn)題l可以隨機(jī)選擇初始解可以隨機(jī)選擇初始解l對(duì)問(wèn)題本身沒(méi)有特別要求，不會(huì)因?yàn)閱?wèn)題對(duì)問(wèn)題本身沒(méi)有特別要求，不會(huì)因?yàn)閱?wèn)題實(shí)例的改變影響性能實(shí)例的改變影響性能l簡(jiǎn)單易行，通用性好簡(jiǎn)單易行，通用性好馬氏鏈描述馬氏鏈描述收斂性收斂性時(shí)齊算法收斂性時(shí)齊算法收斂性非時(shí)齊算法收斂性非時(shí)齊算法收斂性漸近性態(tài)漸近性態(tài)第二節(jié)第二節(jié) SAA的的馬氏

20、鏈描述及收斂性馬氏鏈描述及收斂性 模擬退火算法模擬退火算法(SAA)是將物理退火過(guò)程與是將物理退火過(guò)程與組合優(yōu)化相結(jié)合的一種隨機(jī)迭代尋優(yōu)算法。組合優(yōu)化相結(jié)合的一種隨機(jī)迭代尋優(yōu)算法。數(shù)學(xué)模型描述為數(shù)學(xué)模型描述為 由某一較高初始溫度開(kāi)始，在給定的由某一較高初始溫度開(kāi)始，在給定的鄰域結(jié)構(gòu)中，模擬退火過(guò)程，利用概率特鄰域結(jié)構(gòu)中，模擬退火過(guò)程，利用概率特性與抽樣策略在解空間中隨機(jī)搜索，隨著性與抽樣策略在解空間中隨機(jī)搜索，隨著溫度不斷下降重復(fù)抽樣，用來(lái)優(yōu)化問(wèn)題的溫度不斷下降重復(fù)抽樣，用來(lái)優(yōu)化問(wèn)題的解。解。引言引言設(shè)設(shè) 為所有狀態(tài)構(gòu)成的解空間，為所有狀態(tài)構(gòu)成的解空間，,21ss)(kX為為k時(shí)刻狀態(tài)變量的取

21、值。時(shí)刻狀態(tài)變量的取值。隨機(jī)序列隨機(jī)序列 稱為稱為馬氏鏈馬氏鏈,若若,)(21kkXZn滿足滿足)(|)()(inXjnXPnpij11簡(jiǎn)簡(jiǎn)記記（記憶遺忘功能）（記憶遺忘功能）)1(|)()1(,)1(,)0(|)(10inXjnXPinXiXiXjnXP 一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率)(|)()(inXjnXPnpij11n步轉(zhuǎn)移概率步轉(zhuǎn)移概率)(|)()(iXjnXPpnij0有限狀態(tài)馬氏鏈有限狀態(tài)馬氏鏈若解空間有限。若解空間有限。時(shí)齊馬氏鏈時(shí)齊馬氏鏈)()(,1npnpZnijij模擬退火算法模擬退火算法(SAA)的搜索進(jìn)程：的搜索進(jìn)程： 算法從某一個(gè)初始狀態(tài)開(kāi)始后，每一步算法從某一個(gè)初始狀

22、態(tài)開(kāi)始后，每一步狀態(tài)轉(zhuǎn)移均是在當(dāng)前狀態(tài)的鄰域中隨機(jī)產(chǎn)生狀態(tài)轉(zhuǎn)移均是在當(dāng)前狀態(tài)的鄰域中隨機(jī)產(chǎn)生新?tīng)顟B(tài)，然后以一定概率進(jìn)行接受的。新?tīng)顟B(tài)，然后以一定概率進(jìn)行接受的。 接受概率僅依賴于新?tīng)顟B(tài)和當(dāng)前狀態(tài)，接受概率僅依賴于新?tīng)顟B(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。因此，并由溫度加以控制。因此，SAA對(duì)應(yīng)一個(gè)馬對(duì)應(yīng)一個(gè)馬氏鏈。氏鏈。若固定每一溫度，算法均計(jì)若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度。布，然后下降溫度。時(shí)齊算法時(shí)齊算法非時(shí)齊算法非時(shí)齊算法若無(wú)需各溫度下算法均達(dá)到若無(wú)需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按照一平穩(wěn)分布，但溫度需按照一定的速率下降。或稱非

23、平穩(wěn)定的速率下降。或稱非平穩(wěn)馬氏鏈算法。馬氏鏈算法。SAA基礎(chǔ)理論基礎(chǔ)理論 iNkkiiijijijiijtpijandNjijandNjtagtpji)(10)()(,/ )(exp, 1min,tCCaijji 通通常常令令馬氏鏈模型馬氏鏈模型 iNjiijijigigNjNjigjigg),()(, 0),(/ ),(,SAA要實(shí)現(xiàn)全局收斂必須滿足下列條件：要實(shí)現(xiàn)全局收斂必須滿足下列條件：狀態(tài)可達(dá)性狀態(tài)可達(dá)性初值魯棒性初值魯棒性極限分布存在性極限分布存在性收斂到最優(yōu)解收斂到最優(yōu)解溫度不變，溫度不變，M鏈極限分布存鏈極限分布存在在溫度漸近溫度漸近0，M鏈極限分布存在鏈極限分布存在對(duì)應(yīng)馬氏鏈

24、的狀態(tài)圖是強(qiáng)連通的對(duì)應(yīng)馬氏鏈的狀態(tài)圖是強(qiáng)連通的對(duì)算法的最終結(jié)果不依賴于初值對(duì)算法的最終結(jié)果不依賴于初值定義定義1狀態(tài)狀態(tài)i可達(dá)狀態(tài)可達(dá)狀態(tài)j:00)(|)()(iXjnXPpnijji 定義定義2平穩(wěn)分布平穩(wěn)分布:稱稱 為馬氏鏈的為馬氏鏈的平穩(wěn)分布平穩(wěn)分布,若一步轉(zhuǎn)移概率滿足等式若一步轉(zhuǎn)移概率滿足等式,Zjvj01iijijpvv2.2.1 時(shí)齊算法的收斂性時(shí)齊算法的收斂性 時(shí)齊模擬退火算法的收斂性時(shí)齊模擬退火算法的收斂性結(jié)論結(jié)論：結(jié)論結(jié)論1 時(shí)齊模擬退火算法對(duì)應(yīng)的有限狀態(tài)馬時(shí)齊模擬退火算法對(duì)應(yīng)的有限狀態(tài)馬氏鏈存在平穩(wěn)分布。氏鏈存在平穩(wěn)分布。結(jié)論結(jié)論2 當(dāng)溫度趨于當(dāng)溫度趨于0時(shí)，馬氏鏈以概率時(shí)

25、，馬氏鏈以概率1收斂收斂到最優(yōu)狀態(tài)集，而收斂到非最優(yōu)狀態(tài)的概率到最優(yōu)狀態(tài)集，而收斂到非最優(yōu)狀態(tài)的概率為為0。實(shí)現(xiàn)途徑：實(shí)現(xiàn)途徑：通過(guò)各溫度下各狀態(tài)序列無(wú)限長(zhǎng)通過(guò)各溫度下各狀態(tài)序列無(wú)限長(zhǎng)得以實(shí)現(xiàn)！得以實(shí)現(xiàn)！2.2.2 非時(shí)齊算法的收斂性非時(shí)齊算法的收斂性收斂定理收斂定理 對(duì)退溫函數(shù)加以嚴(yán)格控制，可使得對(duì)退溫函數(shù)加以嚴(yán)格控制，可使得SA算法以概率算法以概率1收斂到全局最優(yōu)收斂到全局最優(yōu)解。解。 可設(shè)計(jì)退溫函數(shù)為可設(shè)計(jì)退溫函數(shù)為, 1, 0,)ln( kmktk m2其中其中 ，則當(dāng)，則當(dāng) 時(shí)，時(shí)，SA算法算法以概率以概率1收斂到全局最優(yōu)解。收斂到全局最優(yōu)解。rL 2.2.3 SA算法漸近性能的逼近

26、算法漸近性能的逼近 收斂可以保證，但是時(shí)間性能不好收斂可以保證，但是時(shí)間性能不好 收斂速度有待研究收斂速度有待研究第三節(jié)第三節(jié) 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)三函數(shù)兩準(zhǔn)則三函數(shù)兩準(zhǔn)則狀態(tài)產(chǎn)生函數(shù)狀態(tài)產(chǎn)生函數(shù)狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)退溫函數(shù)退溫函數(shù)抽樣穩(wěn)定準(zhǔn)則抽樣穩(wěn)定準(zhǔn)則退火結(jié)束準(zhǔn)則退火結(jié)束準(zhǔn)則從算法流程看從算法流程看，SA算法包括三函數(shù)兩準(zhǔn)則算法包括三函數(shù)兩準(zhǔn)則初溫初溫1 狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）設(shè)計(jì)的出發(fā)點(diǎn)：設(shè)計(jì)的出發(fā)點(diǎn)：盡可能保證產(chǎn)生的候選解遍布全部解空間。盡可能保證產(chǎn)生的候選解遍布全部解空間。產(chǎn)生候選解的方式產(chǎn)生候選解的方式候選解

27、產(chǎn)生的概率分布候選解產(chǎn)生的概率分布兩部分兩部分l前者決定由當(dāng)前解產(chǎn)生候選解的方式，后者決前者決定由當(dāng)前解產(chǎn)生候選解的方式，后者決定在當(dāng)前解產(chǎn)生的候選解中選擇不同狀態(tài)的概定在當(dāng)前解產(chǎn)生的候選解中選擇不同狀態(tài)的概率。率。l候選解的產(chǎn)生方式由問(wèn)題的性質(zhì)決定，通常在候選解的產(chǎn)生方式由問(wèn)題的性質(zhì)決定，通常在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式產(chǎn)生，當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式產(chǎn)生，l而鄰域函數(shù)和概率方式可以多樣化設(shè)計(jì)，其中而鄰域函數(shù)和概率方式可以多樣化設(shè)計(jì)，其中概率分布可以是均勻分布、正態(tài)分布、指數(shù)分概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布、柯西分布等。布、柯西分布等。2 狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)

28、目的：目的：盡可能接受優(yōu)化解盡可能接受優(yōu)化解 tC /exp, 1min 狀態(tài)接受函數(shù)一般以概率的方式給狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于出，不同接受函數(shù)的差別主要在于接受接受概率概率的形式不同。的形式不同。固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)函數(shù)值上升的候選解的概率。的概率要大于使目標(biāo)函數(shù)值上升的候選解的概率。隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減小。概率要逐漸減小。當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解。當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解

29、。設(shè)計(jì)狀態(tài)接受概率，應(yīng)遵循的原則：設(shè)計(jì)狀態(tài)接受概率，應(yīng)遵循的原則：3 初溫初溫0t實(shí)驗(yàn)表明：實(shí)驗(yàn)表明：初溫值只要選擇充分大，獲得高初溫值只要選擇充分大，獲得高質(zhì)量解的概率就大！但花費(fèi)計(jì)算時(shí)間增加。質(zhì)量解的概率就大！但花費(fèi)計(jì)算時(shí)間增加。初溫的選擇要足夠高。初溫的選擇要足夠高。初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率。初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率。均勻抽樣一組狀態(tài)，選各狀態(tài)目標(biāo)值的方差均勻抽樣一組狀態(tài)，選各狀態(tài)目標(biāo)值的方差利用經(jīng)驗(yàn)公式利用經(jīng)驗(yàn)公式8 . 0ln0 ppft )(min)(max0jfjfKKtsjsj 充分大充分大隨機(jī)產(chǎn)生一組狀態(tài)，確定兩隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最

30、大目標(biāo)值差，兩狀態(tài)間的最大目標(biāo)值差，然后依據(jù)差值，利用一定的然后依據(jù)差值，利用一定的函數(shù)確定初溫。例如，函數(shù)確定初溫。例如，初始溫度初始溫度溫度更新函數(shù)溫度更新函數(shù)內(nèi)循環(huán)終止準(zhǔn)則內(nèi)循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則退火歷程退火歷程(annealing schedule)4 溫度更新函數(shù)溫度更新函數(shù)衰減量衰減量“以小為宜以小為宜”實(shí)驗(yàn)表明降溫速度越慢，獲得高質(zhì)量解的幾率實(shí)驗(yàn)表明降溫速度越慢，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計(jì)算時(shí)間將同時(shí)增加。越大，但花費(fèi)的計(jì)算時(shí)間將同時(shí)增加。溫度高時(shí)下降的慢些，溫度低時(shí)下降的快些。溫度高時(shí)下降的慢些，溫度低時(shí)下降的快些。即溫度的下降方式，用于在外循環(huán)中修改

31、溫度值。即溫度的下降方式，用于在外循環(huán)中修改溫度值。Nahar及及Skiscim等人把等人把 劃分成劃分成K個(gè)個(gè)小區(qū)間，溫度更新函數(shù)為小區(qū)間，溫度更新函數(shù)為,00 tKktKkKtk, 2 , 1,0 101 kkttKirkpatrick首先提出首先提出被被Johnson,Bonomi及及Lutton采用采用95. 0 取取0.5至至0.99之間之間 5 內(nèi)循環(huán)終止準(zhǔn)則內(nèi)循環(huán)終止準(zhǔn)則檢驗(yàn)?zāi)繕?biāo)函數(shù)值的均值是否穩(wěn)定檢驗(yàn)?zāi)繕?biāo)函數(shù)值的均值是否穩(wěn)定連續(xù)若干步目標(biāo)函數(shù)值的變化較小連續(xù)若干步目標(biāo)函數(shù)值的變化較小按一定的步數(shù)抽樣按一定的步數(shù)抽樣鏈長(zhǎng)鏈長(zhǎng)kL（Metropolis抽樣穩(wěn)定準(zhǔn)則）抽樣穩(wěn)定準(zhǔn)則）用

32、于決定在各溫度下產(chǎn)生候選解的數(shù)目。用于決定在各溫度下產(chǎn)生候選解的數(shù)目。時(shí)齊算法時(shí)齊算法常用常用Metropolis抽樣穩(wěn)定準(zhǔn)則包括抽樣穩(wěn)定準(zhǔn)則包括：非時(shí)齊非時(shí)齊SAA：每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解。每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解。l具體應(yīng)與問(wèn)題規(guī)模成比例。具體應(yīng)與問(wèn)題規(guī)模成比例。l實(shí)驗(yàn)表明高溫時(shí)迭代次數(shù)越多越好，低溫實(shí)驗(yàn)表明高溫時(shí)迭代次數(shù)越多越好，低溫時(shí)迭代次數(shù)可以適當(dāng)減少。時(shí)迭代次數(shù)可以適當(dāng)減少。6 外循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則理論上理論上要求溫度終值趨于零要求溫度終值趨于零設(shè)置終止溫度的閥值設(shè)置終止溫度的閥值設(shè)置外循環(huán)迭代次數(shù)設(shè)置外循環(huán)迭代次數(shù)(6-50)算法搜索到的最優(yōu)值連續(xù)若干步

33、保持不變算法搜索到的最優(yōu)值連續(xù)若干步保持不變optoptrfffe *（算法終止準(zhǔn)則）（算法終止準(zhǔn)則）用于決定算法何時(shí)結(jié)束。用于決定算法何時(shí)結(jié)束。通常的做法包括：通常的做法包括：檢驗(yàn)系統(tǒng)熵是否穩(wěn)定檢驗(yàn)系統(tǒng)熵是否穩(wěn)定三個(gè)參數(shù)三個(gè)參數(shù) 、 和和 值均有顯著影響。值均有顯著影響。kL0t總結(jié)總結(jié)過(guò)大的過(guò)大的 值、值、 值和值和 值均能導(dǎo)致過(guò)長(zhǎng)的值均能導(dǎo)致過(guò)長(zhǎng)的CPU時(shí)間。因而在最終解的質(zhì)量有待較大時(shí)間。因而在最終解的質(zhì)量有待較大 值和值和 值予以保證的前提下，選取較小值予以保證的前提下，選取較小的的 值可以抑制值可以抑制CPU時(shí)間上升的態(tài)勢(shì)。時(shí)間上升的態(tài)勢(shì)。0tkL0tkL模擬退火算法基本要素和設(shè)定

34、方法模擬退火算法基本要素和設(shè)定方法l模擬退火算法是一種通用的隨機(jī)搜索算法，它模擬退火算法是一種通用的隨機(jī)搜索算法，它可用于解決眾多的優(yōu)化問(wèn)題，并已經(jīng)廣泛的應(yīng)可用于解決眾多的優(yōu)化問(wèn)題，并已經(jīng)廣泛的應(yīng)用于其他領(lǐng)域。如用于其他領(lǐng)域。如VLSL設(shè)計(jì)、圖像識(shí)別等。當(dāng)設(shè)計(jì)、圖像識(shí)別等。當(dāng)待解決的問(wèn)題復(fù)雜性較高，而且規(guī)模較大時(shí)，待解決的問(wèn)題復(fù)雜性較高，而且規(guī)模較大時(shí)，在對(duì)問(wèn)題的領(lǐng)域知識(shí)甚少的情況下，采用模擬在對(duì)問(wèn)題的領(lǐng)域知識(shí)甚少的情況下，采用模擬退火算法最合適。因?yàn)槟M退火算法不像其他退火算法最合適。因?yàn)槟M退火算法不像其他確定型啟發(fā)式算法那樣，需要依賴于問(wèn)題的領(lǐng)確定型啟發(fā)式算法那樣，需要依賴于問(wèn)題的領(lǐng)域知

35、識(shí)來(lái)提高算法的性能。域知識(shí)來(lái)提高算法的性能。l但是，從另一方面來(lái)說(shuō)，已知有關(guān)待解決問(wèn)題但是，從另一方面來(lái)說(shuō)，已知有關(guān)待解決問(wèn)題的一些知識(shí)后，模擬退火算法卻無(wú)法充分利用的一些知識(shí)后，模擬退火算法卻無(wú)法充分利用它們，這使得模擬退火算法的優(yōu)點(diǎn)就成了缺點(diǎn)。它們，這使得模擬退火算法的優(yōu)點(diǎn)就成了缺點(diǎn)。如何把傳統(tǒng)的啟發(fā)式搜索方法和模擬退火隨機(jī)如何把傳統(tǒng)的啟發(fā)式搜索方法和模擬退火隨機(jī)搜索算法結(jié)合起來(lái)，這是一個(gè)有待研究的十分搜索算法結(jié)合起來(lái)，這是一個(gè)有待研究的十分有意義的課題。有意義的課題。l模擬退火算法在求解規(guī)模較大的實(shí)際問(wèn)題時(shí)，往模擬退火算法在求解規(guī)模較大的實(shí)際問(wèn)題時(shí)，往往存在以下缺點(diǎn)：往存在以下缺點(diǎn)：（1

36、）收斂速度比較慢。）收斂速度比較慢。（2）盡管理論上只要計(jì)算時(shí)間足夠長(zhǎng)，模擬退火）盡管理論上只要計(jì)算時(shí)間足夠長(zhǎng)，模擬退火法就可以保證以概率法就可以保證以概率1收斂于全局最優(yōu)點(diǎn)。但是收斂于全局最優(yōu)點(diǎn)。但是在實(shí)際算法的實(shí)現(xiàn)過(guò)程中，由于計(jì)算速度和時(shí)間在實(shí)際算法的實(shí)現(xiàn)過(guò)程中，由于計(jì)算速度和時(shí)間的限制，在優(yōu)化效果和計(jì)算時(shí)間二者之間存在矛的限制，在優(yōu)化效果和計(jì)算時(shí)間二者之間存在矛盾，因而難以保證計(jì)算結(jié)果為全局最優(yōu)點(diǎn)，優(yōu)化盾，因而難以保證計(jì)算結(jié)果為全局最優(yōu)點(diǎn)，優(yōu)化效果不甚理想。效果不甚理想。 （3）在）在每一溫度下很難判定是否達(dá)到了平衡狀態(tài)。每一溫度下很難判定是否達(dá)到了平衡狀態(tài)。l為此，人們對(duì)模擬退火算法提

37、出了各種各樣的為此，人們對(duì)模擬退火算法提出了各種各樣的改進(jìn)，其中包括并行模擬退火算法、快速模擬改進(jìn)，其中包括并行模擬退火算法、快速模擬退火算法（退火算法（Cauchy機(jī)）和對(duì)模擬退火算法中各機(jī)）和對(duì)模擬退火算法中各個(gè)函數(shù)和參數(shù)的重新設(shè)計(jì)等。個(gè)函數(shù)和參數(shù)的重新設(shè)計(jì)等。SA算法直接簡(jiǎn)單模擬固體退火。算法直接簡(jiǎn)單模擬固體退火。特點(diǎn)：特點(diǎn)：思路清晰、原理簡(jiǎn)單、使用靈活、應(yīng)用廣泛思路清晰、原理簡(jiǎn)單、使用靈活、應(yīng)用廣泛同時(shí)，由于其直接性和簡(jiǎn)單化，也存在不足同時(shí)，由于其直接性和簡(jiǎn)單化，也存在不足與弊病，使其應(yīng)用及性能受到一定影響。與弊病，使其應(yīng)用及性能受到一定影響。第四節(jié)第四節(jié) 模擬退火算法的改進(jìn)及并行性模

38、擬退火算法的改進(jìn)及并行性不同不同p值對(duì)值對(duì)CHN144實(shí)例測(cè)得實(shí)例測(cè)得 值值0tp0t950.19904900.800.600.700.100.9908494033622459801pftln0 l模擬退火算法的優(yōu)點(diǎn)模擬退火算法的優(yōu)點(diǎn) 質(zhì)量高；質(zhì)量高； 初值魯棒性強(qiáng)；初值魯棒性強(qiáng)； 簡(jiǎn)單、通用、易實(shí)現(xiàn)。簡(jiǎn)單、通用、易實(shí)現(xiàn)。l模擬退火算法的缺點(diǎn)模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過(guò)程較長(zhǎng)。樣，因此優(yōu)化過(guò)程較長(zhǎng)。l改進(jìn)的可行方案改進(jìn)的可行方案

39、（1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)；）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)； （2）設(shè)計(jì)高效的退火歷程；）設(shè)計(jì)高效的退火歷程； （3）避免狀態(tài)的迂回搜索；）避免狀態(tài)的迂回搜索； （4）采用并行搜索結(jié)構(gòu)；）采用并行搜索結(jié)構(gòu)； （5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式；）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式； （6）選擇合適的初始狀態(tài)；）選擇合適的初始狀態(tài)； （7）設(shè)計(jì)合適的算法終止準(zhǔn)則。）設(shè)計(jì)合適的算法終止準(zhǔn)則。 l改進(jìn)的方式改進(jìn)的方式：增加某些新的環(huán)節(jié)：增加某些新的環(huán)節(jié) （1）增加升溫或重升溫過(guò)程，避免陷入局部極??；）增加升溫或重升溫過(guò)程，避免陷入局部極??； （2）增加記憶功能（記憶）增加記憶功能（記憶“B

40、est so far”狀態(tài)）；狀態(tài)）； （3）增加補(bǔ)充搜索過(guò)程（以最優(yōu)結(jié)果為初始解）；）增加補(bǔ)充搜索過(guò)程（以最優(yōu)結(jié)果為初始解）； （4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)；區(qū)域內(nèi)的最優(yōu)狀態(tài)； （5）結(jié)合其它搜索機(jī)制的算法；）結(jié)合其它搜索機(jī)制的算法； （6）上述各方法的綜合。）上述各方法的綜合。 l改進(jìn)的思路改進(jìn)的思路 （1）記錄）記錄“Best so far”狀態(tài)，并即時(shí)更新；狀態(tài)，并即時(shí)更新； （2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù)提下減少

41、計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù) m1 步保持不變則認(rèn)為步保持不變則認(rèn)為Metropolis抽樣穩(wěn)定，若抽樣穩(wěn)定，若連續(xù)連續(xù) m2 次退溫過(guò)程中所得最優(yōu)解不變則認(rèn)為算次退溫過(guò)程中所得最優(yōu)解不變則認(rèn)為算法收斂。法收斂。l改進(jìn)的退火過(guò)程改進(jìn)的退火過(guò)程 （1）給定初溫）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為當(dāng)前狀態(tài)為s(0)=s，i=p=0； （2）令）令t=ti，以，以t，s*和和s(i)調(diào)用改進(jìn)的抽樣過(guò)程，返回其所調(diào)用改進(jìn)的抽樣過(guò)程，返回其所得最優(yōu)解得最優(yōu)解s*和當(dāng)前狀態(tài)和當(dāng)前狀態(tài)s(k)，令當(dāng)前狀態(tài)，令當(dāng)前狀態(tài)s(i)=s(k)； （

42、3）判斷）判斷C(s*)m2? 若是，則轉(zhuǎn)第若是，則轉(zhuǎn)第(6)步；否則，返回第步；否則，返回第(2)步；步； （6）以最優(yōu)解）以最優(yōu)解s*作為最終解輸出，停止算法。作為最終解輸出，停止算法。l改進(jìn)的抽樣過(guò)程改進(jìn)的抽樣過(guò)程 （1）令）令k=0時(shí)的初始當(dāng)前狀態(tài)為時(shí)的初始當(dāng)前狀態(tài)為s(0)=s(i)，q=0； （2）由狀態(tài)）由狀態(tài)s通過(guò)狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新?tīng)顟B(tài)通過(guò)狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新?tīng)顟B(tài)s，計(jì)算增量，計(jì)算增量C=C(s)-C(s)； （3）若）若CC(s)? 若是，則令若是，則令s*=s，q=0；否則，令；否則，令q=q+1。若。若C0，則，則以概率以概率exp(-C/t)接受接受s作為下一當(dāng)前狀態(tài)；作

43、為下一當(dāng)前狀態(tài)； （4）令）令k=k+1，判斷，判斷qm1? 若是，則轉(zhuǎn)第若是，則轉(zhuǎn)第(5)步；否則，返步；否則，返回第回第(2)步；步； （5）將當(dāng)前最優(yōu)解）將當(dāng)前最優(yōu)解s*和當(dāng)前狀態(tài)和當(dāng)前狀態(tài)s(k)返回改進(jìn)退火過(guò)程。返回改進(jìn)退火過(guò)程。TINA lTime-invariant noise algorithml狀態(tài)產(chǎn)生函數(shù)中擾動(dòng)強(qiáng)度不隨時(shí)間改變，而是和能量大小相關(guān)，能量大的擾動(dòng)大，能量小的擾動(dòng)小，能量為零，擾動(dòng)也為零，算法停止。MTRSAl單調(diào)升溫(Monotonic temperature rising) SAl在算法退火后期，溫度很低且陷入局部極小解的時(shí)，算法很難跳出。因此，可以適當(dāng)重新

44、提高溫度，促使算法跳出。SAMGl記憶指導(dǎo)SA(Simulated Annealing with Memmory Guidance ,簡(jiǎn)記為SAMG)l增加一個(gè)記憶裝置，存儲(chǔ)算法計(jì)算過(guò)程產(chǎn)生的最好的解，以這個(gè)解為最終解。自適應(yīng)SAl自適應(yīng)自適應(yīng)SA算法算法, l根據(jù)鄰域搜索進(jìn)展的反饋信息根據(jù)鄰域搜索進(jìn)展的反饋信息, 自適應(yīng)確定溫度變化自適應(yīng)確定溫度變化和鄰域搜索強(qiáng)度和鄰域搜索強(qiáng)度l特點(diǎn)：特點(diǎn)：l1) 退火過(guò)程中溫度參數(shù)變化符合幅值遞減的下降總退火過(guò)程中溫度參數(shù)變化符合幅值遞減的下降總趨勢(shì)趨勢(shì), 但不排除局部升溫的可能但不排除局部升溫的可能, 以保證尋求到合適以保證尋求到合適的溫度序列的溫度序列

45、, 避免陷入局部最優(yōu)避免陷入局部最優(yōu);l2) 算法的終止條件依據(jù)退火溫度和鄰域搜索進(jìn)展?fàn)钏惴ǖ慕K止條件依據(jù)退火溫度和鄰域搜索進(jìn)展?fàn)顟B(tài)設(shè)計(jì)態(tài)設(shè)計(jì);l3) 每一溫度下算法的迭代次數(shù)隨溫度下降而遞增每一溫度下算法的迭代次數(shù)隨溫度下降而遞增, 鄰鄰域搜索強(qiáng)度依其對(duì)目標(biāo)函數(shù)的貢獻(xiàn)動(dòng)態(tài)分配域搜索強(qiáng)度依其對(duì)目標(biāo)函數(shù)的貢獻(xiàn)動(dòng)態(tài)分配;l4) 溫度變化、鄰域搜索和終止條件的控制機(jī)制由算溫度變化、鄰域搜索和終止條件的控制機(jī)制由算法過(guò)程自動(dòng)觸發(fā)。法過(guò)程自動(dòng)觸發(fā)。1、操作并行性操作并行性：各個(gè)環(huán)節(jié)同時(shí)處理；：各個(gè)環(huán)節(jié)同時(shí)處理；2、進(jìn)程并行性進(jìn)程并行性：同時(shí)多個(gè)算法運(yùn)行；：同時(shí)多個(gè)算法運(yùn)行；3、空間并行性空間并行性：解空

46、間分解分別處理，最終組：解空間分解分別處理，最終組合。合。全過(guò)程并行性全過(guò)程并行性子進(jìn)程并行性子進(jìn)程并行性第五節(jié)第五節(jié) 算法的實(shí)現(xiàn)與應(yīng)用算法的實(shí)現(xiàn)與應(yīng)用引言引言SAA應(yīng)用應(yīng)用的一般形式：的一般形式： 從選定的初始解開(kāi)始，在借助于控制參從選定的初始解開(kāi)始，在借助于控制參數(shù)數(shù)t遞減時(shí)產(chǎn)生的一系列遞減時(shí)產(chǎn)生的一系列Markov鏈中，利用鏈中，利用一個(gè)新解產(chǎn)生裝置和接受準(zhǔn)則，重復(fù)進(jìn)行包一個(gè)新解產(chǎn)生裝置和接受準(zhǔn)則，重復(fù)進(jìn)行包括括“產(chǎn)生新解產(chǎn)生新解-計(jì)算目標(biāo)函數(shù)差計(jì)算目標(biāo)函數(shù)差-判斷是判斷是否接受新解否接受新解-接受接受(或舍棄或舍棄)新解新解”這四個(gè)這四個(gè)任務(wù)的實(shí)驗(yàn)，不斷對(duì)當(dāng)前解迭代，從而達(dá)到任務(wù)的實(shí)驗(yàn)

47、，不斷對(duì)當(dāng)前解迭代，從而達(dá)到使目標(biāo)函數(shù)使目標(biāo)函數(shù)最優(yōu)最優(yōu)的執(zhí)行過(guò)程。的執(zhí)行過(guò)程。SAA實(shí)現(xiàn)實(shí)現(xiàn)l通用框架通用框架l確定問(wèn)題編碼方案確定問(wèn)題編碼方案l設(shè)計(jì)初始溫度、終止溫度和溫度下降策略設(shè)計(jì)初始溫度、終止溫度和溫度下降策略（退溫函數(shù)）（退溫函數(shù)）l設(shè)計(jì)能量函數(shù)設(shè)計(jì)能量函數(shù)l設(shè)定穩(wěn)定準(zhǔn)則設(shè)定穩(wěn)定準(zhǔn)則l設(shè)計(jì)產(chǎn)生新解的方式（狀態(tài)產(chǎn)生函數(shù)）設(shè)計(jì)產(chǎn)生新解的方式（狀態(tài)產(chǎn)生函數(shù)）l設(shè)計(jì)設(shè)計(jì)Metropolis接受準(zhǔn)則（狀態(tài)接受函數(shù)）接受準(zhǔn)則（狀態(tài)接受函數(shù)）l生成初始狀態(tài)生成初始狀態(tài)1、數(shù)學(xué)模型、數(shù)學(xué)模型對(duì)問(wèn)題的簡(jiǎn)明描述。對(duì)問(wèn)題的簡(jiǎn)明描述。解空間解空間目標(biāo)函數(shù)目標(biāo)函數(shù)初始解初始解所有所有可能解可能解的集合，它限

48、定了初的集合，它限定了初始解選取和新解產(chǎn)生的范圍始解選取和新解產(chǎn)生的范圍對(duì)問(wèn)題的優(yōu)化目標(biāo)的數(shù)學(xué)描述，對(duì)問(wèn)題的優(yōu)化目標(biāo)的數(shù)學(xué)描述，易計(jì)算，對(duì)應(yīng)關(guān)系明確易計(jì)算，對(duì)應(yīng)關(guān)系明確算法開(kāi)始迭代的起點(diǎn)，它的選取算法開(kāi)始迭代的起點(diǎn)，它的選取使算法能導(dǎo)出較好的最終解使算法能導(dǎo)出較好的最終解2、新解的產(chǎn)生和接受機(jī)制、新解的產(chǎn)生和接受機(jī)制產(chǎn)生新解產(chǎn)生新解由產(chǎn)生裝置從當(dāng)前解的解空間中產(chǎn)生。由產(chǎn)生裝置從當(dāng)前解的解空間中產(chǎn)生。計(jì)算目標(biāo)函數(shù)值之差計(jì)算目標(biāo)函數(shù)值之差最快的方法是按增量計(jì)算。最快的方法是按增量計(jì)算。判斷新解是否被接受判斷新解是否被接受準(zhǔn)則準(zhǔn)則Metropolis.)/exp(,001ftffp新解代替當(dāng)前解新解

49、代替當(dāng)前解代替變換部分，修正目標(biāo)函數(shù)值。代替變換部分，修正目標(biāo)函數(shù)值。3、溫度更新函數(shù)、溫度更新函數(shù)關(guān)鍵參數(shù)：初溫、溫度降低函數(shù)、馬氏關(guān)鍵參數(shù)：初溫、溫度降低函數(shù)、馬氏鏈長(zhǎng)度、停止準(zhǔn)則。鏈長(zhǎng)度、停止準(zhǔn)則。SAA求解求解TSPl關(guān)鍵問(wèn)題關(guān)鍵問(wèn)題l如何由舊的解產(chǎn)生新的解如何由舊的解產(chǎn)生新的解l方式很多方式很多l(xiāng)相鄰兩位置對(duì)換相鄰兩位置對(duì)換變動(dòng)最小變動(dòng)最小l任意兩位置對(duì)換任意兩位置對(duì)換l單點(diǎn)位置移動(dòng)單點(diǎn)位置移動(dòng)l子排列位置移動(dòng)子排列位置移動(dòng)l子排列反序子排列反序l子排列位置移動(dòng)且反序子排列位置移動(dòng)且反序變動(dòng)最大變動(dòng)最大l理論已經(jīng)證明上述所有方式都收斂理論已經(jīng)證明上述所有方式都收斂l實(shí)際驗(yàn)證收斂性能差

50、異很大實(shí)際驗(yàn)證收斂性能差異很大1、組合優(yōu)化問(wèn)題的求解、組合優(yōu)化問(wèn)題的求解數(shù)學(xué)模型數(shù)學(xué)模型 一個(gè)商人欲到一個(gè)商人欲到 個(gè)城市推銷商品，每?jī)蓚€(gè)城市推銷商品，每?jī)蓚€(gè)城市個(gè)城市 和和 之間的距離為之間的距離為 ，如何選擇，如何選擇一條道路使得商人每個(gè)城市走一遍后回到起一條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路經(jīng)最短。點(diǎn)且所走路經(jīng)最短。ijdjin 解空間解空間),(),( | ),(的循環(huán)排列為nSnn212121目標(biāo)函數(shù)目標(biāo)函數(shù)niniidf1211),(初始解初始解),(n21選為選為新解的產(chǎn)生新解的產(chǎn)生1、互換操作、互換操作(SWAP)隨機(jī)交換兩個(gè)不同城市的位置。隨機(jī)交換兩個(gè)不同城市的位置

51、。2、逆序操作、逆序操作(INV)兩個(gè)不同隨機(jī)位置的城市逆序。兩個(gè)不同隨機(jī)位置的城市逆序。3、插入操作、插入操作(INS)隨機(jī)選擇某個(gè)城市插入到不同隨機(jī)位置。隨機(jī)選擇某個(gè)城市插入到不同隨機(jī)位置。)(326897145) 326497185() 326417985() 326971485(101 kktt衰減函數(shù)衰減函數(shù)8 . 0ln0 ppft 初值初值20 kL馬氏鏈長(zhǎng)馬氏鏈長(zhǎng)停止準(zhǔn)則停止準(zhǔn)則設(shè)計(jì)終止溫度的閥值設(shè)計(jì)終止溫度的閥值設(shè)計(jì)外循環(huán)迭代次數(shù)設(shè)計(jì)外循環(huán)迭代次數(shù)算法搜索到的最優(yōu)值連續(xù)若干算法搜索到的最優(yōu)值連續(xù)若干步保持不變步保持不變 lTSP Benchmark 問(wèn)題問(wèn)題 41 94;37

52、 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 50l算法流程算法流程 l初始溫度的計(jì)算初始溫度的計(jì)算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/log(0.9); l狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì) （1）互換操作，隨機(jī)交換兩個(gè)城市的順序；）互換操作，隨機(jī)交換兩個(gè)城市的順序； （2）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序；）逆序操作，兩個(gè)隨機(jī)位置間的城市逆序； （3）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。）插入操作，隨機(jī)選擇某點(diǎn)插入某隨機(jī)位置。 28159346728341956723