AI 筆記29 - Genetic Algorithms

8-Queens again

仍然使用8-queens來當作講解genetic algorithms的範例。
這邊比較不一樣的是board representation，用一個list表示從左至右的column上的queen的位置，index 1在下，index 8在上！

如果找出兩倆queens能互相攻擊的組合，則8-queens有choose(8,2) = 28種可能的pair attacks。這邊利用genetic algorithm來解決這個問題。

Genetic Algorithms

之前在Columbia AI課程筆記中已經有記錄，這邊做一點補充。fitness function就像之前講的那樣 = 28 - 目前#attacking pairs。

一開始怎麼從基因庫中選擇親代？我們假設有基因庫如下：

這四個gene的fitness score = 24, 23, 20, 10。這個population的總共適應能力 = 24+23+20+10 = 78。
根據適應自然的能力，也假設較有交配權（dominant male)，所以可以簡單地用佔比的方式算出交配機率：24/78 = 31%，以此類推：

接下來就是靠交配機率來真的選親代，這就看怎麼implement機率，最簡單方法就是randomInt(1,101)，然後看出來的範圍落在哪就選哪個gene，此例中選了前三個genes，而第二個gene被選中了兩次，所以有兩次的基因傳遞機會：

注意這邊固定一對父母只能生出兩個孩子（二胎政策？！），這關乎於algorithm convergence的速度，算是一個可以調控的參數，這邊不多做討論。

剩下的基因交換過程稱為crossover：

當然最後就來個突變的機率吧，因為有解答的gene有可能永遠不會被選成親代，總之隨機性是這類演算法（例如simulated annealing) 的特色：

這個演算法的主要研究重點在到底要產生多少代的子代才能得到答案。