stdafx.cpp

在vc集成环境下实现基于蚂蚁的算法的机器人路径规划

// stdafx.cpp : source file that includes just the standard includes
//	AntAco.pch will be the pre-compiled header
//	stdafx.obj will contain the pre-compiled type information

#include "stdafx.h"

fstream solvefile;
GInfo Map; 
 double alpha=1; 
 double beta=1; 
double rou=0.5; 
int iItCount=1000;

void CAnt::move2last() 
{ 
	int i; 
	for(i=0;i<iCityCount;i++) 
		if (AllowedCity[i]==1) 
		{ 
			addcity(i); 
			break; 
		} 
} 

void CAnt::Clear() 
{ 
	m_dLength=0; 
	int i; 
	for(i=0;i<iCityCount;i++) 
	{ 
		prob[i]=0; 
		AllowedCity[i]=1; 
	} 
	i=tabu[iCityCount-1]; 
	m_iCityCount=0; 
	addcity(i); 
} 

CAnt::CAnt() 
{ 
	m_dLength=m_dShortest=10000; 
	m_iCityCount=0; 
	int i; 
	for(i=0;i<iCityCount;i++) 
	{ 
		AllowedCity[i]=1; 
		prob[i]=0; 
	} 
/*	for(int j=0;j<iCityCount;j++)
		for(int k=0;k<iCityCount;k++)
		{
			m_dDeltTrial[j][k]=0; 
			m_dTrial[j][k]=0; 
			distance[j][k]=0; 
			counter[j][k]=0;
		}
*/
} 

void CAnt::addcity(int city) 
{ 
	//add city to tabu; 
	tabu[m_iCityCount]=city; 
	m_iCityCount++; 
	AllowedCity[city]=0; 
} 

int CAnt::ChooseNextCity() 
{ 
	//Update the probability of path selection 
	//select a path from tabu[m_iCityCount-1] to next 
	int i; 
	int j=10000; 
	double temp=0; 
	int curCity=tabu[m_iCityCount-1]; 
	for (i=0;i<iCityCount;i++) 
	{ 
		if((AllowedCity[i]==1))  
		{ 
			temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha); 
		} 
	} 
	double sel=0; 
	for (i=0;i<iCityCount;i++) 
	{   
		if((AllowedCity[i]==1)) 
		{ 
			prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp; 
			sel+=prob[i]; 
		} 
		else  
			prob[i]=0; 
	} 

	double mRate=rnd(0,sel); //轮赌法
	double mSelect=0; 
	for (i=0;i<iCityCount;i++) 
	{ 
		if((AllowedCity[i]==1)) 
			mSelect+=prob[i] ; 
		if (mSelect>=mRate) {j=i;break;} 
	} 

/*	
	int count=0;
	int cc[iCityCount];
	for(i=0;i<iCityCount;i++)
	{
		if((AllowedCity[i]==1)) 
		{
			cc[count]=i;
			count++;
		}
	}

	j=cc[(int)rnd(0,count-1)];
*/
/*    double p=0;int K=0;
	for (i=0;i<iCityCount;i++) 
	{ 
		if((AllowedCity[i]==1)) 
		{
			if(p<prob[i])
			{
				K=i;
				p=prob[i];
			}
		} 
	}
	if(p!=0)
		return K;
*/
	
	if (j==10000) //信息素最大的路径
	{ 
		temp=-1; 
		for (i=0;i<iCityCount;i++) 
		{  
			if((AllowedCity[i]==1)) 
				if (temp<pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha))      
				{ 
					temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha); 
					j=i; 
				} 
		} 
	} 
	return j; 
} 

void CAnt::move() 
{ 
	//the CAnt move to next town and add town ID to tabu. 
	int j; 
	j=ChooseNextCity(); 
	addcity(j); 
} 

void CAnt::UpdateResult() 
{ 
	// Update the length of tour 
	int i; 
	for(i=0;i<iCityCount-1;i++) 
	{
		m_dLength+=Map.distance[tabu[i]][tabu[i+1]]; 
	}   
	m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]]; 

	for(i=0;i<iCityCount-1;i++)          //计算路线被走过的次数
	{
		Map.counter[tabu[i]][tabu[i+1]]++;
	}
	Map.counter[tabu[iCityCount-1]][tabu[0]]++;
} 
///////////////////////////////////////////////////////////////////////////////////
CResearcher::CResearcher() 
{ 
	//initial map,read map infomation from file . et. 
	topY=leftX=rightX=bottomY=0;
}

void CResearcher::LoadFile()
{
	ifstream in("tsp.txt");
	if(in.is_open()!=1) cout<<"open file error"<<'\n';
	
	struct city 
	{ 
		int num; 
		double  x; 
		double  y; 
	}cc[iCityCount]; 
	
	for (int i=0;i<iCityCount;i++) 
	{ 
		in>>cc[i].num>>cc[i].x>>cc[i].y; 
		Map.m_CityPos[i][0]=cc[i].x;
		Map.m_CityPos[i][1]=cc[i].y;
		besttour[i]=0; 
	} 
	leftX=Map.m_CityPos[0][0];
	rightX=Map.m_CityPos[0][0];
	topY=Map.m_CityPos[0][1];
	bottomY=Map.m_CityPos[0][1];

	int j; 
	for(i=0;i<iCityCount;i++) 
	{
		for (j=0;j<iCityCount;j++) 
		{ 
			Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2)); 
		}
		if(leftX>Map.m_CityPos[i][0])   leftX=Map.m_CityPos[i][0];
		if(rightX<Map.m_CityPos[i][0])  rightX=Map.m_CityPos[i][0];
		if(bottomY>Map.m_CityPos[i][1]) bottomY=Map.m_CityPos[i][1];
		if(topY<Map.m_CityPos[i][1])    topY=Map.m_CityPos[i][1];
	}
} 

void CResearcher::UpdateTrial() 
{ 
	//calculate the changes of trial information 
	int i; 
	int j; 
	
	for(i=0;i<iAntCount;i++) 
	{ 
		for (j=0;j<iCityCount-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[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength; 
		Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength; 
	} 
	for (i=0;i<iCityCount;i++) 
	{ 
		for (j=0;j<iCityCount;j++) 
		{ 
			Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] ); 
			Map.m_dDeltTrial[i][j]=0; 
		} 
	} 

/*	if(m_Round>(iItCount/2)) 
	{
		for (i=0;i<iCityCount;i++) 
		{ 
			for (j=0;j<iCityCount;j++) 
			{ 
				Map.m_dTrial[i][j]=(0.5*Map.m_dTrial[i][j]); 
			} 
		} 
	}
*/

} 

void CResearcher::init() 
{ 
    Map.init();
	m_dLength=1000; 
	temp=10000;
	m_Round=0;
} 

void CResearcher::GetAnt() 
{ 
	//randomly put ant into map 
	int i=0; 
	int city; 
	srand( (unsigned)time(NULL) +rand()); 
	////solvefile<<"---------------------------------------"<<'\n';
	for (i=0;i<iAntCount;i++) 
	{ 
		city=rnd(iCityCount); 
		ants[i].addcity(city); 
        ////solvefile<<"ant("<<i<<")at"<<'\t'<<city<<'\n';
	} 
	////solvefile<<"---------------------------------------"<<'\n';
} 

void CResearcher::StartSearch() 
{ 
	//begin to find best solution 
	int i; 
	int j; 

/*	if(m_Round>(3*iItCount/4)) 
	{		
		alpha=4;
		beta=8;
		rou=0.6;
	}
	else if(m_Round>(iItCount/2)) 
	{		
		alpha=2;
		beta=7;
		rou=0.5;
	}
	else*/
/*	if(m_Round>(iItCount/3)) 
	{
		alpha=1;
		beta=7;
		rou=0.5;
	}
*/
//	solvefile<<"**************************************************"<<'\n';
//	solvefile<<"start search..........."<<'\t';
	solvefile<<m_Round<<'\t';
	
	for(j=0;j<iAntCount;j++)  
	{  
		for (i=0;i<iCityCount-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<iCityCount;t++) 
//	{
//		temptour[t]=ants[0].tabu[t]; 
//	}
	
	for(j=0;j<iAntCount;j++)  
	{ 
		if (temp>ants[j].m_dLength)
		{ 
			temp=ants[j].m_dLength; 
			for (int t=0;t<iCityCount;t++) 
			{
				temptour[t]=ants[j].tabu[t]; 
			}
		} 
	} 
	
	m_dLength=temp; 
	for (int t=0;t<iCityCount;t++) 
	{
		besttour[t]=temptour[t]; 				
//		solvefile<<besttour[t]<<'\t';
	}
//	solvefile<<'\n';
	solvefile<<m_dLength<<'\n';
	UpdateTrial();  
	m_Round++;

	for(j=0;j<iAntCount;j++)  
	{	
		ants[j].Clear(); //从上次的结束处开始
	}
	
//	printf("Round(%d) : Length(%f)\n",m_Round,m_dLength); 
} 

bool CResearcher::EndResearch()
{
	if(m_Round>=iItCount-1)
	{
		solvefile<<"*****************---->"<<'\n';
		printf("The shortest toure is : %f\n",m_dLength); 
		for ( int t=0;t<iCityCount;t++) 
		{
			printf(" %d ",besttour[t]); 
			solvefile<<besttour[t]<<'\t';
		}
		solvefile<<"::"<<m_dLength<<'\t'; 
		solvefile.close();
		return 1;
	}
	else 
		return 0;
}