初識遺傳算法(一): 基本概念

通過借鑒大自然中物種的繁衍概念，演化算法通過在計算機中模拟每個個體的基因序列(和該個體的表現型)，并通過組合多個個體，形成種群。對種群中的每個個體，采用類似大自然的自然選擇，基因突變等手段促使種群的繁衍，最終達到想要的目标。

構成演化算法的四大要素: 1.代表個體的方法，2.測量個體适應度的函數，3.選擇算法，4.後代變異(包含交叉遺傳crossover,基因突變mutation)

1.代表個體的方法

對于自然中每個生物而言，決定其适應大自然的程度的一般是基因序列，即基因序列決定了該生物的種種特性(即表現型), 而這些特性又決定了其是否适應環境。而對于計算機模拟的遺傳算法而言，如果用真實的基因序列來表達個體未免太過複雜，是以也就有了如下一些表達個體基因的方法。 (1)基因型的結構化表達 對于這種表達方式，最出名的就是神經網絡了(ANNs), 利用模拟神經的結構，搭建網絡。除了神經網絡外，有限狀态機也是常用的一種方法。 (2)樹狀圖表達法 對于這種表達法，較為出名的有John Koza的genetic programming，這種表達法較為顯著的一個優勢是很直覺，很好解釋，但随着時間的推移，樹的不斷增大，會導緻’膨脹’(bloat)，雖然膨脹能很好的削弱突變帶來的幹擾性，但是與此同時會使樹的直覺可解釋性大幅下降并會導緻樹的功能紊亂。通過懲罰項能很好地緩解’bloat’。 (3)基于文法的表達方式 'Lindenmayer' 系統是其中的一種，S對應着ABA，A對應着aBa，B對應着AbA，先由一個S開始，即ABA, 其中的A接着換位aBa, B換為AbA，是以即 S->ABA->aBaAbAaBa->aAbAaaBabaBaaAbAa … 一直循環下去知道達到要求的疊代數為止，并去掉其中的大寫字母 (4)基于String的表達方式 這是最為常見的一種表達方式，接下來也将預設使用這種表達方式來講述其他的内容，此處的string既可以是字元也可以是數字或者是二進制的數字串。

2.測量個體适應度的函數

個體适應度，顧名思義，就是看這個生物是否适合目前的這個環境，也就是說測量它能不不能很好地活在目前這個環境下。其實大自然中測量個體适應度一般是根據這個個體的繁殖能力來判斷，繁殖能力高，意味着基因傳給了很多後代，自然适應度就高。

但在演化算法中，是通過程式計算這個個體的表現好不不好，隻有表現好才能有機會将基因傳給下一代。譬如我假定目前環境下最完美适應的基因型是11001, 如果我現在有一個個體的基因型是10000, 那它跟最優解基因型的漢明距離是2，也就是有兩個位置的基因不相同，而有三個位置的基因是相符合的，那麼簡單來說我這個基因型為10000的個體的适應度就是3。當然這是最簡單的一個适應度函數，我也可以把這個函數設定為指數型的，譬如有三個位置符合，那麼它的适應度就是$$e^3$$當然我也可以設定為log型的，那就是$$log_23$$至于怎麼設定，一般根據實驗目的和實驗要求來。

3.選擇算法

來到了重頭戲環節，選擇算法。像自然選擇一樣，在一個種群中，不同個體的适應度有高有低，那麼怎麼樣選擇個體讓他們繁衍并将基因傳遞下去呢，此時就需要選擇算法。較為常用的選擇算法如下所示 (1)輪盤賭選擇(Proportionate) 輪盤賭選擇，顧名思義，轉一個輪盤，指針指到哪個區間就選哪個個體，如圖所示

而首先第一步就是做出一個基于fitness的輪盤。 僞代碼如下: SUM=0 For i=1 to P:   SUM=SUM+Fitness(pop[i])   Wheel[i]=SUM END 其中i是代表着種群中從第一個到第P個的所有個體，pop代表的是種群，pop[i]即該種群中第i個個體。Fitness是計算該個體的适應度，其實這個輪盤算法相當與累計機率，而選擇的過程就是: pick=(從1到P的随機一個整數)*SUM i=1 While(Wheel[i]<pick):   i++

也就是說随着i值的不斷增大, 總會有一個Wheel[i]的值大于pick的值，那麼我們就傳回這個個體pop[i]，一般來說，fitness越大的個體其在輪盤上對應的區域也就越大，就越容易被選中。 或者在python中可用bisect中bisect_right來快速得到結果。

(2)基于排名的選擇(Rank based) 其實基于排名的選擇與輪盤賭選擇法絕大部分相同，隻是在計算SUM的時候不再是 SUM=SUM+Fitness(pop[i])，而是SUM=SUM+c，而這個c是一個常量，那麼c是怎麼得到的呢，首先第一步先将整個種群中的所有個體按照适應度排個序，生成一個排完序後的清單，不要再管每個個體的适應度了，給每個個體按等差數列賦個值，譬如排名最後的個體指派為1，倒數第二指派為2，以此類推，排名最高的指派即為p(設種群中共有p個個體)，此時我們的c為1，因為我們設定的等差數列的內插補點為1。故此時公式為SUM=SUM+1。其他部分内容都跟輪盤賭選擇法一樣。

(3)錦标賽選擇(Tournament) 錦标賽選擇十分簡單，首先設定一個錦标賽的規模，一般來說規模為2，如果為2的話就是從種群中随機抽取兩個個體，每個個體的取法用僞代碼表示即round(rand()*p)，rand是從0到1的一個随機數，p是種群的體積，round即為小數部分四舍五入。取出兩個個體後分别比較其适應度，留下較大的那個即為最後結果，這是規模為2的情況，如果錦标賽規模是s，那麼則取出s個個體，留下适應度最大的那個即可

(4)截斷選擇法(Truncation) 顧名思義，截斷選擇法先将整個種群根據适應度排序，接着取前面k個個體，k是自己設定的參數

4.後代變異

大體來說，後代變異可分為兩個部分: 交叉遺傳(crossover)和基因突變(mutation)，其中交叉遺傳是屬于基因重組的部分，即有性繁殖，一般隻有遺傳算法包含這個概念，而基因突變是既可有性繁殖也可無性繁殖，即随機突變爬山算法也包含基因突變，但不包含交叉遺傳。 首先對于交叉遺傳而言，有多種方式(1)一點交叉遺傳 (2)n點交叉遺傳 (3)均勻交叉遺傳 譬如我現在有兩個選出來的個體，其基因序列分别為 個體1: 10011 個體2: 00000

(1)一點交叉遺傳: 這兩個個體的基因序列長度為5，随機從1到5取一個整數，譬如3吧，然後在3這個位置把每個基因序列分為兩半 個體1：100 | 01 個體2:  000 | 00 接着分别從這兩個個體中分别取出前一半和後一半分别構成兩個子代 子代1：100 | 00 子代2:  000 | 01

最後留下子代1和子代2中适應度高的那個。

(2)n點交叉遺傳 n點交叉遺傳類似一點遺傳，将基因序列分為n份，每一份分别從父代1或者父代2繼承，最後留下适應度高的那個

(3)均勻交叉遺傳 均勻交叉遺傳相當于将基因序列上每一個基因都看作獨立的，随機從父代1或2抽取 父代1：10001 父代2:  00000

對于子代中第一個基因，若rand()>0.5則繼承父代1中第一個基因，否則父代2，接着對第一個基因，若rand()>0.5則繼承父代1中第二個基因，以此類推，直到子代生成完整的基因序列

對于基因突變而言，有很多種方法，譬如二進制翻轉(适用于用二進制表達的基因序列如0101100)，随機重置，交換變異法，區域打亂法，反轉突變法。 二進制翻轉(Bit Flip Mutation): 對于每一位在基因序列中的基因，如果rand()<p則将0變成1，或1變成0，其中p是自己設定的突變率，這個突變率一般設定為1/L，L是基因序列的長度。

随機重置(Random Resetting): 這是對于那些非二進制編碼的序列，方法與二進制翻轉相似，隻不過将0變1，1變0這個過程改為從有效的字元中選取一個，譬如一個基因序列為9e03a變為9s03a。 交換變異法(Swap Mutation): 随機交換兩個位置的基因 區域打亂法(Scramble Mutation)：随機選取一段區域，将其中的基因打亂 倒轉變異法(Inversion Mutation): 随機選取一段區域，将其中的基因倒過來

下一章，我們研究研究适應度地形(fitness landscape)和協同進化(coevolution)