---
# System prepended metadata

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

---

###### tags: `計算智慧與規劃`
# 智慧計算與規劃WEEK6
## 基因演算法
### Simple Genetic Algorithm 遺傳演算法SGA 
#### 權重算分數->天擇->交配->突變
- search space & fitness space(分數)
- 正規化
    - (自己)/(所有數加起來)
    - 將平滑後的結果正規化
- 權重
    - uniform
        - 中間最高和旁邊的地方 -> 分數都一樣
    - triangle
        - 圖形比較平滑 -> 讓中間比較高的部分分數高，旁邊的分數低
    - Gaussian 高斯
        - 讓圖形變得更平滑 -> 讓中間比較高的部分分數比較高，旁邊的分數比較低，但是分數沒有比中心高
- 天擇說-俄羅斯輪盤
    - 改變"相對機率"大小
    - 分數越大面積越大
- 單點交配(one crossover)
    - 分別從A、B兩長度產生隨機亂數的字串 -> 擷取其中的某一段互換
        - mother strend 
        - original strend
        - daughter strend
    - permutation coding
        - Delete & insert mutation 刪除插入(可能會多基因或是少基因)
        - Swapping mutation 交換(2個不同樣本的同一個位置)
        - Inversion mutation 反轉
  - Pc交配率
- 突變
    - 2種做法
        - string-wise/翻牌突變
        > 機率是否過標 -> 過標突變
        - bit-wise
        > 機率不均勻分布 -> 像硬幣正反面骰出去看要不要突變
    - Variable dependence 變數
        - 設定結束的條件
    - Pm突變率
- 通過疊代的做法將結果進行優化
    - 演算完會有一次結果，將最好的樣本複製給最爛的樣本 -> 再重新進行演算
    - 如果沒有突變，最後的結果可能不是最好的
- 統計誤差
    - 可能的原因
        1.數量太少
        2.天擇法對於這次的情況較不好
- building block
    - ??
#### 定理
- Schema Theorem
    - Schema Order(O(H))
        - 固定的位元有幾個(有幾個家人是固定的)
            > 若固定位元改變 -> 代表不是同一個東西
        - 值越大越容易突變?
    - Defining length(L(H))
        - 值越大越容易交配?
        - ???
    - ex:
        >m(H,t):有H這家人進行t次演算，會有m?
        >當代下一代人口和當代人口的關係

        >樣本H = 11#0#，若字串長度為 l=5
        >固定字元第一個到最後一個的長度為 L(H)=3
        >突變後存活下去的機率為 (剪下去不會發生變動的地方)/(全部可以剪的地方)
        >()/(l-1)
    - 最強
        1.該數據算出來的分數 > 全部數據的平均分數
        2.固定位元個數越少越好
        3.