退火演算法怎麼運用

A. 模擬退火演算法

退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態，然後逐步降溫使之冷卻，最後分子以低能狀態排列，固體達到某種穩定狀態。物理退火包括一下3個過程：

模擬退火演算法分為三部分：初始解、解空間以及目標函數，分別對應物理退火過程中的初始溫度、降溫以及最終溫度。

模擬退火演算法中，退火方式對演算法有很大影響。如果溫度下降過慢，演算法的收斂速度會大大降低。如果溫度下降過快，可能會丟失極值點。為了提高模擬退火演算法的性能，許多學者提出了退火的各種方式，比較有代表性的有以下幾種：

以上三種退火方式各有優缺點以及適用的場景，需針對具體的應用進行選擇。

B. 什麼是退火演算法

模擬退火的基本思想:
(1) 初始化：初始溫度T(充分大)，初始解狀態S(是演算法迭代的起點)， 每個T值的迭代次數L
(2) 對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步。

C. 退火演算法的應用領域及示例

作為模擬退火演算法應用，討論旅行商問題(Travelling Salesman Problem,簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i,j) i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。
求解TSP的模擬退火演算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1,……,n}的所有循環排列的集合,S中的成員記為(w1,w2,……,wn)，並記wn+1= w1。初始解可選為(1,……,n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的產生 隨機產生1和n之間的兩相異數k和m,
若k<m,則將
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變為：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變為：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。
也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(w1,w2,……,wn)變換為(u1,u2,……,un)，則代價函數差為：
根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序：
Procere TSPSA:
begin
init-of-T; { T為初始溫度}
S={1,……,n}; {S為初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 從當前迴路S產生新迴路S′}
Δt:=f(S′））-f(S);{f(S)為路徑總長}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：
⑴ 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。
⑵ 退火速度問題。
模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
⑶ 溫度管理問題。
溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式：
T(t+1)=k×T(t)
式中k為正的略小於1.00的常數,t為降溫的次數 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。
缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。
經典模擬退火演算法的缺點：
⑴如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；
⑵如果降溫過程過快，很可能得不到全局最優解。
􀂄 模擬退火演算法的改進
⑴ 設計合適的狀態產生函數，使其根據搜索進程的需要
表現出狀態的全空間分散性或局部區域性。
⑵ 設計高效的退火策略。
⑶ 避免狀態的迂迴搜索。
⑷ 採用並行搜索結構。
⑸ 為避免陷入局部極小，改進對溫度的控制方式
⑹ 選擇合適的初始狀態。
⑺ 設計合適的演算法終止准則。
也可通過增加某些環節而實現對模擬退火演算法的改進。
主要的改進方式包括：
⑴ 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。
⑵ 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。
⑶ 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。
⑷ 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。
⑸ 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。
⑹上述各方法的綜合應用。

D. 模擬退火演算法優化BP神經網路

bp神經元網路的學習過程真正求解的其實就是權值的最優解，因為有可能會得出局部最優解，所以你才會用模擬退火來跳出局部最優解，也就是引入了逃逸概率。在這里你可以把bp的學習過程理解成關於 誤差=f（w1,w2...） 的函數，讓這個函數在模擬退火中作為目標函數，再加上模擬退火的一些初始參數（初始溫度啊，退火速度啊等等），就能找到權值解空間的一個不錯的最優解，就是一組權向量。把權向量帶入到bp當中去，輸入新的對象，自然就能算出新的輸出了。
演算法學習要腳踏實地，你要先學會神經元，在學會退火，兩個的結合你才能理解。

E. 改進模擬退火演算法與傳統模擬退火演算法相比優缺點是什麼，如有缺點該如何改進

1、模擬退火演算法是一種新的隨機搜索方法,它是近年來提出的一種適合於解決大規模組合優化問題的通用而有效的近似演算法。與以往的近似演算法相比,模擬退火演算法具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優點。
2、模擬退火演算法新解的產生和接受可分為如下四個步驟：
第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。
第三步是判斷新解是否被接受,判斷的依據是一個接受准則，最常用的接受准則是Metropo1is准則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。

F. 實際問題中可以用到模擬退火演算法的有哪些

模擬退火是一種優化演算法，它本身是不能獨立存在的，需要有一個應用場合，其中溫度就是模擬退火需要優化的參數，如果它應用到了聚類分析中，那麼就是說聚類分析中有某個或者某幾個參數需要優化，而這個參數，或者參數集就是溫度所代表的。它可以是某項指標，某項關聯度，某個距離等等

G. 模擬退火法^[1，]

模擬退火演算法最早在1953年由 Metropolis等人提出。在地球物理中的最早應用是Rothman在1983年利用模擬退火演算法處理地震資料的剩餘靜校正。模擬退火法也是類似於蒙特卡洛法的隨機搜索方法。但是在產生模型的過程中引入一些規則，能有效地加快搜索速度，有時又稱這類方法為啟發式蒙特卡洛法。

模擬退火法概念源於統計物理學，是模擬固體熔化狀態逐漸緩慢冷卻最終達到能量最小的結晶狀態的物理過程。對於一個熔化的金屬，當處於某個溫度的熱平衡狀態時，它的每一個分子都有它可能所處的狀態，有些分子可能能量高一些，有些分子可能能量低一些，分子處於何種狀態的概率由分子所具有的能量決定。設分子所有可能的能級總數為n(微觀粒子的能量都是量子化的，不連續的)，則分子處於某種狀態的概率滿足玻爾茲曼概率分布:

地球物理反演教程

其中:Ei為第i個分子的能量;K為玻爾茲曼常數;T為絕對溫度;n為分子所有可能的能級總數，分母稱為配分因子;p_i為第i個分子處於能量E_i的概率。

如果把地球物理反演的模型向量看作分子，把目標函數看作分子的能量，把目標函數的極小值看成分子冷卻結晶的最小能量，反演問題(最優化問題)可以模擬式(8.11)金屬退火的過程，通過緩慢地減小溫度進行反演，使目標函數(能量)逐漸達到極小值，這時所對應的模型(分子狀態)就是反演結果。

為了改善於蒙特卡洛法的隨機搜索方法，1953年 Metropolis等人在產生模型的過程中引入Metropolis接受准則，模型產生並不是完全隨機，而是以前一個模型為基礎隨機產生。對能量減小的模型完全接受，對能量增加的模型按一定的概率接受，這樣能有效地加快搜索速度，同時又有可能跳出局部極小值。具體如下:

設原來模型向量為m_i，新的模型為m_i+1(在m_i基礎上隨機修改產生)，各自的能量(目標函數)為E(m_i)和E(m_i+1)。如果E(m_i+1)＜E(m_i)，則目標函數在減小，新模型可以接受。如果E(m_i+1)＞E(m_i)，則目標函數在增加，按照一定概率來確定是否接受新的模型。具體規則見式(8.12):

E(m_i+1)＜E(m_i) 完全接受m_i+1為新模型

地球物理反演教程

式(8.12)就是Metropolis接受准則。它使得反演過程可以接受使目標函數增加的模型，因此也就使得模擬退火法有可能跳出局部極小，收斂於全局極小值點。由於玻爾茲曼常數K只是起到尺度因子的作用，在實際計算中K可取為1來簡化公式。從式(8.12)可以看出，當溫度較低時，p_i+1/p_i較小，因此接受使能量增加的新模型的可能性較小。而一般溫度較低時，目標函數較小，模型比較靠近真實模型，這時基本上只接受使目標函數減小的模型，使模型盡快收斂於極小值點。

在模擬退火反演中，要求溫度T隨著迭代次數的增加而緩慢降溫。常用的溫度函數有兩種。

(1)指數下降型:

T_k=T₀·exp(-ck^1/N) (8.13)

式中:k為迭代次數;c為衰減因子;N為模型參數的個數;T₀為初始溫度。上式也可以改寫為

地球物理反演教程

通常選擇0.7≤α≤1。在實際應用中可採用0.5或1代替式(8.14)的1/N。圖8.4(a)為指數降溫曲線。採用參數為:T₀=200℃，α=0.99，1/N=0.9。

(2)雙曲線下降型:

T=T₀α^k (8.15)

式中:T₀為初始溫度;k為迭代次數;α為衰減因子，通常取0.99。初始溫度T₀不能取得太高，否則增加計算時間浪費機時;T₀也不能太低，否則模型選取不能遍及整個模型空間，只是在初始模型附近選取，不能進行全局尋優。所以T₀的確定只有通過實驗計算得到。圖8.4(b)為雙曲線降溫曲線。採用參數為:T₀=200℃，α=0.99。從圖8.4可以看出通過對不同溫度曲線和相關參數進行選擇，可以控制溫度下降的方式和速度。

圖8.4 模擬退火法降溫曲線

模擬退火法主要有三種:

(1)MSA演算法(Metropolis Simulated Annealing);

(2)HBSA演算法(Heat Bath Simulated Annealing);

(3)VFSA演算法(Very Fast Simulated Annealing)。

圖8.5 模擬退火MSA演算法程序流程圖

前面介紹的利用 Metropolis接受准則的演算法就是經典的模擬退火法。圖8.5為模擬退火 MSA演算法的程序流程圖。從中可以看出 MSA演算法有一套模型修改准則，依次改變模型參數，每次改變都是在原來模型基礎上改變一個參數，因此容易保持已有搜索成果，持續不斷地向目標函數最小值點接近，因此搜索效率比蒙特卡洛法高。此外，MSA演算法允許接受使目標函數增加的模型，這樣又易於跳出局部極小，達到全局極小。但 MSA演算法在任何溫度下和蒙特卡洛法一樣都是在模型全空間進行搜索，不能根據當前溫度和模型減小搜索空間，此外由於模型的修改全憑運氣，所以不可能像前面介紹的最小二乘法那樣目標函數基本上持續減小，而是呈不規則振盪在宏觀上逐漸減小，因此效率較低。

HBSA演算法與 MSA演算法的不同之處是在模型的修改上。也是首先隨機選擇一個初始M維模型向量m₀(它具有M個參數);然後限制各個模型參數可能的取值范圍，對取值離散化。假設每個模型參數都有N個可能的值，首先固定模型第2個參數m₀(2)直到第M個參數m₀(M)保持不變，只修改第1個參數m₀(1);計算m₀(1)的所有取值時的目標函數，然後按式(8.16)計算「概率」，它就是式(8.11)配分因子取1的公式。即

地球物理反演教程

選擇「概率」最大的為模型第1個參數的修改值。照此依次對所有模型參數進行修改完成依次迭代計算。在每次迭代計算中保持溫度不變。隨著迭代次數增加，溫度降低，最終達到穩定狀態，獲得最小能量解。這種方法的計算由於要計算某個參數的所有可能值，所以計算量也是很大的。

1989年Ingber提出了VFSA演算法，由於速度較快，最為常用。它使得模擬退火法從理論走向了實際應用。VFSA演算法在流程上與傳統的模擬退火法相同，但是在模型修改、接受概率以及降溫曲線上有所改進。

(1)模型修改:常規模擬退火法採用高斯隨機分布修改模型，在任何溫度下都是在模型全空間進行搜索。而Ingber提出採用依賴於溫度的似cauchy分布產生新的模型。即

地球物理反演教程

y_i=Tsgn(u-0.5)[(1+1/T^|2u-1|-1](8.18)

其中:m_i為當前模型第i個參數，m'_i為修改後的模型參數;u為[0，1]的隨機數;[A_i，B_i]為m_i和m'_i的取值范圍;sgn( )為符號函數。

採用以上方式能在高溫下進行大范圍的搜索，低溫時在當前模型附近搜索，而且由於似cauchy分布具有平坦的「尾巴」，使其易於迅速跳出局部極值。這一改進大大加快了模擬退火法的收斂速度。

(2)接收概率:當E(m_i+1)＞E(m_i)時，VFSA演算法採用如下概率接受公式:

地球物理反演教程

上式當h→1時變為式(8.12)。h通過實驗獲得。

(3)降溫曲線(退火計劃):Ingber在1989年採用式(8.13)得出指數降溫曲線。從圖8.4可知，溫度下降較快。

總之，VFSA演算法在模型修改、接受概率以及降溫曲線上的改進使得模擬退火演算法收斂速度大大加快。後人在此基礎上還有很多的改進，讀者可以參考相關文獻。

模擬退火法的優點:由於不需要計算偏導數矩陣，不需要解線性方程組(當然正演計算的除外)，結構簡單，易於編程;此外，由於它搜索范圍大，能接受較差模型，因此易於達到全局極小。缺點:隨機搜索，計算量巨大，往往要計算成百上千次正演，這與前面的最小二乘法十幾次的正演計算相比反演時間太長，因此一般應用在一維反演之中，在二維、三維等高維反演中應用較少。