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

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

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

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

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

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

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

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

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

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

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

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

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

14、doubleDecayScale=0.95;/衰減參數doubleStepFactor=0.02;/步長因子doubleTemperature=100;/初始溫度doubleTolerance=1e-8;/容差doublePreX,NextX;/priorandnextvalueofxdoublePreY,NextY;/priorandnextvalueofydoublePreBestX,PreBestY;/上一個最優解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;/在當前溫度T下迭代loop(即MARKOV鏈長度)次for (int i=0;i<MarkovLength;i+)算法設計與分析 計算機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)是否全局最優解if(ObjectFunction(BestX,BestY)>ObjectFunction(NextX,NextY)/保留上一個最優解PreBestX=BestX;PreBestY=BestY;/此為新的最優解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);結果：最小值在點：-1.956,1.618最小值為：-2