# Genetic Algorithm 基因演算法
最近在研究最佳化問題的時候，發現傳統的梯度下降法容易卡在局部極小值，尤其當函數是多峰的時候。因此這邊想介紹一種不依賴梯度的「全域搜尋演算法」 Genetic Algorithm (GA)。
## Genetic Algorithm
基因演算法 (GA) 是一種模仿達爾文「物競天擇，適者生存」法則的啟發式演算法，這個演算法將問題的每個潛在解視為一個「個體」，透過模擬生物演化中的選擇、交叉與突變等機制，讓解逐代演化，最終趨近於我們所尋找的最佳近似解。
演算法的流程圖大致如下：初始化 → 評估 → 選擇 → 交叉 → 突變 → 迴圈。
### Step 1 初始化族群
第一步要先產生GA的初始族群 $P_0 = \{x_1^{(0)}, x_2^{(0)},\ \cdots, x_N^{(0)} \}$；隨機產生$N$個個體：$x_i^{(0)}$ ～ $U(a, b)$，$U$ 是均勻分布、$a, b$ 是解的初始範圍 (init_range)
例如想要在二維空間搜尋最佳解的話，$P_0 = \{(g_1^{(0)}, g_2^{(0)}):\ g_i^{(0)}～\ U(a, b),\ a, b\in \mathbb{R} \}$
### Step 2 評估適應值
再來需要評估每個個體在「環境」下的適應值 (Fitness) $F(x_i)$，如果原本的問題是最小化問題可以設定$F(x_i) = - f(x_i)$ 或者 $F(x_i) = \frac{1}{1+f(x_i)}$，其中 $f(x)$ 是 Loss function
知道所有個體的適應值後，接著我們就要產生下一代了，對於下一代的族群，我們可以決定是否留下上一個世代的最優解 (Elitism)，這種做法的優點是可以保證目前找到的最好解不會遺失，缺點是可能讓族群多樣性下降，稍微增加過早收斂到局部最佳的風險。
另外也有「穩態基因演算法」（Steady-State GA）的變種，每次只替換部分較差的個體。當然也可以替換掉全部的個體。
### Step 3 選擇 (Selection)
那麼對於一個 $P_{t+1}$ 中的新個體（子代），我們就要選擇兩個 $P_t$ 中的個體出來進行交叉(Crossover)，這邊選擇父代個體的方式有幾種：
1. 輪盤選擇 (Roulette wheel Selection)
每個個體被選擇的機率被定為 $P(x_i) = \frac{F(x_i)}{\sum F(x_i)}$ 進行抽選（要確保Fitness是正的）
2. 競賽選擇 (Tournament Selection)
隨機抽選 $k$ 個，選出其中適應值最大的個體，執行兩次（父母）
> PyGAD 的實作邏輯是先挑選出一批「父母候選」，才在其中利用Selection, Crossover生出子代
### Step 4 交叉 (Crossover)
在挑選完 $P_t$ 的父代後，我們就可以產生子代 $P_{t+1}$ 了，常見的交叉法有幾個：
1. 單點交叉 (Single-point Crossover)
會設定一個切斷點，將父代的兩個個體的值拆成兩個部分再重組獲得新子代，假設父代的兩個個體分別是
$x_1^{(t)} = (a_1, a_2, a_3,\cdots, a_n)$ 和 $x_2^{(t)} = (b_1, b_2, b_3,\cdots, b_n)$
切斷點設定在第二個位置後，則兩個新子代會是
$x_i^{(t+1)} = (a_1, a_2, b_3, b_4, \cdots, b_n)$ 和 $x_j^{(t+1)} = (b_1, b_2, a_3, a_4, \cdots, a_n)$
如果解的參數順序與問題有關的話就很適合用這個方法
2. 均勻交叉 (Uniform Crossover)
對於新子代個體的每個參數，都隨機從兩個父代參數裡抓。
> 如果了解細節的話可以參考：[Crossover in GA](https://www.geeksforgeeks.org/machine-learning/crossover-in-genetic-algorithm/)
### Step 5 突變 (Mutation)
得到新一輪的族群後我們最後要對每個個體做一些小擾動，主要目的是讓我們的解有機會跳出局部極值狀態。這邊有幾個突變的方法：
1. Swap
將被選中的兩個基因參數直接互換
2. Random
將被選中的基因參數值直接替換為 [min_val, max_val] 之間的隨機數（不是加減！）
在 Mutation 這個階段，其實有很多細節能調整，像是可以只讓 $P_t$ 中一定比例的個體進行突變、對於每個個體要突變多少參數也可以調整等等。
### Final
我們已經介紹完基因演算法的每個步驟在做什麼了，接著只要我們持續迭代Step 2 ~ Step 5，直到適應值收斂或者迭代次數足夠大，就可以得到我們的最佳解了！
## PyGAD
知道了Genetic Algorithm在做什麼之後，我們要來看這個演算法實際要麼使用，我這邊要介紹一個Python套件 **PyGAD**，該套件提供了完整的GA框架，實作起來比較方便。
> 如果想要實作整個演算法可以參考這篇文章：[Python — 基因演算法(Genetic Algorithm, GA)求解最佳化問題](https://medium.com/hunter-cheng/python-%E5%9F%BA%E5%9B%A0%E6%BC%94%E7%AE%97%E6%B3%95-genetic-algorithm-ga-%E6%B1%82%E8%A7%A3%E6%9C%80%E4%BD%B3%E5%8C%96%E5%95%8F%E9%A1%8C-b7e6d635922)
第一步要安裝pygad
```
pip install pygad
```
這個套件中最方便的就是我們幾乎只需要寫好Fitness Function，剩下只需要設定好 GA(...) 中的參數，就能輕鬆執行。例如我們今天想要尋找 $f(\vec{x})=(x_1)^2+(x_2)^2+(x_3)^2$ 的最小值，那麼就可以按照底下的例子進行實作。
```python
import pygad
def fitness_func(ga, solution, idx):
x1, x2, x3 = solution
return -(x1**2 + x2**2 + x3**2)
ga = pygad.GA(
# Initialize, fitness
num_generations=100, # 迭代次數上限
sol_per_pop=50, # 每個世代的個體數量
gene_type = float,
num_genes=3, # 每個個體有幾個參數
init_range_low=-2.0, # 每個參數的下限
init_range_high=2.0, # 每個參數的上限
fitness_func=fitness_func, # fitness function
# Selection, Crossover
num_parents_mating=10, # 每個世代挑選出幾個「父母候選」
keep_elitism=1, # 保留一個最優解到下一個世代
parent_selection_type="tournament", # 使用tournament selectio
K_tournament=3, # 每個競賽選擇3個個體
crossover_type="uniform", # 使用 uniform crossover
# Mutation
mutation_type="random", # 使用random mutation
mutation_probability=0.5, # 每個個體有50%的機率會突變
mutation_percent_genes=10, # 每個突變個體中的基因都有10%獨立機率會突變
random_mutation_min_val=-0.5, # 突變範圍的下限
random_mutation_max_val=0.5, # 突變範圍的上限
stop_criteria=["saturate_20"] # 如果迭代20個世代都沒有更好的fitness則會結束演算法
)
ga.run() # 執行基因演算法
solution, fitness, _ = ga.best_solution() # 取得最佳解和其適應值
# Best solution (100 independent runs)
# x1: 0.003346 ± 0.015152
# x2: -0.000702 ± 0.013526
# x3: -0.000641 ± 0.016472
# fitness ≈ -0.000696
```
其實利用PyGAD來使用Genetic Algorithm的時候，只要知道如何針對問題設計fitness function、調整各個參數和使用不同的Selection, Crossover, Mutation等等，就可以順利使用這個基因演算法了
另外補充一個，如果今天的問題是要找 $f(x, y) = (x-1)^2(x-2)^2 + y^2$ 的最小值，這個函數的最小值有兩個 $f(1, 0)$ 和 $f(2, 0)$，那麼如果使用 Genetic Algorithm 找最小值的話，如果在$[0, 3]$的範圍中獨立找100次，結果則會均勻分散在 $(1, 0)$ 和 $(2, 0)$ 附近。
Sign in with Wallet
Connect another wallet