AI 筆記28 - Simulated Annealing

Iterative Improvement to find Optimal Solution

某些NP-hard problems 可以用iteratively improve的方式(可能）找到optimal solution，例如所謂的travelling salesman problem。

這種iterative improve的方法包括simulated annealing, genetic algorithm, random restart。

search技巧在此類problem中通常因為search space太大而失去功能。
舉4-queens board為例：

透過iterative improvement先解除最多攻擊關聯的queen，再找出次者，兩個步驟就能解出一個答案，但是search要花費的時間就遠不止：

N-Queens

這種解題方式算是有點嘗試錯誤法，假設我們有N-queen board如下，並且我們也知道每次在某個column移動一個queen的話，互相攻擊的次數會有怎樣的改變：

既然說是嘗試錯誤法，那就可以random選一個queen來走！

Hill Climbing

這類algorithm牽涉到找到如何對一個objective function找出optimal值，這在此function幾何空間中類似爬山的行為（假設要maximize objective function):

由於每次爬山可能都會卡在shoulder或是local maximum，所以通常會random重選出發點重做，看要做幾次，也可以有些方法減少重做的次數。

這邊要考慮step size: 太小則一來花費時間多，二來卡在shoulder時可能動彈不得，因為演算法通常會對shoulder或是平台加個no-improvement次數限制，所以step size太小時就只能卡在平台。step size太大又可能錯過maximum，甚至導致infinite loop，如果剛好在某個山峰的兩側來回震盪的話。

怎麼解決這個問題？

Simulated Annealing

annealing意思是退火，是鍛冶產業的專有名詞，在高溫（增加分子動能）逐漸冷卻過程中，讓欲打造的事物形成穩定的結構，通常是最能量節約的結構。

所以AI從物理學偷用了這個概念，不過這邊把提高溫度用增加隨機性代替，當然冷卻過程就是減少隨機性。有趣。

演算法如下：

這演算法有一個T(t)的溫度-時間函數，我們仍然隨機選擇能從目前此地能抵達的下一步。如果下一步比目前所在好（兩地的評分差deltaE > 0來衡量），則就前往下一步，否則就根據e^(deltaE/T)來計算是否前往下一步的機率。

一開始溫度T(t)會是趨近無限大使得此機率值趨近於1，也就是必然發生，不論deltaE是正或是負值。這代表一開始即變遇到較差的方向，也是會前往，這就像是退火過程中的升溫狀態，分子跳動的自由度極大且較為隨機性。這保證了我們能夠脫離local maximum或是shoulder的窘境。

當t漸漸變大，T(t)會趨近零，則e^(deltaE/T) = 2.78^會趨近+- inf。這時候其實就是正常的hill climbing了，因為deltaE > 0，則機率竟然爆炸 > 1，反之則趨近於零，所以永遠只會往更好（positive gradient)的方向爬去。

simulated annealing保證會converge在global maximum，如果T一開始購大，且逐漸冷卻的話。