模擬退火演算法引數分析

模擬退火演算法引數分析

一  模擬退火演算法介紹

模擬退火演算法是一種尋找全域性最優解的優化方法,核心思想就是以一定概率接收差解,並且這個概率會隨著退火溫度逐漸降低。一個比較形象的比喻是:一個鍋底凹凸不平有很多坑的大鍋,晃動這個鍋使得一個小球使其達到全域性最低點。一開始晃得比較厲害,小球的變化也就比較大,在趨於全域性最低的時候慢慢減小晃鍋的幅度,直到最後不晃鍋,小球達到全域性最低。

演算法流程如下(最大值問題尋優):

     

   特點:與爬山法比較,最明顯的特點就是,更容易跳出區域性最優解,找到全域性最優解。

   重點來啦,想要用好模擬退火演算法,使演算法收斂,瞭解其各個引數隱含的作用十分必要。

二  影響模擬退火演算法效能的關鍵引數

對演算法影響較大引數如下:

1退火起始、終止溫度

2降溫速度

3測度的計算

4狀態轉換

5接收差解的容忍度

6迭代次數

 

三 各關鍵引數對演算法影響的討論

1退火起始溫度、終止溫度

  

正如前面晃鍋的比喻,這兩個引數決定著晃鍋的劇烈程度。起始溫度越大,晃鍋越劇烈,越容易接收差解,狀態跳動隨機性越大。終止溫度決定著演算法將要停止時,晃鍋的幅度,要是演算法穩定的收斂,終止溫度要設定的比較低(比如,是起始溫度的1000倍)。

2降溫速度

 

 這個引數一般設定為0.99或0.98,越小降溫越快,如果設定過小,就如同淬火一下,演算法來不及充分尋優。

3測度計算

  

測度沒什麼好說的,就是要準。測度的計算具體問題具體分析。

4狀態轉換


  狀態轉換很重要,狀態的搜尋、跳轉策略直接影響著演算法的效能。比如根據具體的問題去分析,狀態有沒有邊界,如果有邊界的話,在狀態跳轉時要用邊界限制。狀態轉換是從當前狀態至下一狀態,每一次跳動都是隨機的,但不是完全隨機的,是在一定範圍內進行的跳動。那麼,兩個問題來了,

<1>範圍怎麼確定?

<2>範圍確定後,狀態怎麼轉換?

回顧一下,退火的跳動幅度是隨著溫度的下降逐漸降低的,因此,跳動範圍須與溫度建立關係,隨溫度下降,跳動範圍減少。

這個減少可以是線性的,也可以是非線性的。

範圍確定了,下一次狀態的跳轉可由高斯隨機數生成,通過控制高斯方差就可以控制跳動範圍。

狀態轉換完全隨機會怎樣?

完全隨機意味著 狀態開始時亂跳,溫度降下來後也亂跳,這就就違背了退火演算法思想。

 

5接受差解的容忍度

接受差解的容忍度由s1根據測度函式值的水平進行調節。容忍度既不能太大也不能太小。

容忍度太大了,演算法啥解都接受,這個算就廢了。容忍度太小了,演算法不會接受差解,這樣做的後果就是優化後的狀態一定是區域性最優的,也違背了退火演算法的思想。

 

6迭代次數

迭代次數控制著演算法尋優的充分程度,需根據具體問題調節。

如理解有偏差,還請指教。