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

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

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

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

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

5、棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。三、模擬退火算法的應(yīng)用領(lǐng)域模擬退火算法是解NP完全組合優(yōu)化問(wèn)題的有效近似算法,將該算法應(yīng)用于路徑優(yōu)化問(wèn)題,利用該算法對(duì)類(lèi)似貨郎擔(dān)問(wèn)題的路徑問(wèn)題進(jìn)行求解;針對(duì)城市道路行走不同的目標(biāo)條件（路徑最短、時(shí)間最短）進(jìn)行優(yōu)化,選擇最佳行走路徑;并將用該算法優(yōu)化得到的計(jì)算結(jié)果與樹(shù)形算法進(jìn)行比較,顯示該算法能夠克服傳統(tǒng)優(yōu)化算法易陷入局部極值的缺點(diǎn),同時(shí)表明該算法在解類(lèi)似貨郎擔(dān)交通

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

7、物學(xué)以及超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖像處理和電子工程等科技領(lǐng)域中，存在大量組合優(yōu)化瓿。其中許多問(wèn)題如貨郎擔(dān)問(wèn)題、圖著色問(wèn)題、設(shè)備布局問(wèn)題以及布線問(wèn)題等，至今沒(méi)有找到有效的多項(xiàng)式時(shí)間算法。這些問(wèn)題已被證明是NP完全問(wèn)題。1982年,KirkPatrick將退火思想引入組合優(yōu)化領(lǐng)域,提出一種解大規(guī)模組合優(yōu)化問(wèn)題的算法，對(duì)NP完全組合優(yōu)化問(wèn)題尤其有效。這源于固體的退火過(guò)程，即先將溫度加到很高，再緩慢降溫（即退火），使達(dá)到能量最低點(diǎn)。如果急速降溫（即為淬火）則不能達(dá)到最低點(diǎn).。即：模擬退火算法是一種能應(yīng)用到求最小值問(wèn)題或基本先前的更新的學(xué)習(xí)過(guò)程（隨機(jī)或決定性的）。在此過(guò)程中，每一步更新過(guò)程的長(zhǎng)度

8、都與相應(yīng)的參數(shù)成正比，這些參數(shù)扮演著溫度的角色。然后，與金屬退火原理相類(lèi)似，在開(kāi)始階段為了更快地最小化或?qū)W習(xí)，溫度被升得很高，然后才（慢慢）降溫以求穩(wěn)定。模擬退火算法的主要思想就函數(shù)最小值問(wèn)題來(lái)說(shuō)，模擬退火的主要思想是：在搜索區(qū)間（二維平面中）隨機(jī)游走（即隨機(jī)選擇點(diǎn)），再以Metropolis抽樣準(zhǔn)則，使隨機(jī)游走逐漸收斂于局部最優(yōu)解。而溫度即是Metropolis算法中的一個(gè)重要控制參數(shù)，可以認(rèn)為這個(gè)參數(shù)的大小控制了隨時(shí)過(guò)程向局部或全局最優(yōu)解移動(dòng)的快慢。冷卻參數(shù)表、領(lǐng)域結(jié)構(gòu)和新解產(chǎn)生器、接受準(zhǔn)則和隨機(jī)數(shù)產(chǎn)生器（即Metropolis算法）一起算法設(shè)計(jì)與分析計(jì)算機(jī)101-04顧鑫構(gòu)成算法的三大支

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

10、零時(shí)，最終求得組合優(yōu)化問(wèn)題的整體最優(yōu)解?？刂茀?shù)的值必須緩慢衰減。其中溫度是一個(gè)Metropolis的重要控制參數(shù)，模擬退火可視為遞減控制參數(shù)什時(shí)Metroplis算法的迭代。開(kāi)始T值大，可能接受較差的惡化解，隨著T的減小，只能接受較好的惡化解，最后在T趨于0時(shí)，就不再接受任何惡化解了。在無(wú)限高溫時(shí)，系統(tǒng)立即均勻分布，接受所有提出的變換。T的衰減越小，T到達(dá)終點(diǎn)的時(shí)間越長(zhǎng)；但可使馬可夫鏈越小，到達(dá)準(zhǔn)平衡分布的時(shí)間越短，參數(shù)的選擇：我們稱(chēng)調(diào)整模擬退火法的一系列重要參數(shù)為冷卻進(jìn)度表。它控制參數(shù)T的初值及其衰減函數(shù)，對(duì)應(yīng)的MARKOV鏈長(zhǎng)度和停止條件，非常重要。一個(gè)冷卻進(jìn)度表應(yīng)當(dāng)規(guī)定下述參數(shù)：1.

11、控制參數(shù)t的初值to；2. 控制參數(shù)t的衰減函數(shù)；3. 馬爾可夫鏈的長(zhǎng)度Lk。（即每一次隨機(jī)游走過(guò)程，要迭代多少次，才能趨于一個(gè)準(zhǔn)平衡分布，即一個(gè)局部收斂解位置）4. 結(jié)束條件的選擇有效的冷卻進(jìn)度表判據(jù)：一. 算法的收斂：主要取決于衰減函數(shù)和馬可夫鏈的長(zhǎng)度及停止準(zhǔn)則的選擇二. 算法的實(shí)驗(yàn)性能：最終解的質(zhì)量和CPU的時(shí)間參數(shù)的選擇：一) 控制參數(shù)初值TO的選取一般要求初始值tO的值要充分大，即一開(kāi)始即處于高溫狀態(tài)，且Metropolis的接收率約為1。二) 衰減函數(shù)的選取衰減函數(shù)用于控制溫度的退火速度，一個(gè)常用的函數(shù)為：T(n+1)=K*T(n)，其中K是一個(gè)非常接近于1的常數(shù)。三) 馬可夫鏈長(zhǎng)

12、度L的選取原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L應(yīng)選得在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡。四) 終止條件有很多種終止條件的選擇，各種不同的條件對(duì)算法的性能和解的質(zhì)量有很大影響，本文只介紹一個(gè)常用的終止條件。即上一個(gè)最優(yōu)解與最新的一個(gè)最優(yōu)解的之差小于某個(gè)容差，即可停止此次馬爾可夫鏈的迭代。以上說(shuō)明可能太過(guò)于抽象，下一節(jié)將以一個(gè)實(shí)際的例子來(lái)說(shuō)明，其中所有的源碼已貼出，可以從中了解到很多細(xì)節(jié)。使用模擬退火法求函數(shù)f(x,y)=5sin(xy)+x2+y2的最小值解：根據(jù)題意，我們?cè)O(shè)計(jì)冷卻表進(jìn)度表為：即初始溫度為100衰減參數(shù)為O.95馬可夫鏈長(zhǎng)度為10000Metropolis的步長(zhǎng)為0

13、.02結(jié)束條件為根據(jù)上一個(gè)最優(yōu)解與最新的一個(gè)最優(yōu)解的之差小于某個(gè)容差。使用METROPOLIS接受準(zhǔn)則進(jìn)行模擬,程序如下/*模擬退火法求函數(shù)f(x,y)=5sin(xy)+xA2+yA2的最小值*結(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(stringar

14、gs)/搜索的最大區(qū)間constdoubleXMAX=4;constdoubleYMAX=4;/冷卻表參數(shù)intMarkovLength=10000;/馬可夫鏈長(zhǎng)度doubleDecayScale=0.95;/衰減參數(shù)doubleStepFactor=0.02;/步長(zhǎng)因子doubleTemperature=100;/初始溫度doubleTolerance=1e-8;/容差doublePreX,NextX;/priorandnextvalueofxdoublePreY,NextY;/priorandnextvalueofydoublePreBestX,PreBestY;/上一個(gè)最優(yōu)解double

15、BestX,BestY;/最終解doubleAcceptPoints=0.0;/Metropolis過(guò)程中總接受點(diǎn)Randomrnd=newRandom();/隨機(jī)選點(diǎn)PreX=-XMAX*rnd.NextDouble();PreY=-YMAX*rnd.NextDouble();PreBestX=BestX=PreX;PreBestY=BestY=PreY;/每迭代一次退火一次(降溫),直到滿足迭代條件為止doTemperature*=DecayScale;AcceptPoints=0.0;/在當(dāng)前溫度T下迭代loop(即MARKOV鏈長(zhǎng)度)次for(inti=0;ivMarkovLength

16、;i+)/1)在此點(diǎn)附近隨機(jī)選下一點(diǎn)doNextX=PreX+StepFactor*XMAX*(rnd.NextDouble()-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)/保留上一個(gè)最優(yōu)解Pr

17、eBestX=BestX;PreBestY=BestY;/此為新的最優(yōu)解BestX=NextX;BestY=NextY;/3)Metropolis過(guò)程if(ObjectFunction(PreX,PreY)-ObjectFunction(NextX,NextY)>0)/接受,此處lastPoint即下一個(gè)迭代的點(diǎn)以新接受的點(diǎn)開(kāi)始PreX=NextX;PreY=NextY;AcceptPoints+;elsedoublechange=-1*(ObjectFunction(NextX,NextY)-ObjectFunction(PreX,PreY)/Temperature;if(Math.E

18、xp(change)>rnd.NextDouble()PreX=NextX;PreY=NextY;AcceptPoints+;/不接受,保存原解Console.WriteLine("0,1,2,3",PreX,PreY,ObjectFunction(PreX,PreY),Temperature);while(Math.Abs(ObjectFunction(BestX,BestY)-ObjectFunction(PreBestX,PreBestY)>Tolerance);Console.WriteLine('最小值在點(diǎn):0,l",BestX,BestY);Console.WriteLine("最小值為:0",ObjectFunction(BestX,BestY);結(jié)果：最小值在點(diǎn):-1.956,1.618最小值