AI-Beyond Classical Search 在感知有限的情況下做的演算 part2

Simulated Annealing(SA) 模擬退火法

在Steepest Descent中容易stuck at local optimum，所以我們希望當爬到某個程度的時候，會有個機率可以掉頭或尋找新的路線。

初期有random walk的行為，到後期才採用steepest descent。

退火的意思出自於打鐵，金屬在高溫的時候比較容易去敲打，或是增加元素，而當溫度慢慢下降的時候，會趨於定型。

這裡用爬山來舉例的話，一開始可以探索的空間會比較寬廣，不會拼命往上走可以願意接受比較差的state，等到經過一段時間之後才會開始由剛剛探索過的地方開始向上爬。

• 假如new state的情況比原來的情況好，接受機率100%
• 若情況較差 (F(X')-F(X)為負)，接受機率為 e^F(X')-F(X)/T

e為自然對數，X為原X、X'為新點，T為溫度參數，也是Simulated Annealing的靈魂。

這裡來看e的指數若是負數則為0~1之間，又T隨著時間變小，所以T越小，接受機率越趨近於0。

理論來說只要T下降的時間夠慢的話，SA永遠會給你global optimum !!(但似乎是有講跟沒講一樣XD)，但SA主要要討論的就是T要如何下降。
可能救是會記錄一些歷史訊息，若偵測到這附近的地形上上下下很劇烈(很多山頭)，那我可能將T下降的速度變慢一些，讓他更有機會去偵測到其他地方；反之若地形很平緩，那我用可以T可以下降快一點讓他專心爬到目前的optimum。

Local Beam Search

目前提到的SD跟SA都注重在單一點的變化，這裡提到local beam search。

Beam為光束，也就是不是單看一個點，而是觀看一個區域，這裡有個有趣的問題：若單看SD的話，如果SD隨機撒點做100次，跟local beam 一次撒100個點有什麼區別？

不過一次K個點去計算會比較快，因為假設一開始撒3個點，每個點附近再產生2個點，最後取最好的4個點，其餘捨棄，最後的結果會有點像「西瓜偎大邊」那樣收斂，隨著時間演變很容易產生最佳解。

不過這樣有好有壞，有可能的情況如下圖，ABC三座山，因為撒點在C的機率較低(較細)所以最後點都收斂在B點。

如果太多人一次往看似好的山做search那結果可能會是錯誤的。

所以又衍生出Stochastic beam search：隨機的選出產生的點，而每個點被選到的機率正比於F(X)，所以最後比較差的點也有可能會被選到作為下次的search。