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。

又Optimization中又分成

Black-Box:在不知道f(n)的情況下，找出能夠得出最高解的X

Glass-Box: 在知道f(n)....

一般來說glass-box雖然看似容易，但情況也建立在如果Function較為簡單的情況，一般的解法就是看是幾次方的function然後作微分求極值。但一般情況下的F可能都較為複雜，可能有幾百個小f在裏頭，也可能是個system，雖然給你x你可以得到解....ㄏㄏ。所以一般情況下，我們如果知道F，但如果過於複雜，我們仍採用Black-box的方式去解。

例如橋梁問題。

假設你有個橋樑的設計X，要去計算在現有的材料下，這個X設計出來最大能夠承載的重量。

其實這個這些都是glass-box problem，但由於問題牽扯到許多複雜的Function所以依然使用black-box。

爬山演算法 Steepest Descent (Gradient descent)

Like climbing Everest in thick fog with amnesia

核心步驟就是，當你站在一個地方，你覺得周圍哪邊傾斜的角度比較大，就往那個方向，雖然你不知道山頂是否是那個方向。

會搜尋附近所有neighbor點，如果neighbor.value<current.value，則return解。

不過這邊會有個問題就是，假設有個台地但後面有個比台地高的高山，但如果你走到台地時發先附近高度跟你一樣了，就不走了，那就永遠走不到後面的高山；反之如果使用neighbor.value<=current.value的情況，假設有個高原(比台地更寬廣的地形)後面才接個高山，程式可能會卡在高原上做無窮迴圈。
所以一般情況我們會設置limit，在有限的時間或是步數之內完成計算，若超出則回傳目前的最佳解。

特性

• 能夠給予local optimum，無法保證global optimum
• Random initial可以幫助接近global optimum，假設撒點可以撒到離global optimum較近的位置，有比較高的機率可以走到山頂。
• 目前steepest descent都為polynomial algorithm，不能給出最佳解，但在一些範圍較小的問題上可以給出不錯的答案。

應用問題

Example: 銷售員問題

有N個城市，有個銷售員要選擇一條最短路徑的線並且能夠經過所有的city

利用swap2(任意挑兩個city互換順序，ex:原本 ABCDE -> AECDB)來找出下個state，再計算每個算出的state所得的分數作為比較值。

每次路線做 Cn取2 (機率) 個state，取最短的重複直到做出的state值都比原來的state大。

Example: 西洋棋皇后問題

假設8*8的棋盤上有八個皇后，彼此不會互相攻擊，要如何擺放