智能優(yōu)化算法-模擬退火算法課件

1、智能優(yōu)化算法與應(yīng)用湖南大學(xué)電氣學(xué)院自動(dòng)化系自我介紹劉敏，電氣學(xué)院自動(dòng)化系副教授2007-2012年美國(guó)加州大學(xué)博士，博士后2000-2007年北京大學(xué)本科,碩士研究方向：計(jì)算機(jī)視覺，圖像處理聯(lián)系方式 liu_min3參考教材：王耀南, 智能信息處理技術(shù), 高等教育出版社, 2003年8月第1版.王凌, 智能優(yōu)化算法及其應(yīng)用, 清華大學(xué)出版社, 施普林格出版社, 2004.模擬退火算法及其應(yīng)用Simulated Annealing，SA5導(dǎo)言模擬退火算法（Simulated Annealing，SA)是一種通用的優(yōu)化算法。目前，已在：生產(chǎn)調(diào)度、控制工程、計(jì)算機(jī)視覺、神經(jīng)網(wǎng)絡(luò)、圖像處理等工程領(lǐng)域中

2、得到了廣泛應(yīng)用。 1953年，Metropolis等提出SA思想；1983年，Kirkpatrick等將其用于組合優(yōu)化，目的在于：為具有NP復(fù)雜性的問題提供有效的近似求解算法；克服優(yōu)化過程陷入局部極小；克服初值依賴性。 7組合優(yōu)化組合優(yōu)化，作為應(yīng)用數(shù)學(xué)中最年輕而又至關(guān)重要的領(lǐng)域之一，整合了組合數(shù)學(xué)、線性規(guī)劃以及算法理論的方法和技巧。由于它在解決從遠(yuǎn)程通訊到超大規(guī)模集成電路、從產(chǎn)品運(yùn)銷到航班機(jī)組排班等領(lǐng)域內(nèi)困難問題方面的成功，這一領(lǐng)域在過去的十年里取得了巨大的、超乎尋常的發(fā)展。8計(jì)算機(jī)視覺制造業(yè)、檢驗(yàn)識(shí)別、文檔分析、醫(yī)療診斷、軍事、智能電網(wǎng)等領(lǐng)域中各種智能系統(tǒng)中不可分割的一部分。美國(guó)把對(duì)計(jì)算機(jī)視

3、覺的研究列為對(duì)經(jīng)濟(jì)和科學(xué)有廣泛影響的科學(xué)和工程中的重大基本問題，即所謂的重大挑戰(zhàn)（grand challenge）。為計(jì)算機(jī)和機(jī)器人開發(fā)具有與人類水平相當(dāng)?shù)囊曈X能力 。10人臉識(shí)別在FBI，人臉識(shí)別終于要真正發(fā)揮在電影中一樣的作用了。作為國(guó)家的指紋數(shù)據(jù)庫(kù)的更新的一部分，美國(guó)聯(lián)邦調(diào)查局已經(jīng)開始推出了面部識(shí)別，識(shí)別罪犯，反恐。而這些高富帥們的手筆也不是一般的大：$1 billion。11機(jī)器視覺其他應(yīng)用：湖南大學(xué)電氣院指紋打卡 美國(guó)加州大學(xué)實(shí)驗(yàn)室紅膜識(shí)別計(jì)算機(jī)視覺又叫做機(jī)器視覺，掃地機(jī)器人http:/ipd.pps.tv/play_373X1J.html12爬山算法14模擬退火(SA, Simul

4、ated Annealing)思想爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是其搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率接受到E的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。15TSP 問題作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問題(Travelling Salesman Problem，簡(jiǎn)記為TSP)：設(shè)有n個(gè)城市，用數(shù)碼1,n代表。城

5、市i和城市j之間的距離為d(i，j) i, j=1,nTSP問題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短。旅行商問題屬于所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時(shí)間復(fù)雜度是O(N!) 。使用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。17NP 問題P問題：可以在以多項(xiàng)式表達(dá)的時(shí)間內(nèi)求出確切解的問題，也就是說它的計(jì)算復(fù)雜度是一個(gè)多項(xiàng)式。我們通常用的O(n),O(logn),O(n2)等等類似的都是這類問題。O(n) for(i=0;i100;i+)O(n2) for(i=0;i100;i+) for(j=0;j100;j+)18非確定性問題什

6、么是非確定性問題呢？有些計(jì)算問題是確定性的，比如加減乘除之類，你只要按照公式推導(dǎo)，按部就班一步步來(lái)，就可以得到結(jié)果。但是，有些問題是無(wú)法按部就班直接地計(jì)算出來(lái)。比如，找大質(zhì)數(shù)的問題。有沒有一個(gè)公式，你一套公式，就可以一步步推算出來(lái)，下一個(gè)質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。19NP問題NP問題：英文是non-deterministic polynomial,是多項(xiàng)式時(shí)間可以驗(yàn)證的問題。最初是在非確定圖靈機(jī)上，如果一個(gè)問題存在一個(gè)解，那么就先猜它，一定可以在多項(xiàng)式時(shí)間內(nèi)猜到這個(gè)解。（關(guān)鍵是就是不判定這個(gè)問題到底有沒有解）p？=NP 目前還沒有被證實(shí)。也就是還不知道P和NP的關(guān)系，但是可以確定的

7、是P屬于NP。2021模擬退火算法及其應(yīng)用SA算法是基于Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。Monte Carlo 蒙特卡洛歐洲地中海之濱、法國(guó)的東南方，有一個(gè)世界上版圖最小的國(guó)家摩納哥公國(guó)，世人稱之為“賭博之國(guó)”、“袖珍之國(guó)”、“郵票小國(guó)”。22蒙特卡羅有關(guān)Monte Carlo方法歷史背景的最精確描述來(lái)自Jun Liu的專著，他指出一批物理學(xué)家在二戰(zhàn)期間為估算薛定諤方程的本征值而發(fā)明了一種基于統(tǒng)計(jì)抽樣的數(shù)值計(jì)算法，其最初想法歸功于Ulam。后來(lái)Ulam的同事Metropolis將該方法命名為Monte

8、Carlo。1950年代Metropolis和幾名統(tǒng)計(jì)物理學(xué)同事發(fā)表了一篇經(jīng)典論文，提出了Markov Chain Monte Carlo(MCMC)算法。而MCMC法后來(lái)是Bayesian統(tǒng)計(jì)學(xué)能夠不斷前進(jìn)的主要?jiǎng)恿Α?4蒙特卡羅蒙特卡羅模擬是曼哈頓計(jì)劃所用到的模擬的核心部分，在20世紀(jì)50年代蒙特卡羅模擬就用在Los Alamos國(guó)家實(shí)驗(yàn)室發(fā)展氫彈的早期工作中，并流行于物理學(xué)和運(yùn)籌學(xué)研究領(lǐng)域。蘭德公司和美國(guó)空軍是這個(gè)時(shí)期主要的兩個(gè)負(fù)責(zé)資助和傳播蒙特卡羅方法的組織，今天蒙特卡羅模擬也被廣泛應(yīng)用于不同的領(lǐng)域，包括工程，物理學(xué)，研發(fā)，商業(yè)和金融。2527 什么是退火 退火 淬火物理退火過程高溫低

9、溫緩慢下降高能狀態(tài)低能狀態(tài)高溫低溫快速下降高能狀態(tài)高能狀態(tài)退火的作用(1) 降低硬度，改善切削加工性.(2)消除殘余應(yīng)力，穩(wěn)定尺寸，減少變形與裂紋傾向；(3)細(xì)化晶粒，調(diào)整組織，消除組織缺陷。(4)均勻材料組織和成分，改善材料性能或?yàn)橐院鬅崽幚碜鼋M織準(zhǔn)備。在生產(chǎn)中，退火工藝應(yīng)用很廣泛。根據(jù)工件要求退火的目的不同，退火的工藝規(guī)范有多種，常用的有完全退火、球化退火、和去應(yīng)力退火等。28模擬退火算法的基本思想啟發(fā)注意到一個(gè)自然規(guī)則：物質(zhì)總是趨于最低的能態(tài)。水總是向低處流。電子總是向最低能級(jí)的軌道排布。最低能態(tài)是最穩(wěn)定的狀態(tài)。物質(zhì)會(huì)”自動(dòng)”地趨向的最低能態(tài)。模擬退火算法的設(shè)計(jì)與原理猜想物質(zhì)自動(dòng)趨向的最

10、低能態(tài)與函數(shù)最小值之間有相似性！我們能不能設(shè)計(jì)一種算法求函數(shù)最小值，就像物質(zhì)”自動(dòng)”地趨向最低能態(tài)？降溫圖像離散函數(shù)圖像相似性?最小值最低能態(tài)物理模型固體退火退火俗稱固體降溫先把固體加熱至足夠高溫，使固體中所有粒子處于無(wú)序的狀態(tài)（最高的熵值），然后將溫度緩慢下降，粒子漸漸有序（熵值下降），這樣只要溫度上升得足夠高，冷卻過程足夠慢，則所有粒子最終會(huì)處于最低能態(tài)（最低的熵值）。最低能態(tài)時(shí)間溫度模擬退火算法的設(shè)計(jì)與原理類比根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于熱平衡的概率為其中E為溫度T時(shí)的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)?？梢栽O(shè)計(jì)算法：將系統(tǒng)熵值類比為函數(shù)值F，來(lái)模擬這個(gè)退

11、火過程。Metropolis準(zhǔn)則（1953）以概率接受新狀態(tài) p=exp-(Ej-Ei)/kBT 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)； 在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。342.3 模擬退火算法及其應(yīng)用物理退火過程由以下三部分組成： 加溫過程增強(qiáng)粒子熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高時(shí)，固體熔解為液體，消除系統(tǒng)可能存在的非均勻態(tài)，使隨后進(jìn)行的冷卻過程以某一平衡態(tài)為起點(diǎn)。等溫過程對(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)能量逐漸下降，從而得到低能的

12、晶體結(jié)構(gòu)。 352.3 模擬退火算法及其應(yīng)用為了模擬固體在恒定溫度下達(dá)到熱平衡的過程，可采用Monte Carlo方法，該方法簡(jiǎn)單，但必須大量采樣才能得到較精確結(jié)果，計(jì)算量很大。考慮到物理系統(tǒng)傾向于能量較低的狀態(tài)，而熱運(yùn)動(dòng)又妨礙它準(zhǔn)確落到最低態(tài)的圖像，采樣時(shí)著重取那些有重要貢獻(xiàn)的狀態(tài)則可較快達(dá)到較好的結(jié)果。1953年，Metropolis等據(jù)此提出了重要性采樣法（也稱為Metropolis 準(zhǔn)則），即以概率接受新狀態(tài)。362.3 模擬退火算法及其應(yīng)用Metropolis準(zhǔn)則：在溫度t，由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j，兩者的能量分別為Ci和Cj，若Cj t0)所處的狀態(tài)與過程在t0時(shí)刻之前的狀態(tài)無(wú)關(guān)，

13、這個(gè)特性成為無(wú)后效性。無(wú)后效的隨機(jī)過程稱為馬爾科夫過程。馬爾科夫過程中的時(shí)同和狀態(tài)既可以是連續(xù)的，又可以是離散的。我們稱時(shí)間離散、狀態(tài)離散的馬爾科夫過程為馬爾科夫鏈。馬爾科夫鏈中，各個(gè)時(shí)刻的狀態(tài)的轉(zhuǎn)變由一個(gè)狀態(tài)轉(zhuǎn)移的概率矩陣控制。40412.3 模擬退火算法及其應(yīng)用例：考慮一元函數(shù)求最大值的優(yōu)化問題 422.2 模擬退火算法及其應(yīng)用SA在局部極小解處有機(jī)會(huì)跳出，并最終趨于全局最優(yōu)的根本原因：算法通過概率判斷來(lái)接受新狀態(tài)。理論上，初溫充分高、降溫足夠慢、每一溫度下抽樣足夠長(zhǎng)、最終溫度趨于零時(shí)，算法以概率1收斂到全局最優(yōu)解。由于SA的某些收斂條件無(wú)法嚴(yán)格實(shí)現(xiàn)，或即使某些收斂條件可以實(shí)現(xiàn)，但常因?yàn)閷?shí)

14、際應(yīng)用的效果不理想而不被采用。迄今為止，SA的參數(shù)選擇依然是一個(gè)難題，通常只能依據(jù)一定的啟發(fā)式準(zhǔn)則或大量的實(shí)驗(yàn)加以選取。43二.退火過程和Bolzman方程（2）44Bolzman方程二.退火過程和Bolzman方程（3）45溫度 對(duì) 的影響當(dāng) 很大時(shí)，各狀態(tài)的概率幾乎相等SA開始做廣域搜索，隨著溫度的下降 差別擴(kuò)大二.退火過程和Bolzman方程（4）46當(dāng) 時(shí)， 與 的小差別帶來(lái) 和 的巨大差別例如： =90， =100，二.退火過程和Bolzman方程（5）47當(dāng)=100時(shí)二.退火過程和Bolzman方程（6）48當(dāng) =1時(shí)此時(shí)結(jié)論: 時(shí)，以概率1趨于最小能量狀態(tài)二.退火過程和Bolzm

15、an方程（7）492.3 模擬退火算法及其應(yīng)用步驟1：確定編碼方式和能量函數(shù)（目標(biāo)函數(shù)）最常用的編碼方案：實(shí)數(shù)編碼，以實(shí)數(shù)來(lái)表示求解狀態(tài)。 s=1.8函數(shù)優(yōu)化問題中，能量函數(shù)由待優(yōu)化函數(shù)變換而成。若目標(biāo)函數(shù)為最大化問題：C(s)=-f(s)若目標(biāo)函數(shù)為最小化問題：C(s)=f(s)502.3 模擬退火算法及其應(yīng)用步驟2：確定初溫實(shí)驗(yàn)表明，初溫t0越大，獲得高質(zhì)量解的幾率越大，但計(jì)算時(shí)間增加。 初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和效率，常用方法包括： 均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。 隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差|max|，計(jì)算初溫，t0=-max / lnpr初始接受

16、概率pr理論上接近于1。初溫也可選為某個(gè)較大的常數(shù)。512.3 模擬退火算法及其應(yīng)用步驟3：確定初始狀態(tài)（初始解）理論上，初始狀態(tài)可以隨機(jī)取，但為了提高優(yōu)化效率，可采用啟發(fā)式算法快速得到一個(gè)解，并以此為SA的初始狀態(tài)。522.3 模擬退火算法及其應(yīng)用步驟4：狀態(tài)產(chǎn)生函數(shù) （新解產(chǎn)生函數(shù)）設(shè)計(jì)的出發(fā)點(diǎn)是盡可能保證產(chǎn)生的候選解遍布全部解空間。最常用的狀態(tài)產(chǎn)生函數(shù)：snew=sold+為擾動(dòng)幅度參數(shù)，為隨機(jī)擾動(dòng)變量。隨機(jī)擾動(dòng)可服從柯西分布、高斯分布、均勻分布。532.3 模擬退火算法及其應(yīng)用柯西分布：a為尺度參數(shù)高斯分布：為方差，均值為0均勻分布：542.3 模擬退火算法及其應(yīng)用以原點(diǎn)為中心的柯西和

17、高斯分布函數(shù)曲線552.3 模擬退火算法及其應(yīng)用步驟5：狀態(tài)接受函數(shù)該函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵因素，一般以概率方式給出。最常用的狀態(tài)接受函數(shù)： min1, exp-(C(sj)-C(si)/tkrandom0,1 ？設(shè)計(jì)狀態(tài)接受概率，應(yīng)該遵循以下原則： 固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)函數(shù)值上升的候選解的概率；隨溫度下降，接受使目標(biāo)函數(shù)值上升解的概率要逐漸減小當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解。 562.3 模擬退火算法及其應(yīng)用步驟6：內(nèi)循環(huán)終止準(zhǔn)則 或稱Metropolis抽樣穩(wěn)定準(zhǔn)則 常用的抽樣穩(wěn)定準(zhǔn)則包括：檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；連續(xù)

18、若干步的目標(biāo)值變化較小；按一定的步數(shù)抽樣。572.3 模擬退火算法及其應(yīng)用步驟7：退溫函數(shù)溫度的下降方式，用于在外循環(huán)中修改溫度值。目前，最常用的溫度更新函數(shù)：指數(shù)退溫函數(shù)：tk+1=tk為退溫速率，0l，且大小可以不斷變化。 582.3 模擬退火算法及其應(yīng)用步驟8：外循環(huán)終止準(zhǔn)則 即算法終止準(zhǔn)則，用于決定算法何時(shí)結(jié)束。設(shè)置溫度終值te是一種簡(jiǎn)單的方法，SA算法的收斂性理論中要求te趨于零，這顯然不實(shí)際。 通常的做法包括：設(shè)置終止溫度的閾值；設(shè)置外循環(huán)迭代次數(shù)；算法搜索到的最優(yōu)值連續(xù)若干步保持不變；檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。592.2 模擬退火算法及其應(yīng)用從算法流程上看，SA算法包括三函數(shù)兩準(zhǔn)則，即

19、：（新）狀態(tài)產(chǎn)生函數(shù)（新）狀態(tài)接受函數(shù)溫度更新函數(shù)（退溫函數(shù)）內(nèi)循環(huán)終止準(zhǔn)則（抽樣穩(wěn)定準(zhǔn)則）外循環(huán)終止準(zhǔn)則（退火結(jié)束準(zhǔn)則）這些環(huán)節(jié)的設(shè)計(jì)決定SA的優(yōu)化性能。初溫的選擇對(duì)SA算法性能也有很大影響。 初溫、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱為退火歷程。60模擬退火算法流程圖 61SA的模擬要求初始溫度足夠高降溫過程足夠慢終止溫度足夠低三.SA的算法構(gòu)造及步驟（1）62問題的描述及要素三.SA的算法構(gòu)造及步驟（2）63SA的計(jì)算步驟初始化,任選初始解, ,給定初始溫度 ，終止溫度 ，令迭代指標(biāo) 。注：選擇 時(shí)，要足夠高，使隨機(jī)產(chǎn)生一個(gè)鄰域解， 計(jì)算目標(biāo)值增量三.SA的算法構(gòu)造及步驟（3）64若 轉(zhuǎn)步 (j比i好無(wú)條件轉(zhuǎn)移) ；否則產(chǎn)生 (j比i好，有條件轉(zhuǎn)移)。 注：高時(shí)，廣域搜索； 低時(shí)，局域搜索若達(dá)到熱平衡(內(nèi)循環(huán)次數(shù)大于 )轉(zhuǎn)步，否則轉(zhuǎn)步。三.SA的算法構(gòu)造及步驟（4）65 降低 ，若 停止，否則轉(zhuǎn)步。注：降低 的方法有以下兩種流程框圖見下頁(yè)三.SA的算法構(gòu)造及步驟（5）66內(nèi)循環(huán)產(chǎn)生開始停止YNYN，降溫外循環(huán)設(shè)定產(chǎn)生 計(jì)算YYNN67問題的提出單機(jī)極小化總流水時(shí)間的排序問題四個(gè)工作： ， 求 的最優(yōu)順序。