---
# System prepended metadata

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

---

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


## Swarm Intelligence 群體智慧

![](https://i.imgur.com/e9tN3wc.jpg =500x)
## Socio-cognition
### Social Enviornmont
### Social Influence 
### Collective behavior

> 書《群的智慧》：向螞蟻、蜜蜂、飛鳥 學習組織運作絕技
> ![](https://i.imgur.com/6GPdiga.jpg =400x)

### 間接學習法
- 基因演算法一代一代演化很慢，若由第三方 (例如螞蟻的費洛蒙) 傳播，速度會快很多
#### 補充
> 每個領域都有不同的專有名詞，但是都有相似的觀念連接

### Ant colony optimization 螞蟻群優演算法
[螞蟻演算法基礎](http://debussy.im.nuu.edu.tw/sjchen/Project_Courses/ML/AntAlgo.pdf)

- 每隻螞蟻行進的路線是依據路上留的費洛蒙多寡 (機率依據費洛蒙多寡決定)
- 最短路徑
- 正向回饋 (指數加成作用)
- 費洛蒙(長期記憶體 -> 找到最佳結果再走)&貪婪法求平衡(短期記憶體 -> 找到路徑就走不管他是不是最短)
{%youtube vG-QZOTc5_Q %}
- 走完之後，再計算最短路徑(因為邊走邊留費洛蒙無法知道最終結果是不是最好的)
### Traveling Salesman Problem (TSP 旅行銷售員問題)
- NP complete
- 求近似解
- 貪婪演算法其實還OK -> 快 & 結果還可以
- 分數為距離倒數 
- 將距離換算成分數的公式
- 控制貪婪值得分數為Beta -> 將Beta值設越大，每一種可能的結果分數差距越大
  ![](https://i.imgur.com/xVOJnDM.png =300x) ![](https://i.imgur.com/PRonasG.png =300x)
- 螞蟻演算法中的處罰：扣費洛蒙
+ ![](https://i.imgur.com/LjvoV3i.jpg =500x)

+ ![](https://i.imgur.com/HjaapIo.jpg =500x)
- 特性
  - 當 Alpha = 0, Beta = 1
    -> 就像是把螞蟻的鼻子割掉，只用眼睛看
    -> 不會收斂, 很多答案(很多解)
  - 當 Beta = 0, Alpha = 1
    -> 就像是把螞蟻的眼睛戳瞎，只用鼻子聞
    -> 很快收斂，很快就會有答案(不一定是最佳)

### Scheduling problem 排程問題
- 目標：生產所有產品花最少時間
  - 看想解決的問題決定目標 
      > 平均等待時間愈短愈好
      > 某人錢給的愈多等待時間愈短
      > ...等等
- 困難點：產品要「少量多樣」。而且如果機台有很多台、同時做, 複雜度愈高, 答案品質愈高, 愈難比較優劣, 愈難找到最佳解
- 為NP-complete問題 -> 不可能找到最佳解，也不能用窮舉法解決，只能找到近似解
- 限制
  - 前置時間可以重疊
  - 要等上一個工作同一台機器&上一台機器同一個工作做完才可以做
  - 有順序性的問題，不是任意點都可以當起點 (TSP可以從任意都市出發) -> 加一個**假的點**, 每一隻螞蟻都從該點出發
- 要解決的問題 
  - 貪婪值如何設定
      - 將額外增加的時間當作距離, 愈短愈好
  - 圖形要怎麼設置
    ![](https://i.imgur.com/EMvAwiY.jpg)
  => 這樣就可以直接沿用螞蟻演算法
