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

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

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

(資料圖)

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

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

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

基本原則：

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

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

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

\[e^{-\frac{\Delta f(i,j)}{t_0}} = P_0 \approx 1\]

由此可推出：

\[t_0=\frac{\Delta f(i,j)}{\ln(P_0^{-1})}\]

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

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

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

\[\begin{align*}\Delta f(i,j) &= \max\limits_{i\in S}(f(i))-\min\limits_{i\in S}(f(i)) \\\Delta f(i,j) &= \frac{\sum\limits_{i,j\in S}|f(i)-f(j)|}{|S|^2} \\\Delta f(i,j) &= \frac{\sum\limits_{i=0}^{|S|-1}|f(S(i))-f(S(i+1))|}{|S|}\end{align*}\]

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

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

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

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

\[m_2e^{-\frac{\overline{\Delta f(i,j)}}{t_0}}\]

則有平均接受概率：

\[P_0 = \frac{m_1 + m_2 e^{-\frac{\overline{\Delta f(i,j)}}{t_0}}}{m_1 + m_2}\]

求解有：

\[t_0 = \frac{\overline{\Delta f(i,j)}}{\ln\left(\frac{m_2}{m_2P_0-m_1(1-P_0)}\right)}\]

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

溫度的下降方法

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

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

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

等比例下降

\[t_{k+1} = \alpha t_k \quad\quad 0 < \alpha < 1\]

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

等值下降

\[t_{k+1} = t_k - \Delta t\]

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

等比例下降較為常用。

每一溫度下的停止準(zhǔn)則

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

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

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

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

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

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

• 固定長度方法

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

算法的終止原則

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