蟻群算法實作TSP（旅行商規劃）問題【人工智能導論作業】C++

資料（自行獲得）：

116.46 39.92
117.2 39.13
121.48 31.22
106.54 29.59
91.11 29.97
87.68 43.77
106.27 38.47
111.65 40.82
108.33 22.84
126.63 45.75
125.35 43.88
123.38 41.8
114.48 38.03
112.53 37.87
101.74 36.56
117 36.65
113.6 34.76
118.78 32.04
117.27 31.86
120.19 30.26
119.3 26.08
115.89 28.68
113 28.21
114.31 30.52
113.23 23.16
121.5 25.05
110.35 20.02
103.73 36.03
108.95 34.27
104.06 30.67
106.71 26.57
102.73 25.04
114.1 22.2
113.33 22.13
           

源代碼（這裡已知最短路徑約為156左右，是以當找不到最短路徑時會自動重新找，直到找到）：

#include<iostream>
#include<string>
#include<stack>
#include<fstream>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define INF 9999999
#define iterat_max 3500;  //疊代次數 
#define City_Max 50    //開辟城市空間 > 實際城市數量  
#define CITY 34        //實際城市數量 
#define ANTS 50        //螞蟻數量 
#define Aerfa 1        //α值 
#define Beta 2        //β值 
#define Q 110          //一隻螞蟻釋放資訊素總量 
#define Rho 0.12      //資訊素消減速度 
using namespace std;
class City{         
	public:
		int id;
		double chance;
		double x;
		double y;
	    friend bool operator<(City a,City b){
	    	return a.chance > b.chance;
	    }
};
class Ant{
	public:
		Ant(){
			vis = 0;    
			len = 0;    
		}
	public:
		int begin;     //初始化位置 
		int temp_pos;  //目前位置 
		bool ban_map[City_Max];    //禁忌表 
		int vis;    //每隻螞蟻在一次循環時經曆過的城市數量
		double len; //每隻螞蟻在一次循環時經曆過的總路程
};
//clock_t start,ends,do_begin,do_end;
int ini_sign = 0;     //初始化資訊素标志位 
int cnt = 0;
double dis;           //最短距離 
double sign[City_Max][City_Max];  //每條路徑資訊素 
City city[City_Max];     //城市群 
Ant ants[ANTS];       //螞蟻群 
int step_min[City_Max];     //最短路徑記錄 
int step[ANTS][City_Max];   //每隻螞蟻路徑記錄 
double route[City_Max][City_Max];  //城市間的距離 
double route_val[City_Max][City_Max]; //城市間距離的倒數 
void Read(){     //讀取城市間距離 
	for(int i = 0;i < 34;i++){
		cin>>city[i].x>>city[i].y;	
		city[i].id = i;
	}
}
void Cal_Route(){    //計算城市間距離 
	for(int i = 0;i < 34;i++)
	for(int j = 0;j < 34;j++){
		double len;
		if(i != j)
		len = sqrt(((city[i].x - city[j].x) * (city[i].x - city[j].x)) + ((city[i].y - city[j].y) * (city[i].y - city[j].y)));
	    else
	    len = INF;
		route[i][j] = len;
		route_val[i][j] = 1/len;
	}
	dis = INF;
}
void Initial(){      //初始化螞蟻 
	srand((unsigned)time(NULL));
	for(int i = 0;i < ANTS;i++){
		ants[i].begin = ants[i].temp_pos = rand() % 34;
		ants[i].len = 0;
		ants[i].vis = 0;
		step[i][ants[i].vis++] = ants[i].temp_pos;
		
	}
	if(ini_sign == 0){
		for(int i = 0;i < 34;i++)
	    for(int j = 0;j < 34;j++)sign[i][j] = 2;
	    ini_sign++;
	}
	for(int i = 0;i < ANTS;i++)
		for(int j = 0;j < City_Max;j++)ants[i].ban_map[j] = false;
}
double Get_Probality(int st,int ed){    
	return pow(sign[st][ed],Aerfa) * pow(route_val[st][ed],Beta);
}
int Route_Select(int index){ //路徑選擇 
	int temp = ants[index].temp_pos;
	double sum = 0;
	double roulette[City_Max];
	stack<int> arr;
	ants[index].ban_map[temp] = true;
	for(int i = 0;i < 34;i++)
	if(!ants[index].ban_map[i] && temp != i){
		sum += Get_Probality(temp,i);
		arr.push(i);
	}
	double max = 0;
	int sle;
	priority_queue<City> q;  //優先隊列實作輪盤賭
	while(!arr.empty()){
		int k = arr.top();arr.pop();
		city[k].chance = Get_Probality(temp,k) / sum;
		q.push(city[k]);
	}
	srand((unsigned)time(NULL)); 
	double num = rand() % 10;
	num = num / 10;
	double aera = 0;
	while(true){
		City p = q.top();q.pop();
		aera += p.chance;
		if(num > aera)continue;
		else {
			sle = p.id;
			break;
		}
	}
	ants[index].ban_map[sle] = true;
	ants[index].len += route[temp][sle];
	ants[index].temp_pos = sle;	
	step[index][ants[index].vis++] = sle;
	return sle;

}
void Update_Sign(int index){   //資訊素更新 
	double avg = Q / ants[index].len;
	for(int i = 0;i < 34;i++)
	sign[step[index][i]][step[index][i + 1]] += avg;	
}
void save(int index){    //儲存最短路徑 
	for(int i = 0;i < 34;i++)
	step_min[i] = step[index][i];
}
void Show(int n){ 
    //system("cls");
	cout<<"iter: "<<n<<" distant: "<<dis<<endl;
	for(int i = 0;i < 34;i++)
	cout<<step_min[i]<<" ";
	cout<<endl<<endl;; 
}
void Solve(){     //蟻群算法主體 
	int iter = iterat_max;
	int total = iterat_max;
	while(iter--){
		Initial();
		int temp_sum = 33; 
		for(int i = 0;i < 34;i++)
		for(int j = 0;j < 34;j++)
		sign[i][j] = (1 - Rho)*sign[i][j];
		for(int i = 0;i < ANTS;i++){
		for(int j = 0;j < 33;j++)Route_Select(i);
		step[i][ants[i].vis] = ants[i].begin;
		ants[i].len += route[step[i][ants[i].vis - 1]][ants[i].begin];
		Update_Sign(i);
		if(dis > ants[i].len){
			dis = ants[i].len;
			cout<<"iter: "<<iter<<" min:"<<dis<<endl;
			save(i);
	    } 
	  }
	   Show(total - iter); 
    } 
}
int main(){
	Read();
	Cal_Route(); 
	while(true){
		ini_sign = 0;
		system("cls");
		Solve();cnt++;
		if(dis <= 157)break;
	}
    cout<<"total run: "<<cnt<<endl;
	
}