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

## Swarm Intelligence 群體智慧

## Socio-cognition
### Social Enviornmont
### Social Influence
### Collective behavior

> 書《群的智慧》：向螞蟻、蜜蜂、飛鳥 學習組織運作絕技
> 

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

### 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值設越大，每一種可能的結果分數差距越大
 
- 螞蟻演算法中的處罰：扣費洛蒙
+ 

+ 
- 特性
- 當 Alpha = 0, Beta = 1
-> 就像是把螞蟻的鼻子割掉，只用眼睛看
-> 不會收斂, 很多答案(很多解)
- 當 Beta = 0, Alpha = 1
-> 就像是把螞蟻的眼睛戳瞎，只用鼻子聞
-> 很快收斂，很快就會有答案(不一定是最佳)

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