模擬退火算法的參數(shù)選擇

這是一篇筆記，是對于B站up主馬少平的視頻（第四篇 如何用隨機方法求解組合優(yōu)化問題（六））的學習與記錄。

算法實現(xiàn)需要確定的參數(shù)：

• 初始溫度 \(t_0\)；
• 溫度 \(t\) 的衰減函數(shù)，即溫度的下降方法；
• 算法的終止準則，終止溫度 \(t_f\) 或者終止條件；
• 每個溫度 \(t\) 下的馬爾可夫鏈長度 \(L_k\)，即算法的內(nèi)循環(huán)次數(shù)。

原則上初始溫度越高越好，但是溫度太高可能會導致求解效率下降。

初始溫度 \(t_0\) 的選取(1)

基本原則：

• 足夠高的初始溫度，使系統(tǒng)可以等概率處于任何一個狀態(tài)；

“足夠高”這個標準與具體的問題有關(guān)。

按照模擬退火算法，遇到好解則百分之百接受，遇到差解則按概率接受，設(shè)概率為 \(P_0\)，則有：

由此可推出：

這里的 \(P_0\) 需要設(shè)置為一個比較大的數(shù)，比如0.95、0.98......需要根據(jù)具體的問題做一些試驗。

通過設(shè)置一個較大的 \(P_0\)，就可以計算出足夠大的初始溫度 \(t_0\)。

其中 \(\Delta f(i,j)\) 為狀態(tài) \(j\) 與狀態(tài) \(i\) 的指標函數(shù)差，可由隨機產(chǎn)生的序列 \(S\) 計算

\(\Delta f(i,j)\)有多種計算方式，可以是：

1. 最大值與最小值的差；
2. 兩兩做差取絕對值，再除以狀態(tài)數(shù)的平方(實際上是求平均值)；
3. 兩個相鄰的狀態(tài)做差取絕對值，再除以狀態(tài)數(shù)。

初始溫度 \(t_0\) 的選取(2)

假設(shè)在 \(t_0\) 下隨機地生成一個狀態(tài)序列，分別用 \(m_1\) 和 \(m_2\) 表示指標函數(shù)下降的狀態(tài)數(shù)和指標函數(shù)上升的狀態(tài)數(shù)，\(\overline{\Delta f(i,j)}\) 表示指標函數(shù)增加的平均值。則 \(m_2\) 個狀態(tài)中，被接受的個數(shù)為：

則有平均接受概率：

求解有：

這種選取方法與前一種方法類似，也是需要先確定一個較大的 \(P_0\)，然后計算出 \(t_0\)。

溫度的下降方法

基本原則：溫度下降足夠緩慢。

• “足夠緩慢”這個標準與實際問題有關(guān)。

• 也不能太緩慢，否則會使計算效率下降。

等比例下降

\(\alpha\) 是一個需要提前確定的常數(shù)，比如：0.99或0.95......

等值下降

在等值下降方法中，對于 \(\Delta t\) 的選取非常重要。如果太小，對于一開始來說太慢；如果太大，對于后期來說難以收斂。

等比例下降較為常用。

每一溫度下的停止準則

• 在每個溫度下要有足夠的交換次數(shù)

  在模擬退火算法的內(nèi)循環(huán)是在保持溫度不變的情況下，反復地進行狀態(tài)的交換。

  理論上來說，在每一個溫度下都應(yīng)該有足夠的交換次數(shù)，這樣才能保證不同狀態(tài)的指標函數(shù)值都能達到一個平穩(wěn)的分布狀態(tài)。

  但是交換次數(shù)過多將影響計算效率，因此需要折中選擇。

  一般來說問題越復雜，則交換次數(shù)應(yīng)該越多。

  下面介紹一種常用的方法叫做固定長度方法，這里的“長度”是指“交換次數(shù)”。

• 固定長度方法

  • 在每一個溫度下，都使用相同的 \(L_k\)（即每一個溫度下，都使用相同的交換次數(shù)）；
  • \(L_k\) 的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模 \(n\) 的一個多項式函數(shù)。

算法的終止原則

• 基本原則：溫度足夠低；
• 零度法：溫度小于某個給定值 \(\varepsilon>0\) 時結(jié)束；
• 循環(huán)總控制法：溫度下降次數(shù)達到給定次數(shù) \(K\) 時結(jié)束；
• 無變化控制法：在相鄰的 \(n\) 個溫度中得到的指標函數(shù)值無變化時結(jié)束。