gasatsp.cpp

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

				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=1;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=1;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(float currTemper)
{
	//AFX_MANAGE_STATE(AfxGetStaticModuleState());
	if( vecPop.empty() )
		return -1;

	srand( (unsigned)time( NULL ) );

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

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

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

SYRouter GetMinRouter()
{
	std::vector<SYRouter>::iterator iter;
	float fMinTotalDist = vecPop[0].m_fTotalDistance;
	int minIndex = 0;
	int index = 0;
	for (iter=vecPop.begin(); iter!=vecPop.end();iter++)
	{
		if (iter->m_fTotalDistance < fMinTotalDist)
		{
			fMinTotalDist = iter->m_fTotalDistance;
			minIndex = index;
		}
		index++;
	}
	return vecPop[minIndex];
}

SYRouter GetMaxRouter()
{
	std::vector<SYRouter>::iterator iter;
	float fMaxTotalDist = vecPop[0].m_fTotalDistance;
	int maxIndex, index;
	maxIndex = index = 0;
	for (iter=vecPop.begin(); iter!=vecPop.end();iter++)
	{
		if (iter->m_fTotalDistance > fMaxTotalDist)
		{
			fMaxTotalDist = iter->m_fTotalDistance;
			maxIndex = index;
		}
		index++;
	}
	return vecPop[maxIndex];
}
/*********************************************************
	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;
	}
}

void GenerateNewPop(float currTemper)
{
	ComputeFitness(currTemper);
	SelectPop();
}


void AddPop(int popIndex, float currentTemper)
{
	SYRouter neighbour;
	CreateCityRouter2opt(vecPop[popIndex].m_CityRouter, neighbour.m_CityRouter);
	float delta = CountTotalDistance(neighbour.m_CityRouter) - vecPop[popIndex].m_fTotalDistance;
	
	double ram = (float)rand()/(float)RAND_MAX;
	if (exp(-delta/currentTemper) > ram )
	{
		vecPop.push_back(neighbour);
	}
}