###### 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都市)，放幾隻螞蟻最好
- 微笑曲線
- 因為是 16都市 所以有 16隻螞蟻 效果最好 ?
- 小結:問題越複雜，螞蟻數越多越好
- α(眼睛)β(鼻子) 比例
- 上週提到的要貪婪的還是收斂的

### bird flocking 鳥群演算法
> 籃城賞鳥會
- 沒有首領，每一隻都做一樣的事，都是代理人
- 三個原則 -> 主要是參考鄰居
- **Separation** - 每隻小鳥的視線有一定範圍，並和其他小鳥維持一定距離
- **Alignment** - 根據附近小鳥判斷飛行速度、方向
- **conhesion** - 每一隻鳥都想要跑到群體的中心 (本能 : 大家都不想當邊緣鳥)
- 程式：Boids
{%youtube M028vafB0l8 %}
- 下一隻鳥出現在...
- 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算
- 進階版
> 如果不想調整超參數 -> 直接用上面的數字也可以，因為他已經幫你算好了
- IW Model：慣性有加權
- CF Model：不用設定加權，他會自己學
### 演化流程
只有3個步驟
1. 計算每隻小鳥分數
2. 更新記憶體(memory) -> 紀錄分數最大的
3. 開始起飛
### V-max
- l-best(設定視線、可見度)
- 由於鳥群演算法中小鳥參考鄰居而動作，**可見度**設定很重要
- 根據拓樸學，決定要用哪一個(?
- g-best換成l-best
#### 設定方式
- FIPS
> 不一定要用第一名計算，有可能第二名比較好，所以將所有分數給電腦自己計算
> 所有鄰居的best 都會一定程度的影響自己

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