gasatsp.cpp

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

}

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

void ComputeFitness(float currTemper)
{
	std::vector<SYRouter>::iterator iter;
	float currMinDist = GetMinRouter().m_fTotalDistance;
	float currDist;

	for (iter=vecPop.begin();iter!=vecPop.end();iter++)
	{
		currDist = iter->m_fTotalDistance;
		iter->m_fFitness = exp(-(currDist-currMinDist)/currTemper);
	}
}
/*********************************************************
	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;
	}

	SYRouter best = GetMinRouter();
	vecSelPop.push_back(best);
	for( i=0;i<CityNumber*POP_CITYNUMBER_RATE-1;i++ )//nPopSize
	{
		nRollNumber = rand()%nRollRange;
		for( j=0;j<nPopSize;j++ )
		{
			if( nRollNumber <= vecRoll[j] )
			{
				vecSelPop.push_back( vecPop[j] );
				break;
			}
		}
	}
	/*int index = 0;
	for (i=0; i<CityNumber*POP_CITYNUMBER_RATE;i++)
	{
		double r = rand()/RAND_MAX;
		while (vecRoll[j] < )
		{
		}
	}*/

	vecPop.clear();
	vecPop = vecSelPop;
}

/*********************************************************
	GreedyErase()——路径序列中删除指定城市，贪婪交叉算法专用
	输入参数： 1、CityRouter		给定行走路径的引用
			   2、ndelcity			需删除城市的索引
	返回值：   空
*********************************************************/
void GreedyErase( CityRouterDef &cityrouter, int ndelcity )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	BOOL bFindCity = FALSE;
	std::vector<int>::iterator iter_city;
	for( iter_city=cityrouter.begin();iter_city!=cityrouter.end();iter_city++ )
	{
		if( *iter_city == ndelcity )
		{
			bFindCity = TRUE;
			break;
		}
	}

	if( bFindCity )
		cityrouter.erase( iter_city );
}

/*********************************************************
	GreedyRight()——路径序列中获取指定城市的右边城市，贪婪交叉算法专用
	输入参数： 1、CityRouter		给定行走路径的引用
			   2、ndelcity			指定城市索引
	返回值：  右端城市索引，int型 
	注：
		路径末端城市的右边城市为首端城市
*********************************************************/
int GreedyRight( CityRouterDef &cityrouter, int nCity )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	BOOL bFindCity = FALSE;
	std::vector<int>::iterator iter_city;
	for( iter_city=cityrouter.begin();iter_city!=cityrouter.end();iter_city++ )
	{
		if( *iter_city == nCity )
		{
			bFindCity = TRUE;
			break;
		}
	}

	if( bFindCity )
	{
		iter_city++;
		if( iter_city == cityrouter.end() )
			iter_city = cityrouter.begin();

		return *iter_city;
	}
	else
		return -1;
}

/*********************************************************
	GreedyLeft()——路径序列中获取指定城市的左边城市，贪婪交叉算法专用
	输入参数： 1、CityRouter		给定行走路径的引用
			   2、ndelcity			指定城市索引
	返回值：  左端城市索引，int型 
	注：
		路径首端城市的左边城市为末端城市
*********************************************************/
int GreedyLeft( CityRouterDef &cityrouter, int nCity )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	BOOL bFindCity = FALSE;
	std::vector<int>::iterator iter_city;
	for( iter_city=cityrouter.begin();iter_city!=cityrouter.end();iter_city++ )
	{
		if( *iter_city == nCity )
		{
			bFindCity = TRUE;
			break;
		}
	}

	if( bFindCity )
	{
		if( iter_city == cityrouter.begin() )
			return cityrouter.back();
		else
		{
			iter_city--;
			return *iter_city;
		}
	}
	else
		return -1;
}

/*********************************************************
	Crossover()——两染色体的交叉实现
	输入参数： 1、nFatherA			父染色体A
			   2、nFatherB			父染色体B
			   3、nMode				交叉方式
	返回值：  空 
	注：
		现有交叉方式
		1、常规交叉方式，该方式比《现代计算方法》（邢文训等编著）p178给出的
		“非常规码的常规交配法”稍复杂些。书中只随机选择一个交配位，两个后代
		交配位之前的基因分别继承双亲的交配位之前的基因。本程序中，是随机选择
		两个不相同的交配位，后代在这两个交配位之间继承双亲在这两个交配位之间
		的基因
		如 父A  1 2 3 | 4 5 6 7 | 8 9 10
		   父B  4 7 8 | 3 2 5 9 | 1 6 10

		   子A  8 3 2 | 4 5 6 7 | 9 1 10
		   子B  1 4 6 | 3 2 5 9 | 7 8 10

		2、贪心交叉方式（Greedy Crossover），
		具体算法可参见	谢胜利,等.求解ＴＳＰ问题的一种改进的遗传算法[Ｊ].计算机工程与应用,2002(8):58～245.
*********************************************************/
void Crossover( int nFatherA, int nFatherB, int nMode )
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	int nPopSize = vecPop.size();

	if( nFatherA < 0 || nFatherA >= nPopSize ||
		nFatherB < 0 || nFatherB >= nPopSize )
		return;

	CityRouterDef  SonA, SonB;
	
	switch( nMode )
	{
		case 1:
		{
			int ncrossoverbegin, ncrossoverend;
			while(1)
			{
				ncrossoverbegin = rand()%(CityNumber-1);		//取交叉范围
				ncrossoverend = rand()%(CityNumber-1);
				if( ncrossoverend > ncrossoverbegin )
					break;
				else if( ncrossoverend < ncrossoverbegin )
				{
					std::swap( ncrossoverbegin, ncrossoverend );
					break;
				}
			}

			for( int i=ncrossoverbegin;i<=ncrossoverend;i++ )
			{
				SonA.push_back( vecPop[nFatherA].m_CityRouter[i] );
				SonB.push_back( vecPop[nFatherB].m_CityRouter[i] );
			}

			std::vector<int>::iterator iter_father, iter_son;
			BOOL hasCity = FALSE;
			int naddbegin = 0;
			for( iter_father=vecPop[nFatherB].m_CityRouter.begin();
				 iter_father!=vecPop[nFatherB].m_CityRouter.end();
				 iter_father++ )
			{
				hasCity = FALSE;
				for( iter_son=SonA.begin();iter_son!=SonA.end();iter_son++ )
				{
					if( *iter_son == *iter_father )
					{
						hasCity = TRUE;
						break;
					}
				}

				if( !hasCity )
				{
					if( naddbegin < ncrossoverbegin )
					{
						SonA.insert( SonA.begin()+naddbegin, *iter_father );
						naddbegin++;
					}
					else
						SonA.push_back( *iter_father );
				}
			}

			naddbegin = 0;
			for( iter_father=vecPop[nFatherA].m_CityRouter.begin();
				 iter_father!=vecPop[nFatherA].m_CityRouter.end();
				 iter_father++ )
			{
				hasCity = FALSE;
				for( iter_son=SonB.begin();iter_son!=SonB.end();iter_son++ )
				{
					if( *iter_son == *iter_father )
					{
						hasCity = TRUE;
						break;
					}
				}