基于熵約束的確定性退火算法綜述

吳征天，戴金宇

（蘇州科技大學(xué) 電子與信息工程學(xué)院，江蘇 蘇州 215009）

資源的組合分配問(wèn)題在理論研究和工程實(shí)際中極為常見(jiàn)，如數(shù)據(jù)壓縮問(wèn)題、模型聚合問(wèn)題、策略規(guī)劃問(wèn)題、區(qū)位優(yōu)化問(wèn)題等。這些問(wèn)題的模型通常是一個(gè)優(yōu)化公式，其成本面是非凸的，有許多局部極小值，因此，尋找全局最小值是一項(xiàng)令人望而卻步的任務(wù)。由于代價(jià)曲面的非凸性，許多傳統(tǒng)方法如梯度下降法會(huì)因初始值選取的不同而陷入較差的局部極小值。一個(gè)最直接的補(bǔ)救方法是選擇多個(gè)初始值，并選擇可實(shí)現(xiàn)的最低成本值作為潛在的全局最小[1]。顯然，由于成本面的結(jié)構(gòu)和資源組合分配的性質(zhì)，這種方法在計(jì)算上是不切實(shí)際的。在這種情況下，同倫方法是有效的。

同倫方法是求解非凸優(yōu)化問(wèn)題的有效方法[2]。與傳統(tǒng)優(yōu)化方法相比，同倫分析法具有如下優(yōu)點(diǎn)：（1）強(qiáng)收斂性，通過(guò)控制參數(shù)來(lái)保證解的收斂；（2）普遍有效性，不管求解的問(wèn)題是否含有參數(shù)，高階級(jí)數(shù)解都能求得；（3）靈活性，對(duì)初始值和輔助算子的選擇不敏感，因此，可以選擇迭代的方法快速得到收斂的解[3]。同時(shí)，F(xiàn)ox提出的“按自然法則計(jì)算”是將大量自然現(xiàn)象與自然規(guī)律中所表現(xiàn)出來(lái)的科學(xué)思想進(jìn)行歸納，并提取其本質(zhì)，用于解決其他新領(lǐng)域中的問(wèn)題[4]，如神經(jīng)網(wǎng)絡(luò)、蟻群算法[5]、協(xié)同進(jìn)化算法[6]等。

Rose 博士于1990 年提出確定性退火技術(shù)[7]，它是一種以溫度為同倫參數(shù)的連續(xù)同倫優(yōu)化技術(shù)[8]，并且它也是按自然法則計(jì)算的一個(gè)分支。參照熱力學(xué)退火過(guò)程，將溫度參數(shù)T 引入問(wèn)題，把求解目標(biāo)函數(shù)的最優(yōu)值轉(zhuǎn)化為求一系列隨溫度變化的自由能函數(shù)的極小，在模式分類(lèi)、圖像分割、矢量量化等領(lǐng)域得到了廣泛應(yīng)用[9-11]。

筆者對(duì)確定性退火技術(shù)進(jìn)行一定的總結(jié)。首先，對(duì)它的熱力學(xué)背景及基本思想作介紹，同時(shí)歸納總結(jié)了確定性退火技術(shù)的研究現(xiàn)狀；其次，從理論分析角度證明確定性退火技術(shù)的可行性；接著，討論了溫度這一參數(shù)對(duì)該技術(shù)的影響，并將該技術(shù)與擁有相似物理背景的模擬退火技術(shù)進(jìn)行分析比較；然后，介紹了確定性退火技術(shù)的應(yīng)用領(lǐng)域；最后，指出確定性退火技術(shù)的發(fā)展挑戰(zhàn)和前景。

1 確定性退火技術(shù)

1.1 基本思想

由統(tǒng)計(jì)物理學(xué)產(chǎn)生啟發(fā)，確定性退火技術(shù)是求解全局最優(yōu)解的一種連續(xù)同倫優(yōu)化方法。該思想來(lái)源于熱力學(xué)退火過(guò)程，將一個(gè)固體物質(zhì)加熱使之熔化成液體，其內(nèi)部微粒的排列由穩(wěn)定的結(jié)晶態(tài)轉(zhuǎn)變成混亂的液態(tài)，然后使溫度緩慢降低，微粒的排列從無(wú)序轉(zhuǎn)變成有序，到達(dá)其結(jié)晶溫度時(shí)，粒子圍繞晶體格點(diǎn)做微小振動(dòng)，此時(shí)該物質(zhì)逐漸變成低能態(tài)的晶格，即達(dá)到固體的基準(zhǔn)態(tài)[12-13]。系統(tǒng)在溫度下降時(shí)達(dá)到這種平衡態(tài)的過(guò)程，可以用統(tǒng)計(jì)物理學(xué)中的吉布斯自由能極小化原理[14]來(lái)描述，即系統(tǒng)在與外界交換熱量而溫度恒定時(shí)，系統(tǒng)自由能下降的方向即為該系統(tǒng)狀態(tài)變化的趨勢(shì)，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)。

確定性退火技術(shù)是由基本信息理論原理（如最大熵和隨機(jī)編碼）在概率框架內(nèi)推導(dǎo)出來(lái)的。以求解的隨機(jī)性（香農(nóng)熵）為約束條件，使特定應(yīng)用成本最小化，并逐漸降低該約束條件。它可以避免許多困擾傳統(tǒng)技術(shù)的糟糕的局部最優(yōu)，而不需要隨機(jī)方法通常需要的緩慢調(diào)度，由該技術(shù)得到的解與初始構(gòu)型的選擇完全無(wú)關(guān)，并且在“溫度”為零的極限下，產(chǎn)生一個(gè)非隨機(jī)（硬）解[1]。

對(duì)于求解極小化問(wèn)題：minE=E（x），E（x）是某一系統(tǒng)的能量。用確定性退火技術(shù)求解該問(wèn)題時(shí)，其最優(yōu)解可由系統(tǒng)自由能函數(shù)的最小值得到。構(gòu)造該系統(tǒng)對(duì)應(yīng)的一個(gè)自由能函數(shù)[15]：F（x，T）=E（x）-TS，其中T 和S 分別是系統(tǒng)的溫度和熵，且溫度控制著系統(tǒng)的能量和熵的平衡[8]。在求解每一個(gè)溫度T 下的最優(yōu)解時(shí)，確定性退火技術(shù)利用信息論中的極大熵原理使F（x，T）最小化[16]，本質(zhì)上也就是對(duì)E（x）最小化；當(dāng)溫度T 從充分大緩慢趨于零時(shí)，F(xiàn)（x，T）也相應(yīng)退化成目標(biāo)函數(shù)E（x）。這種優(yōu)化方式可以看成以溫度為同倫參數(shù)的連續(xù)同倫優(yōu)化方法。同時(shí)，如果要滿(mǎn)足上述的過(guò)程，構(gòu)造的自由能函數(shù)F（x，T）必須符合下述條件：（1）當(dāng)T=∞，F(xiàn)（x，∞）關(guān)于x 的全局極小值極易求出（需要F 是凸函數(shù)，則利用一些傳統(tǒng)優(yōu)化方法極易求解其全局極?。?；（2）當(dāng)T=0，F(xiàn)（x，0）=E（x）。確定性退火技術(shù)的基本思想如圖1 所示。

圖1 確定性退火技術(shù)的求解思路

1.2 研究現(xiàn)狀

為了提高對(duì)確定性退火技術(shù)的理解，在一些比較溫和的假設(shè)下，高溫時(shí)的自由能函數(shù)是凸函數(shù)，因此可以假設(shè)初始值即局部極小值是唯一的，也是全局的[17]。通過(guò)適當(dāng)?shù)耐嘶鸩呗允箿囟冉档?，自由能函?shù)逐漸呈非凸，確定性退火技術(shù)的目標(biāo)就是跟蹤該函數(shù)的全局最小值[18]。文獻(xiàn)[19-29]討論了確定性退火技術(shù)在聚類(lèi)相關(guān)問(wèn)題中的應(yīng)用，將聚類(lèi)問(wèn)題轉(zhuǎn)化為求解全局優(yōu)化問(wèn)題，并將聚類(lèi)模型歸結(jié)為求解極小化，算例表明該方法能夠在開(kāi)發(fā)算法的并行性上帶來(lái)極大的效益。文獻(xiàn)[30-36]將確定性退火技術(shù)應(yīng)用于模式識(shí)別領(lǐng)域。張祥德等設(shè)計(jì)了一個(gè)點(diǎn)匹配算法，得到用于校準(zhǔn)兩個(gè)點(diǎn)集的映射參數(shù)，并由匹配校準(zhǔn)后的點(diǎn)集得出點(diǎn)的對(duì)應(yīng)關(guān)系，實(shí)驗(yàn)結(jié)果表明該算法的有效性[30]；孫冬梅等將點(diǎn)匹配算法與確定性退火算法結(jié)合，得到具有高精確性、高執(zhí)行性、強(qiáng)魯棒性的新方法[31]；曹治國(guó)等提出了基于確定性退火技術(shù)的分類(lèi)器，與最鄰近和貝葉斯分類(lèi)器相比，其識(shí)別率更高[32]；Klock 等在最大熵估計(jì)的框架下提出了一種新的確定性退火技術(shù)，用于解決一個(gè)基本模式識(shí)別問(wèn)題即多維尺度數(shù)據(jù)的可視化，實(shí)驗(yàn)結(jié)果表明該方法優(yōu)于傳統(tǒng)的梯度下降法[34]。文獻(xiàn)[37-42]介紹了應(yīng)用于圖像分割背景下的確定性退火技術(shù)。吳征天等構(gòu)建了一種確定性退火控制技術(shù)用于解決圖分割問(wèn)題，并證明了沿著特定的收斂路徑可以得到圖分割問(wèn)題的近似解[37]；Wu 等提出一種確定性退火的神經(jīng)網(wǎng)絡(luò)算法，用于解決一般的圖分割問(wèn)題[38]；Xu 等考慮通過(guò)聚集節(jié)點(diǎn)和邊來(lái)簡(jiǎn)化大型加權(quán)有向圖的問(wèn)題，提出了一種融合確定性退火算法特征的求解方法[42]。文獻(xiàn)[43-47]研究了確定性退火技術(shù)與矢量量化的關(guān)系，這些研究都來(lái)源于文獻(xiàn)[10]中提出的基于確定性退火的矢量量化理論。Rose 等設(shè)計(jì)了一種改進(jìn)的熵約束矢量量化器，利用確定性退火算法的數(shù)據(jù)聚類(lèi)來(lái)解決傳統(tǒng)的熵約束矢量量化器容易陷入局部極小的陷阱[43]；文獻(xiàn)[44]利用信息理論的最小交叉熵原理，設(shè)計(jì)了一種熵約束樹(shù)結(jié)構(gòu)的矢量量化器，可獲得一致的顯著收益；Miller 等提出了一種新的源信道組合矢量量化方法，利用確定性退火技術(shù)來(lái)避免傳統(tǒng)下降算法所遇到的局部極小問(wèn)題，所得到的矢量量化器能滿(mǎn)足噪聲信道下實(shí)現(xiàn)局部最優(yōu)的必要條件[46]。文獻(xiàn)[48-53]介紹了利用確定性退火算法解決一系列組合優(yōu)化問(wèn)題。算法由拉格朗日乘數(shù)法和Hopfield 型勢(shì)壘函數(shù)的應(yīng)用推導(dǎo)而來(lái)，通過(guò)更新拉格朗日乘數(shù)法全局收斂的迭代過(guò)程找到一種可行的下降方向，利用勢(shì)壘函數(shù)強(qiáng)制使解向全局或近全局最優(yōu)點(diǎn)移動(dòng)；Wu 等還進(jìn)一步給出了一種優(yōu)化神經(jīng)網(wǎng)絡(luò)的迭代方法，并證明該方法是完全穩(wěn)定并收斂于穩(wěn)定的平衡狀態(tài)[50]。文獻(xiàn)[54-57]將確定性退火技術(shù)應(yīng)用于解決旅行商問(wèn)題。求解時(shí)將離散模型轉(zhuǎn)化為連續(xù)模型，楊廣文等給出了一個(gè)簡(jiǎn)單的迭代公式[54]；Dang 等提出一種全局收斂的拉格朗日—?jiǎng)輭镜惴▉?lái)逼近旅行商問(wèn)題的解[55-56]；Baranwal 等提出一個(gè)通用的啟發(fā)式框架來(lái)近似求解多旅行商問(wèn)題及其許多變體的解，該框架獨(dú)立于任何兩對(duì)節(jié)點(diǎn)之間定義的邊，這使得該算法特別適合于諸如“足夠近距離的旅行商問(wèn)題”這樣的變量[57]。文獻(xiàn)[58-59]介紹了確定性退火技術(shù)在數(shù)據(jù)挖掘中的應(yīng)用，解決了神經(jīng)網(wǎng)絡(luò)算法容易陷于局部極優(yōu)的問(wèn)題，并實(shí)現(xiàn)了海量數(shù)據(jù)的聚類(lèi)和降維可視化。文獻(xiàn)[60-62]將確定性退火技術(shù)用于車(chē)輛的路徑規(guī)劃問(wèn)題。文獻(xiàn)[63-66]將確定性退火技術(shù)用于EM 算法，使改進(jìn)的算法可以在不需要初始參數(shù)值的情況下對(duì)參數(shù)進(jìn)行估計(jì)。文獻(xiàn)[67-69]提出了一種確定性退火聚類(lèi)方法來(lái)預(yù)處理輸入數(shù)據(jù)，在電力系統(tǒng)短期負(fù)荷預(yù)測(cè)中取得巨大效益。Gehler 等證明了確定性退火技術(shù)可以應(yīng)用在基于不同的支持向量機(jī)的多實(shí)例學(xué)習(xí)問(wèn)題[70]；李曉花等結(jié)合確定性退火技術(shù)，提出了改進(jìn)的針對(duì)概率多假設(shè)跟蹤算法用于水下純方位多目標(biāo)跟蹤[71]；曹懷虎等提出了基于確定性退火技術(shù)的任務(wù)調(diào)度算法，使區(qū)塊鏈轉(zhuǎn)化為并行處理過(guò)程，提高了響應(yīng)速度[72]；Thomas 等提出了一種基于確定性退火的方法，以避免困擾移相器約束模擬波束形成器的局部最優(yōu)問(wèn)題[73]；姚劍奇等將確定性退火技術(shù)引入陣列稀疏優(yōu)化問(wèn)題[74]。

2 算法的理論分析

對(duì)于求解極小化問(wèn)題：minE=E（x），首先構(gòu)造自由能函數(shù)F（x，T），滿(mǎn)足前面提出的兩個(gè)條件，然后按照下列過(guò)程求解問(wèn)題：

（1）取足夠大的T0，k=0，求解優(yōu)化問(wèn)題：minF（x，Tk），設(shè)最優(yōu)解為xmin（Tk）；

（2）Tk+1＝cTk（0＜c＜1），以xmin（Tk）為初始解，選取一種傳統(tǒng)方法求解minF（x，Tk+1），設(shè)最優(yōu)解為xmin（Tk+1）；

（3）判斷是否滿(mǎn)足收斂準(zhǔn)則，若滿(mǎn)足，則停，xmin（Tk+1）為最優(yōu)解；否則，轉(zhuǎn)（4）；

（4）k=k+1，轉(zhuǎn)（2）。

從上述過(guò)程中不難看出，確定性退火技術(shù)的基本思想是試圖建立一個(gè)映射φ（T），φ（T）在某一點(diǎn)T0的像就是函數(shù)F（x，T0）的某一個(gè)全局最小點(diǎn)。若F（x，T）具有某種連續(xù)性，就有理由認(rèn)為在T 連續(xù)從∞下降到0的過(guò)程中，對(duì)應(yīng)的全局最小點(diǎn)φ（T）也是連續(xù)變化的。在這種連續(xù)性的假設(shè)下，就可能以φ（T+ΔT）為初始點(diǎn)，利用梯度下降法等傳統(tǒng)優(yōu)化方法求得φ（T）；不斷下降T 最終可求得φ（0），即目標(biāo)函數(shù)的全局最小值。

文獻(xiàn)[75]從理論上證明了映射φ（T）的連續(xù)性以及一致連續(xù)性，并強(qiáng)調(diào)該映射的連續(xù)性是影響確定性退火算法的關(guān)鍵因素，倘若不能滿(mǎn)足，使用傳統(tǒng)的優(yōu)化方法就可能無(wú)法搜索到下一時(shí)刻溫度下的全局最優(yōu)點(diǎn)，從而使算法陷入局部極小點(diǎn)。文獻(xiàn)[5]證明了當(dāng)ΔT 的變化很小時(shí)，minF（x，T）與minF（x，T+ΔT）的全局最優(yōu)點(diǎn)φ（T）和φ（T+ΔT）很接近，即可認(rèn)為minF（x，T）的全局最優(yōu)點(diǎn)位于minF（x，T+ΔT）的全局最優(yōu)點(diǎn)所在的局部極小鄰域內(nèi)，所以在溫度T 時(shí)，可將φ（T+ΔT）作為初始點(diǎn)求解minF（x，T）。文獻(xiàn)[13]說(shuō)明了只要溫度下降充分緩慢，最終得到的解為目標(biāo)函數(shù)的全局最優(yōu)解，并證明了全局最優(yōu)點(diǎn)x（T）在[0，+∞]是連續(xù)的，從而證明了全局最優(yōu)值φ（T）在[0，+∞]是連續(xù)的。文獻(xiàn)[30]證明了若F（x，T）為T(mén) 的連續(xù)函數(shù)，minF（x，T）的全局最優(yōu)值為T(mén) 的單調(diào)非增函數(shù)，則退火速率充分緩慢時(shí)該算法的結(jié)果收斂到目標(biāo)函數(shù)E（x）的全局最優(yōu)解。

3 溫度控制與退火過(guò)程

確定性退火技術(shù)是由信息論原理在概率框架內(nèi)推導(dǎo)出來(lái)的，以求解的隨機(jī)性（香農(nóng)熵）為約束條件，使應(yīng)用成本最小化[1]。Fox 證明該技術(shù)的初始點(diǎn)應(yīng)選擇在高溫下，因?yàn)樵谳^高溫度下的解初始化可以減輕非線(xiàn)性效應(yīng)。在高溫時(shí)最大化熵，當(dāng)溫度降低時(shí)逐漸降低該約束條件，當(dāng)溫度為零時(shí)，直接最小化系統(tǒng)的能量函數(shù)，產(chǎn)生一個(gè)非隨機(jī)（硬）解。冷卻計(jì)劃對(duì)該技術(shù)的性能有著至關(guān)重要的影響，快速冷卻將引起淬火效應(yīng)，很可能導(dǎo)致零溫度下的非全局最小值；緩慢冷卻能使系統(tǒng)始終保持平衡狀態(tài)，因此在零溫度時(shí)，系統(tǒng)的能量配置最小，能得到最好的解，但這計(jì)算工作量很大[5]，意味著資源的浪費(fèi)。確定性退火技術(shù)允許幾何冷卻定律：T（t）=ρT（t-1），0＜ρ＜1，且ρ 通常取0.95 到0.99 之間。文獻(xiàn)[76]表明，當(dāng)T（t）=O（（logt）-1）時(shí)，可以實(shí)現(xiàn)全局最小值的概率收斂，其中T（t）為t 時(shí)刻的溫度[18]，這個(gè)結(jié)論在文獻(xiàn)[77]中被進(jìn)一步強(qiáng)化。

雖然在文獻(xiàn)[13]中已經(jīng)證明，自由能函數(shù)的最優(yōu)值及最優(yōu)點(diǎn)連續(xù)變動(dòng)到系統(tǒng)能量函數(shù)的全局最優(yōu)值和全局最優(yōu)點(diǎn)，但如果冷卻速度較快，就不能保證在每一溫度下按傳統(tǒng)優(yōu)化方法求解F（x，T）的極小值正好是全局極小點(diǎn)，更談不上最終達(dá)到自由能函數(shù)的全局最優(yōu)點(diǎn)所對(duì)應(yīng)的基態(tài)，即能量函數(shù)E（x）的全局極小點(diǎn)。因此，如何控制溫度參數(shù)的下降規(guī)律，對(duì)確定性退火技術(shù)的性能有質(zhì)的影響，還需要進(jìn)一步研究。

4 確定性退火與模擬退火

模擬退火技術(shù)和確定性退火技術(shù)有著相似的熱力學(xué)背景，且都是按自然法則計(jì)算的一個(gè)重要分支。表1比較了隨機(jī)退火和確定性退火，從優(yōu)化的角度來(lái)看，有兩個(gè)顯著的區(qū)別[78]。第一個(gè)區(qū)別是，如果所要解決的問(wèn)題是一個(gè)連續(xù)變量的優(yōu)化問(wèn)題，那么確定性退火技術(shù)有可能使用連續(xù)優(yōu)化理論中著名的強(qiáng)大結(jié)論。第二個(gè)區(qū)別是，模擬退火過(guò)程用Metropolis 準(zhǔn)則（通過(guò)蒙特卡羅法）來(lái)模擬系統(tǒng)的平衡態(tài)，其核心是在前期搜索時(shí)不完全拒絕比當(dāng)前解差的解，且引入了概率這一隨機(jī)因素[79]，而確定性退火對(duì)應(yīng)于解析積分（通過(guò)平均場(chǎng)近似），在每一溫度下的優(yōu)化步驟都使用最合適的方法選擇最無(wú)偏和給定條件下不可置否的解[13]，而非利用隨機(jī)概率，因此算法搜索的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)低于隨機(jī)模擬退火過(guò)程，算法的收斂也就非?？焖?。同時(shí)注意到，確定性退火的一個(gè)次要優(yōu)點(diǎn)是，對(duì)于任何問(wèn)題都有固定的T 的最小值和最大值，算法的這一部分不是啟發(fā)式的，在原則上是可以計(jì)算的。

表1 確定性退火與隨機(jī)退火的比較

5 基于確定性退火技術(shù)的應(yīng)用

5.1 在聚類(lèi)問(wèn)題中的應(yīng)用

傳統(tǒng)的聚類(lèi)模型可以歸結(jié)為求解極小化問(wèn)題[19]：minD=（d（xi，yi））2，對(duì)于任意的Y={y1，y2，…，yM}及J={j1，j2，…，jM}，稱(chēng){Y，J}為聚類(lèi)問(wèn)題的一個(gè)實(shí)例，引入溫度T，將聚類(lèi)問(wèn)題看作一個(gè)物理系統(tǒng)，系統(tǒng)取實(shí)例{Y，J}的概率為P{Y，J}。定義物理系統(tǒng)的能量函數(shù)和熵函數(shù)分別為

在每一溫度下，利用極大熵原理，使熵H 取極大的概率分布P{Y，J}稱(chēng)為物理系統(tǒng)的平衡態(tài)，使P{Y，J}取極大的實(shí)例{Y，J}稱(chēng)為聚類(lèi)系統(tǒng)的最可幾實(shí)例，通過(guò)求解變分問(wèn)題

可得到

其中U∝1/T，P{Y，J}為溫度T 時(shí)系統(tǒng)的平衡態(tài)，考慮其邊緣分布

使P（Y）極大的y1，y2，…，yM應(yīng)使F（y1，y2，…，yM，U）取極小，使概率分布極大的y1，y2，…，yM稱(chēng)為聚類(lèi)系統(tǒng)在溫度T 時(shí)的最可幾結(jié)構(gòu)。因此，可以通過(guò)求解自由能函數(shù)F（y1，y2，…，yM，U）的極小來(lái)得到聚類(lèi)問(wèn)題的解。

接著，給出F（y1，y2，…，yM，U）在T=0 和T=∞下的情況，考察

該聚類(lèi)算法具有較強(qiáng)的實(shí)用性，可適用于大規(guī)模的數(shù)據(jù)處理[19-20]。

5.2 在旅行商問(wèn)題中的應(yīng)用

設(shè)X＝{x1，x2，…，xN}是n 維歐式空間內(nèi)一集合，表示旅行商問(wèn)題中的城市集，Y＝{y1，y2，…，yN}是對(duì)應(yīng)于X的一組向量參數(shù)集，表示旅行商問(wèn)題的一個(gè)最優(yōu)解，V 稱(chēng)為關(guān)聯(lián)集，，定義V＝{vxj}是合法的。則旅行商問(wèn)題可以描述為求Y 和V，使得D（Y，V）＝極小，其中yj為第j 類(lèi)Cj的代表元，d（x，yj）為x 與yj的距離。若再加上使最小的限制，則求解旅行商問(wèn)題可通過(guò)求解下述問(wèn)題

若xi屬于yj所對(duì)應(yīng)的類(lèi)，則xi稱(chēng)為售貨員走的第j 個(gè)城市。λ 是一可變系數(shù)，用來(lái)衡量第二項(xiàng)的關(guān)鍵程度。

（1）取U0=0，minF（Y，0）的最優(yōu)點(diǎn)為

（2）Uk+1=T（UK）（函數(shù)T 滿(mǎn)足Uk+1＞Uk），以Ymin（Uk）作為初始點(diǎn)求解minF（Y，Uk+1），設(shè)求得的最優(yōu)點(diǎn)為Ymin（Uk+1）；

（3）判斷是否滿(mǎn)足收斂準(zhǔn)則，若滿(mǎn)足，則Ymin（Uk+1）作為旅行商問(wèn)題的一個(gè)最優(yōu)解；否則，轉(zhuǎn)（4）；

（4）k=k+1，轉(zhuǎn)（2）。

該算法收斂于旅行商問(wèn)題的全局最優(yōu)解，當(dāng)U＝∞，即T=0 時(shí)，F(xiàn)（Y，U）的第一項(xiàng)為0，第二項(xiàng)為最短路徑[54-56]。

5.3 在點(diǎn)匹配問(wèn)題中的應(yīng)用

該算法對(duì)噪聲、平移、旋轉(zhuǎn)、丟失點(diǎn)和出格點(diǎn)都有較強(qiáng)的魯棒性，具有廣泛的應(yīng)用[30-31]。

6 挑戰(zhàn)和展望

自Rose 于1990 年提出確定性退火技術(shù)以來(lái)，受到了許多學(xué)者的關(guān)注。它最初僅僅作為一優(yōu)化技術(shù)用于聚類(lèi)分析，隨著研究的不斷深入，該技術(shù)在模式識(shí)別以及人工智能領(lǐng)域嶄露頭角，取得了一些實(shí)質(zhì)性的、令人滿(mǎn)意的成果。但是，它仍然面臨著一些挑戰(zhàn)和關(guān)鍵技術(shù)問(wèn)題。例如，如何尋找一個(gè)優(yōu)化問(wèn)題所對(duì)應(yīng)的物理系統(tǒng)，從而構(gòu)造出它的自由能函數(shù)；對(duì)于不同的物理系統(tǒng)，退火過(guò)程分別如何控制，有無(wú)一般結(jié)論；如何放寬約束條件，仍能使利用該技術(shù)得到的最優(yōu)解關(guān)于溫度連續(xù)；能否更進(jìn)一步降低算法的復(fù)雜度，以避免昂貴的計(jì)算成本。

確定性退火技術(shù)是可拓展的，該技術(shù)未來(lái)研究的重點(diǎn)，主要集中在以下幾個(gè)方面：第一，對(duì)確定性退火技術(shù)進(jìn)行更加深入的理論研究，討論解的性質(zhì)及其全局收斂能力，從理論層面給出運(yùn)用該技術(shù)的更寬松的條件；第二，將該技術(shù)與某個(gè)實(shí)際問(wèn)題結(jié)合，創(chuàng)造出一個(gè)可供學(xué)習(xí)和實(shí)踐的比較成熟且具有標(biāo)志性的模型；第三，總結(jié)該技術(shù)的研究成果，并基于目前的一些應(yīng)用領(lǐng)域，試圖解決更多與之相關(guān)的問(wèn)題；第四，將確定性退火技術(shù)拓展到更多應(yīng)用領(lǐng)域，解決其他一些重要問(wèn)題，如NP 難問(wèn)題、非凸優(yōu)化問(wèn)題等。由于對(duì)不同的優(yōu)化問(wèn)題，其自由能函數(shù)的構(gòu)造也各不同，所以要試圖給出自由能函數(shù)的一般構(gòu)造方法是極其困難的，這也是其區(qū)別于模擬退火技術(shù)廣泛應(yīng)用的原因之一?？梢云诖?，隨著理論研究的不斷深入與完善，隨著許多難點(diǎn)的攻克，確定性退火技術(shù)必將擁有無(wú)比廣闊的應(yīng)用前景。

7 結(jié)語(yǔ)

目前，隨著科學(xué)和工程問(wèn)題的復(fù)雜程度越來(lái)越高，一些傳統(tǒng)的優(yōu)化方法已難以應(yīng)對(duì)，確定性退火技術(shù)憑借自身的快速收斂性、通用性、可拓展性等特點(diǎn)成為解決大型復(fù)雜模型的重要方法。在此背景下，文中對(duì)確定性退火技術(shù)及其應(yīng)用進(jìn)行系統(tǒng)的總結(jié)與歸納。確定性退火技術(shù)是通過(guò)求解一個(gè)相關(guān)但較簡(jiǎn)單的問(wèn)題，并在較簡(jiǎn)單的問(wèn)題收斂到原始問(wèn)題時(shí)跟蹤其解的演化來(lái)求解組合優(yōu)化問(wèn)題，它可以被認(rèn)為是與同倫方法相關(guān)的，且面向全局優(yōu)化。同時(shí)，指出自由能函數(shù)的構(gòu)造和退火溫度的控制是影響該技術(shù)性能的關(guān)鍵，在此基礎(chǔ)上，從理論層面分析了它的優(yōu)勢(shì)。最后，提出了確定性退火技術(shù)在未來(lái)發(fā)展中亟需解決的問(wèn)題并給出其未來(lái)的研究重點(diǎn)。該文有望為確定性退火技術(shù)的理論研究與工程實(shí)踐示范提供參考。