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

吳征天，戴金宇

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

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

同倫方法是求解非凸優化問題的有效方法[2]。與傳統優化方法相比，同倫分析法具有如下優點：（1）強收斂性，通過控制參數來保證解的收斂；（2）普遍有效性，不管求解的問題是否含有參數，高階級數解都能求得；（3）靈活性，對初始值和輔助算子的選擇不敏感，因此，可以選擇迭代的方法快速得到收斂的解[3]。同時，Fox提出的“按自然法則計算”是將大量自然現象與自然規律中所表現出來的科學思想進行歸納，并提取其本質，用于解決其他新領域中的問題[4]，如神經網絡、蟻群算法[5]、協同進化算法[6]等。

Rose 博士于1990 年提出確定性退火技術[7]，它是一種以溫度為同倫參數的連續同倫優化技術[8]，并且它也是按自然法則計算的一個分支。參照熱力學退火過程，將溫度參數T 引入問題，把求解目標函數的最優值轉化為求一系列隨溫度變化的自由能函數的極小，在模式分類、圖像分割、矢量量化等領域得到了廣泛應用[9-11]。

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

1 確定性退火技術

1.1 基本思想

由統計物理學產生啟發，確定性退火技術是求解全局最優解的一種連續同倫優化方法。該思想來源于熱力學退火過程，將一個固體物質加熱使之熔化成液體，其內部微粒的排列由穩定的結晶態轉變成混亂的液態，然后使溫度緩慢降低，微粒的排列從無序轉變成有序，到達其結晶溫度時，粒子圍繞晶體格點做微小振動，此時該物質逐漸變成低能態的晶格，即達到固體的基準態[12-13]。系統在溫度下降時達到這種平衡態的過程，可以用統計物理學中的吉布斯自由能極小化原理[14]來描述，即系統在與外界交換熱量而溫度恒定時，系統自由能下降的方向即為該系統狀態變化的趨勢，當自由能達到最小時，系統達到平衡態。

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

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

圖1 確定性退火技術的求解思路

1.2 研究現狀

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

2 算法的理論分析

對于求解極小化問題：minE=E（x），首先構造自由能函數F（x，T），滿足前面提出的兩個條件，然后按照下列過程求解問題：

（1）取足夠大的T0，k=0，求解優化問題：minF（x，Tk），設最優解為xmin（Tk）；

（2）Tk+1＝cTk（0＜c＜1），以xmin（Tk）為初始解，選取一種傳統方法求解minF（x，Tk+1），設最優解為xmin（Tk+1）；

（3）判斷是否滿足收斂準則，若滿足，則停，xmin（Tk+1）為最優解；否則，轉（4）；

（4）k=k+1，轉（2）。

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

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

3 溫度控制與退火過程

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

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

4 確定性退火與模擬退火

模擬退火技術和確定性退火技術有著相似的熱力學背景，且都是按自然法則計算的一個重要分支。表1比較了隨機退火和確定性退火，從優化的角度來看，有兩個顯著的區別[78]。第一個區別是，如果所要解決的問題是一個連續變量的優化問題，那么確定性退火技術有可能使用連續優化理論中著名的強大結論。第二個區別是，模擬退火過程用Metropolis 準則（通過蒙特卡羅法）來模擬系統的平衡態，其核心是在前期搜索時不完全拒絕比當前解差的解，且引入了概率這一隨機因素[79]，而確定性退火對應于解析積分（通過平均場近似），在每一溫度下的優化步驟都使用最合適的方法選擇最無偏和給定條件下不可置否的解[13]，而非利用隨機概率，因此算法搜索的時間復雜度遠遠低于隨機模擬退火過程，算法的收斂也就非常快速。同時注意到，確定性退火的一個次要優點是，對于任何問題都有固定的T 的最小值和最大值，算法的這一部分不是啟發式的，在原則上是可以計算的。

表1 確定性退火與隨機退火的比較

5 基于確定性退火技術的應用

5.1 在聚類問題中的應用

傳統的聚類模型可以歸結為求解極小化問題[19]：minD=（d（xi，yi））2，對于任意的Y={y1，y2，…，yM}及J={j1，j2，…，jM}，稱{Y，J}為聚類問題的一個實例，引入溫度T，將聚類問題看作一個物理系統，系統取實例{Y，J}的概率為P{Y，J}。定義物理系統的能量函數和熵函數分別為

在每一溫度下，利用極大熵原理，使熵H 取極大的概率分布P{Y，J}稱為物理系統的平衡態，使P{Y，J}取極大的實例{Y，J}稱為聚類系統的最可幾實例，通過求解變分問題

可得到

其中U∝1/T，P{Y，J}為溫度T 時系統的平衡態，考慮其邊緣分布

使P（Y）極大的y1，y2，…，yM應使F（y1，y2，…，yM，U）取極小，使概率分布極大的y1，y2，…，yM稱為聚類系統在溫度T 時的最可幾結構。因此，可以通過求解自由能函數F（y1，y2，…，yM，U）的極小來得到聚類問題的解。

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

該聚類算法具有較強的實用性，可適用于大規模的數據處理[19-20]。

5.2 在旅行商問題中的應用

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

若xi屬于yj所對應的類，則xi稱為售貨員走的第j 個城市。λ 是一可變系數，用來衡量第二項的關鍵程度。

（1）取U0=0，minF（Y，0）的最優點為

（2）Uk+1=T（UK）（函數T 滿足Uk+1＞Uk），以Ymin（Uk）作為初始點求解minF（Y，Uk+1），設求得的最優點為Ymin（Uk+1）；

（3）判斷是否滿足收斂準則，若滿足，則Ymin（Uk+1）作為旅行商問題的一個最優解；否則，轉（4）；

（4）k=k+1，轉（2）。

該算法收斂于旅行商問題的全局最優解，當U＝∞，即T=0 時，F（Y，U）的第一項為0，第二項為最短路徑[54-56]。

5.3 在點匹配問題中的應用

該算法對噪聲、平移、旋轉、丟失點和出格點都有較強的魯棒性，具有廣泛的應用[30-31]。

6 挑戰和展望

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

確定性退火技術是可拓展的，該技術未來研究的重點，主要集中在以下幾個方面：第一，對確定性退火技術進行更加深入的理論研究，討論解的性質及其全局收斂能力，從理論層面給出運用該技術的更寬松的條件；第二，將該技術與某個實際問題結合，創造出一個可供學習和實踐的比較成熟且具有標志性的模型；第三，總結該技術的研究成果，并基于目前的一些應用領域，試圖解決更多與之相關的問題；第四，將確定性退火技術拓展到更多應用領域，解決其他一些重要問題，如NP 難問題、非凸優化問題等。由于對不同的優化問題，其自由能函數的構造也各不同，所以要試圖給出自由能函數的一般構造方法是極其困難的，這也是其區別于模擬退火技術廣泛應用的原因之一。可以期待，隨著理論研究的不斷深入與完善，隨著許多難點的攻克，確定性退火技術必將擁有無比廣闊的應用前景。

7 結語

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