ant1.cpp

利用蚂蚁算法解决TSP旅行商问题

#include <iostream>
#include <fstream>
#include <math.h>
#include <time.h> 
using namespace std;


const int iAntCount=34;//      ant numbers
const int iNodeCount=20;
const int iItCount=200;//      rounds
const double Q=1000;//         constant
const double alpha=1;//        路径轨迹相对重要性
const double beta=2;//         路径可见度相对重要性
const double rou=0.8;//        轨迹持久性


int bestroute[iNodeCount];// 输出的最佳路径

double  rnd(int low,double uper)//random between low and double
{
 double p=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);

 return (p);
};

int rnd(int uper)//random from uper
{
 return (rand()%uper);
};


class TopoInfo//topology
{
public:
	double Connect[iNodeCount][iNodeCount];
	double m_dDeltTrial[iNodeCount][iNodeCount];
	double m_dTrial[iNodeCount][iNodeCount];
	double LoadTraffic[iNodeCount][iNodeCount];
	double distance[iNodeCount][iNodeCount];
};
TopoInfo Map;


class ant//ant
{
private:
	int ChooseNextNode();
	double prob[iNodeCount];
	int m_iNodeCount;
	int AllowedNode[iNodeCount];
public:
	int SNode;
	int DNode;
	void AddNode(int node);
	int tabu[iNodeCount];
	void Clear();
	void UpdateResult();
	double m_dLength;
	double m_dShortest;
	void move();
	ant();
	void move2last();
};


void ant::move2last()
{
    int i;
    for(i=0;i<iNodeCount;i++)
		if(AllowedNode[i]==1)
		{
			AddNode(i);
			break;
		}
}

void ant::Clear()
{
	m_dLength=0;
	int i;
	for(i=0;i<iNodeCount;i++)
	{
		prob[i]=0;
		AllowedNode[i]=1;
	}
	i=19;    //fist node
	m_iNodeCount=0;
	AddNode(i);
}

ant::ant()
	{
		m_dLength=m_dShortest=0;
		m_iNodeCount=0;
		int i;
		for(i=0;i<iNodeCount;i++)
		{
			AllowedNode[i]=1;
			prob[i]=0;
		}
	}

void ant::AddNode(int node)//add Node to tuba;
{
	
	tabu[m_iNodeCount]=node;
	m_iNodeCount++;
	AllowedNode[node]=0;
	//cout<<tabu[m_iNodeCount-1]<<m_iNodeCount<<AllowedNode[node]<<endl;//test1
	
}

int ant::ChooseNextNode()//返回一个最低的值
{
//Update the probability of path selection
//select a path from tabu[m_iCityCount-1] to next

	int i;
	int j=2000;
	double temp=0;
	int curNode=tabu[m_iNodeCount-1];
	for(i=0;i<iNodeCount;i++)
	{
		
		if((AllowedNode[i]==1))
		{
			temp+=pow((1.0/Map.distance[curNode][i]),beta)*pow((Map.m_dTrial[curNode][i]),alpha);
		}
	}
double sel=0;
for(i=0;i<iNodeCount;i++)
{
	if((AllowedNode[i]==1))
	{
		prob[i]=pow((1.0/Map.distance[curNode][i]),beta)*pow((Map.m_dTrial[curNode][i]),alpha)/temp;
		sel+=prob[i];
	}
	else
		prob[i]=0;
}
double mRate=rnd(0,sel);
double mSelect=0;

for(i=0;i<iNodeCount;i++)
{
	if((AllowedNode[i]==1))
		mSelect+=prob[i];
	if(mSelect>=mRate) {j=i;break;}
}
if (j==2000)
{
  temp=-1;
  for(i=0;i<iNodeCount;i++)
  { 
   if((AllowedNode[i]==1))
	   if(temp<pow((1.0/Map.distance[curNode][i]),beta)*pow((Map.m_dTrial[curNode][i]),alpha))
		   {
		   temp=pow((1.0/Map.distance[curNode][i]),beta)*pow((Map.m_dTrial[curNode][i]),alpha);
		   j=i;
	   }
	   }
}

return j;

}

void ant::UpdateResult()
{
 // Update the length of Routing
 int i;
 for(i=0;i<iNodeCount-1;i++)
	 m_dLength+=Map.distance[tabu[i]][tabu[i+1]];
    // m_dLength+=Map.distance[tabu[iNodeCount-1]][tabu[0]];//TSP问题时路程是个圈，所以加上这个值
}
void ant::move()
{
 //the ant move to next town and add town ID to tabu.
 int j;
 j=ChooseNextNode();
 if (j==0)
 {
	 AddNode(j);
	 for(int i=0;i<iNodeCount;i++){
		 AllowedNode[i]=0;}
 
 }
 else
	 AddNode(j);
}

class project
{
public:
	int SNode;
	int DNode;
	int m_iNodeCount;
	void UpdateTrial();
	double m_dLength;
	void initmap();
	ant ants[iAntCount];
	void GetAnt();
	void StartSearch();
	project();
};

void project::UpdateTrial()
{
	//calculate the changes of trial information
	int i;
	int j;
	
	for (i=0;i<iAntCount;i++)
	{
		for(j=0;j<iNodeCount-1;j++)
		{
			Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength;
			Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength;
		}
		Map.m_dDeltTrial[ants[i].tabu[iNodeCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength;
	//	Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iNodeCount-1]]+=Q/ants[i].m_dLength;
	}

	for (i=0;i<iNodeCount;i++)
	{
		for(j=0;j<iNodeCount;j++)
		{
			Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j]);
			//Map.m_dDeltTrial[i][j]=0;
		}
	}
}

void project::initmap()
{
 int i;
 int j;
 for(i=0;i<iNodeCount;i++)
	 for(j=0;j<iNodeCount;j++)
	 {
		 Map.m_dTrial[i][j]=1;
		 Map.m_dDeltTrial[i][j]=0;
	 }
}

project::project()
{
 //initial map,read map infomation from file . et.
	initmap();
	m_dLength=10e9;

ifstream in("c:\\distance1.txt");
 
 
 
 for (int i=0;i<iNodeCount;i++)
	 { for (int j=0;j<iNodeCount;j++)
	
 {
	 in>>Map.distance[i][j];
	 //cout<<Map.distance[i][j]<<endl;
	 bestroute[i]=0;
 }
	 }

 


}


void project::GetAnt()
{


/*input the Source and the Destination
	cout<<"Print the SourceNode"<<endl;
	cin>>SNode;
	cout<<"Print the DestinationNode"<<endl;
	cin>>DNode;
*/
 //randomly put ant into map
    int i=0;
	int Node;
  srand( (unsigned)time( NULL ) +rand());
	for (i=0;i<iAntCount;i++)
	{
		
	
		Node=19;
	   // Node=rnd(iNodeCount);//put a random ant to a random node
		ants[i].AddNode(Node);
	}
}

void project::StartSearch()
{
 //begin to find best solution
	int max=0;//every ant tours times
	int i;
	int j;
	double temp;
	int temproute[iNodeCount];
	while (max<iItCount)
	{
		for(j=0;j<iAntCount;j++)//任一蚂蚁
		{
			for (i=0;i<iNodeCount-1;i++)
				ants[j].move();
		}
		for(j=0;j<iAntCount;j++)
		{
			ants[j].move2last();
			ants[j].UpdateResult ();
		}

 //find out the best solution of the step and put it into temp
	 int t;
	 temp=ants[0].m_dLength;
	 for (t=0;t<iNodeCount;t++)
		 temproute[t]=ants[0].tabu[t];
	 	 for(j=0;j<iAntCount;j++)
	 {
		 if (temp>ants[j].m_dLength)
		 {
			 temp=ants[j].m_dLength;
			 for ( t=0;t<iNodeCount;t++)
				 temproute[t]=ants[j].tabu[t];
		 }
	 

	 if(temp<m_dLength){
		 m_dLength=temp;
		 for ( t=0;t<iNodeCount;t++)
			 bestroute[t]=temproute[t];  //最佳路径最终版
	 }}
	 printf("%d : %f\n",max,m_dLength);
	 UpdateTrial();//每次产生的最佳路径才能修改路径的信息浓度
	 
	 for(j=0;j<iAntCount;j++)
		 ants[j].Clear();
	 max++;
 }

 printf("The shortest route is : %f\n",m_dLength);

 for ( int t=0;t<iNodeCount;t++)
	 printf(" %d ",bestroute[t]);//输出最佳路径
}



int main()
{

	project Route;
    Route.GetAnt();
	Route.StartSearch();
	return 0;
}