模擬退火算法基本原理介紹

1、算法設(shè)計與分析 計算機101-04 顧鑫一、模擬退火算法概念模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時趨于平衡的概率為e-AE/(kT),其中E為溫度T時的內(nèi)能，AE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)產(chǎn)生新解-計算目標(biāo)函數(shù)差-接受

2、或舍棄”的迭代，并逐步衰減t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子At每個t值時的迭代次數(shù)L和停止條件S。二、模擬退火算法的模型模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火的基本思想:(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)，每個T值的迭代次數(shù)L(2)對k=1,L做第(3)至第6步：(3)產(chǎn)生新解S'(4)計算增量At'=C(SC($),其中C(S)為評價函數(shù)(5)若At'則接受

3、S作為新的當(dāng)前解，否則以概率exp(-At'磔S作為新的當(dāng)前解.(6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。(7) T逐漸減少，且T->0,然后轉(zhuǎn)第2步。算法對應(yīng)動態(tài)演示圖：模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。第二步是計算與新解

4、所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則：若At'則0受S作為新的當(dāng)前解S,否則以概率exp(-At'擲翼S作為新的當(dāng)前解S。第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。此時，當(dāng)前解實現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當(dāng)新解被判定為舍棄時，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。模擬退火算法與初始

5、值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭彳t的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。三、模擬退火算法的應(yīng)用領(lǐng)域模擬退火算法是解NP完全組合優(yōu)化問題的有效近似算法,將該算法應(yīng)用于路徑優(yōu)化問題,利用該算法對類似貨郎擔(dān)問題的路徑問題進行求解;針對城市道路行走不同的目標(biāo)條件（路徑最短、時間最短）進行優(yōu)化,選擇最佳行走路徑;并將用該算法優(yōu)化得到的計算結(jié)果與樹形算法進行比較,顯示該算法能夠克服傳統(tǒng)優(yōu)化算法易陷入局部極值的缺點,同時表明該算法在解類似貨郎擔(dān)交通路徑方面的問題時有較高的精確性。因而該算法在解決城市道路交

6、通問題方面具有一定的實用價值。在企業(yè)運營與管理中,管理者總是希望把人員最佳分派以發(fā)揮其優(yōu)勢,從而降低成本,提高效益.例如，某公司需完成m項任務(wù)，恰好有n名員工可承擔(dān)這些任務(wù)（nRm海項任務(wù)只能由一名員工來做,每名員工也只能做一項任務(wù);不同的員工完成各項任務(wù)的成本不同.這樣就可采用模擬退火算法將企業(yè)的人員分配做到最佳的分配。四、具體案例C#數(shù)值計算之模擬退火法簡介摘要本文簡介了模擬退火的基本思想，以于模擬時的主要參數(shù)的選擇根據(jù)，然后給出一個求二維函數(shù)極值的具體問題和解法，并給出C#源代碼。l概述在管理科學(xué)、計算機科學(xué)、分子物理學(xué)和生物學(xué)以及超大規(guī)模集成電路設(shè)計、代碼設(shè)計、圖像處理和電子工程等科技

7、領(lǐng)域中，存在大量組合優(yōu)化瓿。其中許多問題如貨郎擔(dān)問題、圖著色問題、設(shè)備布局問題以及布線問題等，至今沒有找到有效的多項式時間算法。這些問題已被證明是NP完全問題。1982年,KirkPatrick將退火思想引入組合優(yōu)化領(lǐng)域，提出一種解大規(guī)模組合優(yōu)化問題的算法，對NP完全組合優(yōu)化問題尤其有效。這源于固體的退火過程，即先將溫度加到很高,再緩慢降溫（即退火），使達到能量最低點。如果急速降溫（即為淬火）則不能達到最低點.。即：模擬退火算法是一種能應(yīng)用到求最小值問題或基本先前的更新的學(xué)習(xí)過程（隨機或決定性的）。在此過程中，每一步更新過程的長度都與相應(yīng)的參數(shù)成正比，這些參數(shù)扮演著溫度的角色。然后，與金屬退火

8、原理相類似，在開始階段為了更快地最小化或?qū)W習(xí)，溫度被升得很高，然后才（慢慢）降溫以求穩(wěn)定。模擬退火算法的主要思想就函數(shù)最小值問題來說，模擬退火的主要思想是：在搜索區(qū)間（二維平面中）隨機游走（即隨機選擇點），再以Metropolis抽樣準(zhǔn)則，使隨機游走逐漸收斂于局部最優(yōu)解。而溫度即是Metropolis算法中的一個重要控制參數(shù)，可以認為這個參數(shù)的大小控制了隨時過程向局部或全局最優(yōu)解移動的快慢。冷卻參數(shù)表、領(lǐng)域結(jié)構(gòu)和新解產(chǎn)生器、接受準(zhǔn)則和隨機數(shù)產(chǎn)生器（即Metropolis算法）一起構(gòu)成算法的三大支柱。重點抽樣與Metroplis算法：Metropolis是一種有效的重點抽樣法，其算法為：系統(tǒng)從能

9、量一個狀態(tài)變化到另一個狀態(tài)時，相應(yīng)的能量從E1變化到E2,概率為p=exp-（E2-E1）/kT。如果E2<E1,系統(tǒng)接收此狀態(tài)，否則，以一個隨機的概率接收此或丟棄此狀態(tài)。這種經(jīng)常一定次數(shù)的迭代，系統(tǒng)會逐漸趨于一引穩(wěn)定的分布狀態(tài)。重點抽樣時，新狀態(tài)下如果向下則接受（局部最優(yōu)），若向上（全局搜索），以一定機率接受。模擬退火方法從某個初始解出發(fā)，經(jīng)過大量解的變換后，可以求得給定控制參數(shù)值時組合優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)T的值，重復(fù)執(zhí)行Metropolis算法，就可以在控制參數(shù)T趨于零時，最終求得組合優(yōu)化問題的整體最優(yōu)解?？刂茀?shù)的值必須緩慢衰減。其中溫度是一個Metropolis

10、的重要控制參數(shù)，模擬退火可視為遞減控制參數(shù)什時Metroplis算法的迭代。開始T值大，可能接受較差的惡化解，隨著T的減小，只能接受較好的惡化解，最后在T趨于0時，就不再接受任何惡化解了。在無限高溫時，系統(tǒng)立即均勻分布，接受所有提出的變換。T的衰減越小，T到達終點的時間越長；但可使馬可夫鏈越小，到達準(zhǔn)平衡分布的時間越短，參數(shù)的選擇：我們稱調(diào)整模擬退火法的一系列重要參數(shù)為冷卻進度表。它控制參數(shù)T的初值及其衰減函數(shù)，對應(yīng)的MARKOV鏈長度和停止條件，非常重要。一個冷卻進度表應(yīng)當(dāng)規(guī)定下述參數(shù)：1 .控制參數(shù)t的初值t0;2 .控制參數(shù)t的衰減函數(shù)；3 .馬爾可夫鏈的長度Lk。（即每一次隨機游走過程

11、，要迭代多少次，才能趨于一個準(zhǔn)平衡分布，即一個局部收斂解位置）4,結(jié)束條件的選擇有效的冷卻進度表判據(jù)：一.算法的收斂：主要取決于衰減函數(shù)和馬可夫鏈的長度及停止準(zhǔn)則的選擇二.算法的實驗性能：最終解的質(zhì)量和CPU的時間參數(shù)的選擇：一)控制參數(shù)初值T0的選取一般要求初始值t0的值要充分大，即一開始即處于高溫狀態(tài)，且Metropolis的接收率約為1。二)衰減函數(shù)的選取衰減函數(shù)用于控制溫度的退火速度，一個常用的函數(shù)為：T(n+1)=K*T(n)，其中K是一個非常接近于1的常數(shù)。三)馬可夫鏈長度L的選取原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L應(yīng)選得在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡。四)終止條

12、件有很多種終止條件的選擇，各種不同的條件對算法的性能和解的質(zhì)量有很大影響，本文只介紹一個常用的終止條件。即上一個最優(yōu)解與最新的一個最優(yōu)解的之差小于某個容差，即可停止此次馬爾可夫鏈的迭代。以上說明可能太過于抽象，下一節(jié)將以一個實際的例子來說明，其中所有的源碼已貼出，可以從中了解到很多細節(jié)。使用模擬退火法求函數(shù)f(x,y)=5sin(xy)+x2+y2的最小值解：根據(jù)題意，我們設(shè)計冷卻表進度表為：即初始溫度為100衰減參數(shù)為0.95馬可夫鏈長度為10000Metropolis的步長為0.02結(jié)束條件為根據(jù)上一個最優(yōu)解與最新的一個最優(yōu)解的之差小于某個容差。使用METROPOLIS接受準(zhǔn)則進行模擬,程

13、序如下/* 模擬退火法求函數(shù)f(x,y)=5sin(xy)+xA2+yA2的最小值3* 結(jié)束條件為兩次最優(yōu)解之差小于某小量* /usingSystem;namespaceSimulateAnnealingclassClass1/要求最優(yōu)值的目標(biāo)函數(shù)staticdoubleObjectFunction(doublex,doubley)doublez=0.0;z=5.0*Math.Sin(x*y)+x*x+y*y;returnz;STAThreadstaticvoidMain(stringargs)/搜索的最大區(qū)間constdoubleXMAX=4;constdoubleYMAX=4;/冷卻表參數(shù)

14、doubleDecayScale=0.95;/衰減參數(shù)doubleStepFactor=0.02;/步長因子doubleTemperature=100;/初始溫度doubleTolerance=1e-8;/容差doublePreX,NextX;/priorandnextvalueofxdoublePreY,NextY;/priorandnextvalueofydoublePreBestX,PreBestY;/上一個最優(yōu)解doubleBestX,BestY;/最終解doubleAcceptPoints=0.0;/Metropolis過程中總接受點Randomrnd=newRandom();/隨機

15、選點PreX=-XMAX*rnd.NextDouble();PreY=-YMAX*rnd.NextDouble();PreBestX=BestX=PreX;PreBestY=BestY=PreY;/每迭代一次退火一次(降溫),直到滿足迭代條件為止doTemperature*=DecayScale;AcceptPoints=0.0;/在當(dāng)前溫度T下迭代loop(即MARKOV鏈長度)次for (int i=0;i<MarkovLength;i+)算法設(shè)計與分析 計算機101-04 顧鑫/1)在此點附近隨機選下一點doNextX=PreX+StepFactor*XMAX*(rnd.NextD

16、ouble()-0.5);NextY=PreY+StepFactor*YMAX*(rnd.NextDouble()-0.5);while(!(NextX>=-XMAX&&NextX<=XMAX&&NextY>=-YMAX&&NextY<=YMAX);/2)是否全局最優(yōu)解if(ObjectFunction(BestX,BestY)>ObjectFunction(NextX,NextY)/保留上一個最優(yōu)解PreBestX=BestX;PreBestY=BestY;/此為新的最優(yōu)解BestX=NextX;BestY=Nex

17、tY;/3)Metropolis過程if(ObjectFunction(PreX,PreY)-ObjectFunction(NextX,NextY)>0)/接受,此處lastPoint即下一個迭代的點以新接受的點開始PreX=NextX;PreY=NextY;AcceptPoints+;elsedoublechange=-1*(ObjectFunction(NextX,NextY)-ObjectFunction(PreX,PreY)/Temperature;if(Math.Exp(change)>rnd.NextDouble()PreX=NextX;PreY=NextY;Accep

18、tPoints+;/不接受,保存原解Console.WriteLine("0,1,2,3",PreX,PreY,ObjectFunction(PreX,PreY),Temperature);while(Math.Abs(ObjectFunction(BestX,BestY)-ObjectFunction(PreBestX,PreBestY)>Tolerance);Console.WriteLine("最小值在點:0,1",BestX,BestY);Console.WriteLine("最小值為:0",ObjectFunction(BestX,BestY);結(jié)果：最小值在點：-1.956,1.618最小值為：-2