如何用隨機方法求解組合優化問題（六）
模擬退火算法的參數選擇
這是一篇筆記，是對于B站up主馬少平的視頻（第四篇 如何用隨機方法求解組合優化問題（六））的學習與記錄。
算法實現需要確定的參數：
- 初始溫度 \(t_0\)；
- 溫度 \(t\) 的衰減函數，即溫度的下降方法；
- 算法的終止準則，終止溫度 \(t_f\) 或者終止條件；
- 每個溫度 \(t\) 下的馬爾可夫鏈長度 \(L_k\)，即算法的內循環次數。
原則上初始溫度越高越好，但是溫度太高可能會導致求解效率下降。
【資料圖】
初始溫度 \(t_0\) 的選取(1)
基本原則：
- 足夠高的初始溫度，使系統可以等概率處于任何一個狀態；
“足夠高”這個標準與具體的問題有關。
按照模擬退火算法，遇到好解則百分之百接受，遇到差解則按概率接受，設概率為 \(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\) 需要設置為一個比較大的數，比如0.95、0.98......需要根據具體的問題做一些試驗。
通過設置一個較大的 \(P_0\)，就可以計算出足夠大的初始溫度 \(t_0\)。
其中 \(\Delta f(i,j)\) 為狀態 \(j\) 與狀態 \(i\) 的指標函數差，可由隨機產生的序列 \(S\) 計算
\[\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)\)有多種計算方式，可以是：
- 最大值與最小值的差；
- 兩兩做差取絕對值，再除以狀態數的平方(實際上是求平均值)；
- 兩個相鄰的狀態做差取絕對值，再除以狀態數。
初始溫度 \(t_0\) 的選取(2)
假設在 \(t_0\) 下隨機地生成一個狀態序列，分別用 \(m_1\) 和 \(m_2\) 表示指標函數下降的狀態數和指標函數上升的狀態數，\(\overline{\Delta f(i,j)}\) 表示指標函數增加的平均值。則 \(m_2\) 個狀態中，被接受的個數為：
\[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\)，然后計算出 \(t_0\)。
溫度的下降方法
基本原則：溫度下降足夠緩慢。
“足夠緩慢”這個標準與實際問題有關。
也不能太緩慢，否則會使計算效率下降。
等比例下降
\[t_{k+1} = \alpha t_k \quad\quad 0 < \alpha < 1\]\(\alpha\) 是一個需要提前確定的常數，比如：0.99或0.95......
等值下降
\[t_{k+1} = t_k - \Delta t\]在等值下降方法中，對于 \(\Delta t\) 的選取非常重要。如果太小，對于一開始來說太慢；如果太大，對于后期來說難以收斂。
等比例下降較為常用。
每一溫度下的停止準則
在每個溫度下要有足夠的交換次數
在模擬退火算法的內循環是在保持溫度不變的情況下，反復地進行狀態的交換。
理論上來說，在每一個溫度下都應該有足夠的交換次數，這樣才能保證不同狀態的指標函數值都能達到一個平穩的分布狀態。
但是交換次數過多將影響計算效率，因此需要折中選擇。
一般來說問題越復雜，則交換次數應該越多。
下面介紹一種常用的方法叫做固定長度方法，這里的“長度”是指“交換次數”。
固定長度方法
- 在每一個溫度下，都使用相同的 \(L_k\)（即每一個溫度下，都使用相同的交換次數）；
- \(L_k\) 的選取與具體的問題相關，一般與鄰域的大小直接關聯，通常選擇為問題規模 \(n\) 的一個多項式函數。
算法的終止原則
- 基本原則：溫度足夠低；
- 零度法：溫度小于某個給定值 \(\varepsilon>0\) 時結束；
- 循環總控制法：溫度下降次數達到給定次數 \(K\) 時結束；
- 無變化控制法：在相鄰的 \(n\) 個溫度中得到的指標函數值無變化時結束。
關鍵詞：
相關文章
精彩推送
