簡單例子搞懂遺傳演算法(genetic algorithm)

關於遺傳演算法知乎上已經有眾多大神給出了詳細的解釋，但有小朋友表示並不好理解

作為一個跨到供應鏈管理順便學了點ml皮毛的生物狗，想從小白的視角以簡單的背包問題(knapsack problem)引入，讓各位對於遺傳演算法有個直觀的印象。

背包問題： 有5件物品可選，每件物品的價值和體積如表所示。 背包的容積為10，怎麼樣選取物品使總價值最大？

1. Obtain a population of parents

在所有可行的選取組合先隨機的抽5個出來。表中第一個solution代表選取了第4和第5件物品，總價值為5，總體積佔8

表中最後一列P(selection)代表的是這個solution被挑中作為parent(親本)的概率。 當然啦，我們目標要使背包總價值 (Wi) 最大，那就是Wi越高的值被挑中當親本的概率越大咯～ 所以在這一步需要有一個function來給每個Wi指定一個選中概率 (P) （具體數學算式可以多種多樣，但是要滿足Wi越大它被指定的P也越大）

這裡就可以引出為什麼把它稱為遺傳演算法。 類比於生物進化論，生存能力弱的個體會被自然選擇淘汰，早早就gg了，無法把劣質的基因遺傳給下一代。 而生命力強的個體（使背包價值Wi高的solution)會存活下來的可能性大，從而保留了優質基因。

2.1 Crossover

根據概率P從原始的population（最初的那5個solution)里隨機選兩個親本（parent), 這裡選到的是solution1 & solution 3。 solution1是挑了物品4&5，solution3是選了物品1&4。 隨機選取1個插入點，ppt里選了第3個點。 solution1 和3從這個點開始交叉互換得到了2個子代(offspring solutions) 。 這裡solution1關於前3項物品的選取和solution3的後兩項物品選取結果組合到了一起，得到offspring 000 10, 同理另一條offspring是100 11。

2.2 Mutation

回到遺傳學：除了染色體交叉互換可以使子代性狀更多樣化，神奇的大自然還存在著突變(mutation)這麼一個機制。 染色體交叉重組說白了也只是在父母的性狀中進行重組嘛，比如白貓和黑貓的孩子的毛色只能在（純白，純黑和白黑)中選（比喻不恰當，實際毛色遺傳機制很複雜），但是這樣太單調了呀，我們還想得到橘貓。 這時候僅靠交叉互換是不能得到想要的性狀的，還要允許子代自己的基因能夠突變。

在這裡第一個offspring的結果就突變了， crossover得到offspring1本來是000 10(選第4件)，這裡突變成了010 10(選第2和第4件)

為什麼要突變： 在親本solution上交叉重組可以增加得到更好solution的概率，但還不夠。 允許突變說不定可以偶然得到更優的solution

怎麼突變：突變的方向隨機且概率很小

然後可以把得到的offspring放到原來的那5個solution(population)里，替換掉之前P較低的solution, 再重新計算每個solution的P，再選2個親本迭代，得到下一輪的offspring。以此往複，直到得到你滿意的solution為止～

3. Remarks

1. 剛剛例子里只用了1個交叉重組點，實際上在遺傳演算法中crossover point可以有2個甚至更多
2. 關於offspring替換進原population： 可以是漸進式的，一次用一個offspring替換掉一個原population里的一個solution; 也可以一次性從原population里抽多次，每次隨機抽2個親本，得到多個offspring。 然後把原來的solutions全部淘汰掉，直接把現在得到的所有offsprings當成親本。
3. 本文只提供一個框架，略過了很多細節，以求在最短的時間內讓給讀者對遺傳演算法是什麼有個basic idea. 我一直覺得吸收知識最快的途徑是先畫枝幹再補充細節，添枝加葉。 所有的知識點一股腦全部倒出來，反而不容易消化。

演算法小白，歡迎指正~ 0.0

Good luck everyone~!