---
# System prepended metadata

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

---

# 計算智慧與規劃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**
    - 將大題目拆成子問題，再將子問題分別解開後，回傳並結合成為大題目的解決方法 -> 不一定是最好的
    ![](https://i.imgur.com/shicj9u.jpg =300x)
- 定義一個遞迴函數 -> 節省很多窮舉、時間
- 路線種類:數字相加，但是窮舉是數字相乘
- 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
  ![](https://i.imgur.com/zUbHgSv.png =300x)
- 基本上是窮舉法


***


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
  ![](https://i.imgur.com/QLTUekf.png =300x)
    - 等距編碼 (平常用的Binary Code是不等距編碼)
    - 每走一步，變化量較小且在某個範圍 -> 符合現實情況
    - 判斷是不是鄰居 -> 看相對位置的編碼是否相似
- 演化資訊
  - 外觀 PhenoType 
  - 內部 GenoType
- 例子
    - 有4個變數 -> 構成一個答案
    - 為了讓演算法有效率 -> 變數不是基因而是透過**編碼**形成
