gasatsp.cpp

采用遗传模拟退火的方法解决TSP问题

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

std::vector<SYCity> vecCitys;						//城市列表
std::vector<SYCityDistance> vecCityDistances;		//城市距离列表
int CityNumber = 0;									//城市个数
int NowGenNumber = 0;								//当前第几代
std::vector<SYRouter> vecPop;						//由N个城市路径构成的群体
int FileType;										//文件格式 0 无效格式 1 坐标格式 2 对称距离矩阵格式


void ClearGA();
void InitialGA();
CString FormRouterString( SYRouter &CityRouter );

//__declspec(dllexport) int OpenDataFile( CString &strFileName );
//__declspec(dllexport) int OneIterGACompution();
//__declspec(dllexport) double GetMinRouterFromPop( CString &strTemp );
//__declspec(dllexport) int GetTotalGeneration();
//__declspec(dllexport) void GetMinRouterFileStringFromPop( CString &strTemp );


/*********************************************************
	OpenDataFile()——根据城市坐标文件名称打开并读取城市坐标信息
	输入参数： 1、strFileName			文件名称字符串引用
	返回值：   文件中所含城市个数，int型
	注：城市坐标文件的格式要求
		城市名称 空格 X轴坐标 空格 Y轴坐标
		|-----------------------------------|
		|1 37 52							|
		|2 49 49							|
		|3 52 64							|
		|* ** **							|
		|.......							|
		|-----------------------------------|
*********************************************************/
int OpenDataFile( CString &strFileName )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	ClearGA();
	CString strValue, strTemp;

	CStdioFile DataFile( strFileName, CFile::modeRead );
	CString strReadString;

	DataFile.ReadString(strReadString);
	if( strReadString == "coordinate" )
		FileType = 1;
	else if( strReadString == "distancematrix" )
		FileType = 2;
	else
		FileType = 0;

	if( FileType == 0 )
	{
		DataFile.Close();
		return -1;
	}
	else
	{
		if( FileType == 1 )
		{
			int ncityindex = 1;
			while( DataFile.ReadString(strReadString) ) 
			{
				strReadString.TrimLeft();
				strReadString.TrimRight();

				CString cityName, citycodx, citycody;
				int nspace = 0;
				nspace = strReadString.Find(" ");
				if( nspace > 0 )
				cityName = strReadString.Left( nspace );

				strReadString = strReadString.Mid( nspace+1 );
				nspace = strReadString.Find(" ");
				if( nspace > 0 )
					citycodx = strReadString.Left( nspace );

				strReadString = strReadString.Mid( nspace+1 );
				citycody = strReadString;
	
				SYCity tmpCity;
				tmpCity.m_strName = "城市 "+cityName;
				tmpCity.m_nIndex = ncityindex;
				tmpCity.m_Coordinate.m_fcodx = atof( citycodx );
				tmpCity.m_Coordinate.m_fcody = atof( citycody );

				vecCitys.push_back( tmpCity );

				ncityindex++;
			}
		}
		else if( FileType == 2 )
		{
			int nMatrixRow = 1;			//代表第几个城市所对应的行
			int nMatrixCol = 1;
			int nMaxMatrixCol = -1;		//记录第一行的列数,后续行的列数如果不等于第一行,则数据文件错误
			CString strDistance;
			while( DataFile.ReadString(strReadString) )
			{
				strReadString.TrimLeft();
				strReadString.TrimRight();

				if( strReadString.IsEmpty() )
					continue;

				int nspace = 0;
				nMatrixCol = 1;
				while(1)
				{
					nspace = strReadString.Find(" ");
					SYCityDistance tmp_citydistance;
					if( nspace > 0 )
					{
						strDistance = strReadString.Left( nspace );
						tmp_citydistance.m_fDistance = atof( strDistance );
						tmp_citydistance.m_nFromCity = nMatrixRow;
						tmp_citydistance.m_nToCity = nMatrixCol;
						vecCityDistances.push_back( tmp_citydistance );

						strReadString = strReadString.Mid( nspace+1 );
						strReadString.TrimLeft();
					}
					else 
					{
						if( !strReadString.IsEmpty() )
						{
							strDistance = strReadString;
							tmp_citydistance.m_fDistance = atof( strDistance );
							tmp_citydistance.m_nFromCity = nMatrixRow;
							tmp_citydistance.m_nToCity = nMatrixCol;
							vecCityDistances.push_back( tmp_citydistance );

							strReadString.Empty();
							break;
						}
						else
							break;
					}
					nMatrixCol++;
				}

				if( nMaxMatrixCol < 0 )
					nMaxMatrixCol = nMatrixCol;
				else
				{
					if( nMaxMatrixCol != nMatrixCol )
						return -1;
				}

				nMatrixRow++;
			}
		}
	}

	DataFile.Close();

	InitialGA();

	return CityNumber;
}

/*********************************************************
	FormInitialPop()——生成最初的群体
	最初群体个数设为城市个数的POP_CITYNUMBER_RATE倍
*********************************************************/
void FormInitialPop()			
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	vecPop.clear();
//	vecPop.reserve( CityNumber+1 );

	std::vector<SYRouter>::iterator iter_router;
	BOOL bPopHasRouter;
	for( int i=0;i<CityNumber*POP_CITYNUMBER_RATE;i++ )
	{
		while(1)
		{
			SYRouter tmpRouter;
			bPopHasRouter = FALSE;
			for( iter_router=vecPop.begin();
				 iter_router!=vecPop.end();
				 iter_router++ )
			{
				if( tmpRouter.m_CityRouter == iter_router->m_CityRouter )
				{
					bPopHasRouter = TRUE;
					break;
				}
			}

			if( !bPopHasRouter )
			{
				vecPop.push_back( tmpRouter );
				break;
			}
		}
	}
}

/*********************************************************
	InitialGA()——遗传算法的初始化
	1. 根据直角坐标生成城市距离矩阵
	2. 生成初始群体
*********************************************************/
void InitialGA()
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());

	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();
	}

	NowGenNumber = 0;
//	FormInitialPop();
}

/*********************************************************
	ClearGA()——清空残留数据
*********************************************************/
void ClearGA()
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	vecCitys.clear();
	vecCityDistances.clear();
	vecPop.clear();
	CityNumber = 0;
	NowGenNumber = 0;
}

/*********************************************************
	CountCityDistance()——计算城市之间的距离
	输入参数： 1、FromCity			源城市引用
			   2、ToCity			目标城市引用
			   3、CityDistance		城市距离利用，返回值
	返回值：   源城市与目标城市之间的距离，double型
*********************************************************/
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	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;

}

/*********************************************************
	CreateCityRouter()——生成城市行走路径
	输入参数： 1、CityRouter	城市行走路径的vector引用，返回值
	返回值：   空
	注：先生成1->2->3->......->n的城市行走顺序，然后利用random_shuffle进行随机排序
*********************************************************/
void CreateCityRouter( CityRouterDef &CityRouter )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	for( int i=1;i<=CityNumber;i++ )
		CityRouter.push_back( i );

	std::random_shuffle(CityRouter.begin(), CityRouter.end()); 
}

/*********************************************************
	CreateCityRouter2opt()——从某行走路径的邻域中随机选择一个新的行走路径，邻域映射为2-opt
	输入参数： 1、preCityRouter		原先行走路径的vector引用
			   2、CityRouter		新的行走路径的vector引用，返回值
	返回值：   空
*********************************************************/
void CreateCityRouter2opt( CityRouterDef &preCityRouter, CityRouterDef &CityRouter )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	int swapA, swapB;
	CityRouter = preCityRouter;

	while(1)
	{
		swapA = (rand()%CityNumber)-1;
		if( swapA >= 0 )
			break;
	}

	while(1)
	{
		swapB = (rand()%CityNumber)-1;
		if( swapA != swapB && swapB >= 0 )
		{
			int tmp = CityRouter[swapA];
			CityRouter[swapA] = CityRouter[swapB];
			CityRouter[swapB] = tmp;
			break;
		}
	}
}

/*********************************************************
	CountTotalDistance()——根据给定路径计算该路径对应的总路程
	输入参数： 1、CityRouter		给定行走路径的vector引用
	返回值：   总路程，double型
*********************************************************/
double CountTotalDistance( CityRouterDef &CityRouter )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	if( CityRouter.size() != CityNumber )
		return 0.0;

	double totaldis = 0.0;
	for( int i=1;i<CityNumber;i++ )
	{
		totaldis += FindCityDistance( CityRouter[i-1], CityRouter[i] );
	}
	totaldis += FindCityDistance( CityRouter[CityNumber-1], CityRouter[0] );
	return totaldis;