---
# System prepended metadata

title: 智慧計算與規劃WEEK7
tags: [計算智慧與規劃]

---

# 智慧計算與規劃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，直到子代基因都被生出來
    ![](https://i.imgur.com/lMyjK3g.png =400x)

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