---
# System prepended metadata

title: 計算智慧與規劃WEEK12 --- 找最佳解
tags: [計算智慧與規劃]

---

###### tags:    `計算智慧與規劃`
# 計算智慧與規劃WEEK12 --- 找最佳解


## 期末 Project：找最佳解
:::info
1. 問題從哪裡來
2. 找open source、自己寫程式碼、學長姐的程式碼
3. 分析、解釋程式碼去分析問題
4. 從問題哪一個點切入解決
:::
### 問題一：PM2.5
- 從眾多個當中選出幾個最好的
- 資料:2016年埔里氣象資料 (大約56700小時)
- 回歸：改寫 GA - fitness function
- 線性回歸的PM2.5預測
  - 4個變數y加減乘除後得出預測值
  - 學w
  - loss function：MAPE, MSE, RMSE
- 找到影響埔里PM2.5變化的因素有哪些
- 資料清理
  - 用程式 check (自己寫 or 用 python)
  - 缺值 -> [python補值](https://ithelp.ithome.com.tw/articles/10201106)
      > 可以用平均、前一個小時、後一個小時、去年同時刻補上去

### 問題二：flow shop
- 所有程序一併要按照順序做完
- NP complete
- 工廠排程：一產品須經由 A生產線 和 B生產線，找最佳排程 (使用時間最少)
- ex:
    > A生產線先跑，而生產的過程中會產出廢料，等廢料足夠讓B生產線開始生產，B生產線就會開始跑
### 其他問題
- 自己找


# 螞蟻演算法後續
## Ant robotics 螞蟻機器人
- 解決離散型的問題，不要套用實數問題
- 告訴它幾隻螞蟻, 設定α, β等超參數
- 螞蟻走過變黑色
- indirect learning：角色間不會直接對話，而是透過第三方訊息溝通 (群體ㄉ奧妙)
- 整數座標
    > 可以直接找到整數塗黑直線(類似螞蟻所走過的路釋放費洛蒙)
- 實數座標
    > 半徑為多少的距離畫一個圓，圓內塗黑
    > 每到一個點就產生、紀錄sample
- 用實數座標，基因演算法在螞蟻演算法比較便利
- 補充： Vitorino Ramos 螞蟻有自我組織的行為，設定二個動作即產生這種現象
  - pick
  - drop
  => 只需要決定這2個動作的閾值是多少
  => 應用 : image habitats
### 流程
1. 產生基因可機器
   - 螞蟻演算法的答案是它的**路徑圖**
   - 輸入一個圖片 -> 將圖片變成線段圖 -> 將現有圖形做轉換，**形成一個地圖** -> 讓螞蟻去跑
2. 交配(天擇??)
   - 多親組合，前段+上本身的機率 
3. 突變
   - TSP(整數型問題)任意二點都有連線，只是機率不同 -> 不需要突變
   - 實數型問題需要突變
4. 打分數
5. 天擇
    - 統計誤差
- (局部費洛蒙更新)可做可不做 -> suffling，在走過的路留下些微費洛蒙，告訴其他螞蟻不要再走這裡
### MMAS(Max-Min Ant System) 著名版本
  - 只有第一名的螞蟻能留費洛蒙
  - 蒸發很慢
  - 一開始所有路都都有100費洛蒙，慢慢下降
  - 費洛蒙設值有設範圍：最大值(max)和最小值(min)，高於max算max，低於min算min
  - restart：一段時間內所產生的結果(Generation)沒有進步，[將數據設成max(等同於退回第一代)](等等問大馬達)(對~)
    > 上一周教的螞蟻演算法的restart是費洛蒙歸零(1.0)

調整超參數
- 放幾隻螞蟻最好?
  - 時間成本 = 螞蟻數量*代數(generation)
    > 數量 & 代數成反比，不然會花費太多CPU
  - TSP問題(16都市)，放幾隻螞蟻最好
     ![](https://i.imgur.com/VrAyxp7.jpg =300x)
     - 微笑曲線
     - 因為是 16都市 所以有 16隻螞蟻 效果最好 ?
  - 小結:問題越複雜，螞蟻數越多越好 
- α(眼睛)β(鼻子) 比例
    - 上週提到的要貪婪的還是收斂的


### bird flocking 鳥群演算法
> 籃城賞鳥會
- 沒有首領，每一隻都做一樣的事，都是代理人
- 三個原則 -> 主要是參考鄰居
  - **Separation** - 每隻小鳥的視線有一定範圍，並和其他小鳥維持一定距離
  - **Alignment** - 根據附近小鳥判斷飛行速度、方向
  - **conhesion** - 每一隻鳥都想要跑到群體的中心 (本能 : 大家都不想當邊緣鳥)
- 程式：Boids
  {%youtube M028vafB0l8 %} 
- 下一隻鳥出現在...
   ![](https://i.imgur.com/YTQI1AY.png)
  - v：慣性 -> 往原本的方向多跑一步
  - c1*(...), c2*(...)：經驗值
  - p-best：個人經驗
  - g-best：所有人的經驗
    > (pbest - x) 是向量 * 1.5(c) *(random(0,1))
    > 取得向量後，乘上1.5倍 -> 把得出的距離當作1，再乘上random(0,1)代表0~上述得到的距離之間都有可能
    > 每一隻小鳥最好的pbest，拿出來跟其他小鳥一起比較，得出的結果為gbest
  - 下一隻小鳥的會出現在粉色區域的任一點
  - 為了避免某隻鳥會突然加速，設 v 有最大值(Vmax)。若 v 超過 Vmax，v = Vmax -> 用 V max算
- 進階版
   ![](https://i.imgur.com/Dkh0Yrq.png =500x)
    > 如果不想調整超參數 -> 直接用上面的數字也可以，因為他已經幫你算好了
  - IW Model：慣性有加權
  - CF Model：不用設定加權，他會自己學
### 演化流程
只有3個步驟
1. 計算每隻小鳥分數
2. 更新記憶體(memory) -> 紀錄分數最大的
3. 開始起飛
### V-max
- l-best(設定視線、可見度)
  - 由於鳥群演算法中小鳥參考鄰居而動作，**可見度**設定很重要
  - 根據拓樸學，決定要用哪一個(?
  - g-best換成l-best
#### 設定方式
- FIPS
  > 不一定要用第一名計算，有可能第二名比較好，所以將所有分數給電腦自己計算
  > 所有鄰居的best 都會一定程度的影響自己

- stochastic toplogy(每次都隨機產生鄰居)
