# Homework 5: Ant Algorithm

## 蟻群演算法
ACO(Ant Colony Optimization)是模擬自然界中蟻群尋找食物的仿生演算法。在螞蟻移動的過程中，不斷嘗試最短路徑，並會在走過的路上留下特殊的費洛蒙，螞蟻之間可以感知這種物質濃度。如果路徑上的費洛蒙量較高，代表走過該路徑的螞蟻較多或是最新才走過，則後續的螞蟻有較大機率亦選擇此路徑。
在旅行商人的問題中，所有路徑都嘗試的方式為$\frac{n!}{2}$，即便使用平行運算進行暴力破解也需要花費許多時間(例如：最小的作業有17個城市需要3.5568743e+14次)。利用ACO演算法，由於每一次迭代就有m隻螞蟻依照規定走完所有的城市，並傳遞下訊息，可以優化下次選擇過程，讓我們在“猜測”路徑更有效率。

調整權重參數 $\alpha$、$\beta$ 和 $\rho$ 可以改變最終結果：
* $\alpha$ : 決定局部資訊影響性，提高可以讓收斂速度變快，但也可能不是最佳解
* $\beta$ : 距離影響決策程度，提高提高會讓選擇變得隨機
* $\rho$ : 訊息揮發速度，較小的話可以保留長時間訓系進行比較（但會慢一些）

## 效能與討論
1. 速度
3. 結果 (NC=10000)
* gr17_d: 2407
Path: 9 10 14 5 12 15 6 7 16 8 11 0 3 13 2 4 1 9
* fri26_d: 1621
Path: 10 14 7 13 15 16 20 18 19 23 21 22 17 25 24 6 8 9 2 5 3 4 1 0 11 12 10
* dantzig42_d: 2219
Path: 10 17 15 14 33 39 8 0 38 35 32 19 12 13 7 30 26 29 34 24 3 1 41 40 4 9 6 25 27 20 21 31 5 37 16 28 18 22 2 11 23 36 10
* att48_d: 108523
Path: 16 39 17 18 30 7 37 24 23 44 28 38 20 25 8 5 45 12 34 47 41 1 40 4 10 43 19 0 15 21 33 22 46 2 3 32 14 29 26 35 9 13 31 11 27 6 42 36 16

3. 問題：
在一開始對蟻群中每隻螞蟻作初始化時，我使用rand()決定在哪個城市。

    vector<Ant> ants(ANTSIZE);
            for(Ant a:ants){
                a.curr_city = rand() % num_city;
                a.tour.push_back(a.curr_city);
                a.isCityVisited.resize(num_city, false);
                a.isCityVisited[a.curr_city] = true;
            }

雖然compile沒有問題，但執行時遇到以下錯誤：
後來發現應該是[rand()](https://stackoverflow.com/questions/6161322/using-stdlibs-rand-from-multiple-threads/)不是Thread safe，所以我改用:

    random_device rd;
    mt19937 gen(rd());

4. 討論：
用gr17_d在不同參數下得到的結果：
| $\alpha$ | $\beta$ | $\rho$ | Q | NC | Result |
| -------- | ------- |:------ | ------- |:----- |:------ |
| 1 | 5 | 0.2 | 2500 | 10000 | 2462 |
| 2 | 3 | 0.2 | 2500 | 10000 | 2461 |
| 2 | 3 | 0.2 | 2500 | 10000 | 2513 |
| 1 | 5 | 0.2 | 2500 | 10000 | 2521 |
| 1 | 3 | 0.2 | 2500 | 10000 | 2503 |
| 1 | 5 | 0.2 | Dynamic | 10000 | 2489 |
| 1 | 3 | 0.2 | Dynamic | 10000 | 2407 |

Ｑ是螞蟻的費洛蒙總量，一開始設定成固定量，但是在後續路徑逐漸縮小後，似乎會變得有點多，所以我改成「當最小路徑更新後，連帶把Q的數值也更新成此路徑長度」，從結果來看確實達到一定效果。

5. 未來：實驗後，嘗試調整參數還是離助教提供的最佳解有差距，畢竟利用機率挑選路徑，在可能性有很多的題目中未必可選中最佳路徑，所以我目前嘗試把NC改成10,000,000，希望增加此數可以找到，不過跑了45小時，仍在執行運算中。

改進方向或許可以讓Process之間可以分享當前最短路徑的資料？同時考慮讓比較長的路徑更不可能被選到的的方式。

##
[Travel Salesman Problem](http://www.exatas.ufpr.br/portal/docs_degraf/paulo/TravellingSalesmanProblem.pdf)
[Code](https://github.com/abnormal749/Parallel_Computing_2022/tree/main/HW6)
[蚁群算法-求解TSP问题](https://zhuanlan.zhihu.com/p/95782157)
[Homework6 題目](https://hackmd.io/@ZZta/Sy-TqS8Qo)