gacode.cpp

遗传算法求解旅行商问题

#include "StdAfx.h"					//只能放在第一个？？
#include "gacode.h"
#include <algorithm>
#include "math.h"

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

/*********************************************************
	#define宏定义——GA的参数设置
*********************************************************/
#define CROSSOVER_P				0.3					//交配概率
#define MUTATION_P				0.1					//变异概率
#define EVAL_BASE				0.5					//基于序评价基数
#define POP_CITYNUMBER_RATE		5					//群体个数与城市个数之比
#define FITNESS_MODE			1					//评价函数计算方式
#define CROSSOVER_MODE			2					//交叉方式
#define MUTATION_MODE			1					//变异方式
#define TOTAL_GENERATION		5000				//迭代次数


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

/*********************************************************
	FindCityDistance()——根据两城市的索引获得两城市之间的路程
	输入参数： 1、FromCityIndex		源城市的索引
			   2、ToCityIndex		目标城市的索引
	返回值：   两城市之间的路程，double型
*********************************************************/
double FindCityDistance( int FromCityIndex, int ToCityIndex )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	int nIndex = (FromCityIndex-1)*CityNumber+(ToCityIndex-1);

	std::vector<SYCityDistance>::iterator iter_citydis;
	iter_citydis = vecCityDistances.begin()+nIndex;

	if( iter_citydis->m_nFromCity == FromCityIndex &&
		iter_citydis->m_nToCity == ToCityIndex )
		return( iter_citydis->m_fDistance );
	else
		return( 0.0 );
}

/*********************************************************
	FormRouterString()——根据行走路径生成路径字符串，供显示使用
	输入参数： 1、CityRouter		给定行走路径的引用
	返回值：   行走路径的显示字符串
*********************************************************/
CString FormRouterString( SYRouter &CityRouter )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	CString strTemp, strValue;

	strTemp = "路径 ";
	
	std::vector<int>::iterator iter_cityindex;
	for( iter_cityindex=CityRouter.m_CityRouter.begin();
		 iter_cityindex!=CityRouter.m_CityRouter.end();
		 iter_cityindex++ )
	{
		strValue.Format("%d",*iter_cityindex);
		strTemp += strValue;

		if( iter_cityindex+1 == CityRouter.m_CityRouter.end() )
			strTemp += " ";
		else
			strTemp +=" ";
	}

	strTemp += "  ";
	strTemp += "总路程 ";
	strValue.Format("%10.4f",CityRouter.m_fTotalDistance);
	strTemp += strValue;
	return strTemp;
}

/*********************************************************
	CreateFitnessofPop()——对群体中的每个染色体计算适应函数/评价函数
	输入参数： 1、nMode		计算方式
	返回值：   空
	注：现有计算方式 
			1、基于序的评价函数
			其它的计算方式陆续添加中
*********************************************************/
void CreateFitnessofPop( int nMode )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	std::vector<SYRouter>::iterator iter_router;

	switch( nMode )
	{
		case 1:			//基于序的评价函数
		{
			double alpha = EVAL_BASE;
			std::vector<double> vecSort;
			for( iter_router=vecPop.begin();iter_router!=vecPop.end();iter_router++ )
			{
				vecSort.push_back( iter_router->m_fTotalDistance );
				iter_router->m_fFitness = -100.0;
			}

			std::sort( vecSort.begin(), vecSort.end() );

			std::vector<double>::iterator iter_sort;
			int nIndex = 0;
			for( iter_sort=vecSort.begin();iter_sort!=vecSort.end();iter_sort++ )
			{
				for( iter_router=vecPop.begin();iter_router!=vecPop.end();iter_router++ )
				{
					if( fabs(iter_router->m_fTotalDistance-(*iter_sort)) < 0.00001 &&
						iter_router->m_fFitness < -10.0 )
						break;
				}

				iter_router->m_fFitness = alpha*pow(1-alpha,(double)nIndex);
				nIndex++;
			}
			break;
		}

		default:
			break;
	}
}

/*********************************************************
	SelectPop()——轮盘赌方式竞争选择染色体
	输入参数： 空
	返回值：   空
*********************************************************/
void SelectPop()			//群体竞争  轮盘赌选择
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	std::vector<double> vecRoll;
	std::vector<SYRouter> vecSelPop;
	int nRollNumber, nRollRange;
	int nPopSize = vecPop.size();
	int i, j;

	for( i=0;i<nPopSize;i++ )
	{
		double fsumfitness = 0.0;
		for( int j=0;j<=i;j++ )
		{
			fsumfitness += vecPop[j].m_fFitness*10000;
		}

		vecRoll.push_back( fsumfitness );
		nRollRange = (int)fsumfitness;
	}

	for( i=0;i<nPopSize;i++ )
	{
		nRollNumber = rand()%nRollRange;
		for( j=0;j<nPopSize;j++ )
		{
			if( nRollNumber <= vecRoll[j] )
			{