模擬退火法完整介紹

【摘要】模仿自然界的退火現象而得的演算法「模擬退火」，可應用到電腦輔助電路設計、影像處理、生物學、材料科學等。

自然現象
在熱力學上，退火（annealing）現象指物體逐漸降溫的物理現象，溫度愈低，物體的能量狀態會低；夠低後，液體開始冷凝與結晶，在結晶狀態時，系統的能量狀態最低。如圖一所示，大自然在緩慢降溫（亦即，退火）時，可「找到」最低能量狀態：結晶。但是，如果過程急就章，快速降溫（亦稱「淬煉」，quenching）時，會導致不是最低能態的非晶形。
似乎，大自然知道慢工出細活：緩緩降溫，使得物體分子在每一溫度時，能夠有足夠時間找到安頓位置，則逐漸地，到最後可得到最低能態，系統最安穩。
人類在找尋最適解（optimal solution）──例如系統的最低能態──時，可以學學大自然的「智慧」嗎？

關鍵人物
美國物理學家默察波利斯（N.Metropolis）和同仁在1953年發表研究複雜系統、計算其中能量分布的文章，他們使用蒙特卡羅模擬（Monte Carlo simulation）〔註一〕計算多分子系統中分子的能量分布。
美國IBM公司物理學家科克派特瑞克（S.Kirkpatrick）和同仁於1983年在《科學》（Science）上發表了一篇頗具影響力的文章：〈以模擬退火法求最適解〉（Optimization by Simulated Annealing）。
他們借用了默察波利斯等人的方法探討一種旋轉玻璃態系統（spin glass system）時，發覺其物理系統的能量和一些組合最適（combinatorial optimization）問題（以下將描述的旅行推銷員問題即是一個代表例子）的成本函數相當類似：尋求最低成本即似尋求最低能量。於是，他們發展出以默察波利方法為本的一套演算法（algorithm），可用來解決組合問題等的尋求最適解。
幾乎同時，歐洲物理學家卡尼（V.Carny）也發表了幾乎相同的發現，但兩者是各自獨立發現的；只是卡尼「運氣不佳」，當時沒什麼人注意到他的大作；或許可以說，《科學》雜誌行銷全球，「曝光度」很高，素負盛名，而卡尼卻在發行數量小的專門學術期刊（J.Opt.Theory Appl.）發表的。
科克派特瑞克等人受到默察波利斯等人用蒙特卡羅模擬的啟發而發明了「模擬退火」這個名詞，因為它和物體退火過程相類似。尋找問題的最適解（最小值）即類似尋找系統的最低能量〔註二〕。因此系統降溫時，能量也逐漸下降，而同樣意義地，問題的解也「下降」到最小值。此兩者的類似可用表一對照表明。

簡單的數學描述
在一物達熱平衡時，溫度為T，其能量狀態為E，則其概率值P（E）可表為波茲曼分布律（Boltzmann distribution）：P(E)=1／Z( T )．exp(-E／kT)
其中，Z（T）為歸一化因數（normaliz-ation factor），k為波茲曼常數（Boltzmann constant），exp(－E／kT)稱為波茲曼因數（Boltzmann factor）。
由上述方程式可知，在溫度降低時波茲曼分布傾向於最低能量狀態。
默察波利斯標準
為了模擬物體熱平衡的進展，默察波利斯等人提議以蒙特卡羅法，逐漸計算系列中不同能態。從某一狀態開（降溫），隨意選一粒子施予小小隨意產生的擾動（perturbation），此前後兩能態的差是dE。如果dE＜0（即為負值），表示此種擾動導致物體的較低能態，因為這是所要的方向，因此繼續由此狀態改變下去。但是如果dE≧0，則表示能態升高，不是我們所要的方向，但是，且慢，先不要放棄這個方向，暫時假設可行，但不是像負的dE能差值一樣順勢推舟放行，而是有條件的接納此行進方向，此條件接受此新狀態的概率是exp(-dE／kT)。此值可由上述的波茲曼分布律公式推導而得：將前後兩不同狀態的方程式相除，可得此前後變化的相對概率為左邊，而方程式右邊即為此值。以方程式表示即為
  P=exp(-dE／kT)〔註三〕
此一接受新狀態的規則即稱為默察波利斯標準（Metropolis criterion），亦即，若磁到能態降低時，立即放行，但若能態升高，但要看看默察波利斯標準，以決定繼續此方向，或停止尋找此方向而另起爐灶，找新的方向以求得最低狀態。
我們為何要這麼自找麻煩地弄個默察波利斯標準為尋找較低能態的指導原則呢？這和一般難題的佈景（landscape）有關，它們常是起起伏伏的（「故佈疑陣」地讓你弄不清尋找方向，但「山窮水盡疑無路，柳暗花明又一村」）。
為何它有效？
一般求最小值的麻煩在於跳不出局部解（local minimum），如圖二的點（x₂,y₂）。
假設我們從右邊向左（向下）尋找函數的最小值（y₁），每一次能量均降低，我們順利地抵達（x₂,y₂）點，發現無論怎麼嘗試都會以為我們已找到最小值，因為「在附近」它最低，但是其實它只是個局部最小值，實際上我們並沒有如圖二的全圖可宏觀地知道到底我們是否已找到真正最小解（global minimum）。要怎樣才會跳出那個陷阱而達到真正的最小值（y₁）所在的點（x₁,y₁）呢？
模擬退火法提供的管道是有條件的接受較高方向的爬升，其接受的概率是exp(-dE／kT)。就因為它能「忍讓一時」才得以「顧全大局」，最後終於求得最小值。這也是為何使用此方法需要一些「嘗試錯誤」，各方向到處試試升降，若實在試不出，則表示確已抵達真正最小解。以數學證明，它漸近地（asymptotically）可找到最小值（概率為1）──這可由馬可夫鏈（Markov chain）理論解得。


模擬退火方法
將它用在求最小解上，先找個可行的初解，以某一擾動方式產生下一可能解，比較新舊「能態」（或是別的衡量函數，例如成本費用、總收入、使用的時間等），若新值較小就接受此一新解，若新值較大則接受此新解的概率是exp(-dE／kT)。通常在運算時視k為1（或結合在溫度T值內），因此概率值是exp(-dE／T)。
但是，「接受的概率是exp(-dE／T)」是如何運作的呢？首先，產生一個隨機數（randomnumber）q，q值在0與1之間。比較q和exp(-dE／T)，若q＜exp(-dE／T)，則接受此新解；若q≧exp(-dE／T)，則不接受此新解，另外再產生一可能解（另謀生路），比照上法繼續下去。
總之，接受新解較高能（或者說，向上爬）的概率依默察波利斯標準而定，它來自人模仿大自然智慧（退火以找到最低能態）時，發出的「智慧火花」。
求解的步驟
使用模擬退火方法解決最適化問題的步驟是：
（1）分析問題與退火方法的類比
（2）選擇退火的計畫（溫度遞減方式、停留在每個溫度的時間）
（3）找一個擾動、形成新能態的方法（函數）
通常從某個「高溫」開始，在系統達平衡後，逐漸降溫，平衡，降溫……直到系統沒改善（能量不再變低）。
在這兒，溫度T是個借用的「物理名詞」，和實際的物理意義無關；它可以是個自變數，或某個「系統往低下的方向」，因此它只是個「控制參數」。而所謂的能態在大部分最適化問題中可能是總成本、花費時間、總共行進距離……等，而可以「成本函數」（cost function）來表示。
有四個因素影響最適化過程（求解的速度、計算工作量、答案趨近真正最佳解的程度等）：
（1）起始狀態（或稱熱狀態，hotcondition）
（2）步驟大小（或稱降溫量，temperature decrement）
（3）平衡狀態（equilibriumcondition）
（4）終結狀態（或稱冷凝狀態，frozen condition）
此四因素和待解問題均有關，因此了解問題和模擬退火的類比方式很重要，然後才方便決定此四個因素，也許需要「嘗試錯誤」幾次後才解得較有效率些。
起始條件通常是個可行的解答（feasible solution）即可，亦即在「有效解的範疇內」。對大部分的最適問題，這通常不難找到。步驟大小是指下降的幅度；改變的太大，可能跨過最低值而「錯失良機」，改變的太小則有可能太費時間（缺乏效率）。溫度下降方式常以函數表示，也許是線性、對數方程式等，也許在最初階段，步伐大些，在計算後半段起，就步伐小些、精細些。在每個溫度時通常要反覆運算多次（例如，在多維空間中，各個角度、各個方向嘗試）；平衡狀態即指在跳到一個新溫度時，嘗試到什麼地步（程度）才算是已達平衡狀態，而可跳到下一新溫度。嘗試計算的次數可能是溫度的函數，而其中一個指標是成功的次數（例如，在此溫度下，已嘗試5000次，其中2000次是成功的：亦即能量降低2000次）。終結條件可能是總嘗試次數已達某個量，或嘗試成功的次數是零（一直找不到更低能態），或已達某個特定溫度，因此就不再嘗試，可以宣告此最終能態為最適化問題的答案。
以上的描述看似繁複，但實際上由電腦來做（產生隨機數、反覆執行5000次等）易如反掌折枝，有興趣的讀者請參考文末附記的兩本書。


應用例子
模擬退火方法有很多實際應用的例子。積體電路的電腦輔助設計、影像處理、類神經網路、平衡運算等，也有生物學上的應用例子。
模擬退火方法在組合問題（combinatorial problems）的求解方面，相當管用。組合問題是不同選擇的排列組合，一個有名的例子是旅行推銷員問題（traveling salesman problem, TSP）：
他必需到N個地方，每個地方只經過一次，然後回到起始點。問題是找最適解（最短時間、最短行程、或最少花費……）。
這問題自1931年發表以來已引起不少迴響，它很容易描述，但不容易解答，尤其是N值大的時候（例如N＝500，或5000）時更難倒眾生！它的重要性不只是在現實世界中有不少應用例子，更要緊的是它代表一類非常要緊的「組合最適化問題」（combinatorial-optimization problem），而且是資源分配、管理的例子〔註四〕。
旅行推銷員問題的計算複雜度（computational complexity）可以簡單說明如下：
走過N＋1個地方的方法有N！/2種（若無方向性限制）；例如，6個地方的走法就有5！/2＝60種，51個地方的走法是3×10⁶⁴種。若N＝1001，則可能解有上千上萬種，要從其中找出「最適解」，恐怕是幾輩子也算不出來。這是組合最適化問題令人傷腦筋的原因。
如果再改一下旅行者所受的限制（例如，他必需先到第5個地方才能到第9個地方），即擴充為「一般化的（generalized）旅行推銷員問題，GTSP」，則麻煩就更大了。
適合一般求解
由於組合問題可能很不易求得最適解，而求解的方式又不少，一般的做法是在「效率」和「儘可能合理地近似」間求平衡。若尋找完全解（exact solution）可能需很多的時間、心力，甚至可能在有生之年還看不見答案，因此可用近似解，或稱近乎最適解（near optimum）。近似解法又分為：
（1）特定演算法（tailoredalgorithm）──亦即針對某一問題而裁剪的解法。
（2）一般演算法（generalalgorithm）──可解答相當多類的問題。
模擬退火方法是解組合最適化問題的一般解法；而從另一種歸類角度看，它是一種適應學習法（adaptive heuristics），因為它的演算過程包含「自我修正」的機制（mechanism），例如默察波利斯標準。它適合複雜的多維難題，不論是整數解與否均管用。


結語
自從模擬退火方法發表以來，已有不少「改進」的新方法出籠。美國橡嶺國家實驗室的波哈謝斯基（I.Bohachevsky）等人1986年即提出「一般化的模擬退火方法」（generalized simulated annealing, GSA）。另外，它也衍生了波茲曼機器（Boltzmann machine）的方法等。
它又和其他的人工智慧方法有所關聯（系列之後會談）；例如，有些求解的方法結合它和遺傳演算法（genetic algorithm）的優點。它也和類神經網路有某些程度的相似。
國內中研院數學所與台大資訊所等有人從事模擬退火研究；有興趣的讀者可參考：
1.William Press等人在1989年出的書《Numerical Recipes》。
2.P.van Laarhovern和E.Aarts在1988年合寫的書《Simulated Annealing: Theory and Applications》。
註一：它大約在1945年由馮諾曼（John von Neumann）和烏蘭（S.M.Ulam）提出，以隨機數（random number）建立數學模式。有人稱模擬退火法為「蒙特卡羅法」，讀者將可從本文的描述知道原因。
註二：若是找最大值，很簡單，只要在原問題加個負號就行，亦即，把問題「顛倒看」。
註三：因為dE、kT均是正值，因此p值一定在0與1之間，符合一般概率定義。
註四：在作業研究（operations research），旅行推銷員和它的無數演變問題一直是個熱門題目。美國航空暨太空協會（AIAA）在1988年提出「人工智慧設計挑戰」難題，即是前述旅行推銷員的演變。筆者即以模擬退火方法求解，成績很好。
林基興任職於行政院科技顧問組

轉貼自：http://tw.myblog.yahoo.com/jw!2I.ae0ieQ0bJH5eWZoCQkA--/article?mid=209 朱色虫居