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

## 直接法
### branch and bound - 線性(LP Linear programming )
- 找最佳解
> 有機會用最佳解就用最佳解，不然求近似解
- 單調性
> 不是所有問題都有單調性
- `branch` 分支 `bound` 計算答案
- ==LP & ILP==(Integer for Linear programming)
- loop: {找branch => 找bound}
- 找到最大值(天花板)
- 慢慢爬
- 跳躍式
- 基本上是窮舉法，但運氣好的話很快就可以找到答案(貪婪法式的窮舉法)
- 好情況：
- 回傳**整數**
- **==no solution==** (代表不用再走這一個分支)
### Dynamic programming 動態規劃
- 大前提：**divide and conquer**
- 將大題目拆成子問題，再將子問題分別解開後，回傳並結合成為大題目的解決方法 -> 不一定是最好的
- 定義一個遞迴函數 -> 節省很多窮舉、時間
- 路線種類:數字相加，但是窮舉是數字相乘
- forward
- backward：終點找短的，起點找長的
### LCS (Longest Common Subsequence 共同最長子序列)
- 並不是所有資料都是數字型態，當要比較大小時，比**string的相似度**
- subsequence: 一字串字母的排列次序。和substring不同的是，substring 是連續的，subsequence 只要**相對位置**一樣就好
> 舉例
> S1="ABCDE" 和 S2="ACE"的LCS = 3
- 找LCS：
- Step1. 邊界補0
- Step2. 走訪Table填數字。填 Table[i, j]：
- S1[i] 和 S2[j] 一樣 -> Table[i, j] =斜上 + 1
- S1[i] 和 S2[j] 不一樣 -> Table[i, j] = min(左, 上)
- Step3. 走到最後一個格子就是答案
- 找LCS子字串：填表後backtrace
- 基本上是窮舉法

***

Chapter2
## Drawinism - 達爾文進化論
多個物種之間的競爭
### 原則
#### survival of the fittest 適者生存(天擇)
#### Diversity and selection pressure 多樣性和演化壓力
### Selfish Gene 自私基因
- 舉例：布穀鳥托卵
- 蛋殼硬
- 孵化期短
- 破壞其他卵
- 比起其他幼鳥，外表看起來健康又有活力 -> 優先被餵食
- 演化的過程是殘酷的
- 遺傳的證據
### 演化計算(EC, Evolutionary computation)
- 透過群體(人口, population)演化，彼此互相競爭
- 程式跟程式之間的演化
> 「程式設計師的夢想是再也不用寫程式」
#### ES (Evolution Strategies) 演化策略
#### EP (Evolutionary Programming) 演化規畫
#### GAs (Genetic Algorithm) *基因演算法*
- SGA(Simple Genetic Algorithm)
1. BOOM! -> 亂數產生染色體
- 染色體：各式各樣的資料結構，大多用string
- **loop (重複 2. ~ 4. )**
2. 演化
3. 計算分數(適合度, fitness)
- 計算標準：解決問題的優劣
- 計算函數設成目標函數 -> 不一定
4. 判斷是否採用
- 交配和突變
#### GP (Genetic Programming) 遺傳規劃

## SGA (simple Genetic Algorithm)
- 如何定義染色體的資料結構和編碼
- 資料結構
1. structure(架構)
2. value(值)
3. Tree(限制式)
- 編碼：Gray Code
- 等距編碼 (平常用的Binary Code是不等距編碼)
- 每走一步，變化量較小且在某個範圍 -> 符合現實情況
- 判斷是不是鄰居 -> 看相對位置的編碼是否相似
- 演化資訊
- 外觀 PhenoType
- 內部 GenoType
- 例子
- 有4個變數 -> 構成一個答案
- 為了讓演算法有效率 -> 變數不是基因而是透過**編碼**形成