gacode.cpp

模拟退火算法、遗传算法求解TSP修改版2 下载

				vecSelPop.push_back( vecPop[j] );
				break;
			}
		}
	}

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

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

		case 2:
		{
			int randomcity, nowopcity, nextopcity, rightA, rightB, leftA, leftB;
			randomcity = rand()%(CityNumber-1)+1;

			nowopcity = randomcity;
			SonA.push_back( nowopcity );
			CityRouterDef FatherA = vecPop[nFatherA].m_CityRouter;
			CityRouterDef FatherB = vecPop[nFatherB].m_CityRouter;
			while( FatherA.size() > 1 && FatherB.size() > 1 )
			{
				rightA = GreedyRight( FatherA, nowopcity );
				rightB = GreedyRight( FatherB, nowopcity );

				if( FindCityDistance( nowopcity, rightA ) < FindCityDistance( nowopcity, rightB ) )
				{
					SonA.push_back( rightA );
					nextopcity = rightA;
				}
				else
				{
					SonA.push_back( rightB );
					nextopcity = rightB;
				}

				GreedyErase( FatherA, nowopcity );
				GreedyErase( FatherB, nowopcity );
				nowopcity = nextopcity;
			}

			nowopcity = randomcity;
			SonB.push_back( nowopcity );
			FatherA = vecPop[nFatherA].m_CityRouter;
			FatherB = vecPop[nFatherB].m_CityRouter;
			while( FatherA.size() > 1 && FatherB.size() > 1 )
			{
				leftA = GreedyLeft( FatherA, nowopcity );
				leftB = GreedyLeft( FatherB, nowopcity );

				if( FindCityDistance( nowopcity, leftA ) < FindCityDistance( nowopcity, leftB ) )
				{
					SonB.push_back( leftA );
					nextopcity = leftA;
				}
				else
				{
					SonB.push_back( leftB );
					nextopcity = leftB;
				}

				GreedyErase( FatherA, nowopcity );
				GreedyErase( FatherB, nowopcity );
				nowopcity = nextopcity;
			}
			break;
		}

		default:
			break;
	}

	vecPop[nFatherA].m_CityRouter.clear(); 
	vecPop[nFatherB].m_CityRouter.clear();
	vecPop[nFatherA].m_CityRouter = SonA; 
	vecPop[nFatherB].m_CityRouter = SonB;

	vecPop[nFatherA].m_fTotalDistance = CountTotalDistance( vecPop[nFatherA].m_CityRouter );
	vecPop[nFatherB].m_fTotalDistance = CountTotalDistance( vecPop[nFatherB].m_CityRouter );
}

/*********************************************************
	CrossoverPop()——种群交叉
	输入参数： 1、nMode				交叉方式
	返回值：  空 
*********************************************************/
void CrossoverPop( int nMode )			//交配
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	double fProbability = CROSSOVER_P;			//交配概率
	std::vector<int> vecCrossoverIndexs;
	int nPopSize = vecPop.size();
	double random;

	for( int i=0;i<nPopSize;i++ )
	{
		random = ((double)(rand()%10000))/10000.0;
		if( random < fProbability )
			vecCrossoverIndexs.push_back( i );
	}

	int CrossoverNumber = vecCrossoverIndexs.size();
	if( CrossoverNumber%2 != 0 )
		vecCrossoverIndexs.pop_back();

	CrossoverNumber = vecCrossoverIndexs.size();
	for( i=0;i<CrossoverNumber;i=i+2)
	{
		int nFatherA = vecCrossoverIndexs[i];
		int nFatherB = vecCrossoverIndexs[i+1];

		CString strTemp1, strTemp2;
		strTemp1 = FormRouterString( vecPop[nFatherA] );
		strTemp2 = FormRouterString( vecPop[nFatherB] );
		Crossover( nFatherA, nFatherB, nMode );
		strTemp1 = FormRouterString( vecPop[nFatherA] );
		strTemp2 = FormRouterString( vecPop[nFatherB] );
	}
}

/*********************************************************
	MutationPop()——种群变异
	输入参数： 1、nMode				变异方式
	返回值：  空 
	注：
		现提供两种变异方式
		1、取两个不同的随机数，对这两个数确定的基因区间进行随机排序
		2、在染色体的2-opt邻域中随机取出一个染色体
*********************************************************/
void MutationPop( int nMode )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	double fProbability = MUTATION_P;			//变异概率
	std::vector<int> vecMutationIndexs;
	int nPopSize = vecPop.size();
	double random;

	for( int i=0;i<nPopSize;i++ )
	{
		random = ((double)(rand()%10000))/10000.0;
		if( random < fProbability )
			vecMutationIndexs.push_back( i );
	}

	int MutationNumber = vecMutationIndexs.size();

	switch( nMode )
	{
		case 1:
			for( i=0;i<MutationNumber;i++ )
			{
				int randombegin;
				int randomend;
				while(1)
				{
					randombegin = rand()%(CityNumber-1);
					randomend = rand()%(CityNumber-1);
					if( randombegin < randomend )
						break;
					else if( randombegin > randomend )
					{
						std::swap( randombegin, randomend );
						break;
					}
				}

				std::random_shuffle( vecPop[vecMutationIndexs[i]].m_CityRouter.begin()+randombegin,
									 vecPop[vecMutationIndexs[i]].m_CityRouter.begin()+randomend );
				vecPop[vecMutationIndexs[i]].m_fTotalDistance = 
					CountTotalDistance( vecPop[vecMutationIndexs[i]].m_CityRouter );
			}
			break;

		case 2:
			for( i=0;i<MutationNumber;i++ )
			{
				SYRouter MuRouter( vecPop[vecMutationIndexs[i]].m_CityRouter );
				vecPop[vecMutationIndexs[i]] = MuRouter;
			}
			break;

		default:
			break;

	}
}

/*********************************************************
	OneIterGACompution()——遗传算法的一次迭代过程
	返回值：  当前的遗传代数，int型 
*********************************************************/
int OneIterGACompution()
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	if( vecPop.empty() )
		return -1;

	srand( (unsigned)time( NULL ) );

	CreateFitnessofPop(FITNESS_MODE);
	SelectPop();
	CrossoverPop(CROSSOVER_MODE);
	MutationPop(MUTATION_MODE);
	NowGenNumber++;
	return NowGenNumber;
}

/*********************************************************
	GetMinRouterFromPop()——获取当前代的最小路径，并返回其表示字符串
	返回值：  最小路径的表示字符串，CString型 
*********************************************************/
double GetMinRouterFromPop( CString &strTemp )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	strTemp.Empty();
	std::vector<SYRouter>::iterator iter_router;
	double fMinTotalDistance = 10000000.0;
	int nMinIndex = 0;
	int nIndex = 0;
	for( iter_router=vecPop.begin();iter_router!=vecPop.end();iter_router++ )
	{
		if( iter_router->m_fTotalDistance < fMinTotalDistance )
		{
			fMinTotalDistance = iter_router->m_fTotalDistance;
			nMinIndex = nIndex;
		}
		nIndex++;
	}

	strTemp = FormRouterString( vecPop[nMinIndex] );
	return( fMinTotalDistance );
}

/*********************************************************
	GetTotalGeneration()——获取最大迭代代数
	返回值：  最大迭代代数，int型 
*********************************************************/
int GetTotalGeneration()
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	return TOTAL_GENERATION;
}

/*********************************************************
	GetCoordinatebyCityIndex()——根据城市索引获取城市坐标
	输入参数： 1、cityindex				城市索引
			   2、coordx				城市X坐标
			   3、coordy				城市Y坐标
	返回值：  空 
*********************************************************/
void GetCoordinatebyCityIndex( int cityindex, double &coordx, double &coordy )
{
	coordx = 0.0;
	coordy = 0.0;

	if( cityindex > 0 && cityindex <= CityNumber )
	{
		std::vector<SYCity>::iterator iter_city;
		iter_city = vecCitys.begin()+cityindex-1;

		if( iter_city->m_nIndex == cityindex )
		{
			coordx = iter_city->m_Coordinate.m_fcodx;
			coordy = iter_city->m_Coordinate.m_fcody;
		}
	}
}

/*********************************************************
	GetMinRouterFileStringFromPop()——获取当前代的最小路径，并返回城市坐标字符串
	输入参数： 1、strTemp				城市坐标字符串
	返回值：  空 
*********************************************************/
void GetMinRouterFileStringFromPop( CString &strTemp )
{
	AFX_MANAGE_STATE(AfxGetStaticModuleState());
	strTemp.Empty();
	std::vector<SYRouter>::iterator iter_router;
	double fMinTotalDistance = 10000000.0;
	int nMinIndex = 0;
	int nIndex = 0;
	for( iter_router=vecPop.begin();iter_router!=vecPop.end();iter_router++ )
	{
		if( iter_router->m_fTotalDistance < fMinTotalDistance )
		{
			fMinTotalDistance = iter_router->m_fTotalDistance;
			nMinIndex = nIndex;
		}
		nIndex++;
	}

	CString strValue;
	std::vector<int>::iterator iter_city;
	double coordx, coordy;
	for( iter_city=vecPop[nMinIndex].m_CityRouter.begin();
		 iter_city!=vecPop[nMinIndex].m_CityRouter.end();
		 iter_city++ )
	{
		GetCoordinatebyCityIndex( *iter_city, coordx, coordy );
		strValue.Format("%.4f %.4f\n",coordx, coordy );
		strTemp += strValue;
	}
}