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

11迎下載模擬退火算法概念體處于非晶體狀態(tài)。我們將固體加溫至充分高〔中圖〕，再讓其緩緩冷卻，也就退火〔右圖〕。加溫量狀態(tài)會(huì)低；夠低后，液體開(kāi)頭冷凝與結(jié)晶，在結(jié)晶狀態(tài)時(shí)，系統(tǒng)的能量狀態(tài)最低。大自然在緩慢降溫〔亦即，退火〕時(shí)，可“找到”最低能量狀態(tài)：結(jié)晶。但是，假設(shè)過(guò)程過(guò)急過(guò)快，快速降溫〔亦稱(chēng)「淬煉」〕如以下圖所示，首先〔左圖〕物體處于非晶體狀態(tài)。我們將固體加溫至充分高〔中圖〕，再讓其緩緩冷卻，也就退火〔右圖〕。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩緩冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)平衡態(tài)，最終在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小〔此時(shí)物體以晶體形態(tài)呈現(xiàn)〕。時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩緩冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都到達(dá)平衡態(tài)，最終在常溫時(shí)到達(dá)基態(tài)，內(nèi)能減為最小〔此時(shí)物體以晶體形態(tài)呈現(xiàn)〕。似乎，大自然知道慢工出細(xì)活：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安排位置，則漸漸地，到最終可得到最低能態(tài)，系統(tǒng)最平穩(wěn)。模擬退火算法(SA)最早的思想是由N.Metropolis1953似乎，大自然知道慢工出細(xì)活：緩緩降溫，使得物體分子在每一溫度時(shí)，能夠有足夠時(shí)間找到安排位置，則漸漸地，到最終可得到最低能態(tài)，系統(tǒng)最平穩(wěn)。模擬退火算法(SA)最早的思想是由N.Metropolis19531983年,S.Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其動(dòng)身點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相像性。模擬退火算法從某一較高初溫動(dòng)身，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)查找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火其實(shí)也是一種貪心算法，但是它的搜尋過(guò)程引入了隨機(jī)因素。在迭代更可行解時(shí)，以以以下圖為例，假定初始解為左邊藍(lán)色點(diǎn)以以下圖為例，假定初始解為左邊藍(lán)色點(diǎn)A，模擬退火算法會(huì)快速搜尋到局部最優(yōu)解B，但在搜尋到局部最優(yōu)解后，不是就此完畢，而是會(huì)以肯定的概率承受到左邊的移動(dòng)?；蛟S經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)全局最優(yōu)點(diǎn)部最優(yōu)解后，不是就此完畢，而是會(huì)以肯定的概率承受到左邊的移動(dòng)?；蛟S經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)全局最優(yōu)點(diǎn)D，于是就跳出了局部最小值。依據(jù)熱力學(xué)的原理，在溫度為T(mén)時(shí)，消滅能量差dE的降溫的概率為P(dE)，

kT

。其中k函數(shù)的取值范圍是(0,1)。滿(mǎn)足概率密度函數(shù)的定義。其實(shí)這條公式更直觀(guān)意思就是：溫度越高，消滅一次能量差為P(dE)的降溫的概率就越大；溫度越低，則消滅降溫的概率就越小。在實(shí)際問(wèn)題中，這里的“肯定的概率”的計(jì)算參考了金屬冶煉的退火過(guò)程。x，迭代更后的解為x_new，那么對(duì)應(yīng)的“能量差”定義為：ffx_newfx，其對(duì)應(yīng)的肯定概率為： f exp fPf {

kTfexp ，最大值優(yōu)化問(wèn)題kTSA狀態(tài)空間與狀態(tài)產(chǎn)生函數(shù)狀態(tài)產(chǎn)生函數(shù)〔鄰域函數(shù)〕應(yīng)盡可能保證產(chǎn)生的候選解遍布全部解空間。通常由兩局部組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。候選解一般承受依據(jù)某一概率密度函數(shù)對(duì)解空間進(jìn)展隨機(jī)采樣來(lái)獲得。概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等。狀態(tài)轉(zhuǎn)移概率2〕通俗的理解是承受一個(gè)解為當(dāng)前解的概率。3〕它與當(dāng)前的溫度參數(shù)T有關(guān)，隨溫度下降而減小。4〕Metropolis內(nèi)循環(huán)終止準(zhǔn)則Metropolis常用的抽樣穩(wěn)定準(zhǔn)則包括：檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定。連續(xù)假設(shè)干步的目標(biāo)值變化較小。按肯定的步數(shù)抽樣。外循環(huán)終止準(zhǔn)則1〕設(shè)置終止溫度的閾值。設(shè)置外循環(huán)迭代次數(shù)。算法搜尋到的最優(yōu)值連續(xù)假設(shè)干步保持不變。檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。算法步驟(1)初始化：初始溫度T〔充分大〕，Tmin〔充分小〕，x(是算法迭代的起點(diǎn))，每個(gè)TL；(2)l=1,2,...,L(3)至第(6)步；產(chǎn)生解x_new:(x_new=x+Δx)；利計(jì)算增量Δf=f(x_new)f(x)，其中f(x)為優(yōu)化目標(biāo)；假設(shè)Δf<0，Δf>0)x_new作為的當(dāng)前解，否則以概率 fx_new kT假設(shè)滿(mǎn)足終止條件則輸出當(dāng)前解作為最優(yōu)解，完畢程序。(終止條件通常取為連續(xù)假設(shè)干個(gè)解都沒(méi)有被承受時(shí)終止算法。)；T漸漸削減，且T>Tmin，然后轉(zhuǎn)第(2)步。SASA算法很簡(jiǎn)潔找到最優(yōu)解，但是參數(shù)難以掌握，不能保證一次就收斂到最優(yōu)值，一般〔大局部狀況下還是會(huì)陷入局部最優(yōu)值覺(jué)察其主要存在如下三個(gè)參數(shù)問(wèn)題：溫度T溫度T的初始值設(shè)置是影響模擬退火算法全局搜尋性能的重要因素之一、初始溫度高，但全局搜尋性能可能受到影響。退火速度問(wèn)題，即每個(gè)T值的迭代次數(shù)搜尋是相當(dāng)必要的，但這也需要計(jì)算時(shí)間。循環(huán)次數(shù)增加必定帶來(lái)計(jì)算開(kāi)銷(xiāo)的增大。溫度治理問(wèn)題簡(jiǎn)單度的切實(shí)可行性等問(wèn)題，常承受如下所示的降溫方式：TT,0,1，為了保證較大的搜尋空間，α10.95、0.9。SA設(shè)計(jì)適宜的狀態(tài)產(chǎn)生函數(shù)，使其依據(jù)搜尋進(jìn)程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性；設(shè)計(jì)高效的退火策略；避開(kāi)狀態(tài)的迂回搜尋；承受并行搜尋構(gòu)造；為避開(kāi)陷入局部微小，改進(jìn)對(duì)溫度的掌握方式；選擇適宜的初始狀態(tài)；設(shè)計(jì)適宜的算法終止準(zhǔn)則。也可通過(guò)增加某些環(huán)節(jié)而實(shí)現(xiàn)對(duì)模擬退火算法的改進(jìn)。主要的改進(jìn)方式包括：的承受概率，以調(diào)整搜尋進(jìn)程中的當(dāng)前狀態(tài)，避開(kāi)算法在局部微小解處停滯不前。通過(guò)增加存儲(chǔ)環(huán)節(jié)，將一些在這之前好的態(tài)記憶下來(lái)。擬退火過(guò)程或局部性搜尋。對(duì)每一當(dāng)前狀態(tài)，承受屢次搜尋策略，以概率承受區(qū)域內(nèi)的最優(yōu)狀態(tài)，而非標(biāo)準(zhǔn)SA的單次比較方式。結(jié)合其他搜尋機(jī)制的算法，如遺傳算法、混沌搜尋等。(6)上述各方法的綜合應(yīng)用。二SA模擬退火算法作為一種通用的隨機(jī)搜尋算法，現(xiàn)已廣泛用于VLSI設(shè)計(jì)、圖像識(shí)別和神NP完全問(wèn)題，如TSP問(wèn)題(TravellingSalesmanProblemTSP)、最大截問(wèn)題(MaxCutProblem)、0-1(ZeroOneKnapsackProblem)、圖著色問(wèn)題(GraphColouring模擬退火算法作為一種通用的隨機(jī)搜尋算法，現(xiàn)已廣泛用于VLSI設(shè)計(jì)、圖像識(shí)別和神現(xiàn)已廣泛用于現(xiàn)已廣泛用于VLSI設(shè)計(jì)、圖像識(shí)別和神經(jīng)網(wǎng)計(jì)算機(jī)的爭(zhēng)論。模擬退火算法的應(yīng)用如下：模擬退火算法在VLSI模擬退火算法在VLSI設(shè)計(jì)中的應(yīng)用利用模擬退火算法進(jìn)展VLSI利用模擬退火算法進(jìn)展VLSI用模擬退火算法幾乎可以很好地完成全部?jī)?yōu)化的VLSI設(shè)計(jì)工作。如全局布線(xiàn)、布板、布局模擬退火算法在神經(jīng)網(wǎng)計(jì)算機(jī)中的應(yīng)用Boltzmann模擬退火算法在神經(jīng)網(wǎng)計(jì)算機(jī)中的應(yīng)用Boltzmann模擬退火算法在圖像處理中的應(yīng)用模擬退火算法可用來(lái)進(jìn)展圖像恢復(fù)等工作最優(yōu)的陷阱，經(jīng)過(guò)一段時(shí)間后，它還能再跳出來(lái)，再系統(tǒng)最終將往全局最優(yōu)值的方向收斂。3)模擬退火算法在圖像處理中的應(yīng)用模擬退火算法可用來(lái)進(jìn)展圖像恢復(fù)等工作圖，濾掉其中被畸變的局部。因此它在圖像處理方面的應(yīng)用前景是寬闊的。其中，SA算法在圖像處理領(lǐng)域應(yīng)用比較廣泛。比方：其中，SA算法在圖像處理領(lǐng)域應(yīng)用比較廣泛。比方：1〕SA圖像分割是圖像處理與計(jì)算機(jī)視覺(jué)領(lǐng)域中最為根底和關(guān)鍵的任務(wù)之一,是對(duì)圖像進(jìn)展視處理步驟。在眾多圖像分割方法中,閾值分割主要利用圖像中目標(biāo)與背景在灰度特征上的差圖像分割是圖像處理與計(jì)算機(jī)視覺(jué)領(lǐng)域中最為根底和關(guān)鍵的任務(wù)之一,是對(duì)圖像進(jìn)展視處理步驟。在眾多圖像分割方法中,閾值分割主要利用圖像中目標(biāo)與背景在灰度特征上的差異將圖像劃分為假設(shè)干局部。因?qū)崿F(xiàn)簡(jiǎn)潔、計(jì)算量小、性能較穩(wěn)定,閾值分割已成為最根本和應(yīng)用最廣泛的分割技術(shù)。1979年日本學(xué)者大津提出了最大類(lèi)間方差法因計(jì)算方法簡(jiǎn)潔、自適應(yīng)強(qiáng)而成為使用最廣泛的圖像閾值自動(dòng)選取方法之一。但傳統(tǒng)的Otsu是承受遍歷的方式查找使類(lèi)間方差最大的閾值T,計(jì)算量會(huì)隨分類(lèi)數(shù)增加呈幾何級(jí)數(shù)增長(zhǎng),這在很大程度上限制了Otsu算法的應(yīng)用，為了解決多閾值圖像分割時(shí)最大類(lèi)間方差法計(jì)算量浩大的問(wèn)題，引入了入了SA算法，用模擬退火演進(jìn)代替窮舉法搜尋最優(yōu)閾值向量可以使計(jì)算量大大削減。然而如下三步進(jìn)展：如下三步進(jìn)展：對(duì)直方圖進(jìn)展高斯濾波。圖像的直方圖包含了圖像的分類(lèi)信息,但它通常是一條呈a)對(duì)直方圖進(jìn)展高斯濾波。圖像的直方圖包含了圖像的分類(lèi)信息,但它通常是一條呈現(xiàn)很多微小波峰的不光滑曲線(xiàn),從原始直方圖很難識(shí)別和提取出符合應(yīng)用要求的閾值向量?，F(xiàn)很多微小波峰的不光滑曲線(xiàn),從原始直方圖很難識(shí)別和提取出符合應(yīng)用要求的閾值向量。b)計(jì)算濾波后的直方圖的梯度得并找出直方圖的谷點(diǎn)序列,稱(chēng)之為候選閾值點(diǎn)列。這些點(diǎn)幾乎蘊(yùn)涵了圖像的全局部類(lèi)信息。那么最大類(lèi)間方差法的SA算法的目標(biāo)函數(shù)為最大方差：σσ2B=ω(μ -μ)2+ω(μ-μ)2+…+ω(μ-μ)20 0 T1 1 Tc c TSA2〕SA承受傳感器對(duì)外界圖像進(jìn)展采集傳輸和變換過(guò)程中承受傳感器對(duì)外界圖像進(jìn)展采集傳輸和變換過(guò)程中—種改善圖像質(zhì)量技術(shù)。而目前應(yīng)用最廣泛的超區(qū)分率重建方法是LLE算法，—種改善圖像質(zhì)量技術(shù)。而目前應(yīng)用最廣泛的超區(qū)分率重建方法是LLE算法，LLE算法是LLE算法的難點(diǎn)在于確定鄰域K點(diǎn)在于確定鄰域K值的大小，假設(shè)KK值過(guò)小，則會(huì)造成浩大SA算法來(lái)求出最優(yōu)的KSA算法的LLE對(duì)圖像進(jìn)展均勻分塊操作，將其劃分成多個(gè)子圖像塊。1)對(duì)圖像進(jìn)展均勻分塊操作，將其劃分成多個(gè)子圖像塊。對(duì)于每一個(gè)子圖像塊，分別提取歸一化亮度和小波變換子帶系數(shù)特征。2)對(duì)于每一個(gè)子圖像塊，分別提取歸一化亮度和小波變換子帶系數(shù)特征。用LLE算法對(duì)圖像特征向量進(jìn)展選擇。用LLE算法對(duì)圖像特征向量進(jìn)展選擇。承受模擬退火算法優(yōu)化K承受模擬退火算法優(yōu)化K個(gè)近鄰的值。將高區(qū)分率圖像的梯度作為目標(biāo)梯度域，承受LLE將高區(qū)分率圖像的梯度作為目標(biāo)梯度域，承受LLE算法重構(gòu)權(quán)值，依據(jù)重構(gòu)權(quán)值實(shí)現(xiàn)超區(qū)分率圖像重建。超區(qū)分率圖像重建。SA算法在TSPTSP已逐步滲透到各個(gè)技術(shù)領(lǐng)域和我們的日常生活中.它一開(kāi)頭是為交通運(yùn)輸而提出的，比方飛其他領(lǐng)域，如在VLSI面舉幾個(gè)實(shí)例：電路板鉆孔進(jìn)度的安排.機(jī)器在電路板上鉆孔的調(diào)度問(wèn)題是TSP應(yīng)用的經(jīng)典例子，在一電路板上打成百上千個(gè)孔，轉(zhuǎn)頭在這些孔之間移動(dòng)，相當(dāng)于對(duì)全部的孔進(jìn)展一次巡游。把這個(gè)問(wèn)題轉(zhuǎn)化為T(mén)SP，孔相當(dāng)于城市，轉(zhuǎn)頭從一個(gè)孔移到另一個(gè)孔所耗的時(shí)間相當(dāng)于TSP中的旅費(fèi)。車(chē)輛選路.一個(gè)經(jīng)典的路由問(wèn)題是在一個(gè)網(wǎng)絡(luò)上覺(jué)察從源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)的最正確交通線(xiàn)路，使與距離成比例的流淌費(fèi)用降低到最小.這個(gè)問(wèn)題的關(guān)鍵是在交通網(wǎng)絡(luò)上計(jì)算TSP問(wèn)題，在這個(gè)問(wèn)題中，車(chē)輛從源點(diǎn)動(dòng)身訪(fǎng)問(wèn)多個(gè)目的地并且最終回到源點(diǎn)。Cnoocdre是一種求解旅行商問(wèn)題的程序.美國(guó)國(guó)家衛(wèi)生氣構(gòu)的爭(zhēng)論人員利用這一程序來(lái)進(jìn)展基因測(cè)序.在這一應(yīng)用中，DNA片斷作為城市，它們之間的相像程度作為城市與城市的距離.爭(zhēng)論人員試圖查找一種可能性最高的連接方式把這些DNA片斷合成為整張DNA。SA算法解決TSPS_0S(0)=S_0，同時(shí)設(shè)初始溫度T，令i=0。令T=T_i，以TS_i調(diào)用MetorpolisSS_i=S_0。依據(jù)肯定方式降溫，即T=T_(i+1)，其中T_(i+1)<T_i，i=i+1。檢查終止條件，假設(shè)滿(mǎn)足則轉(zhuǎn)步驟(5),否則轉(zhuǎn)步驟(2)當(dāng)前解S_i為最優(yōu)解，輸出結(jié)果，停頓。Metropolis1〕k=0S(0)=S_0，在溫度T按某個(gè)規(guī)定的方式依據(jù)當(dāng)前解S產(chǎn)生一個(gè)近鄰子集NN(S(k)S”作為下一個(gè)候選解，計(jì)算能量之差：△C”=C〔S”〕-C(S(k)〕。3〕假設(shè)△C”<0，則承受S”作為下一個(gè)當(dāng)前解，否則，以概率exp(一△C”/T)承受S”作為下一個(gè)當(dāng)前解。假設(shè)S”被承受，則令S(k1)S”，否則S(k+1)=S〔k〕。4〕k=k+1，檢查算法是否滿(mǎn)足終止條件，假設(shè)滿(mǎn)足，則轉(zhuǎn)步驟(5)，否則轉(zhuǎn)步驟(2)。5〕返回S(k)，完畢。三SA模擬退火算法最早的思想是由Metropolis在1953年提出，直到1983年才由rkPatrick決局部微小問(wèn)題上的突出表現(xiàn)快速得到大家的青睞，也引起了眾多學(xué)者廣泛的爭(zhēng)論興趣，使模擬退火算法也得到了突飛猛進(jìn)的進(jìn)展。國(guó)內(nèi)引進(jìn)模擬退火算法的歷史較短，相比于蟻群算法等所進(jìn)展的爭(zhēng)論也不是很多，而且大多數(shù)都是關(guān)于模擬退火在工程等方面的實(shí)際應(yīng)法(SA)在理論上已得到證明，它可以到達(dá)全局微小值