如何用隨機方法求解組合優(yōu)化問題（六）

2023-08-19 06:57:12 來源：博客園

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

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

算法實現(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ù)具體的問題做一些試驗。

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

其中 \(\Delta f(i,j)\) 為狀態(tài) \(j\) 與狀態(tài) \(i\) 的指標(biāo)函數(shù)差，可由隨機產(chǎn)生的序列 \(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ài)數(shù)的平方(實際上是求平均值)；
兩個相鄰的狀態(tài)做差取絕對值，再除以狀態(tài)數(shù)。

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

假設(shè)在 \(t_0\) 下隨機地生成一個狀態(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\)，然后計算出 \(t_0\)。

溫度的下降方法

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

“足夠緩慢”這個標(biāo)準(zhǔn)與實際問題有關(guān)。
也不能太緩慢，否則會使計算效率下降。

等比例下降

\[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ù)過多將影響計算效率，因此需要折中選擇。
一般來說問題越復(fù)雜，則交換次數(shù)應(yīng)該越多。
下面介紹一種常用的方法叫做固定長度方法，這里的“長度”是指“交換次數(shù)”。
固定長度方法
- 在每一個溫度下，都使用相同的 \(L_k\)（即每一個溫度下，都使用相同的交換次數(shù)）；
- \(L_k\) 的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模 \(n\) 的一個多項式函數(shù)。