遺傳算法 （Genetic Algorithm）

基礎資訊

選擇政策： 物競天擇，适者生存。即按照某一特定條件進行選擇。

遺傳因子: 在計算機中是用0/1編碼來完成的

遺傳方式： 交叉、變異

選擇政策

輪盤賭選擇法

輪盤賭選擇法是根據個體的适應度值計算每個個體在子代中出現的機率，并按照此機率随機選擇個體構成子代種群。

常用步驟

1. 将種群中個體的适應度值疊加，其中m為種群個體數。 ∑ i = 1 m y ( x i ) \sum_{i=1}^{m}y(x_{i}) ∑i=1m​y(xi​)
2. 每個個體的适應度值除以總适應度值得到個體被選擇的機率。
3. 計算個體的累計機率以構造一個輪盤。
4. 輪盤選擇：産生一個[0,1]區間内的随機數，若該随機數小于或等于個體的累積機率，選擇個體進入子代種群。

重複上述步驟，即可得到一個由新個體構成的種群。

随即周遊抽樣法

像輪盤賭一樣計算選擇機率，隻是在随機周遊選擇中等距離的選擇個體。設npoint為需要選擇的個體數目，等距離的選擇個體，選擇指針的距離是 [ 1 , 1 n p o i n t ] [1,\frac{1}{npoint}] [1,npoint1​] ，第一個指針的位置由 [ 1 , 1 n p o i n t ] [1,\frac{1}{npoint}] [1,npoint1​] 的均勻随機數決定。

錦标賽選擇法

錦标賽選擇法選擇政策每次從種群中選取出一定數量個體，然後選擇其中最好的一個進入子代種群。重複該操作直到新的種群規模到達原來種群規。

步驟:

1. 确定每次選擇的個體數量（百分比）
2. 從種群中随機選擇個體（每個機率相同）構成組，根據每個個體的适應度值，選擇其中适應度值最好的個體進入子代種群。

重複上述步驟，直到得到新一代種群。

遺傳算法編碼

二進制編碼法

就像人類的基因有AGCT四種堿基序列一樣，不過在這裡我們隻用0和1兩種堿基，然後将他們串成一條鍊來形成一條染色體，一個為能表示出2種狀态的資訊量，是以足夠長的二進制染色體便能夠表示所有的特征。

例如：111000110101

優點：

1. 編碼、解碼操作簡單易行
2. 交叉、變異等遺傳操作便于實作
3. 合最小字元集編碼原則
4. 利用模式定理對算法進行理論分析

缺點

1. 高精度問題上面表現較差
2. 容易陷入局部最優

浮點編碼法

二進制編碼雖然簡單直覺，但明顯地存在着連續函數離散化時的映射誤差。個體長度較短時，可能達不到精度要求，而個體編碼長度較長時，雖然能夠提高精度，但增加了解碼的難度，使遺傳算法的搜尋空間急劇擴大。

浮點法： 是指個體的每個基因值用某一範圍内的一個浮點數來表示。在浮點數位方法中，必須保證基因值在給定的區間限制範圍内，遺傳反中所使用的交叉、變異等遺傳操作也必須保證其運算結果所産生的新個體的基因值也在這個區間限制範圍内。

例如：1.2-3.2-5.3-7.2-1.4-9.7

優點

1. 适用于在遺傳算法表示範圍較大的數
2. 适用于精度要求較高的遺傳算法
3. 便于較大空間的遺傳搜尋
4. 改善了遺傳算法的計算複雜性，提高了運算交率
5. 便于遺傳算法于經典優化方法的混合使用
6. 便于設計針對問題的專門知識的知識型遺傳算子
7. 便于處理複雜的決策變量限制條件

符号編碼法

符号編碼是指個體染色體編碼串中的基因值取自一個無數值含義、而隻有代碼含義的符号集如（A,B,C…）

優點

1. 符合有意義奇數塊編碼原則
2. 便于在遺傳算法中利用所求解問題的專門知識
3. 便于遺傳算法與相近似算法之間的混合使用

交叉

交叉操作： 是指對兩個互相配對的染色體按某種方式互相交換其餘部分基因，進而形成兩個新的個體。

适用于二進制編碼個體或浮點數編碼個體的交叉算子：

1. 單點交叉 (One-point Crossover):指在個體編碼串中隻随機設定一個交叉點，然後再該點互相交換兩個配對個體的部分染色體。
2. 兩點交叉 (Two-point Crossover)：在個體編碼串中随機設定了兩個交叉點，然後在進行部分基因交換。
3. 多點交叉 (Multi-point Crossover): 在個體編碼串中随機選擇多個交叉點，然後進行部分基因交換。
4. 均勻交叉 (Uniform Corssover): 兩個配對個體的每個基因座上的基因都以相同的交叉機率進行交換，進而形成兩個新個體。
5. 算數交叉 (Arithmetic Crossover): 由兩個個體的線性組合而産生出兩個新的個體，該操作對象一般是由浮點數編碼表示的個體。

變異

遺傳算法中的變異運算，是指将個體染色體編碼串中的某些基因座上的級音質用該基因座上的其他等位基因來替換，進而形成新的個體。

适用于二進制編碼和浮點數編碼的個體：

1. 基本位變異 (Simple Mutation): 對個體編碼串以變異機率、随即制定的某一位或某幾位僅基因座上的值進行變異運算。
2. 均勻變異 (Uniform Mutation): 分别用符合某一範圍内均勻分布的随機數，以某一較小的機率來替換個體編碼傳中各個基因座上的原有基因值。
3. 邊界變異 (Boundary Mutation): 随機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。
4. 非均勻變異：對原有的基因值做一随機擾動，以擾動後的結果作為變異後的新的基因值。對每個基因座都以相同的機率進行變異運算之後，相當于整個解向量的解空間中做了一次輕微的變動。