###### 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.