遺傳算法初級

遺傳算法是一種基于仿生學的計算機算法，通過模擬自然進化和優勝劣汰法則來搜索問題的最優解(我會說這其實就是稍微改良了一下的暴搜？)

它是由美國的J.Holland于1975年提出來的玄學概率學混合暴力搜索方法，廣泛適用于尋找算法優解、機器學習、人工生命、自適應自學習算法等等各種領域。

但是要知道，這個玄學的算法在用于尋找算法最優解時有一些限制：該算法最好是不能直接用公式套出最優解的算法。

such as luoguP1018的乘積最大，雖然理論上你可以用遺傳來做，但明顯這道題用動歸就能算出來好不好。。。

像經濟預測這類的，根本沒有一種算法能夠算出最優解(完全符合實際的趨勢)的問題，遺傳算法的極大優勢才會凸顯出來

OK現在來講講遺傳算法是什么

讓我們想像有一群山羊，每個山羊跑步的能力不同，有的跑的快，有的跑的慢。這其實就是一個種群。

比如說這群山羊有100只

1 struct goat{
2     int speed;
3     int dna;
4 }f[101];

至于dna是什么待會再說。

山羊每年都會繁殖，且假定每年種群中增加的新生兒都是10個。這樣這個種群就會以一個一次函數的形式增長好吧我只是順便溫習前幾天學的高中生物

但不幸的是，這群神奇的山羊生活的地方又有一群狼，每年狼都會吃掉羊群中的十只跑得最慢的山羊。所以很明顯的，每年山羊種群中跑得最慢的個體被淘汰掉，所以留下來的跑得越來越快，也更有機會能產下后代。慢慢的，整個山羊種群中活下來的都是跑得最快的山羊，以及它們產下的優良子代。

所以整個算法就是：計算每個個體的適應環境程度，然后根據適應度越高繁殖后代概率越大的原則，從群體中選出兩個個體作為父方母方產下后代，然后對該后代的基因進行變異。不斷重復上述操作，直到你決定停為止。然后選出一個最優個體。

怎么實現呢?

先來說繁殖。

受到人類染色體結構的啟發，我們可以設想一下，假設目前只有“0”，“1”兩種堿基，我們也用一條鏈條把他們有序的串連在一起，因為每一個單位都能表現出 1 bit的信息量，所以一條足夠長的染色體就能為我們勾勒出一個個體的所有特征。這就是二進制編碼法，染色體大致如下：

010010011011011110111110

這就是一只山羊的DNA。(當然是模擬山羊)

應當注意的是，我們要學會分辨個體的特征中哪些比較重要，哪些不大重要。比如說山羊，雖然它頭上的角花紋是螺旋形還是條紋形也算它的一個遺傳特征，但這跟它跑得快還是跑得慢完全沒有關系。對于這種特征，我們就不需要把它編程實現了。

然后來討論一下有用的特征。DNA就類似于一個二進制集合，01分別表示該特征存在還是不存在。比如01表示一只山羊沒有靈活的關節但有四條長腿，10表示山羊的關節很靈活但是腿很短，等等(至于11這種人生贏家和00這樣的辣雞都去死吧)有關于二進制集合的操作我也有發博客。

現在我們有一個父親0100和母親1001

對于后代的每一位dna，我們可以抽隨機數，表示這一位dna是隨他爸爸還是隨他媽媽。讓我們假設他的運氣比較好，第一位隨他媽媽，第二位隨他爸爸，第三位隨他媽媽，第四位又隨他媽媽

這樣后代的DNA就是1101

當然，只有遺傳是不夠的，沒有變異怎么能算的上是一個好模擬(好你可以閉嘴了)

假設對于山羊的每一位基因，有%0.01的概率，能讓該位的1變成0,0變成1。然后這個神奇的后代又足夠幸運，剛好在第三位DNA變異了

第一位羊生贏家誕生！

好了現在它的DNA序列是1111，也就是最好狀況。假設一個‘1’代表速度+1，那么它現在的速度就是4

然后自然而然的，我們就講到了父母親代的選擇上。在這里，我們用一個輪盤賭的算法來模擬哪只山羊能被選中。

首先把所有的個體適應度相加作為總適應度sum，然后 隨機生成一個1~sum之間的數random

然后從1開始遍歷群體數組，每次tot+=f[i]的適應度。當tot>=random的時候，選擇當前個體作為遺傳親代。

當然母方也是這么選咯

使用這個輪盤賭算法，你可以發現，適應度越高的個體越容易被選中，但被選中的也不全是適應度最高的個體。因為有一種可能，所有適應度高的個體普遍缺少最后兩個優勢特征，而一個適應度很低的個體卻正好擁有這兩個特征

比如說這三個

01101111000

10111111000

00000000111

很明顯第一個或者第二個跟第三個個體繁殖都會取到明顯的好效果。所以說給別人留臺階就是給自己留后路啊

這就是輪盤賭的意義

好了遺傳算法初級部分大概講完了。布置兩道小題目

1.創造一個有1000個個體的種群，并在500次進化中使最優個體的基因盡量接近這串字符DNA碼“mynameislife”。

2.試著用遺傳算法做01背包。(當然如果你得到的答案是錯誤的真的不怪你，因為這個問題有最優解算法不適合遺傳)發個luogu二維背包鏈接

本篇博客就講到這里，謝謝大家