AI 筆記12 - Local Search & Generic Algorithms

當系統性搜尋不可能的時候

我們這時候可以用另外一類的algorithm來找“夠好的solution”，稱為local search (for local optimum）。

或是當search出來的path不重要的時候（我們只在意找到的goal state，不在意optimal path to goal），也可以嘗試使用local search。

local search implementation的好處就是只處理少量的neighbors，也只管目前state怎麼被further improve towards the goal，所以不會maintain search tree/graph！這是節省記憶體的優勢。

local search常見演算法包括：

Hill Climbing (local greedy search)

hill climbing是最基本的方法，簡單來說就是只對目前最好的neighbor去explore，不管其他的可能性，以下圖來說，可能最後會找到local optima, global optima, 但也有可能遇到平台而卡死：

演算法如下：

克服在山地平台上打滾

爬坡遇到平台，最後可能變成無法收斂的無窮迴圈，可以：
1. 定義在平台上停留的上限次數，超過則選擇次佳的neighbor
2. 引進隨機性：做多次的re-climbing，隨機選擇新的initial state出發（實務中常使用）。
3. 一樣引進隨機性，但是是在上下坡的時候

Genetic Algorithms

這比較有趣的是child state是parent states的combination，還頗有遺傳的意味，事實上這的確是天擇的local search版本。

借用生物學的名詞：

individual: state，通常是finite set of 1's and 0's，或是以8-queen problem來說，是八個queen目前的位置：

population: k個隨機產生的individual

fitness: objective function! 就是“適者生存”的適者函數。例如8-queens中可能就是“目前沒有互相攻擊到的queens pair數目”。8-queens可能的pairs組合一共有choose(8,2) = 28，我們可以定義fitness為可能的組合中，最少互相攻擊的pairs數目： fitness = 28 - #attacking pairs。所以當目前有互相攻擊的pairs數目為零時，會有最大的fitness 28，反之如果目前有互相攻擊的pairs數目為28（意即倆倆互相攻擊），則fitness = 28-28 = 0。

cross-over point: 就是兩個親代states要怎麼結合成一個子代state的決定點，通常是隨機決定的。由下圖中的8-queen例子可以看到，child state是兩個parent states的結合，兩個親代(P1 P2)從crossover point分裂成兩半，再各取一半結合。

mutation: 在決定crossover point之後，子代的產生還可以有一些隨機變化，這就是X-MEN!

selection: 某個天擇的函數，用來隨機淘汰某些individual。

整個族群繁衍的過程如下：

假設我們有四個random產生的individual b1 b2 b3 b4，我們先經過selection隨機選出三個親代（淘汰b4，因為其selection value 最低，只有14%)，並且隨機兩兩交配產生四個子代，這邊注意b2進行了兩次的基因交換（強勢個體？！），這邊不知道為什麼不讓b1 b3交配，老師沒有說明，但我想應該沒有絕對：

最後步驟對子代做小規模（一個char)的mutation，好有趣！

演算法如下：