# 智慧計算與規劃WEEK7
###### tags: `計算智慧與規劃`

## SGA流程

**產生初始數據 -> 算分數 -> 天擇 -> 交配 -> 突變**

#### Step1. 產生初始數據
- 資料種類
- 二進位
- 十進位
- 實數：很難重複
- 方法
- 使用亂數
- Unbiased：不使用亂數，上下任挑兩個互換數次使其打亂，0和1的出現總數一樣
- Uniform：選定n格不同範圍，在數個小範圍內產生亂數，較均勻，適用實數和十進位
- 田口實驗法(Taguchi's array):選定好幾個範圍，符合Unbiased,符合Uniform，均勻分布
公式：Lp(n^m)
- n: 每個變數有n個區間
- m: 有m個變數
- p: 做p次

#### Step2. 算分數
- fitness space:計算存活率的分數
- 平滑化 Convolution
- filing scaling(線性內插法)
- 限制每代分數相差幾倍(r, 3~10)
- 可避免相差100倍、掉進局部最佳解的情況發生(即 某一條染色體支配全局的情況)
- fitness sharing:
- 考慮附近鄰居的**擁擠程度**
- 雞蛋不放在同一個籃子
- 如果太近扣分
- 自己分到1張，最遠的地方(α)分到0張，距1/2*α的地方分到0.5張
- α可以調整
- If 有限制式g -> Contraint Handling
- Special gennetic operators
- 一開始就不產生限制式外的東西
- Repairing Algorithms ((產生重複數字要麼整理?
- 先產生出來，再事後修正
- Penalty Function
- 死亡(Dead):扣他分(誰叫他賴皮XD)
- Static 靜態型處罰，每一代的處罰一樣重
- 動態的(Dynamic)：把時間因子也考慮進去，愈到演化中後期，處罰愈重

#### Step3. 天擇(Nature Selection)
- Roultte-wheel 俄羅斯輪盤法
- 純亂數
- 取代式(replacement model)：一直射飛鏢, 射完飛鏢後面積沒有減少
- 不容易發生淘汰
- Expected-value期望值法
- 非取代式(non-replacement model):選中後將他的分數扣掉(也可以說 飛鏢射中後拿掉那一塊面積)
- f/f bar: 你值得生幾個小孩
- 分數高於某門檻(如0.5), 才有機會有小孩。當全部低於門檻時，開放自由競爭
- 誤差到最後階段才會發生 -> 使累積誤差降到最小
- 最完美的情況：net count都等於0
- 適當地介入淘汰
- 命令式法 (Deterministic sampling)
- 先把f/f bar次生完
- 把剩下的小數部分排序，決定生誰
- 沒有隨機的成分
- 天擇壓力較大
- 很容易淘汰
- Remender stochastic with replacement
- 整數部分用命令式法
- 小數部分用輪盤法
- Remender stochastic without replacement
- 整數部分用命令式法
- 小數部分用期望值法
- (最好的方法)
- Tournament Selection 公開賽法
- 捉對PK
- 從目前的人口中，隨機挑二個人比分數，贏的人可以有下一代
- replacement model (可以重複PK)
- 選k個，比完後，最後(k-1)個一定會被淘汰
- 調整k(k 越大天擇壓力越大，不一定比較好)

==**前面幾種方法都是：親代生下一代後，親代就死掉了**==
- Rank selection 排名天擇法
- 將排名變成倒數轉成機率
- Truncation Selection
- 父代子代有交換時可用
- 父代子代全部排名取前100
- generation gap 菁英策略
- 將最好的基因copy下，來多活一代
- 父代的前n 名一定留下
- 子代剩下100- n 可以生

#### Step4. 交配(Crossover)
想辦法找出最好的基因
- 單點--------多點----------n點
- 單點交配(one crossover)：一剪 (三點交配就是三剪)
- n點交配(uniform crossover):一直丟銅板，依正反面決定要誰的基因
- 二親代, 多親代(multi-parent crossover)
> 揠苗助長不是好事。若太極端，當環境改變時反而第一個被淘汰
- 田口正交法 (Orthogonal/Taguchi crossover)
- 完全介入式
- 實數做交配
- Arithmetic Crossover
- 二進位或整數可以直接互換，但實數不行
- 實數為互補(ex:媽媽 * 0.4,爸爸就是 * 0.6)
- 線性組合
- 原則上，子代會出現在爸爸和媽媽的「對角線之間*α」
(之所以*α是為了避免收斂太快，族群愈來愈小)
- α(alpha)-extension crossover
- 交配範圍不侷限在爸媽之間
- 整數做交配 -> 要克服數字重複的問題(不合理解)
- Partially Matched Crossover(PMX)
- 會重複的先做記號，換下來的時候，重複的部分換成原本的整數
- Order Crossover (OX)
- 若是要交換的數字剛好都有重複，用上面那種方法會不變，那就交換順序
- 只擾亂一條基因
- 沒有生物學上的意義，是為了滿足限制式發展出的方法
- Cycle crossover (CX)
- 有生物學上的意義
- 起點是隨機的
- 有好幾個起點、好幾個cycle，直到子代基因都被生出來

#### Step5. 突變(Mutation)
1. Gaussian
2. Uniform
3. Non-uniform