退火技術是什麼？是夏天火氣大要一起去買青草茶退火嗎？不是喔！不過倒是有那麼一點關係。退火這個名詞是冶金技術的一種方式，在金屬結構排列尚未穩定之前，把金屬加熱到高溫，然後再緩慢降溫，降溫就是退火。這時候金屬內部的排列就有可能冷卻到一個排列更整齊、能量更低，比之前更穩定的狀態。下圖一是將各種分子想像成不同顏色的像素，若顏色相似的像素在近距離會互相吸引，而在遠距離會互相排斥，透過模擬退火的方式，快速退火就會得到圖一左邊的樣式，而緩慢退火就會如圖一右圖。從圖一中就可以看出退火快慢的影響。而這種方式因為有機會得到最低能量，所以後來退火這個名詞也被衍生成最佳化的方法之一。

圖1. 快速退火（左圖）與緩慢退火（右圖）的範例，可以發現右圖的排列更整齊。
本圖片取自https://en.wikipedia.org/wiki/Simulated_annealing

退火技術怎麼對金屬以外的過程進行最佳化呢？舉例來說如果我們用退火法來解決倉儲問題：一個貨物倉庫，有大小不同的貨物要盡量放進去這個倉庫中，希望能夠把這個倉庫堆滿，目標就是讓倉庫剩餘空間最少。這就像上述冶金過程中，把每一個貨物想像成一個原子一樣。假設有 n=100 個貨物，放入與不放入倉庫兩種選擇，那麼就會有2ⁿ=2¹⁰⁰≈10³⁰種放置方法。一開始我們可以隨意放幾件貨物進倉庫，也就是設定一個初始的放置方法。在此我們設定一個能量函數，就是將貨物放置到倉庫之後剩下的倉庫空間。這個問題就是要問怎麼放貨物進倉庫，才能讓能量函數最小。「加熱到高溫」的這件事，當然不是在貨物上面加熱，而是想像有一個高溫讓分子移動，也就是貨物移動，如改變一下貨物擺放的方式，或是交換另一個不同的貨物進來倉庫。當然我們希望每次交換都能讓倉庫剩下的空間越少！但事實上交換可能會讓剩下的空間變多，例如移出一個大貨物交換一個小貨物進來。但誰知道最後是不是要把大貨物先搬出來，才有可能用小貨物把倉庫堆滿呢？所以在退火法中就設定了一個跟溫度有關的接受機率，溫度越高，就有高的機率允許倉庫內的設置往高能量的方向，也就是像剛剛所說的，允許搬出一個大貨物換一個小貨物進去；溫度越低，則讓設置往低能量的方向去，也就是希望每次交換貨物進來，都能讓倉庫剩下的空間變小。這個接受機率p的設定一般會用下列的指數函數：

來設定，其中T是假想的溫度，Δ是新舊設置之間能量函數的差異。若新設置的能量函數較舊設置小，就是找到了更低的能量，此時Δ<0，接受機率p>1，則一定會接受新的設置。若新設置的能量函數較舊設置大，此時Δ>0，接受機率p<1，就不見得會接受這樣的新設置，端看溫度T的高低以及隨機亂數模擬是否接受的結果。而溫度T越高，p會越來越靠近1，就代表可以接受一些提高能量的設置，而溫度T降低，就逐漸只能往低能量的設置去，這就是退火法的精髓。高溫時允許廣泛的搜尋，退火後專注在找尋最小值。在這樣的退火搜尋之下，數學上可以證明它有機率可以從所有可能的設置中找到剩下的倉庫空間最少的設置，也就是上述設定的能量函數最小值。而這個能量函數，就是我們做最佳化的目標。

 

其實就是這9行9列中尚未滿足數獨規則的數字個數有多少，這個紀錄方式如圖四。之後每填入一種不同的方式，就會對應到不同的能量值。如果這個值變成0，就代表了1到9在每一行、每一列都出現1次了，也就是解出了這一個數獨了。接著我們可以設置一個溫度T，讓它隨著每一次試驗下降，舉例來說，每次下降1%，也就是乘上0.99。然後每一次試驗隨機選一個框交換其中某幾個數字，並計算出能量值，透過接受機率看目前的能量值是否能被接受為下一個試驗的起始值。隨著溫度漸漸下降，退火，我們就有機會得到這個數獨的答案。完整的算法有興趣的讀者可以參考文獻1或2，有對應的python程式可以實作。

圖2. 數獨關卡
 

圖3. 在每個3x3的框框中
隨機填入剩餘的數字（以紅色表示）

圖4. 計算每行（綠色標示）每列（藍色標示）
尚未出現的1~9的個數及其總和（紫色標示）

退火技術可以用來解決很多問題，目前常用來解決的模型問題就是二次非限定的二元優化問題，Quadratic Unconstrained Binary Optimization，簡稱QUBO問題，它的能量函數設計如下

其中x_𝑖是0或1，通常就是一個很長的二元向量，Q_𝑖,_𝑗是對應的權重。這個模型你可以想像成手中有許多神奇寶貝，上場時每一隻𝑋_𝑖有它的攻擊力Q_𝑖,_𝑗（因為𝑋_𝑖是0或1，所以𝑋_𝑖²=𝑋_𝑖）；而當兩隻神奇寶貝𝑋_𝑖、𝑋_𝑗同時上場時，它們會有攻擊加成Q_𝑖,_𝑗（不見得是正的喔，搞不好上場會互相干擾），而E()就是總攻擊力。退火技術就是在搜尋最低的攻擊力組合，若要找最高的攻擊力，則將所有的Q_𝑖,_𝑗加負號即可。QUBO可以對應到許多不同的生活問題，如售貨員問題、排班問題、封裝問題、交通問題等等，可以參考文獻3，這些問題都與生活息息相關。

上述的退火技術或QUBO問題，在計算每一種設置是可以平行處理的。在目前量子技術火熱的年代，它可以透過量子Qubic來同時模擬不同的設置情況。像D-Wave公司所推出的Quantum Annealing（量子退火），就可以很快將所有的情況模擬出來並得到解答，可以參考文獻4。若不是透過量子電腦，像Fujitsu公司推出的Digital Annealing Units，也是一種受量子計算法啟發的而改進的數位退火，可以達到同樣的效果。這些在2022年Science Reports中有關於量子退火及數位退火之間效能的比較，可以參考文獻5。目前數位退火在位元耦合上是比量子退火來得有效率的，實用的案例像KutxaBank透過數位退火器來計算投資的最佳分配（參考文獻6）；多倫多大學工程學院也透過數位退火進行分子設計來改進製氫的催化劑（參考文獻7）。或許在不久的將來，我們都能夠透過不管是量子、數位或是模擬的退火技術來享受更好的未來。在某個陽光午後，解不出數獨時，也不妨來杯青草茶退火一下，或許答案就出來了喔！

舒宇宸
國立成功大學數學系副教授

參考文獻

本文引用格式：舒宇宸（2023）。退火（Annealing）是什麼？科學研習，62（1），82-86。