# 演化計算總結 Evolutionary Computation
###### tags: `Evolutionary Computation`

[TOC]

修了陳穎平的**演化計算 Evolutionary Computation**，總結期末做的成果。

## Problem

我們考慮的問題是 Min-Max Cycle Cover Problem (MMCCP)。在這個問題，給定一個圖 $G=(V,E)$ ，圖的點和邊都有非負的權重，寫作 $h_v$ 和 $w_e$ ， $v\in V,e\in E$。目標是在圖上找 $k$ 個 cycles，使得每個點都至少被一個 cycle cover 到。同時，我們希望最大的 cycle 的權重被最小化，也就是：

$$
\max_{1\leq i\leq k} w(C_i),\quad\text{where }w(C)=\sum_{v\in V(C)}h_v+\sum_{e\in E(C)}w_e.
$$

<img style="display: block;margin-left: auto;margin-right: auto;width: 30%;" src="https://i.imgur.com/nPMl4mg.png">

## Chromosome Representation

用 genetic algorithm 解這個問題的話，首先要定義如何表示一個 solution。

這裡我們的方法是構造一個長 $|V|+k-1$ 的 permutation。 $[1,n]$ 的部分代表點的編號，其他數字則代表**分隔點**，從這些位置分隔後，剩下的每一段就對應了一個 cycle。

<img style="display: block;margin-left: auto;margin-right: auto;width: 40%;" src="https://i.imgur.com/NXMKgCm.png">

所以來說

- 對，分隔點的數字是多少不影響其表示的解，只是為了讓他是個 permutation。
- 對，這樣搜尋的空間大的離譜，很多 representation 都對應到一樣的解，例如單個 cycle 內的 circular rotation、cycle 先後順序變換等等。
- 但好處就是方便套用現有的 policies

## Policies, Grid Search

下一個要決定的是演化的流程，一般包含

- selection
- 決定哪些人要產出子代 (offspring)
- elitism, roulette wheel, random, tounament
- crossover
- 給定 parent ，生出子代的方法
- 子代通常和 parent 長的很不一樣，類比於在 exploration
- 這部分高度取決於你的 representation，以 permutation 類型的來說，有以下
- PMX、OX、Cycle Crossover、Edge recombination
- 簡單來說，給定兩個 permutation，該如何產生一個新的，但又充分利用那兩個 permutation 的資訊的 permutation？ 這幾種方法都蠻有意思的
- mutation
- 對某些人作微小的變動，類比於 exploitation
- insert, swap, inverse, scramble
- replacement
- 人口變多，要有一個篩選機制讓一些人口死亡
- elitism, age-based...

這裡四部分 policy 個挑一種就是一種 genetic algorithm 的玩法，這麼多種組合該用誰？就都試試看吧！

Grid Search 是一個很暴力的 hyperparameter optimization 方法，descrete parameter 就都試試看，continuous parameter 就切幾部分然後還是都跑跑看。

<img style="display: block;margin-left: auto;margin-right: auto;width: 80%;" src="https://i.imgur.com/hXTIYLr.png">

## Result of GA

先看看這部分的結果吧，哪個組合最好，哪個 policy 好其實沒那麼重要，給個都有自己最適用的場合，來看別的吧。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/0rd877a.png">

一個正常的結果應該長上面這樣，快速找到升到不錯的數字，而後持續緩慢進步。

很有趣的問題是在後期， crossover 因為很隨機，很難想像能生出能在人口中存活的 offspring。但統計證明還是約有 $1/3$ 的子代有競爭力，存活了下來。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/thWq5s4.png">

再來是 diversity，diversity 太小代表 exploration 不足，會在一個 local optima 附近轉來轉去：太大代表一個 local 找不夠，局部還沒鑽到頂就去找其他地方。

我的部分是略高，exploitation 可能不太夠。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/a6c11ck.png">

## Interesting Instance Finding

我們還有第二 part。這部分，我們打算跟一個現有的演算法 $\mathcal A$ 比較，但我們的目標是找一些 instance，用他們的演算法會做很爛，但我們會做很好。

因為他們的做法是 combitorial 的，所以在某些 instance 可能會有很神奇，不符合直覺的做法發生，而 GA 是相對 general，不像是會對某些 instance 做出特殊行為的算法。

這部分就套用課堂上另一個系統 Evolution Strategies 來解它。

## Evolution Strategies

和剛剛差在沒有 crossover，但給 mutation 更大的彈性。值域是連續區間時適用。我用了

- $(1+1)$-ES
- 生一個子代，兩個選較好的那個存活
- $1/5$ rule
- 一個決定 mutation step $\sigma$ 的做法

懶的說了，看結果吧。首先是不同的 $\sigma$，可以發現給太大它會自己降下去，給太小它會上升。

注意它並不是趨近於 $0$，會落在 $0.02$ 附近。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/YqsSGWA.png">

再來是 fitness，一個新的子代一開始可能會被高估而衝上去，但多回合後他的分數會被平均掉而慢慢下去，然後某天會被更好的 (或只是更賽的) instance 給取代掉。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/C0EmehR.png">

我最喜歡的還是直接看 instance 了。左邊是我們的GA，右邊是他們的演算法，中間是原始的 instance。圈圈大小代表 $h_v$，距離直接代表 $w_e$。

可以看到我們的在小 instance 下做的多美，而他們的則會圈在很神祕的地方。同時，instance 也不是很極端，例如全都貼到邊界，這符合我們需求，就是看起來正正常常的 instance，但它的的演算法就是會做出看不懂的行為。

<img style="display: block;margin-left: auto;margin-right: auto;width: 90%;" src="https://i.imgur.com/0QZ5Snw.png">

<img style="display: block;margin-left: auto;margin-right: auto;width: 90%;" src="https://i.imgur.com/uyqyZPL.png">

## 小結

整體來說還不錯，但 exploitation 可能不夠，還是因為一開始 code 寫不好，改進改錯方向。

雖然做了一堆沒用的改進，但內容是有用的，所以也提一提，也順便提一提可以改進的地方。

### Worst Among Most Similar (WAMS)

概念大致上是，為了避免 diversity 過小，在要加入新子代，把老人踢掉的時候，踢一個跟自己比較像的。

<img style="display: block;margin-left: auto;margin-right: auto;width: 40%;" src="https://i.imgur.com/l0lsRxH.png">

當時的 code WAMS 會有一定的效果，但在正確的 code 中，我 diversity 一直蠻高的，自然沒這個問題了。

### Tabu Search

很暴力，建一個表，把有生過的 chromosome 都記錄起來，之後真的遇到就無視掉或再把它改掉，總之重複的不要再做。

很直覺，假設我們原本會卡在 local optima，加了這個之後，我們只要把這個 local optima 充分找過，就會開始撞 table，然後開始搜其他地方。

<img style="display: block;margin-left: auto;margin-right: auto;width: 60%;" src="https://i.imgur.com/nKHGX0F.png">

在正確的 code 中，撞的機率低的離譜，完全沒有加的必要。

### Representation

可以改進的地方，representation 絕對是一個部分。搜尋的成效還是很大一部分取決於 search space，太大它也是沒轍。

### Memetic Algorithm

這個東西說白了就是 genetic algorithm 加上 local search，也就是某些時候用更直接的方法去找 local optimum，例如套一層 ES，而非只用 GA 的 mutation 靠賽。

Mutation 雖然是做微小的改動，但一大問題是在越貼近 local optimum 的時後，要做出能進步、**正確的** mutation 的機率就越低。那更直接的方法就很重要了。

**強烈建議每一組在發現 exploitation 不夠時，搞搞看這個。**