---
tags: Data science
---

# 論文閱讀: An Improved Hybrid Genetic Algorithm with a New Local Search Procedure
[論文](http://downloads.hindawi.com/journals/jam/2013/103591.pdf)

## Introduction
[Genetic algorithm](https://en.wikipedia.org/wiki/Genetic_algorithm) 是一個表現佳的 global search 技巧，但缺點是其經常花費相對長的時間收斂到全域最佳。因此 local search 技巧可以被結合到 GA 中以提升表現。舉例來說，HGA(hybrid genetic algorithm, 又稱 [memetic algorithms, MA](https://en.wikipedia.org/wiki/Memetic_algorithm) )。

MA 是近年在 evolutionary computation 中持續成長的領域。所有 population-based 的 metaheuristic 搜尋技巧(啟發自達爾文的天擇說)結合 individual learning(Dawkins 提出的 [meme](https://en.wikipedia.org/wiki/Meme) 概念)都屬於 MA 的範圍。MA 面臨的最大挑戰是在 local search 和 global search 間的取捨(計算時間和準確度的取捨)，也就是甚麼時候該 local search、該對 population 中的哪個 individual 做 local search、對 local search 該投入多少運算資源等議題。有許多文獻提出非經典的 MA 技巧可以減少運算量，不過這些非經典方法不被廣泛接受，某些方法也需要設定額外的參數。

另一個對於 MA 的難題是如何選擇好的 local search 技巧，在 [Choice of Memes In Memetic Algorithm](https://www.semanticscholar.org/paper/Choice-of-Memes-In-Memetic-Algorithm-Ning-Ong/fb37c8d885e922cfd93f15c770bacece403fc41c) 論文研究中認為沒辦法找到一個在所有 benchmark 上總體表現都很好的方法。

在本論文中，為了做到在減少計算耗費並不使用任何參數，提出了 BOHGA "a best-offspring HGA"。BOHGA 僅在在後代 population 的最佳同時也是在 parent population 的最佳時運作 local search。此外，也提出了一個 [derivative-free](https://en.wikipedia.org/wiki/Derivative-free_optimization) 跟 [self-adaptive](https://en.wikipedia.org/wiki/Self-adaptive_mechanisms) 新 local search 技巧 three-directional local search (TD)。TD 的中心思想是當後代的表現優於 parent 時，從 parent 到其中一個子代會建立 3 個特定步長的方向。

論文會將此方法與新的 individual-learning HGA、BOHGA、以及傳統的 HGA，並各自使用兩個 memes : TD 以及 Neld-Mead simplex method 來做比較。

## The Genetic Algorithm and Hybrid Genetic Algorithm

GA 是一個透過重複的篩選、交配、突變的過程找尋最佳解的過程。對於 k 維度的搜尋空間，將解編碼成一個字串(對應生物學中的染色體)，染色體中有 k 個字元(對應生物學中的基因)，這些字串的集合稱做 population。

而在 GA 中混合 local search 的方法就稱為 hybrid genetic algorithm (HGA)，演算法的流程大致如下：
1. 定義一個 fitness function，並設定 GA operator(例如 population size, parent/offspring ratio, 選擇方法, 交配方法, 突變的比率)
2. 隨機產生初始的母群體
3. 對於初始的個體計算 objective function
4. 透過 GA operator 產生後代
5. 對於後代通過 GA operator 計算 objective function
6. 對於每個後代，使用 local search，評估每個基因改變的影響，如果有 locally 的更佳解，則替換掉該後代
7. 決定下一代的的母體有哪些個體要留下
8. 如果滿足終止條件則停止，否則回到第 4 步

如果把第 6 步拿走，其實整個演算法就是 GA。HGA 的演算根據策略的不同而有許多的變形，在這篇論文中，假設有 k 個變數：(細節待補)
* 母體的 population size 會是 2k，而產生的子代也會是 2k
* 選擇的方法為 random pairing
* 使用 blending crossover 且 crossover 的數量會根據特定的 objective function 決定
* 使用 Random uniform mutation
* mutation rate 為 1/k 或 1/k 左右
* 母體與子代間的替換透過 ranking 或者 tournament

在 local search 上也有許多的方法，在此篇研究中應用了兩種。一種是由論文提出的 three-directional LS (TD)，另一種則是知名的 Nelder-Mead Simplex method。

## The Best-Offspring Hybrid Genetic Algorithm
local search 的目的是希望可以儘早找到目標，然而如果過度的 local search 可能使得母體中的染色體缺乏變異，最後卡在 local optimum 上，因此論文中提出了 best-offspring HGA (BOHGA)，使得 LS 只在子代的最佳同時也是母體的最佳時執行。因為論文中認為，當 best-offspring 出現時，十分可能這個解已經達到另一個山峰(跳出某個 local optimal)，這個作法可以是 BOHGA 在減少運算量的同時跳出 local optimum。

BOHGA 和 HGA 類似，只是把前面提到的第 6 步做調整：
6.1. 是否子代也是母體中的最佳？
6.2. 如果不是則不做 local search，前進到第七步
6.3. 如果是，做 local search 並找到 local 的最佳解，再前進到第七步

## A Three-Directional (TD) Meme
TD 的概念是，當子代比起母體有進步時，很可能從母體到子代的「路徑」，就是得到最佳解的方向。因此 TD 中，其中兩個方向是從其中兩個母體中的染色體到最佳子代的方向。

以此圖為例，假設一個子代 $O$($X_{O} = [X_{O1},...,X_{Ok}]$)，母體中其二為 $P1$($X_{P1} = [X_{P11},...,X_{P1k}]$)、$X_{P2}$($X_{P2} = [X_{P21},...,X_{P2k}]$)。因此就有方向 $\delta_{P1O}$ = $X_{O}$ - $X_{P1}$ = [$\delta_{11}$, $\delta_{12}$, ...... $\delta_{1k}$]$'$，以及 $\delta_{P2O}$ = $X_{O}$ - $X_{P2}$ = [$\delta_{21}$, $\delta_{22}$, ...... $\delta_{2k}$]$'$

第 3 個方向 $\delta$ = [$\delta_{31}$, $\delta_{32}$, ...... $\delta_{3k}$]$'$則是根據前兩個方向，如果 $\delta_{1i}$ 和 $\delta_{2i}$ 同正或同負，則 $\delta_{3i}$ 也與該方向相同(至於要移動多少？參件論文附錄)，如果 $\delta_{1i}$ 和 $\delta_{2i}$ 方向相反，則 $\delta_{3i}$ 為 0。

決定方向之後，從 $O$ 開始根據此方向前進做 local search ，直到在 objective function 上沒有進步為止，以上面的為例就是星號的位置。

選擇的步長 d 會根據 objective function 的顛簸程度調整，論文中建議是在 0.01 到 1.0 之間，如果 objective function 很顛簸，建議用小一點的 d，否則大一點的 d 理應可以比較有效率的運算。

## Nelder-Mead Simplex Meme
[Nelder-Mead simplex method](https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method) 是另一個有名的 local search 方法，以二維的問題為例，simplex 會是一個三角形，而方法的概念是搜索三角形的 3 個頂點，而最差的頂點會被新的頂點替換掉，形成新的三角形。隨著這個步驟會生成一系列的三角形(形狀可能各有差異)，三角形也會愈來愈小，直到找到最小的點。在許多數值測試中，這個方法可以有效的減少運算量，但相對的容易收斂到 local optimal，且通常不適合高度非線性的目標函數。

與 TD 類似，此方法也需要設定步長的參數。在本論文中設為和 TD 的步長設為相同。
## Examples: Benchmark Functions
為了比較 BOHGA 與其他方法的差異，不同方法的 GA operator 參數和起始母體的 seed 會一致。此外，因為不同的 seed 可能會導致計算量的差異，因此採用蒙地卡羅法：對於每個演算法使用不同的 seed 重複進行 100 次，並取其平均代表該演算法的表現結果。

實驗中使用 20 維(k = 20)的資料，因此根據前面所說，母體和子代的大小是 40，crossover 的點是 4 或 8，mutation rate 是 0.05 or 0.06，母體和子代間的選擇是透過 ranking 或者 tournament。

實驗中的終止條件有二，一種是根據使用者對最佳解的猜測(near-global optimum)，設定指定的數值來停止，此方法可以被用來比較 4 個演算法對尋找 near-global optimum 運算的效能，取 100 次實驗的總共執行的 function 數量的平均來比較。另一種是在特定的 generation 後終止，在這種情境下，比較方法收斂到到 global 或者 near-global 的比例，比較每個方法在各代數平均的最佳分數以及各代數的 function 計算量繪圖。4個 bechmark function 在這裡被使用(Rastrigin’s, Schwefel’s, Rosenbrock’s, and Griewank’s，但結果相近且考慮篇幅因此文中只展示了前兩種的結果)

### Rastrigin’s Function


k 為 dimension 數量，如圖為一維和二維的平面樣貌，目標是找到平面上的最小值 min(f(x)) = f(0, . . . , 0) = 0.0.。


上表 1 為在第 1 種終止條件下的結果，在 100 次實驗中 evalution 次數的平均值。可以看到整體而言 $BOHGA_{s}$ 的計算量為最佳，而 $BOHGA_{TD}$ 次之。而從表格中來看，ranking 方法的結果也比 tournament 來得好。


在第 2 種終止條件下(5000 代)，如上圖，從左圖中可以看到除了 $HGA_{s}$ 以外的方法都已經達到收斂，而 $BOHGA_{s}$ 的收斂速度最快。右圖中則把左邊的結果進一步放大，可以更明顯看出 $BOHGA_{s}$ 是最早收斂到指定 cutoff 的，此外，我們也可以看出 TD 方法可以較快 "接近" 最佳解，但是容易卡在附近徘徊，而 Nelder-Mead simplex meme 雖然步伐比較小，但是可以比較精準的抵達最佳解。

### Schwefel’s Function


k 為 dimension 數量，如圖為一維和二維的平面樣貌，目標是找到平面上的最小值 min(f(x)) = f(420.9687,, . . . , 420.9687)(在 k = 20 時會等於 -837966)。



整體結果而言與 Rastrigin’s Function 大同小異。

## Conclusion and Discussion

論文中提出了 BOHGA，和其他的 HGA 不同，僅在限定的條件下對特定的子代去做 local search，並且不需要額外調整的參數，也提出了新的 local search 方法 TD。

整合前面的結果可以看到，BOHGA 比起一般的 HGA 有更佳的運算效率，而 TD 方法對於收斂到靠近最佳解有幫助(可以從 $HGA_{s}$ 和 $HGA_{TD}$ 的差異觀察出)，但是由於 Nelder-Mead simplex meme 可以更準確的走到最佳解，所以整體而言收斂的較快。

從實驗的結果也看到，ranking 方法相較 tournament 的表現較佳，而絕大情況下 mutation rate 0.05 (1/K) 比 0.06 都來得更好，crossover 的數量對結果的影響則沒有太大的顯著性。
## TODO

[Toward Truly "Memetic" Memetic Algorithms: discussion and proofs of concept](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.6200)