mytsp.cpp

使用蚁群算法解决旅行商问题

#include "stdafx.h"
#include "MyTsp.h"

int besttour[iCityCount]; //最佳路线列表


/***************************产生low、high之间的随机数***************************/

double  doublernd(int low,double uper)
{
	double p=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);
	return (p);
};

/****************************产生0-uper之间的随机数*****************************/

int intrnd(int uper)
{
	return (rand()%uper);
};

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

/////////////////////////////////////////////////////////////////////////////////
void ant::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);
}

///////////////////////////////初始化一些参数/////////////////////////////////////
ant::ant()
{
	m_dLength=m_dShortest=0;
	m_iCityCount=0;
	int i;
	for(i=0;i<iCityCount;i++)
	{
		AllowedCity[i]=1;
		prob[i]=0;
	}
}

////////////////////把所经过的城市列入“所经城市列表”///////////////////////////
void ant::addcity(int city)
{
 //add city to tabu;
	tabu[m_iCityCount]=city;     //把所经过的城市列入“所经城市列表”
	m_iCityCount++;
	AllowedCity[city]=0;    //把当前城市设为不可选
}

/////////////////////通过比较信息素等信息找寻下一个城市的ID//////////////////////////////
int ant::ChooseNextCity()
{	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=doublernd(0,sel);
	double mSelect=0;
	for ( i=0;i<iCityCount;i++)
	{
		if((AllowedCity[i]==1))
			mSelect+=prob[i] ;
		if (mSelect>=mRate) 
		{
			j=i;
			break;
		}
	}
	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 ant::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]];  //再加最后返回时的一段
}

//////////////////////////获取下一个城市的ID并将其加入所经城市列表//////////////
void ant::move()
{
 //the ant move to next town and add town ID to tabu.
	int j;
	j=ChooseNextCity();
	addcity(j);
}

///////////////////更新地图信息///////////////////
void project::UpdateTrial()
{
	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;
		}
	}
}

///////////////////////////////初始化地图参数/////////////////////////////////
void project::initmap()
{
	int i;
	int j;
	for(i=0;i<iCityCount;i++)
	{
		for (j=0;j<iCityCount;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("eil51.tsp");
 
	for (int i=0;i<iCityCount;i++)
	{
		in>>cc[i].num>>cc[i].x>>cc[i].y;
		besttour[i]=0;
	}
	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));
			}
		}
	}
}

/////////////////////////////////////////////////////////////////////////////////
void project::GetAnt()
{
 //randomly put ant into map
	int i=0;
	int city;
	srand( (unsigned)time( NULL ) +rand());
	for (i=0;i<iAntCount;i++)
	{
		city=intrnd(iCityCount);
		ants[i].addcity(city);
	}
}

///////////////////////////////////////////////////////////////////////////////////
void project::StartSearch()
{
 //begin to find best solution
	int max=0;//every ant tours times
	int i;
	int j;
	double temp;
	int temptour[iCityCount];
	while (max<iItCount)
	{  
		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 ( t=0;t<iCityCount;t++)
					temptour[t]=ants[j].tabu[t];
			}
		}
		if(temp<m_dLength)
		{
			m_dLength=temp;
			for ( t=0;t<iCityCount;t++)
			besttour[t]=temptour[t];
		}
	//	printf("%d : %f\n",max,m_dLength);
		UpdateTrial(); 
		for(j=0;j<iAntCount;j++) 
			ants[j].Clear();
		max++;
	}
	printf("The shortest toure is : %f\n",m_dLength);
	for (int t=0; t<iCityCount; t++)
		printf(" %d ",besttour[t]);
}

/*求eil51最优到了438，可以修改循环次数和其他参数。以得到更好的解。
使用TSP数据的时候，将前面的一些字符串信息删除，只留下坐标数据。*/

/*
int main(int argc, char *argv[])
{
    project TSP;
    TSP.GetAnt();
    TSP.StartSearch();
	return 0;
}*/