模擬退火算法報(bào)告

1、模擬退火算法一 定義1 概念什么是退火？在熱力學(xué)上，退火現(xiàn)象指物體逐漸降溫的物理現(xiàn)象，溫度愈低，物體的能量狀態(tài)會(huì)低；夠低后，液體開始冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。大自然在緩慢降溫（亦即，退火）時(shí)，可“找到”最低能量狀態(tài)：結(jié)晶。但是，如果過程過急過快，快速降溫（亦稱淬煉）時(shí)，會(huì)導(dǎo)致不是最低能態(tài)的非晶形。如下圖所示，首先（左圖）物體處于非晶體狀態(tài)。我們將固體加溫至充分高（中圖），再讓其徐徐冷卻，也就退火（右圖）。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小（此時(shí)物體以晶體形態(tài)呈現(xiàn)）。似乎，大自然

2、知道慢工出細(xì)活：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安頓位置，則逐漸地，到最后可得到最低能態(tài)，系統(tǒng)最安穩(wěn)。模擬退火算法(SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火

3、其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。在迭代更新可行解時(shí)，以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以下圖為例，假定初始解為左邊藍(lán)色點(diǎn)A，模擬退火算法會(huì)快速搜索到局部最優(yōu)解B，但在搜索到局部最優(yōu)解后，不是就此結(jié)束，而是會(huì)以一定的概率接受到左邊的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)全局最優(yōu)點(diǎn)D，于是就跳出了局部最小值。 根據(jù)熱力學(xué)的原理，在溫度為T時(shí)，出現(xiàn)能量差dE的降溫的概率為P(dE)，表示為: 。其中k是波爾茲曼常數(shù)，值為，exp表示自然指數(shù)，且dE<0。因此dE/kT<0，所以

4、P(dE)函數(shù)的取值范圍是(0,1)。滿足概率密度函數(shù)的定義。其實(shí)這條公式更直觀意思就是：溫度越高，出現(xiàn)一次能量差為P(dE)的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。在實(shí)際問題中，這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過程。假定當(dāng)前可行解為x，迭代更新后的解為x_new，那么對應(yīng)的“能量差”定義為：，其對應(yīng)的一定概率為：2 SA算法基本要素(1) 狀態(tài)空間與狀態(tài)產(chǎn)生函數(shù)1） 搜索空間也稱為狀態(tài)空間，它由經(jīng)過編碼的可行解的集合組成。2）狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）應(yīng)盡可能保證產(chǎn)生的候選解遍布全部解空間。通常由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。3）候選解一般采

5、用按照某一概率密度函數(shù)對解空間進(jìn)行隨機(jī)采樣來獲得。4）概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等。(2) 狀態(tài)轉(zhuǎn)移概率1） 狀態(tài)轉(zhuǎn)移概率是指從一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)移概率。2）通俗的理解是接受一個(gè)新解為當(dāng)前解的概率。3）它與當(dāng)前的溫度參數(shù)T有關(guān)，隨溫度下降而減小。4）一般采用Metropolis準(zhǔn)則。(3) 內(nèi)循環(huán)終止準(zhǔn)則也稱Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。常用的抽樣穩(wěn)定準(zhǔn)則包括：1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定。2）連續(xù)若干步的目標(biāo)值變化較小。3）按一定的步數(shù)抽樣。(4) 外循環(huán)終止準(zhǔn)則即算法終止準(zhǔn)則，常用的包括：1）設(shè)置終止溫度的閾值。2）設(shè)置外循環(huán)

6、迭代次數(shù)。3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變。4）檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。3 算法步驟(1) 初始化：初始溫度T（充分大），溫度下限Tmin（充分?。跏冀鉅顟B(tài)x(是算法迭代的起點(diǎn))，每個(gè)T值的迭代次數(shù)L；(2) 對l=1,2,.,L做第(3)至第(6)步；(3) 產(chǎn)生新解x_new: ( x_new = x + x )；(4) 利計(jì)算增量f=f(x_new)f(x)，其中f(x)為優(yōu)化目標(biāo)；(5) 若f < 0 (若尋找最小值，f > 0)則接受x_new作為新的當(dāng)前解，否則以概率接受x_new作為新的當(dāng)前解；(6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。(終止條

7、件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。)；(7) T逐漸減少，且T>Tmin，然后轉(zhuǎn)第(2)步。4 SA算法的優(yōu)缺點(diǎn)SA算法很容易找到最優(yōu)解，但是參數(shù)難以控制，不能保證一次就收斂到最優(yōu)值，一般需要多次嘗試才能獲得（大部分情況下還是會(huì)陷入局部最優(yōu)值）。觀察模擬退火算法的過程，發(fā)現(xiàn)其主要存在如下三個(gè)參數(shù)問題：(1) 溫度T的初始值設(shè)置問題 溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。(2) 退火速度問題，即每個(gè)T值的迭代次數(shù)

8、0;模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的“充分”搜索是相當(dāng)必要的，但這也需要計(jì)算時(shí)間。循環(huán)次數(shù)增加必定帶來計(jì)算開銷的增大。(3) 溫度管理問題 溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式：，為了保證較大的搜索空間，一般取接近于1的值，如0.95、0.9。5 SA算法的改進(jìn)（1） 設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)，使其根據(jù)搜索進(jìn)程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性；（2）設(shè)計(jì)高效的退火策略；（3）避免狀態(tài)的迂回搜索；（4）采用并行搜索結(jié)構(gòu)；（5）為避免陷入局部極小，改進(jìn)對

9、溫度的控制方式；（6）選擇合適的初始狀態(tài)；（7）設(shè)計(jì)合適的算法終止準(zhǔn)則。也可通過增加某些環(huán)節(jié)而實(shí)現(xiàn)對模擬退火算法的改進(jìn)。主要的改進(jìn)方式包括：(1) 增加升溫或重升溫過程。在算法進(jìn)程的適當(dāng)時(shí)機(jī)，將溫度適當(dāng)提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進(jìn)程中的當(dāng)前狀態(tài)，避免算法在局部極小解處停滯不前。(2) 增加記憶功能。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解，可通過增加存儲(chǔ)環(huán)節(jié)，將一些在這之前好的態(tài)記憶下來。(3) 增加補(bǔ)充搜索過程。即在退火過程結(jié)束后，以搜索到的最優(yōu)解為初始狀態(tài)，再次執(zhí)行模擬退火過程或局部性搜索。(4) 對每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)

10、狀態(tài)，而非標(biāo)準(zhǔn)SA的單次比較方式。(5) 結(jié)合其他搜索機(jī)制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應(yīng)用。二 SA算法的應(yīng)用模擬退火算法的應(yīng)用很廣泛，可以高效地求解NP完全問題，如TSP問題(Travelling Salesman Problem，簡記為TSP)、最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)等等。模擬退火算法作為一種通用的隨機(jī)搜索算法，現(xiàn)已廣泛用于VLSI設(shè)計(jì)、圖像識別和神經(jīng)網(wǎng)計(jì)算機(jī)的研究。模擬退火算法的應(yīng)用如下：模擬退火算法作為一種通

11、用的隨機(jī)搜索算法，現(xiàn)已廣泛用于VLSI設(shè)計(jì)、圖像識別和神經(jīng)網(wǎng)計(jì)算機(jī)的研究。模擬退火算法的應(yīng)用如下：1) 模擬退火算法在VLSI設(shè)計(jì)中的應(yīng)用利用模擬退火算法進(jìn)行VLSI的最優(yōu)設(shè)計(jì)，是目前模擬退火算法最成功的應(yīng)用實(shí)例之一。用模擬退火算法幾乎可以很好地完成所有優(yōu)化的VLSI設(shè)計(jì)工作。如全局布線、布板、布局和邏輯最小化等等。2) 模擬退火算法在神經(jīng)網(wǎng)計(jì)算機(jī)中的應(yīng)用 模擬退火算法具有跳出局部最優(yōu)陷阱的能力。在Boltzmann機(jī)中，即使系統(tǒng)落入了局部最優(yōu)的陷阱，經(jīng)過一段時(shí)間后，它還能再跳出來，再系統(tǒng)最終將往全局最優(yōu)值的方向收斂。3) 模擬退火算法在圖像處理中的應(yīng)用模擬退火算法可用來進(jìn)行圖像恢復(fù)

12、等工作，即把一幅被污染的圖像重新恢復(fù)成清晰的原圖，濾掉其中被畸變的部分。因此它在圖像處理方面的應(yīng)用前景是廣闊的。其中，SA算法在圖像處理領(lǐng)域應(yīng)用比較廣泛。比如：1） SA算法在多閾值圖像分割中的應(yīng)用圖像分割是圖像處理與計(jì)算機(jī)視覺領(lǐng)域中最為基礎(chǔ)和關(guān)鍵的任務(wù)之一,是對圖像進(jìn)行視覺分析和模式識別的前提。它不僅可以大量壓縮數(shù)據(jù),減少存儲(chǔ)容量,而且能極大地簡化后續(xù)處理步驟。在眾多圖像分割方法中,閾值分割主要利用圖像中目標(biāo)與背景在灰度特征上的差異將圖像劃分為若干部分。因?qū)崿F(xiàn)簡單、計(jì)算量小、性能較穩(wěn)定,閾值分割已成為最基本和應(yīng)用最廣泛的分割技術(shù)。1979年日本學(xué)者大津提出了最大類間方差法因計(jì)算方法簡單、自適

13、應(yīng)強(qiáng)而成為使用最廣泛的圖像閾值自動(dòng)選取方法之一。但傳統(tǒng)的Otsu是采用遍歷的方式尋找使類間方差最大的閾值T,計(jì)算量會(huì)隨分類數(shù)增加呈幾何級數(shù)增長,這在很大程度上限制了Otsu算法的應(yīng)用，為了解決多閾值圖像分割時(shí)最大類間方差法計(jì)算量龐大的問題，引入了SA算法，用模擬退火演進(jìn)代替窮舉法搜索最優(yōu)閾值向量可以使計(jì)算量大大減少。然而為了能夠更快地逼近最優(yōu)值，需要對初始閾值做處理，由直方圖提取初始閾值向量的任務(wù)分如下三步進(jìn)行：a) 對直方圖進(jìn)行高斯濾波。圖像的直方圖包含了圖像的分類信息,但它通常是一條呈現(xiàn)很多微小波峰的不光滑曲線,從原始直方圖很難識別和提取出符合應(yīng)用要求的閾值向量。b) 計(jì)算濾波后的直方圖的

14、梯度得并找出直方圖的谷點(diǎn)序列,稱之為候選閾值點(diǎn)列。這些點(diǎn)幾乎蘊(yùn)涵了圖像的全部分類信息。那么最大類間方差法的SA算法的目標(biāo)函數(shù)為最大方差：那么SA算法可以找出最優(yōu)的閾值序列來對圖像進(jìn)行分割。2） SA算法在超分辨率圖像重建中的應(yīng)用采用傳感器對外界圖像進(jìn)行采集傳輸和變換過程中，由于成像設(shè)備自身?xiàng)l件的限制常難以獲得高分辨圖的圖像，而改善成像設(shè)備的硬件成本高，短期內(nèi)技術(shù)難以突破、無法應(yīng)用實(shí)踐，因此目前主要采用軟件技術(shù)提高圖像的分辨率，改善圖像的質(zhì)量，其中超分辨率重建是 一 種改善圖像質(zhì)量技術(shù)。而目前應(yīng)用最廣泛的超分辨率重建方法是LLE算法，LLE算法是一種局部線性嵌入算法，它的原理是建設(shè)在局部領(lǐng)域內(nèi)的

15、數(shù)據(jù)點(diǎn)是線性的，所以領(lǐng)域內(nèi)任意一點(diǎn)都可由局部近鄰點(diǎn)線性表示，其中權(quán)值能反映出局部領(lǐng)域的信息，根據(jù)這些信息可是這種低維空間仍然保留原高維空間中的幾何性質(zhì)，通過重疊的局部領(lǐng)域得到整體的信息，實(shí)質(zhì)上是在保持原始數(shù)據(jù)性質(zhì)不變的情況下，將高維空間的信息映射到低維空間。LLE算法的難點(diǎn)在于確定鄰域K值的大小，若K值過大，容易丟失整體信息；若K值過小，則會(huì)造成龐大的計(jì)算量。所以我們引進(jìn)了SA算法來求出最優(yōu)的K值。引入SA算法的LLE算法的操作步驟：1) 對圖像進(jìn)行均勻分塊操作，將其劃分成多個(gè)子圖像塊。2) 對于每一個(gè)子圖像塊，分別提取歸一化亮度和小波變換子帶系數(shù)特征。3) 用 LLE 算法對圖像特征向量進(jìn)行

16、選擇。4) 采用模擬退火算法優(yōu)化 K 個(gè)近鄰的值。5) 將高分辨率圖像的梯度作為目標(biāo)梯度域，采用 LLE 算法重構(gòu)權(quán)值，根據(jù)重構(gòu)權(quán)值實(shí)現(xiàn)超分辨率圖像重建。SA算法在TSP問題中取得了顯著的效果，TSP是最有代表性的優(yōu)化組合問題之一，其應(yīng)用已逐步滲透到各個(gè)技術(shù)領(lǐng)域和我們的日常生活中.它一開始是為交通運(yùn)輸而提出的，比如飛機(jī)航線安排、送郵件、快遞服務(wù)、設(shè)計(jì)校車行進(jìn)路線等等，實(shí)際上其應(yīng)用范圍擴(kuò)展到了許多其他領(lǐng)域，如在VLSI芯片設(shè)計(jì)、電路板布局、機(jī)器人控制、車輛選路、物流配送等方面，下面舉幾個(gè)實(shí)例：(1) 電路板鉆孔進(jìn)度的安排.機(jī)器在電路板上鉆孔的調(diào)度問題是TSP應(yīng)用的經(jīng)典例子，在一電路板上打成百上千

17、個(gè)孔，轉(zhuǎn)頭在這些孔之間移動(dòng)，相當(dāng)于對所有的孔進(jìn)行一次巡游。把這個(gè)問題轉(zhuǎn)化為TSP，孔相當(dāng)于城市，轉(zhuǎn)頭從一個(gè)孔移到另一個(gè)孔所耗的時(shí)間相當(dāng)于TSP中的旅費(fèi)。(2) 車輛選路.一個(gè)經(jīng)典的路由問題是在一個(gè)網(wǎng)絡(luò)上發(fā)現(xiàn)從源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)的最佳交通線路，使與距離成比例的流動(dòng)費(fèi)用降低到最小.這個(gè)問題的關(guān)鍵是在交通網(wǎng)絡(luò)上計(jì)算從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的最短路徑。對這個(gè)最小費(fèi)用流動(dòng)問題進(jìn)行擴(kuò)展，就構(gòu)成TSP問題，在這個(gè)問題中，車輛從源點(diǎn)出發(fā)訪問多個(gè)目的地并且最后回到源點(diǎn)。(3) 基因測序。Cnoocdre是一種求解旅行商問題的程序.美國國家衛(wèi)生機(jī)構(gòu)的研究人員利用這一程序來進(jìn)行基因測序.在這一應(yīng)用中，DNA片斷作為

18、城市，它們之間的相似程度作為城市與城市的距離.研究人員試圖尋找一種可能性最高的連接方式把這些DNA片斷合成為整張DNA。SA算法解決TSP問題的基本思想：(1) 選S_0作為初始狀態(tài)，令S (0)=S_0，同時(shí)設(shè)初始溫度T，令i=0。(2) 令 T=T_i，以T和S_i調(diào)用Metorpolis抽樣算法，返回狀態(tài)S作為本算法的當(dāng)前解，S_i=S_0。(3) 按照一定方式降溫，即T =T_(i+1)，其中T_(i+1)<T_i，i=i+1。(4) 檢查終止條件，如果滿足則轉(zhuǎn)步驟 (5),否則轉(zhuǎn)步驟(2)(5) 當(dāng)前解S_i為最優(yōu)解，輸出結(jié)果，停止。Metropolis抽樣算法描述如下：

19、60;       1）令k=0時(shí)，當(dāng)前解 S (0)=S_0，在溫度T下，進(jìn)行以下各步操作。        2）按某個(gè)規(guī)定的方式根據(jù)當(dāng)前解 S（k）所處的狀態(tài)S產(chǎn)生一個(gè)近鄰子集N (S（k)+S，從N(S (k)中隨機(jī)得到一個(gè)新狀態(tài) S' 作為下一個(gè)候選解，計(jì)算能量之差：C' = C（S'） - C(S(k)）。      3）如果C' <  0 ，則接受 S' 作為下一個(gè)當(dāng)前解，否則，以概率exp(一C' / T)接受 S' 作為下一個(gè)當(dāng)前解。若 S' 被接受，則令S (k十1) = S' ，否則 S(k+1)=S（k）。        4）k =k +1，檢查算法是否滿足終止條件，若滿足，則轉(zhuǎn)步驟(5)，否則轉(zhuǎn)步驟(2)