Python — 基因演算法(Genetic Algorithm, GA)求解最佳化問題

Published in

學習漂流瓶 Drift Bottle

11 min readAug 29, 2021

基因演算法是一種優化演算法，主要依據達爾文“進化論”中所提出的「物競天擇，適者生存，不適者淘汰」的生物演化法則而來，其核心觀念為模擬基因的優勝劣汰，以進行最佳化的計算。

基因演算法（又叫遺傳演算法, 以下通稱GA）是啟發式演算法的入門，其目的為找到近似最佳解，優點為演算速度快、易上手，而缺點則為運算成本高、不保證最佳化，依據使用的方法不同可能會得到區域最佳解而非整體最佳解。以下筆者會採用較熱門的菁英挑選法（Elitism Selection）進行GA的描述。

須具備基本能力：
因是以最簡單的方法進行介紹，本次實戰前所需具備的基本技巧需擅長numpy、list 語法及 decimal & binary 轉換的基本概念。

關於 decimal & binary 間的轉換，可以參考以下筆者曾寫過的文章，此篇主要是針對整數＋浮點數進行說明，而本文只會對整數進行說明。

Python — 十進位與二進位間的轉換(Decimal to Binary)

huntercheng1013.medium.com

以下正文開始～

最佳化問題

此次求解最佳化問題為Rastrigin function，為最佳化常用的測試函數，其最佳解為 f(0,0,…,0) = 0，公式如下：

GA基因演算法

GA主要步驟為，Initialization、Evaluation、Selection、Crossover & Mutation；不斷的演算迭代基本上就是以 Evaluation、Selection、Crossover & Mutation 為核心下去循環得到的結果。

變數定義及介紹

N：Initial population 的大小，此變數決定初始群集內 chromosome 的個數。
D：Dimension 維度大小，欲求解目標問題之變數數量。
B：Bits number，D 維度中每個變數可能出現的數字受限於 bit 數的控制。
n：於每次 Iteration 中從 population 抓取菁英個數的數量。
cr：Crossover rate，交配之門檻值。
mr：Mutation rate，突變之門檻值。
max_iter：欲進行迭代之總次數。

步驟說明

Step 1：產生初始群集（Initial Population）。藉由設定參數 N、D ，給予群集內每個 chromosome 不同的初始解。

Step 2：計算適應度（Fitness）。將初始群集內所有 chromosomes 解碼後對應的 real value 代入問題模型中，以計算 fitness。Fitness 越小代表此 chromosome 具有較好的資質，將來被複製或選取為菁英個體的機率也較高。

Step 3：複製（Reproduction）或選取（Selection）。為演化出更優良的個體，必須從父代群集中篩選出較佳的 chromosome，以演化下一代的群集。通常採用輪盤法（Roulette wheel）來選取菁英個體。輪盤法是一種回放式隨機取樣法，將一輪盤分成 N 個部分，根據 fitness 決定其盤面面積大小，fitness 越佳面積就越大，故在隨機取樣中被選到的機會就會越大。此部分會從初始群集中篩選出 n 組最佳 chromosome 當做父代。

輪盤法(Roulette Wheel Selection)
為一種回放式隨機取樣法，將一輪盤分成N個部分，根據fitness決定其盤面面積大小，fitness越大面積就越大，故在隨機取樣中被選到的機會就會越大。補：其他挑選法還有 競爭法（tournament selection）、等級輪盤法（Rank Based Wheel Selection）等等...。如下圖，假設 Chromosome_5 的結果較佳，於每次抽取時隨機生成一介於（0,1）之間的亂數落在此區間的機率就會增加；換言之， Chromosome_3 的結果較差，則被選取成為菁英個體的機會就比較小

本篇選用的挑選法則為菁英挑選法（Elitism Selection），此方法可以確保每次 iteration 時都會保留最好的 chromosome（本文假設為 n 組）；將欲選取之優秀 chromosomes 兩兩隨機挑選進行 crossover 、mutation 並生成 offsprings （本文假設為 N-n 組），隨後此 offsprings 會再和前段提及之優秀 chromosomes 成為下一次 iteration 新的群集。由此可知此方法優點為沒有任何變化的最佳 chromosome 都可以保留至下個 iteration，缺點為容易陷入局部最佳解。

本文於實作時，本文會提供兩種方法：> 1. 每代挑選前幾名fitness，共n組菁英chromosome，當成欲進行crossover和mutation之群集。> 2. 每代挑選以輪盤法進行挑選n組菁英chromosome，當成欲進行crossover和mutation之群集。方法1為基本菁英挑選法的方法；方法2為菁英挑選法加上輪盤法的變形，採用此方法可能會增加陷入局部最佳解的機率，但換言之，最佳chromosome被重新選取的機率會更高，最佳個體被複製（Reproduction）的機會就會提高，但藉由將mutation rate提高，雖有別於常理，但陷入局部最佳的機率又會降低了。PS.：方法2讀者可以當參考就好，因採用輪盤法篩選菁英個體，優良基因可被複製的機會就會較高，所以我想嘗試看看這樣做是否會較好。

Step 4：交配（Crossover）。首先定義一交配率（Crossover rate），隨後以均勻分配產生一機率值，機率值小於交配率則需進行交配。採用交配方法為單點交配（One-point crossover），首先依亂數決定一個切斷點，利用此切斷點將原先挑選出欲進行交配兩個的染色體切成兩部分，再將切開的部分重新組合成一對新 chromosome。根據欲求解問題，每個 chromosome 內會有 D 組不同的變數，將父代的編碼依序對應並進行單點交配。

Step 5：突變（Mutation）。演化最後一個流程是突變，首先要定義一突變率（Mutation rate），於過程中均勻分配產生一機率值，機率值小於突變率則需進行突變。採用突變方法為單點突變（One-point Mutation），隨機選取染色體其中的位元，將此位元做0與1的互換。

Step 6：若達到 iteration 次數的上限時，則停止並輸出最佳解，若尚未滿足則回到Step 3。

Python 實作開始

Initial Population

產生初始群集、群集內每個 chromosome 包含對應維度的編碼值，每個編碼值均是以 4 個 bits 組成；將每個 chromosome 解碼後，進行 fitness 的計算。

初始參數設定為，N（10）、D（3）、B（4）、n（4）、cr（0.9）、mr（0.2）、max_iter（10000）。

Minimum: 65

Selection

採用前一段提及的兩種方法個別下去篩選菁英個體。

每代挑選前幾名表現較好的 fitness，共 n 組菁英 chromosome，當成欲進行 crossover 和 mutation 之群集。
每代挑選以輪盤法進行挑選 n 組菁英 chromosome，當成欲進行 crossover 和 mutation 之群集。

關於輪盤法，若是最大化問題，將各個 fitness 標準化後，再做階段性的累加，隨機生成一介於 0~1 的亂數後，即可選擇落在該區間的 chromosome；因本次目標問題為最小化問題，故在將每個 fitness 標準化時，只需要反轉每個函數的概率即可。

本次已預先知道目標問題的最佳解為 “0”；極端情況下假設在終止條件前就跑出最佳解且 population 中每條 chromosome 都為最佳解 0 ，此情況下如要是進行輪盤法，每條 chromosome 均會跳出 num 值，原因為全部 chromosome 的 fitness 總和為 0，而任何數除上 0 都是無意義的。故在 Selection 前可加上一條保險，倘若 sum( fitness )為 0，則可忽略篩選條件，直接從 population 中隨機抓取所需要的 n 組 chromosomes 即可。

Selection 1 & Selection 2 代碼

兩種不同的篩選方法結果如下圖，可看出方法一為直接取 fitness 前幾名小的來當作菁英，方法二為使用輪盤法篩選菁英，可以看到透過輪盤法，fitness 較小（較佳）的 chromosome 都有被選取起來，但因該方法包含隨機性，還是會選到 fitness 較大（較差）的 chromosome。因輪盤法是採用抽出放回的機制，故在實際寫程式時，也要確保 chromosome 不要被重複選取，除非是母體有相同 fitness 的chromosome。

Crossover

定義一交配率（Crossover rate），隨後以均勻分配產生一介於 0~1 的機率值，該機率值小於交配率則需進行交配，通常來說 Crossover rate 都會設的很大，如 0.9，為何不設 1 就好？概念大概是，有一成的機率交配失敗吧！

採用的交配方法為單點交配（One-point crossover），示意圖如下，藉由編碼所需的 bits 變數 B，可知欲交配的點有 3 個，在此可理解為 4-bit 所組成的 chromosome 有 3 個間隔，隨機生成一介於 0~1 的亂數後乘上此間隔數 3，並以無條件進入法的方式選取 crossover location，確認好 crossover location 後便可開始交配了。

Mutation

演化的最後一個流程即突變（Mutation），定義一突變率（Mutation rate），並以均勻分配產生一介於 0~1 的機率值，該機率值小於 Mutation rate 則需進行突變，Mutation rate 都設的很小，最常看到就是 0.1，概念為自然界中發生突變的機率本來就很低了；本文中 Mutation rate 設定為 0.2 ，主要目的是因為 Selection 時採用菁英挑選法，而為避免落在局部最佳解就必須將 Mutation rate 調高些，增加演算時跳脫區域最佳解的機率。

採用突變方法為單點突變（One-point Mutation），隨機選取染色體其中的位元，將此位元做0與1的互換。如選到值為 1 則轉換為 0，反之選到 0 則轉換為 1。