sacode.cpp

用VC++编写的蚁群算法求解TSP问题的程序

#include <StdAfx.h>
#include <math.h>
#include <algorithm>
using std::random_shuffle;
using std::swap;


/*********************************************************
	InitialSA()——算法的初始化
	根据直角坐标生成城市距离矩阵
*********************************************************/
void InitialSA()
{
	if( FileType == 1 )
	{
		CityNumber = vecCitys.size();
	
		vecCityDistances.clear();
		std::vector<SYCity>::iterator iter_from, iter_to;
		for( iter_from=vecCitys.begin();iter_from!=vecCitys.end();iter_from++ )
		{
			for( iter_to=vecCitys.begin();iter_to!=vecCitys.end();iter_to++ )
			{
				SYCityDistance tmp_citydistance;
				CountCityDistance( *iter_from, *iter_to, tmp_citydistance );

				vecCityDistances.push_back( tmp_citydistance );
			}
		}
	}
	else if( FileType == 2 )
	{
		vecCitys.clear();

		int nRow = -1;
		int ncityindex;
		CString strcityname;
		std::vector<SYCityDistance>::iterator iter_dis;
		for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
		{
			if( nRow < 0 )
				nRow = iter_dis->m_nFromCity;

			if( iter_dis->m_nFromCity == nRow )
			{
				ncityindex = iter_dis->m_nToCity;
				strcityname.Format("城市 %d",ncityindex);

				SYCity tmpCity;
				tmpCity.m_strName = strcityname;
				tmpCity.m_nIndex = ncityindex;
				tmpCity.m_Coordinate.m_fcodx = 0.0;
				tmpCity.m_Coordinate.m_fcody = 0.0;
				vecCitys.push_back( tmpCity );
			}
			else
				break;
		}
		CityNumber = vecCitys.size();
	}	
	
	 fMaxCityDistance = 0.0;
	double fMinCityDistance = 100000.0;
	double fCityDistance = 0.0;
	std::vector<SYCityDistance>::iterator iter_dis;
	for( iter_dis=vecCityDistances.begin();iter_dis!=vecCityDistances.end();iter_dis++ )
	{
		fCityDistance = iter_dis->m_fDistance;

		if( fCityDistance > fMaxCityDistance )
			fMaxCityDistance = fCityDistance;

		if( fCityDistance < fMinCityDistance )
			fMinCityDistance = fCityDistance;
	}

	}

/*********************************************************
	ClearSA()——清空残留数据
*********************************************************/
void ClearSA()
{
	vecCitys.clear();
	vecCityDistances.clear();
	CityNumber = 0;

}

/*********************************************************
	CountCityDistance()——计算城市之间的距离
	输入参数： 1、FromCity			源城市引用
			   2、ToCity			目标城市引用
			   3、CityDistance		城市距离引用，返回值
	返回值：   源城市与目标城市之间的距离，double型
*********************************************************/
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;

	CityDistance.m_fDistance = sqrt( (FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx)*(FromCity.m_Coordinate.m_fcodx-ToCity.m_Coordinate.m_fcodx) +
									 (FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody)*(FromCity.m_Coordinate.m_fcody-ToCity.m_Coordinate.m_fcody) );

	return CityDistance.m_fDistance;

}


NNAnt::NNAnt(int start_city)
{
		START_CITY=start_city;
	}

void moveTo(int to_city)
	{	
	Allowed[to_city] = 0;
	
	CURRENT_TOUR[CURRENT_TOUR_INDEX][0]=CURRENT_CITY;
	CURRENT_TOUR[CURRENT_TOUR_INDEX][1]=to_city;

		CURRENT_TOUR_INDEX++;	//行程表
		CURRENT_CITY=to_city;
	}


	 NNAnt::choose()
	{
		double best_length=(double)CityNumber*fMaxCityDistance;
		int best_choose=-1;		//初始化城市号，对应距离

		

		for(int j=0;j<CityNumber;j++)
	{
					
	if((Allowed[j]==1)&&(CityDistances[CURRENT_CITY][j]<best_length))
			{
				best_choose=j;
				best_length=CityDistances[CURRENT_CITY][j];
			}
		}
		return best_choose;//只返回城市号，距离是它的函数
	}
	
	 NNAnt::search()
	{
		CURRENT_CITY=START_CITY;
		CURRENT_TOUR_INDEX=0;	//城市号与索引号是不同的概念
	
		for (int i=0;i<CityNumber;i++)
		{
			Allowed[i]=1;
		}					//初始化禁忌表
	Allowed[CURRENT_CITY]=0;

		int temp_sum=0;
		for ( i=0;i<CityNumber;i++)
		{
			temp_sum+=Allowed[i];
		}
		while (temp_sum>0)
		{
			moveTo(choose());			//调用两个函数，完成大部分工作
			temp_sum=0;
			for ( i=0;i<CityNumber;i++)
		{			
			temp_sum+=Allowed[i];
		}
		}
		Allowed[START_CITY]=1;
		moveTo(START_CITY);
	}

double calc_length()
{
	double l=0;
for (int n=0;n<CityNumber;n++)
	{
		int i=CURRENT_TOUR[n][0];
		int j=CURRENT_TOUR[n][1];
		l+=CityDistances[i][j];
	}
return (l);
}


double transition(int i, int j)
{
	double temp;
	temp=pow(TAU[i][j],ALPHA)*pow(ETA[i][j],BETA);
	if(i!=j)
		return temp;
	else
		return(0.0);
}



ACSAnt::ACSAnt(int start_city)
{
		START_CITY=start_city;
	}


ACSAnt::choose()
{
 	double best_value=-1.0;
	int best_choose=-1;
	for (int j=0;j<CityNumber;j++)
	{
		if ((Allowed[j]==1)&&(transition(CURRENT_CITY,j)>best_value))
		{
			best_choose=j;
			best_value=transition(CURRENT_CITY,j);
		}
	}
	return best_choose;
 }


ACSAnt::search()
{
	CURRENT_CITY=START_CITY;
	int tocity;

	CURRENT_TOUR_INDEX=0;
	for (int i=0;i<CityNumber;i++)
		{
			Allowed[i]=1;
		}

	Allowed[CURRENT_CITY]=0;
	int LAST_CITY;
	
	while (1)
	{
		LAST_CITY=CURRENT_CITY;
		tocity=choose();	//选择城市
		if (tocity==-1){break;}
		moveTo(tocity);		//移动
		//ACS->local_update_rule(LAST_CITY,CURRENT_CITY);
	}
	//以下是收尾工作
	Allowed[START_CITY]=1;
	//ACS->local_update_rule(CURRENT_CITY,START_CITY);
	moveTo(START_CITY);
	
}