基于平均增益模型的模擬退火算法計(jì)算時(shí)間分析

周竹連，周珍勝，馮 樂(lè)，湯華椿，吳 磊，譚 棉

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

0 引言

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

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

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

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

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

1.1 模擬退火算法隨機(jī)過(guò)程

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

算法1模擬退火算法流程

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

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

定義1設(shè)是一個(gè)隨機(jī)過(guò)程，當(dāng)任意的t≥0，T≥Tend，滿足≥0 成立，且存在目標(biāo)精度ε＞0，那么模擬退火算法的首達(dá)時(shí)間為hε=min

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

1.2 模擬退火算法計(jì)算時(shí)間分析

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

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

2 模擬退火算法個(gè)案平均計(jì)算時(shí)間分析

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

2.1 標(biāo)準(zhǔn)正態(tài)分布條件下模擬退火算法計(jì)算時(shí)間分析

在算法1 的基礎(chǔ)上加入變異算子與選擇算子，改進(jìn)的算法描述如下：

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

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

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

證畢。

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

2.2 均勻分布條件下模擬退火算法計(jì)算時(shí)間分析

3 數(shù)值實(shí)驗(yàn)分析

本節(jié)實(shí)驗(yàn)采用變異算子為N(0，1)和來(lái)驗(yàn)證定理2與定理4的準(zhǔn)確性。

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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