1、模擬退火算法文獻綜述呂正祥 交控15011模擬退火算法簡述1.1模擬退火算法的來源模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。 模擬退火算法(Simulated Annealing，SA)最早由Kirkpatrick等應用于組合優化領域，它是基于Monte-Carlo迭代求解策略的一種隨機尋優算法，其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。模擬退火算法從某一較高初溫出發，伴隨溫度參數的不斷下降,結合概率突跳特性

2、在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出并最終趨于全局最優。模擬退火算法是一種通用的優化算法，理論上算法具有概率的全局優化性能,目前已在工程中得到了廣泛應用，諸如VLSI、生產調度、控制工程、機器學習、神經網絡、信號處理等領域。 模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優的串行結構的優化算法。1.2模擬退火算法的模型 模擬退火算法可以分解為解空間、目標函數和初始解三部分。 1.3模擬退火的基本思想 (1) 初始化：初始溫度T(充分大)，初始解狀態S(是算法迭代的起點)， 每個T值的迭代次數L (2)

3、對k=1，L做第(3)至第6步： (3) 產生新解S (4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數 (5) 若t<0則接受S作為新的當前解，否則以概率exp(-t/T)接受S作為新的當前解. (6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接受時終止算法。 (7) T逐漸減少，且T->0，然后轉第2步。2.模擬退火算法流程2.1模擬退火算法流程圖2.2模擬退火算法中參數的選擇2.2.1冷卻進度表我們稱調整模擬退火法的一系列重要參數為冷卻進度表。它控制參數T的初值及其衰減函數，對應的MARKOV鏈長度和停止條件，非常重

4、要。一個冷卻進度表應當規定下述參數：1控制參數t的初值t0;2控制參數t的衰減函數；3馬爾可夫鏈的長度Lk。（即每一次隨機游走過程，要迭代多少次，才能趨于一個準平衡分布，即一個局部收斂解位置）4結束條件的選擇2.2.2有效的冷卻進度表判據：一算法的收斂：主要取決于衰減函數和馬可夫鏈的長度及停止準則的選擇二算法的實驗性能：最終解的質量和CPU的時間  參數的選取：一）控制參數初值T0的選取一般要求初始值t0的值要充分大，即一開始即處于高溫狀態，且Metropolis的接收率約為1。(1) 均勻抽樣一組狀態，以各狀態目標值的方差為初溫。(2) 隨機產生一組狀態，確定兩兩狀態間的

5、最大目標值差|max|，然后依據差值，利用一定的函數確定初溫。比如，t0=max/pr ，其中pr為初始接受概率。二）衰減函數的選取衰減函數用于控制溫度的退火速度，一個常用的函數為：T(n + 1) = K*T(n)，其中K是一個非常接近于1的常數。三）馬可夫鏈長度L的選取原則是：在衰減參數T的衰減函數已選定的前提下，L應選得在控制參數的每一取值上都能恢復準平衡。四）終止條件有很多種終止條件的選擇，各種不同的條件對算法的性能和解的質量有很大影響，我們只介紹一個常用的終止條件。即上一個最優解與最新的一個最優解的之差小于某個容差，即可停止此次馬爾可夫鏈的迭代。3模擬退火算法的優缺點 &#

6、160; 優點：計算過程簡單，通用，魯棒性強，適用于并行處理，可用于求解復雜的非線性優化問題。缺點：收斂速度慢，執行時間長，算法性能與初始值有關及參數敏感等缺點經典模擬退火算法的缺點：（1)如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；(2)如果降溫過程過快，很可能得不到全局最優解。 模擬退火算法的改進：(1) 設計合適的狀態產生函數，使其根據搜索進程的需要表現出狀態的全空間分散性或局部區域性。(2) 設計高效的退火策略。(3) 避免狀態的迂回搜索。(4) 采用并行搜索結構。(5) 為避免陷入局部極小，改進對溫度的控制方式(6) 選擇合適的初始狀態。(7) 設計合

7、適的算法終止準則。也可通過增加某些環節而實現對模擬退火算法的改進。主要的改進方式包括：(1) 增加升溫或重升溫過程。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免算法在局部極小解處停滯不前。(2) 增加記憶功能。為避免搜索過程中由于執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。(3) 增加補充搜索過程。即在退火過程結束后，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。(4) 對每一當前狀態，采用多次搜索策略，以概率接受區域內的最優狀態，而非標準SA的單次比較方式。(5) 結合其他搜索

8、機制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應用。4船舶碰撞相關領域有關模擬退火算法的應用4.1舶碰撞危險的量化研究基本上經歷了四個階段:第一階段是基于交通流理論，以船舶會遇率( 或會遇次數等)、特定水域歷史碰撞事故等，評價特定水域的碰撞危險度。第二階段是從微觀的角度，根據人體行為學及心理學等，以船舶領域或動界評價碰撞危險度。第三階段在確定船舶碰撞危險度時，應該綜合考慮 DDCPA和TTCPA兩方面的影響。第四階段是實現TTCPA與DDCPA 確定碰撞危險度1。船舶會遇態勢的劃分船舶會遇是海上最常見的船舶交會態勢，其劃分原則是根據國際海上避碰規則、航海習慣和自動避碰方法三者綜合分

9、析的結果。由文獻 1可知，海上互見中的兩船，可劃分為對遇 (F)、交叉相遇 (A、B、E)和追越 (C、D)幾類會遇態勢，如圖1所示。圖中對相對舷角為F、A、B區域的來船，本船為讓路船。對來自F、A區域的船，本船應采取向右轉向避讓操縱，對來自B區域的船，因與本船的相對舷角較大，可采用向左轉向避讓操縱；對相對舷角為E、D、C區域的來船，本船可視為直航船而不采取任何避讓操縱，只有當出現緊近局面時，本船才采取避讓操縱。圖一 互見中的兩船會遇態勢的劃分4.2船舶碰撞危險度的確定本文將綜合前人的研究成果 ,以來船與本船構成的方位 (B)、距離 (D)、船速比 (K)、最近會遇距離 ( DCPA)和最近會

10、遇時間 ( TCPA)為參數 ,給出來船與本船構成的碰撞危險度估計。設與本船會遇的目標船數為n1艘 , UDCPAi 、UTCPAi、UDi、UBi 、UKi為目標船i各參數的危險隸屬度且屬于 0, 1， i = 1, 2, ,n，則目標船i的碰撞危險度fi可表示18 為： fi (uDCPAi、uTCPAi、uDi、uBi、uKi ) = aDCPA uDCPAi + aTCPAuTCPAi+ aDuDi+aBuBi +aKuKiD1為最晚避讓距離，D2為可采取避讓措施距離；C為碰角 (0C 180°)；W為常數，取W =2；aDCPA、aTCPA 、aD、aB、aK為目標船參數的

11、權重，均屬于 0, 1,且aDCPA+aTCPA +aD+aB+aK=1。4.3目標函數模型當本船與多個來船會遇時 ,如何根據多個來船的會遇態勢 ,選擇較為合理和最為有效的轉讓幅度問題，一直是人們關注和研究的焦點。 將本船與多船間的轉向避碰幅度問題視作一類多目標函數優化問題 ,然后應用模擬退火算法 ,從可行解空間中求出滿足目標函數和約束條件的最優轉向避碰幅度解 ,使得轉讓后的本船滿足: 與各會遇目標船間的碰撞危險度盡量減小; 盡量使轉讓的角度最小； 航行最少的時間后，本船恢復原航向、航速。4.4模擬退火算法的最優轉向避碰幅度決策模擬退火算法2 是源于對固體退火過程的直接簡單模擬而建立起的一種通

12、用隨機搜索技術。由于其具有穩鍵性、健壯性和高效性等特點 ,近年來已在求解許多組合優化問題 ,特別是在解 NP完全問題中得到了成功應用。 本文將結合船舶避碰實際 ,把模擬退火算法引入到船舶避碰決策領域 ,在可行解空間中隨機搜索 ,從中求出本船滿足多目標函數和約束條件的最優轉向幅度。 具體實現步驟為：以均勻概率在可行解空間 30, 180中隨機產成一個轉向幅度 x ,作為初始狀態的當前最優點;設置初始溫度 T0 = Tmax；設置循環初值 num = 1；算出本船轉向前與各目標船構成的碰撞危險度 fi和轉向x 后與各目標船構成的碰撞危險度 f1i (x) ,i = 1, 2, ,n；計算殘差和；對當前最優點x作一隨機擾動 (如加白噪聲 ) ,產生一個新的最優點。重新計算增量；應用 Meteopolis規則確定是否接受新產生的最優點。如果 < 0,則接受該新產生的最優點為當前最優點 ,否則以概率接受該新產生的最優點為當前最優點；判斷num ,若num <終止步數,則num = num+ 1 ,轉至步驟 ,否則進行降溫 ,使 T0 取值為T，這里0<T<1；若連續若干次降溫后最優點沒有改進或降溫到給定的閾值 ,或殘差最小 ,則輸出當前優點 ,計算結束;否則轉至步驟。參考文獻：1