# TSP with ACO

###### tags: `Algorithm` `Metaheuristic`

---

[toc]

---

## 定義

### 初始化

void Initial(
vector<vector<double>>&pheromone,
vector<vector<double>>&n,
vector<vector<int>>&path,
vector<vector<double>>&dis);

pheromone費洛蒙表
n距離倒數表
path每隻螞蟻所走過的路徑
dis距離表

執行初始化時會先將pheromone(費洛蒙表)表都先給予最小值0.000001，以及先將dis(距離表)和n(距離倒數表)建立(將51個城市之間的距離算好)，將path路徑初始化。

pheromone[i][j] 路徑ij的費洛蒙
dis[i][j] 路徑ij的距離
n[i][j] 路徑ij的距離的倒數
path[i][j] 城市(第i隻螞蟻，第j個順序的城市)

### 建構螞蟻初始路徑

void ConstructAntSolutions(
vector<vector<int>>&path,
vector<vector<double>>pheromone,
vector<vector<double>>n);

pheromone[i][j]=路徑ij的費洛蒙
path[i][j]=城市(第i隻螞蟻，第j個順序的城市)
n[i][j]=路徑ij的距離的倒數

### 更新費洛蒙及最佳解

void UpdatePheromones(
vector<vector<double>>&pheromone,
vector<vector<double>>dis,
vector<vector<int>>path,
vector<double>&Lk,
vector<int>&best_path,
double &MIN_Lk);

Lk每隻隻螞蟻的總路徑長
best_path存放最佳解的路徑
MIN_LK存放最佳解的路徑長

pheromone[i][j]=路徑ij的費洛蒙
dis[i][j]=路徑ij的距離
path[i][j]=城市(第i隻螞蟻，第j個順序的城市)
Lk[i] 存放51隻螞蟻的總路徑長
best_path[i] 存放最佳解的路徑
MIN_LK 存放最佳解的路徑長

### 計算距離

double Distance(
int x1,
int y1,
int x2,
int y2);

回傳第二個點跟第一個點之間的距離

### 計算機率


double Prob(   
vector<vector<double>>pheromone,
vector<vector<double>>n,
int alpha,
int beta,
int i,
int j,
vector<double>p);

pheromone[i][j]=路徑ij的費洛蒙
n[i][j]=路徑ij的距離的倒數
alpha=1
beta=2
i 城市1
j 城市2
p[i] 如果不等於-1，代表城市尚未走過

公式上半部為費洛蒙表[i][j]的alpha次方乘上距離倒數[i][j]的beta次方

公式下半部為尚未走過的路徑的，費洛蒙表[i][j]的alpha次方乘上距離倒數[i][j]的beta次方的加總

### 計算總路徑長

void CalculateLk(    
vector<vector<int>>path,
vector<vector<double>>dis,
vector<double>&Lk);

dis[i][j]=路徑ij的距離
path[i][j]=城市(第i隻螞蟻，第j個順序的城市)
Lk[i] 存放51隻螞蟻的總路徑長

計算每隻螞蟻的總路徑長(一整圈)

### 查看這隻螞蟻是否走過此路徑

bool FindAntPath(
int pos1,
int pos2,
int ant,
vector<vector<int>>path);

pos1 城市1
pos2 城市2
ant 哪一隻螞蟻
path[i][j]=城市(第i隻螞蟻，第j個順序的城市)

判斷螞蟻是否走過指定路徑，回傳true或false

### 查看城市(debug用)

void ShowCity(
int size,
vector<city>City);

查看讀入的測資

### 查看路徑(debug用)

void ShowPath(
vector<vector<int>>path);

查看每一隻螞蟻所走過的路徑

## 程式碼說明

### 建構螞蟻初始路徑

> 上圖中，宣告以及將城市洗牌，rnd_city[i]代表第i隻螞蟻的初始城市


> 上圖中，外迴圈圍每隻螞蟻，pos紀錄順序(已經選擇到第幾個城市了)，p[]為建立機率表，來決定下一點要走向哪個城市，已經走過的點p[第幾個城市(而不是前述的pos，pos是順序)]=-1，path[第幾隻螞蟻][順序]=起始城市。進入無窮迴圈，這邊會將每座城市的機率算出來(其中i為我現在所在的城市，j為我尚未走過的城市)，temp會將所有機率相加，rnd_d會隨機產生亂數範圍從0~temp(大約為1.多)，下面迴圈的部份是我將剛剛所產生的rnd_d(機率)，如果尚未走過(p[k]!=-1)，如果rnd_d大於此機率那就減去，如果rnd_d小於此機率代表下一個要選擇的城市為此，如果pos已經走完所有城市那就代表已經建構完成。

### 更新費洛蒙及最佳解



> 上圖中，CalculateLk為計算每隻螞蟻所走的路徑總長，雙重迴圈當中是利用上面的公式將費洛蒙表做更新，公式前半部是要留下之前的多少比例，後半部為先判斷每隻螞蟻是否有走過此路徑（ｉｊ），如果有的話dis_total會將走過此路段的螞蟻，使用mQ/路徑長(Lk[i])相加。結束費洛蒙表更新後，會來判斷每隻螞蟻的總路徑長是否有小於目前的最佳解的路徑長(MIN_Lk)，如果有的話將路徑長(MIN_Lk)及最佳解(best_path)更新。

### 主程式


## 執行(目前最好為427.389，但因疏失沒有紀錄)

### Github
> https://github.com/taro0520/TSP_ACO

### 指令

> ./main [#runs] [#iteration] [#ants] [#citynumber] [#alpha] [#beta] [#p] [#q] [#filename]

### 參數設置

> Runs:30
> Iteration:1000(平均執行完1000iteration需花16-30分鐘)
> Ants:51(小於等於城市數量)
> Citynumber:51
> Alpha:1
> Beta:2
> P:0.8
> Q:100
> Filename:data.txt
> 測資: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ (eil51)

### 產生gnuplot圖

1. 將產生好的Best Path貼至result/path.txt
2. 使用此指令將路徑轉成xy座標.\point 51 city.txt path.txt path_xy.txt
(城市數量:51 城市座標:city.txt 路徑順序:path.txt 輸出:path_xy.txt)
3. plt寫法
4. 使用gnuplot產生圖檔

### 輸出(持續更新)

> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:9
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:100
> **#Best Distance:432.187**
> **#Best Path:**
> **36 16 3 17 13 24 12 40 18 39 41 43 14 44 32 38 9 48 4 37 10 31 0 21 1 15 49 8 29 33 20 28 19 34 35 2 27 30 7 25 6 42 23 22 47 5 26 50 45 11 46**
> #Cost Time:13140s

#### gnuplot圖


### 多筆測試輸出

1.
> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:30
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:100
> **#Best Distance:433.795**
> **#Best Path:**
> **8 49 15 1 21 0 31 10 37 4 48 9 38 32 44 14 43 41 39 18 40 12 24 13 17 46 3 16 36 11 45 50 26 47 5 22 23 42 6 25 7 30 27 2 35 34 19 28 20 33 29**
> #Cost Time:41646s

2.
> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:30
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:100
> **#Best Distance:435.644**
> **#Best Path:**
> **24 12 40 18 39 41 16 36 43 14 44 32 38 9 29 8 48 4 37 10 31 0 21 1 15 49 33 20 28 19 34 35 2 27 30 25 7 47 22 6 42 23 13 5 26 50 45 11 46 3 17**
> #Cost Time:46916s

3.
> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:30
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:100
> **#Best Distance:436.646**
> **#Best Path:**
> **5 26 50 45 11 46 3 17 13 24 12 40 18 39 41 16 36 43 14 44 32 38 9 29 33 49 15 1 21 0 31 10 37 4 48 8 20 28 19 34 35 2 27 30 25 7 47 22 6 42 23**
> #Cost Time:46863s

4.
> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:30
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:120
> **#Best Distance:437.053**
> **#Best Path:**
> **14 44 32 38 9 48 4 37 10 31 0 21 1 15 49 33 29 8 20 28 19 34 35 2 27 30 7 25 6
42 23 22 47 5 26 50 45 11 46 3 17 13 24 12 40 39 18 41 43 36 16**
> #Cost Time:41593s

5.
> =[Travelling Salesman Problem]=
> #Algorithm:Ant Colony Optimization
> #Runs:30
> #Iteration:1000
> #Ants:51
> #Citynumber:51
> #Alpha:1
> #Beta:2
> #P:0.8
> #Q:100
> **#Best Distance:437.615**
> **#Best Path:
> **22 6 42 23 13 24 12 40 18 39 41 16 36 43 14 44 32 9 38 29 8 48 4 37 10 31 0 21 1 15 49 33 20 28 19 34 35 2 27 30 25 7 47 26 50 45 11 46 3 17 5**
> #Cost Time:46893s