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。

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

Black-Box Optimization

原則上電腦能幫人類做的是分成兩種

1. Equation Solving
2. Optimization Solving

在Equation Solving中

例如: X+2=5

假如我們給X=3，電腦會理解為是正確的；若給X=2.5，那回傳一定為False 

但假如為optimization中，如果以上面的例子 X+2=5，若我們給X為3，會回傳的分數值為100分；如果X給2.5可能就只有拿到80分。

optimization中讓電腦能夠知道，是否接近我們預期的結果，而不是錯了後就翻盤。

每個可能的X都是一個solution，但是不同的solution會對應不同的分數，那就希望我們能夠找到分數最高的解，這個過程就叫optimization。