antcycle.cpp

蚁群算法经典TSP模型

#pragma warning(disable:4786)
#include <map>
#include <vector>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;

//该版本是采用大量STL数据结构实现的速度比较慢



map<pair<size_t,size_t > ,double>preInfo;// 先验信息---距离信息
map<pair<size_t ,size_t > ,double >posInfo;//信息素浓度信息

int main()
{
	
	const size_t NUMOFCITY(30);//和问题的规模有关
	size_t NUMOFANT;
	double city[NUMOFCITY][2];//位置坐标矩阵
	map<pair<size_t,size_t > ,double>dis;//距离矩阵
	map<size_t,vector<size_t> >tabu;
	map<size_t,double>pathAnt;//蚂蚁的某次循环总路径长度
	map<pair<size_t ,size_t > ,double >tempInfo;//某次循环中ij边的增加信息
	
	double alphaV,beta;//
	double p;//消散系数
	double Q;//
	size_t NCMAX;
	cout<<"初始化参数 :"<<endl;
	cout<<"输出蚂蚁的个数m:"<<ends;cin>>NUMOFANT;
	cout<<"信息素影响因子alpha:"<<ends;cin>>alphaV;
	cout<<"先验信息影响因子beta:"<<ends;cin>>beta;
	cout<<"残留系数p:"<<ends;cin>>p;
	cout<<"常量Q"<<ends;cin>>Q;
	cout<<"要循环的最大次数"<<ends;cin>>NCMAX;

	
	size_t NC(0);//循环次数
	const double c=1;//初始个边的信息素浓度------
	
	ifstream infile("oliver30Tsp.dat",ios::in);
	if (!infile)
	{
		cerr<<"数据文件无法打开";
		return -1;
	}
	double x,y,z;
	size_t i(0);
	while(infile>>x>>y>>z)
	{
		city[i][0]=y;
		city[i][1]=z;	
		++i;
	}
	
	for(i=0;i!=NUMOFCITY;++i)
		for(size_t j=(0);j!=NUMOFCITY;++j)
		{
			dis[make_pair(i,j)]=
				sqrt(pow((city[i][0]-city[j][0]),2.0)+pow((city[i][1]-city[j][1]),2.0));
			preInfo[make_pair(i,j)]=1.0/dis[make_pair(i,j)];
			posInfo[make_pair(i,j)]=c;
			tempInfo[make_pair(i,j)]=0.0;
		}
	for(i=0;i!=NUMOFANT;++i)
	{
		tabu[i].reserve(NUMOFCITY);
		tabu[i].push_back(i);//相当于初始时 蚂蚁i在i城
		pathAnt[i]=0.0;
	}
	//////////////////////////////////////////////////////////////////////////
/*	string fileName;
	cout<<"输入存储的文件名 最好和参数有关"<<endl;
	cin>>fileName;
	fileName+=".txt";
	ofstream outfile(fileName.c_str(),ios::out);
	outfile<<"蚂蚁的个数m:"<<NUMOFANT<<endl;
	outfile<<"信息素影响因子alpha:"<<alphaV<<endl;
	outfile<<"先验信息影响因子beta:"<<beta<<endl;
	outfile<<"残留系数p:"<<p<<endl;
	outfile<<"常量Q"<<Q<<endl;
	outfile<<"要循环的最大次数"<<NCMAX<<endl;*/
	bool AntInRoute(const size_t &i,const size_t &j,
		const vector<size_t>::const_iterator & first,
		const vector<size_t>::const_iterator & last);

	double probTrans(const double & pos,const double & alphaV,
		const double & pre,const double & beta);
	double probTransSum(const vector <size_t > &,
		const size_t & curCity,const double & alphaV,const double & beta );
	double shortestPathFinal(100000.0);
	do
	{
		cout<<"第"<<++NC<<"次循环"<<endl;
		size_t t(0);//步数
		srand(unsigned(time(0))); //产生不同的种子----------不写则产生相同的种子
		for(i=0;i!=NUMOFCITY-1;++i)//i表示本循环的步数 一共是NUMOFCITY-1个
			{
			//time(0)返回当前的时间
			for(size_t k(0);k!=NUMOFANT;++k)
				{
					size_t currCity(*(tabu[k].end()-1));
					double sumAvalible=probTransSum(tabu[k],currCity,alphaV,beta);
					double pAccumlate=0.0;
					double pRand=rand()/(double)RAND_MAX; //产生随机概率-每个蚂蚁的概率不同
					size_t tempJ(0);
					for (size_t j=0;j!=NUMOFCITY;++j)
					{			
						if (tabu[k].end()==find(tabu[k].begin(),tabu[k].end(),j))
						{
							pAccumlate+=probTrans(posInfo[make_pair(currCity,j)],alphaV,
								preInfo[make_pair(currCity,j)],beta)/sumAvalible;
							if (pRand<=pAccumlate)
							{
								tempJ=j; break;
								
							}

						}
					}
					tabu[k].push_back(tempJ);
				}
			}
	
		// 计算每个蚂蚁的路径
		double shortestPathEach(0);
		for(i=0;i!=NUMOFANT;++i)
		{
			for(size_t j=0;j!=NUMOFCITY-1;++j)
			{
				pathAnt[i]+=dis[make_pair(tabu[i].at(j),tabu[i].at(j+1))];
			}
			pathAnt[i]+=dis[make_pair(tabu[i].back(),tabu[i].front())];
	//		cout<<"蚂蚁"<<i<<"的路径长度:"<<pathAnt[i]<<endl;
		//	outfile<<"蚂蚁"<<i<<"的路径长度:"<<pathAnt[i]<<ends;
			
	//		cout<<"蚂蚁"<<i<<"的路线图:"<<ends;
	//		outfile<<"蚂蚁"<<i<<"的路线图:"<<ends;
		/*	for(j=0;j!=tabu[i].size();++j)
			{
				cout<<tabu[i].at(j)<<" ";
//				outfile<<tabu[i].at(j)<<" ";
			}*/
		//	cout<<endl;
	//		outfile<<endl;
		}
		// 计算最短路径
		shortestPathEach=pathAnt[0];
		for(i=1;i!=NUMOFANT;++i)
			if(pathAnt[i]<shortestPathEach)
				shortestPathEach=pathAnt[i];
			cout<<"该次循环最短路径"<<shortestPathEach<<endl;
	//		outfile<<"该次循环最短路径"<<shortestPathEach<<endl;
		if (shortestPathEach<shortestPathFinal)
		{
			shortestPathFinal=shortestPathEach;
		}
		cout<<"截至本次循环 总的最短路径"<<shortestPathFinal<<endl;
//		outfile<<"截至本次循环 最短路径"<<shortestPathFinal<<endl;

	
		//更新信息素
		for(i=0;i!=NUMOFCITY;++i)
			for(size_t j=i+1;j!=NUMOFCITY;++j)
			{//对于每一条路径 每一只蚂蚁
				for(size_t k(0);k!=NUMOFANT;++k)
				{
					if(AntInRoute(i,j,tabu[k].begin(),tabu[k].end()))
					{//判断时候ij边或ji边出现在禁忌表中
						//此时凡是经过ij或ji边的信息素进行累加
						tempInfo[make_pair(i,j)]+=(Q*1.0)/pathAnt[k];
					}
				}
				tempInfo[make_pair(j,i)]=tempInfo[make_pair(i,j)];
				//开始更新该ij边的信息素
				posInfo[make_pair(i,j)]
					=p*posInfo[make_pair(i,j)]+tempInfo[make_pair(i,j)];
		//		cout<<"更新后ij边"<<posInfo[make_pair(i,j)]<<" ";
				posInfo[make_pair(j,i)]=posInfo[make_pair(i,j)];
			}


		for(i=0;i!=NUMOFCITY;++i)
			for(size_t j=0;j!=NUMOFCITY;++j)
			{
				tempInfo[make_pair(i,j)]=0;
			}
		//清空禁忌表---放到循环开始 以便于在while判断语句中可以提取该信息
		for(i=0;i!=NUMOFANT;++i)
		{//相关状态复原 
			tabu[i].clear();
			tabu[i].push_back(i);//蚂蚁归位
			pathAnt[i]=0.0;//此时要进行下一次循环 所以路径必须清空
		}

	}
	while(NC!=NCMAX);
	return 0;
	//重新循环 直到所有蚂蚁的禁忌表相同或者达到循环次数
}

double probTrans(const double & pos,const double & alphaV,
				 const double & pre,const double & beta)
{
	return (pow(pos,alphaV)*pow(pre,beta));
}

bool AntInRoute(const size_t & i,const  size_t & j,
				const vector<size_t>::const_iterator & first,
				const vector<size_t>::const_iterator & last)
{//判断ij或ji是否连续的出现在由first last指向的序列中
	vector<size_t>::const_iterator iter(first);
	for(;iter!=last-1;++iter)
	{
		if( (*iter==i&&*(iter+1)==j)
			|| (*iter==j&&*(iter+1)==i) )
			break;
	}
	if(iter!=last-1)
		return true;
	return false;
}

double probTransSum(const vector <size_t > & tabu,const size_t & curCity,
					const double & alphaV,const  double & beta )
{
	double sum(0.0);
	for (size_t i(0);i!=30;++i)
	{
		if (tabu.end()==find(tabu.begin(),tabu.end(),i))
		{
			sum+=probTrans(posInfo[make_pair(curCity,i)],alphaV,
				preInfo[make_pair(curCity,i)],beta);
		}
	}
	return sum;
}