基于平均增益模型的模擬退火算法計算時間分析

周竹連，周珍勝，馮 樂，湯華椿，吳 磊，譚 棉

（1.貴州民族大學 數(shù)據(jù)科學與信息工程學院；2.貴州民族大學 貴州省模式識別與智能系統(tǒng)重點實驗室，貴州 貴陽 550025）

0 引言

模擬退火算法由Metropolis 等［1］首次提出，并廣泛應用于組合優(yōu)化領域，目前在神經網(wǎng)絡超參數(shù)優(yōu)化、神經網(wǎng)絡結構優(yōu)化、組合優(yōu)化、部分機理模型難以建立的黑箱優(yōu)化問題和多目標優(yōu)化問題方面都進行了一定研究［2-8］。但關于模擬退火算法理論分析，尤其是計算時間分析的研究不多，因此模擬退火算法計算時間分析是如今國內外學者關注的熱點話題［9］。

近年來，關于模擬退火算法設計的研究已經有了一些成果，例如，常媛等［9］對模擬退火算法、遺傳算法和啟發(fā)式算法在鋼筋下料優(yōu)化問題上進行比較，不同算法都具有各自的特點；傅文淵等［10］將模擬退火算法與布朗運動相結合，提高了算法的搜索速度與穩(wěn)定性；張德富等［3］將模擬退火算法與啟發(fā)式算法相結合，提出了混合模擬退火算法，并驗證了該算法在三維裝箱問題上的有效性。此外，結合遺傳算法，Yi 等［4］改進了模擬退火算法，有效減少了立體車庫調度優(yōu)化問題的優(yōu)化時間；Guo 等［5］基于模擬退火算法和遺傳算法設計了一種混合算法，在機械系統(tǒng)上提高了摩擦力參數(shù)識別精度；Fan 等［6］將模擬退火算法與免疫機制加入遺傳算法中以解決圖像聚類問題，并解決了遺傳算法易陷入局部最優(yōu)的問題；Yu 等［7］將改進的遺傳算法和模擬退火算法用于測試數(shù)據(jù)集的生成，實驗結果表明其效果優(yōu)于遺傳算法；Jia 等［8］改進了模擬退火算法，并將其用于在大數(shù)據(jù)集中搜索離群數(shù)據(jù)，有效提高了搜索速度；李元香等［11］將動力系統(tǒng)理論引入模擬退火算法的理論分析，通過建立動力系統(tǒng)模型，分析了模擬退火算法的收斂性。此外，其將弛豫模型引入模擬退火算法時間復雜性分析，設置動態(tài)馬爾科夫鏈長度的動力系統(tǒng)模型分析了模擬退火算法的收斂性，并給出了模擬退火算法的停止準則［12］。李元香等［13］還針對模擬退火算法的運行機制提出動態(tài)自適應退火溫度設置方法。綜上所述，模擬退火算法在工業(yè)應用與理論研究等方面都有了一定基礎，但主要針對算法設計，關于模擬退火算法計算時間分析的研究仍然較少。因此，關于該領域需要作進一步研究。

另外，國內外學者在算法計算時間分析方面也進行了研究，例如，He 等［14］提出漂移分析理論，并嚴格分析了進化算法在采用不同變異算子和精英選擇算子時種群規(guī)模對計算時間的影響［15］；Yu 等［16］提出轉換分析法，該方法主要討論了不同變異算子下進化算法的期望運行時間；黃翰等［17］建立一種等態(tài)關系模型與強/弱態(tài)偏序關系模型，分析了進化算法與不同變異算子的關系；馮夫健等［18］提出等同關系模型，該模型分析了不同選擇算子和不同變異算子進化算法的性能對比關系；張宇山等［19-20］提出平均增益模型，以球函數(shù)為例分析了進化算法的平均計算時間，并提出停時理論模型來分析進化算法的首達時間，其還在平均增益模型上加入鞅論和停時理論，分析了連續(xù)型演化算法的平均首達時間上界；Huang 等［21］基于平均增益模型提出一種求解連續(xù)優(yōu)化問題的進化算法運行時間實驗方法。總體而言，目前關于算法理論的研究主要集中在計算時間分析與收斂性分析上，而首達時間是計算時間分析中的一個重要概念，指算法首次找到最優(yōu)解所花費的運行時間（迭代次數(shù)）。

本文將以首達時間作為分析工具展開研究，主要目的在于建立模擬退火算法的平均增益模型，并加以驗證，通過理論分析與數(shù)值實驗的方式驗證平均增益模型在模擬退火算法上的可行性。因此，基于平均增益模型推導模擬退火算法的計算時間上界，并在變異算子滿足正態(tài)分布與均勻分布時分析線性函數(shù)上模擬退火算法的期望首達時間。數(shù)值實驗結果驗證了理論推導的正確性，并且理論分析與數(shù)值實驗結果一致，表明平均增益模型應用于模擬退火算法是可行的。

1 模擬退火算法平均增益模型

1.1 模擬退火算法隨機過程

模擬退火算法的原理來源于固體退火，是一種基于概率的算法［1］。該算法的思想是從一個較高的初始溫度開始，以一定速率降溫，直到溫度降到終止條件為止。在每個溫度下進行搜索，每輪搜索以特定規(guī)則產生新解，并按照Metropolis 準則接受新解。假設T0表示初始溫度，任取初始解，在每個溫度下迭代L輪，也稱為Metropolis 鏈長。具體模擬退火算法流程如下：

算法1模擬退火算法流程

根據(jù)算法1 可知，步驟6 表示當前解Yt通過隨機擾動產生一個新解Ynew，其中f(Yt)為Yt的代價函數(shù)；步驟10-16表示按照Metropolis 準則判斷是否接受新解。如果滿足終止條件，則輸出最優(yōu)解，結束程序。否則按衰減函數(shù)衰減后返回步驟3。

設(Ω，U，)是概率空間，映射f()：Ω →Rn稱為n維的隨機變量［20］。本文考慮找到一個全局最優(yōu)解x*∈Ω，使得目標函數(shù)值最小f(x*)=minf()。

定義1設是一個隨機過程，當任意的t≥0，T≥Tend，滿足≥0 成立，且存在目標精度ε＞0，那么模擬退火算法的首達時間為hε=min

定義1 表明，模擬退火算法的首達時間是在目標精度ε下得到的，首達時間的期望表達為E(hε)，稱為期望首達時間。模擬退火算法的首達時間表示算法找到目標解的最小降火次數(shù)。

1.2 模擬退火算法計算時間分析

下面給出模擬退火算法的平均增益定義：

引理1 給出了模擬退火算法的平均增益模型求解期望首達時間上界的公式。基于引理1，將以線性函數(shù)為個案討論模擬退火算法的計算時間。

2 模擬退火算法個案平均計算時間分析

本節(jié)將運用模擬退火算法的平均增益模型分析線性函數(shù)的期望首達時間上界。

2.1 標準正態(tài)分布條件下模擬退火算法計算時間分析

在算法1 的基礎上加入變異算子與選擇算子，改進的算法描述如下：

算法2基于變異算子的模擬退火算法

定理2在線性函數(shù)f(X)上，最小值為W0時，模擬退火算法的期望首達時間上界如下：

假設函數(shù)f的起始函數(shù)值為W0+ncW0，則=ncW0，c=Wi表示xi的權重，根據(jù)定理2，期望首達時間上界推導為：

證畢。

由定理2 可得模擬退火算法在變異算子滿足標準正態(tài)分布時的上界為下一節(jié)將分析變異算子為均勻分布時的計算時間上界。

2.2 均勻分布條件下模擬退火算法計算時間分析

3 數(shù)值實驗分析

本節(jié)實驗采用變異算子為N(0，1)和來驗證定理2與定理4的準確性。

3.1 變異算子為N(0，1)的計算時間分析

Table 1 Comparison of expected first hitting time and theoretical upper bound of simulated annealing algorithm表1 模擬退火算法期望首達時間與理論上界比較

圖1 顯示了當變異算子為N(0，1)，在n=10 與n=20時的迭代過程。由圖1 可以看出，存在多次迭代得到的目標函數(shù)值相同的情況，表明模擬退火算法在迭代過程中，當前解優(yōu)于新解，并且Metropolis 準則沒有發(fā)生，導致多次迭代下得到的最優(yōu)函數(shù)值相同，整個優(yōu)化過程呈遞減趨勢，直到滿足終止條件為止。從圖1（a）和圖1（b）的迭代次數(shù)得出，隨著n的增大，迭代次數(shù)也增加，數(shù)值實驗結果與理論分析一致。

3.2 變異算子為U(-，)的計算時間分析

Fig.1 Optimization process of function values圖1 函數(shù)值優(yōu)化過程

Table 2 Comparison of expected first hitting time and theoretical upper bound of simulated annealing algorithm表2 模擬退火算法期望首達時間與理論上界比較

4 結語

Fig.2 Optimization process of function values圖2 函數(shù)值優(yōu)化過程

本文針對模擬退火算法的首達時間理論分析問題，建立模擬退火算法的平均增益模型。基于平均增益模型求解模擬退火算法采用標準正態(tài)分布變異算子和均勻分布變異算子時在線性函數(shù)上的期望首達時間，并通過數(shù)值實驗進行驗證，計算時間與問題規(guī)模n有關。理論分析結果表明，當n越大時，期望首達時間越長，且數(shù)值實驗結果與理論分析相吻合。此外，通過理論分析與實驗論證了平均增益模型能夠用于分析模擬退火算法計算時間。未來工作中，將應用模擬退火算法的平均增益模型建立計算時間對比模型，繼續(xù)深入探索與分析模擬退火算法計算時間。