ant.cpp

本程序利用蚂蚁算法解决TSP（旅行商问题）问题

#include <iostream.h>  
#include <fstream.h>  
#include <math.h>  
#include <time.h> 
#include <stdlib.h>  

#define N 31 //city size  
#define M 31 //ant number  

double inittao=1;   //初始信息素数量
double tao[N][N];  //两个城市间的信息素数量
double detatao[N][N];  //两个城市间的信息素增加量
double distance[N][N]; //表示任何两个城市之间的距离 
double yita[N][N];  //路径的启发信息=1/distance
int tabu[M][N];  //标志第M个蚂蚁是否经过第N个城市
int route[M][N]; //记录每个蚂蚁的路径 
double solution[M];  //记录每个蚂蚁的一次路径长度
int BestRoute[N];  //记录最优路径
double BestSolution=10000000000;  //初始化最优路径长度
double alfa,beta,rou,Q;  //常数
int NcMax;  //循环次数
void initparameter(void); // initialize the parameters of basic ACA 
double EvalueSolution(int *a); // evaluate the solution of TSP, and calculate the length of path 
void InCityXY( double x[], double y[], char *infile ); // input the nodes' coordinates of TSP 



void main()  
{
	int NC=0;  //循环变量(0-NcMax) 
	initparameter();  
	double x[N];  
	double y[N];
	InCityXY( x, y, "city31.txt" );  

	for(int i=0;i<N;i++)  
		for(int j=i+1;j<N;j++)
		{ 
			distance[j][i]=sqrt(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2));
			distance[i][j]=distance[j][i];
		}  
// calculate the heuristic parameters 
//初始化环境
		for(i=0;i<N;i++)
			for(int j=0;j<N;j++)
			{
				tao[i][j]=inittao; 
				if(j!=i)  
					yita[i][j]=1/distance[i][j];  
			}  
 //初始化位置标志
			for(int k=0;k<M;k++)  
				for(i=0;i<N;i++)  
					route[k][i]=-1;//表示所有蚂蚁没有去过任何城市 

				
				for(k=0;k<M;k++)  
				{  
					route[k][0]=k%N;//初始化每只蚂蚁的位置（城市）
					tabu[k][route[k][0]]=1; //初始化路径标志（未经过某个城市标志为0，经过某个城市标志为1）
				}  

//each ant try to find the optiamal path 
				srand(time(NULL)); 
				do {  
					int s=1;  
					double partsum;  
					double pper;  
					double drand;
					
//ant choose one whole path 
					while(s<N) 
					{  
						for(k=0;k<M;k++) 
						{  
							drand=rand()/((RAND_MAX+1)*1.0);//(产生（0，1）之间的均匀分布的随机数)
// 							int jrand=rand()%3000;
// 							drand=jrand/3000.;  
							partsum=0;  
							pper=0;  
							for(int j=0;j<N;j++)
							{  
								if(tabu[k][j]==0) 
									partsum+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta);
							}  
							for(j=0;j<N;j++)
							{  
								if(tabu[k][j]==0)  
									pper+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta)/partsum;  
								if(pper>drand)  
									break;  
							}  
							tabu[k][j]=1;  
							route[k][s]=j;
						}  
						s++;  
					}  
// the pheromone is updated 
					for(i=0;i<N;i++)  
						for(int j=0;j<N;j++)
							detatao[i][j]=0; 
						for(k=0;k<M;k++) 
						{ 
							solution[k]=EvalueSolution(route[k]); //求第k个蚂蚁的总路程 
							if(solution[k]<BestSolution)  
							{  
								BestSolution=solution[k];
								for(s=0;s<N;s++)  
									BestRoute[s]=route[k][s];
							}  
						} 
						for(k=0;k<M;k++) //同一个蚂蚁走过的路径上的信息素增加量相同
						{  
							for(s=0;s<N-1;s++) 
								detatao[route[k][s]][route[k][s+1]]+=Q/solution[k];
							detatao[route[k][N-1]][route[k][0]]+=Q/solution[k]; 
						}  
						for(i=0;i<N;i++)  
							for(int j=0;j<N;j++)  
							{  
								tao[i][j]=rou*tao[i][j]+detatao[i][j];
								if(tao[i][j]<0.00001)  
									tao[i][j]=0.00001; 
								if(tao[i][j]>20)  
									tao[i][j]=20; 
							}  
							for(k=0;k<M;k++)  
								for(int j=1;j<N;j++)  
								{  
									tabu[k][route[k][j]]=0; 
									route[k][j]=-1;  
								}  
								NC++;  
				} 
				while(NC<NcMax);  
//output the calculating results 
				fstream result;  
				result.open("optimal_results.log", ios::app);
				if(!result)  
				{  
					cout<<"can't open the <optimal_results.log> file!\n"; 
					exit(0);  
				}  
				result<<"*-------------------------------------------------------------------------*"<<endl;  
				result<<"the initialized parameters of ACA are as follows:"<<endl;  
				result<<"alfa="<<alfa<<", beta="<<beta<<", rou="<<rou<<", Q="<<Q<<endl;  
				result<<"the maximum iteration number of ACA is:"<<NcMax<<endl;  
				result<<"the shortest length of the path is:"<<BestSolution<<endl;  
				result<<"the best route is:"<<endl; 
				for(i=0;i<N;i++)  
					result<<BestRoute[i]<<" "; 
				result<<endl;  
				result<<"*-------------------------------------------------------------------------*"<<endl<<endl; 
				result.close();  
				cout<<"the shortest length of the path is:"<<BestSolution<<endl;  
}  

void initparameter(void) 
{
	alfa=1; beta=5; rou=0.9; Q=100; //alfa、beta是决定信息素和启发信息的权,rou是信息素的挥发率,Q为一正的常数
	NcMax=200; 
} 


double EvalueSolution(int *a)  
{  
	double dist=0;  
	for(int i=0;i<N-1;i++)  
		dist+=distance[a[i]][a[i+1]]; 
	dist+=distance[a[i]][a[0]]; 
	return dist;  
}  


void InCityXY( double x[], double y[], char *infile )  
{  
	fstream inxyfile( infile, ios::in | ios::nocreate ); 
	if( !inxyfile )  
	{  
		cout<<"can't open the <"<<infile<<"> file!\n"; 
		exit(0); 
	}  
	int i=0; 
	while( !inxyfile.eof() ) //判断是否到了文件尾部
	{ 
		inxyfile>>x[i]>>y[i]; 
		if( ++i >= N ) 
			break; 
	} 
}