fork(1) download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <time.h>
  5. #include <algorithm>		/*	find	*/
  6. #include <vector>			/*	vector	*/
  7. #include <fstream>			/*	to read and write file	*/
  8. #include <string>       	/*	std::string, std::to_string	*/
  9. #include <iterator>  		/*	std::begin, std::end	*/
  10. #include <sstream>
  11. #include <math.h>			/*	sqrt pow	*/
  12. #include <cfloat>			/*	Limits of floating point types	*/
  13.  
  14. using namespace std;
  15.  
  16. typedef vector<int> i1d;
  17. typedef vector<i1d> i2d;
  18. typedef vector<double> d1d;
  19. typedef vector<d1d> d2d;
  20. typedef vector<bool> b1d;
  21. typedef vector<b1d> b2d;
  22.  
  23. i1d shortest_tour;
  24. i2d ant_position;
  25. b2d tabu;
  26. d2d trail;
  27. d2d delta_trail;
  28. d2d distanceXY;
  29. d2d locationXY;
  30. d2d transportation_probability;
  31. i1d unused_position;
  32.  
  33. int edge_weight_type;
  34. int dimension;
  35. int sum_ant;
  36. int Nc = 0;		//NC is the cycles counter
  37. int NcMax;
  38. int S;
  39.  
  40. double alpha;
  41. double beta;
  42. double rho;
  43. double tau;
  44. double Q;
  45. double shortest_distance = DBL_MAX;
  46.  
  47. string dataset_name;
  48.  
  49. void 	init();
  50. int 	random(int low, int up=0);
  51. double 	random(double low, double up=0.0);
  52. void	read_file(string filename);
  53. void	write_file(string ,string);	//[filename, context]
  54. void	file_context_analyse(string, int);
  55. double	Euclidean_distance(d1d, d1d);
  56. void	caculate_distance();
  57. void	run();
  58. double	get_distance(int, int);
  59. double	get_trail(int, int);
  60. void 	ant_system();
  61. void 	first_trip();
  62. void	delta_trail_update(int, int, double);
  63. void	trail_update_and_reset_delta_trail();
  64. void	unused_position_reset();
  65. void	unused_position_used(int);
  66. double	caculate_transition_probability(int, int, int);
  67.  
  68. int main(int argc, char* argv[])
  69. {
  70. 	srand( (unsigned)time(NULL) );
  71.  
  72. 	NcMax = 100;
  73. 	tau=0.0;
  74. 	Q=100.0;					// not sure what data to set
  75. 	alpha = 0.1;
  76. 	beta = 2;
  77. 	rho = 0.9;
  78.  
  79. 	edge_weight_type = 2;
  80. 	dimension = 51;	dataset_name = "tsp51.txt";
  81. 	sum_ant = dimension;
  82.  
  83. 	run();
  84.  
  85. 	cout << "End of the Ant optimization." << endl;
  86. 	system("pause");
  87. 	return 0;
  88. }
  89.  
  90. void run(){
  91. 	init();
  92. 	read_file(dataset_name);
  93. 	caculate_distance();
  94. 	ant_system();
  95. }
  96.  
  97. void init(){
  98. 	ant_position.assign(sum_ant, i1d(dimension+1, 0));			/*need go to start at end of the trip*/
  99. 	shortest_tour.assign(dimension+1, 0);
  100. 	tabu.assign(sum_ant, b1d(dimension, true));
  101. 	trail.assign(dimension, d1d(dimension, tau));				/*	trail[i][j]	j>=i	*/
  102. 	delta_trail.assign(dimension, d1d(dimension, 0.0));			/*	delta_trail[i][j]	j>=i	*/
  103. 	locationXY.assign(dimension, d1d(edge_weight_type, 0.0));
  104. 	distanceXY.assign(dimension, d1d(dimension, 0.0));			/*	distanceXY[i][j]	j>=i*/
  105. 	transportation_probability.assign(sum_ant, d1d(dimension, 0.0));
  106. 	unused_position.assign(dimension, 0);
  107. 	for(int i=0; i<dimension; i++)	unused_position[i] = i;
  108. }
  109.  
  110. void ant_system(){
  111. 	first_trip();
  112.  
  113. 	do{
  114. 		trail_update_and_reset_delta_trail();
  115. 		Nc++;
  116.  
  117. 		unused_position_reset();
  118.  
  119. 		int this_position , next_position;
  120.  
  121. 		for(int k=0; k<sum_ant; k++){		//k is index of ant
  122. 			unused_position_reset();
  123. 			this_position = random(dimension-1);
  124.  
  125. 			ant_position[k][0] = this_position;
  126. 			unused_position_used(this_position);
  127.  
  128. 			for(int s=1; s<dimension; s++){			//s is index of tabu, is number of cities
  129. 				double q;
  130. 				do{
  131. 					//if q=1.0 , r will be something wrong
  132. 					q = random(1.0);
  133. 				}while(q==1.0);
  134. 				int i = 0;
  135. 				double r = caculate_transition_probability(this_position, unused_position[i], k);;
  136.  
  137. 				while( r<q && i<unused_position.size() ){
  138. 					i++;
  139. 					double p = caculate_transition_probability(this_position, unused_position[i], k);
  140. 					r += p;
  141. 				}
  142. 				next_position = unused_position[i];
  143.  
  144. 				unused_position_used(next_position);
  145. 				ant_position[k][s] = next_position;
  146. 				this_position = next_position;
  147. 			}
  148. 		}
  149. 	}while(Nc<NcMax);
  150.  
  151. }
  152.  
  153. void first_trip(){
  154. 	int next_position;
  155. 	/*Place the k ants on the s nodes, first time all ants walk randomly without repeat city*/
  156. 	for(int k=0; k<sum_ant; k++){		/*k is index of ant*/
  157. 		unused_position_reset();
  158. 		for(int s=0; s<dimension; s++){			/*s is index of tabu, is number of cities*/
  159. 			next_position = unused_position[ random( (int)unused_position.size() - 1 ) ];
  160. 			unused_position_used(next_position);
  161.  
  162. 			ant_position[k][s] = next_position;
  163. 		}
  164. 	}
  165. 	Nc++;
  166. }
  167.  
  168. void trail_update_and_reset_delta_trail(){
  169. 	for(int k=0; k<sum_ant; k++){								/*k is the index of ant*/
  170. 		ant_position[k][dimension] = ant_position[k][0];		/*set last position equal to first position*/
  171.  
  172. 		double distance=0.0;
  173.  
  174. 		for(int s=0; s<dimension; s++)
  175. 			distance += get_distance(ant_position[k][s], ant_position[k][s+1]);
  176. 		for(int s=0; s<dimension; s++){
  177. 			delta_trail_update(ant_position[k][s], ant_position[k][s+1], distance);
  178. 		}
  179.  
  180.  		if(shortest_distance>distance){
  181. 			shortest_distance = distance;
  182. 			shortest_tour.assign(ant_position[k].begin(), ant_position[k].end());
  183. 			cout << "NO." << Nc << " ant= "<< k << "\tshortest_distance = " << shortest_distance << endl;
  184.  
  185. 			/* This shown the optimal position  
  186. 			for(int i=0; i<dimension; i++){
  187. 				cout << ant_position[k][i] << " ";
  188. 			}
  189. 			cout << endl;
  190. 			/* End of shown the optimal position  */
  191. 		}
  192. 	}
  193.  
  194. 	//
  195. 	for(int i=0; i<distanceXY.size(); i++){
  196. 		for(int j=i; j<distanceXY.size(); j++){
  197. 			trail[i][j]  = trail[i][j]*rho + delta_trail[i][j];
  198. 			delta_trail[i][j] = 0.0;				
  199. 		}
  200. 	}
  201. }
  202.  
  203. double caculate_transition_probability(int this_position, int next_position, int k){
  204. 	double p, q=0.0;
  205.  
  206. 	p  = pow( get_trail(this_position, next_position), alpha );
  207. 	p *= pow( 1/get_distance(this_position, next_position), beta );
  208. 	for(int j=0; j<(int)unused_position.size(); j++){
  209. 		q += ( pow( get_trail(this_position, unused_position[j]), alpha ) * pow( 1/get_distance(this_position, unused_position[j]), beta ) );
  210. 	}
  211. 	return p/q;
  212. }
  213.  
  214. void delta_trail_update(int i, int j, double d){
  215. 	if(i>j)	delta_trail[j][i] += Q/d;
  216. 	else	delta_trail[i][j] += Q/d;
  217. }
  218.  
  219. void unused_position_reset(){
  220. 	unused_position.assign(dimension, 0);
  221. 	for(int i=0; i<dimension; i++)	unused_position[i] = i;
  222. }
  223.  
  224. void unused_position_used(int position){
  225. 	vector<int>::iterator pos;
  226. 	pos = find(unused_position.begin(), unused_position.end(), position);
  227. 	unused_position.erase(pos);
  228. }
  229.  
  230. int random(int low, int up){						/*	low<=random(low,up)<=up	*/
  231. 	if(low>up)	swap(low,up);						/*		0<=random(a)<=a		*/
  232. 	return rand() % (up - low + 1) + low ;
  233. }
  234.  
  235. double random(double low, double up){ 				/* low<=random(low,up)<=up	*/
  236. 	if(up<low)	swap(low,up);						/*		0<=random(a)<=a		*/
  237. 	return (up - low) * rand() / (RAND_MAX ) + low;
  238. }
  239.  
  240. void read_file(string filename){
  241. //	http://w...content-available-to-author-only...s.com/doc/tutorial/files/
  242. 	int count = 0;
  243. 	string line;
  244. 	ifstream myfile (filename.c_str());
  245. 	if (myfile.is_open()){
  246. 		while ( getline (myfile,line) ){
  247. 			file_context_analyse(line, count);
  248. 			count++;
  249. 		}
  250. 		myfile.close();
  251. 	}else{
  252. 		cout << "Read file error. Please check again." << endl;
  253. 		exit(1);
  254. 	}
  255. }
  256.  
  257. void write_file(string filename, string context){
  258. 	ofstream myfile (filename.c_str());
  259. 	if (myfile.is_open()){
  260. 		myfile << context;
  261. 		myfile.close();
  262. 	}else {
  263. 		cout << "Unable to open file" << endl;
  264. 		exit(1);
  265. 	}
  266. }
  267.  
  268. void file_context_analyse(string str, int count){
  269. 	istringstream ss(str);
  270.     istream_iterator<double> begin(ss), end;
  271.  
  272.     //putting all the tokens in the vector
  273.     d1d arrayTokens(begin, end);
  274.  
  275. 	/*check the dimension is as same as file*/
  276.     if(edge_weight_type!=arrayTokens.size()){
  277.     	cout << "Dimension setting error, Please check again." << endl;
  278.     	exit(1);
  279. 	}
  280.  
  281.     /*Save context to locationXY*/
  282.     for(int i=0; i<arrayTokens.size(); i++){
  283.     	locationXY[count][i] = arrayTokens[i];
  284. 	}
  285. }
  286.  
  287. double Euclidean_distance(d1d location1, d1d location2){
  288. 	//https://e...content-available-to-author-only...a.org/wiki/Euclidean_distance
  289. 	double d=0.0;
  290. 	for(int i=0; i<location1.size(); i++){
  291. 		d += (pow(location1[i]-location2[i],2));
  292. 	}
  293. 	return sqrt(d);
  294. }
  295.  
  296. void caculate_distance(){
  297. 	for(int i=0; i<locationXY.size(); i++){
  298. 		for(int j=i; j<locationXY.size(); j++){
  299. 			if(i==j){
  300. 				distanceXY[i][j] = 0;
  301. 			}else{
  302. 				distanceXY[i][j] = Euclidean_distance(locationXY[i], locationXY[j]);
  303. 			}
  304. 		}
  305. 	}
  306. }
  307.  
  308. double get_distance(int i, int j){
  309. 	if(i>j)	/*swap(i, j);*/ return( distanceXY[j][i] );
  310. 	else return( distanceXY[i][j] );
  311. }
  312.  
  313. double get_trail(int i, int j){
  314. 	if(i>j)	/*swap(i, j);*/ return( trail[j][i] );
  315. 	else return( trail[i][j] );
  316. }
  317.  
Runtime error #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Read file error. Please check again.
https://ideone.com/5UpRnQ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!