wsgenalogrith.cpp

开发环境：Visual C++ .net2003 功能：利用遗传算法求解TSP问题。

	l_TmpCityInfo.m_pCityOrder = m_BaseCityInfo.m_pCityOrder;
	while(l_MemberNum < m_MemberNum)
	{		
		WSTSP::GenRandCityOrder(l_TmpCityInfo);	
		m_TmpVector.push_back(l_TmpCityInfo);	
		++l_MemberNum;
	}
	//////////////////////////////////////////////////////////////////////////////////////
	m_pCityInfoOfMembers.clear();
	m_pCityInfoOfMembers = m_TmpVector;
	m_TmpVector.clear();
	return ;
}


/*
功能：选择不同的交叉模式
输入：交叉模式编号。
*/
BOOL WSGeneticAlogrith::MakeCross(INT _Mode)
{
	switch( _Mode )
	{
	case 0:
		{
			MakeCross_NoreplaceParent();
			return TRUE;
		}
	case 1:
		{
			MakeCross_ReplaceParent();
			return TRUE;
		}
	case 2:
		{
			MakeCross_Greedy();
			return TRUE;
		}
	default:
		return FALSE;
	}
}
/*
功能：交叉运算，其产生的新个体将直接代替双亲（除了0号父体被选中）
注：该函数用于个体间交叉运算产生新子群
*/
BOOL WSGeneticAlogrith::MakeCross_ReplaceParent()
{
	//INT l_OrgMembers = m_pCityInfoOfMembers.size(), l_curMembers = m_pCityInfoOfMembers.size();
	//INT l_A, l_B;

	//printf("________________________PARENT___________________________\n");
	//for(INT i = 0; i < l_OrgMembers; ++i) Show(m_pCityInfoOfMembers[i].m_pCityOrder);
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//生成的孩子和父母共存
	//while(l_curMembers < m_MemberNum)
	//{
	//	CityInfo l_CityInfoA(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
	//	CityInfo l_CityInfoB(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
	//	//g_pCityInfoA = new CityInfo(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
	//	//g_pCityInfoA = new CityInfo(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);

	//	if(l_OrgMembers < 2)
	//	{
	//		printf("Stop\n");
	//	}

	//	do{
	//		l_A = WSRandom::GenRand(0, l_OrgMembers - 1);
	//		l_B = WSRandom::GenRand(0, l_curMembers - 1);
	//	}while(l_A == l_B);//随机选择两个交配体

	//	if( !WSTSP::CrossSubOrder(m_pCityInfoOfMembers[l_A].m_pCityOrder, m_pCityInfoOfMembers[l_B].m_pCityOrder, l_CityInfoA.m_pCityOrder, l_CityInfoB.m_pCityOrder) ) return FALSE;				
	//	//if( !WSTSP::CrossSubOrder(m_pCityInfoOfMembers[l_A].m_pCityOrder, m_pCityInfoOfMembers[l_B].m_pCityOrder, g_pCityInfoA->m_pCityOrder, g_pCityInfoB->m_pCityOrder) ) return FALSE;		

	//	//printf("________________________WORK___________________________\n");
	//	//Show(l_CityInfoA.m_pCityOrder);
	//	//Show(l_CityInfoB.m_pCityOrder);

	//	//m_pCityInfoOfMembers.push_back(*g_pCityInfoA);
	//	m_pCityInfoOfMembers.push_back(l_CityInfoA);//怀疑点：可能是因为局部空间被释放
	//	++l_curMembers;								//导致内存错误
	//	if(l_curMembers == m_MemberNum) break;

	//	//m_pCityInfoOfMembers.push_back(*g_pCityInfoB);
	//	m_pCityInfoOfMembers.push_back(l_CityInfoB);
	//	++l_curMembers;

	//}
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//生成的孩子替代父母
	INT i = 0;
	INT l_A, l_B;
	while(i++ < m_CrossProbability * m_MemberNum /2)
	{
		CityInfo l_CityInfoA(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
		CityInfo l_CityInfoB(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);

		if(m_MemberNum < 2) break;

		do{
			l_A = WSRandom::GenRand(0, m_MemberNum - 1);
			l_B = WSRandom::GenRand(0, m_MemberNum - 1);
		}while(l_A == l_B);//随机选择两个交配体

		if(l_A > l_B) WSTSP::SwapValues(l_A, l_B);

		if( !WSTSP::CrossSubOrder(m_pCityInfoOfMembers[l_A].m_pCityOrder, m_pCityInfoOfMembers[l_B].m_pCityOrder,l_CityInfoA.m_pCityOrder,l_CityInfoB.m_pCityOrder) ) return FALSE;				

		if(!l_A)
		{
			m_pCityInfoOfMembers[l_B].m_pCityOrder = l_CityInfoB.m_pCityOrder;			
		}
		else
		{
			m_pCityInfoOfMembers[l_A].m_pCityOrder = l_CityInfoA.m_pCityOrder;
			m_pCityInfoOfMembers[l_B].m_pCityOrder = l_CityInfoB.m_pCityOrder;			
		}
	}
	return TRUE;
}

/*
功能：本交叉算法要求在适配选择时，采用淘汰法；然后，本算法中将利用掩码交叉法产生新个体填充，
	以保持种群的大小一定。
*/
BOOL WSGeneticAlogrith::MakeCross_NoreplaceParent()
{
	INT l_OrgMembers = m_pCityInfoOfMembers.size()/2, l_curMembers = m_pCityInfoOfMembers.size();
	INT i = 0;
	INT l_A, l_B;
	while(l_curMembers < m_MemberNum)
	{
		CityInfo l_CityInfoA(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
		CityInfo l_CityInfoB(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);

		if(l_OrgMembers < 2) break;
		
		do{
			l_A = WSRandom::GenRand(0, l_OrgMembers - 1);
			l_B = WSRandom::GenRand(0, l_curMembers - 1);
		}while(l_A == l_B);//随机选择两个交配体

		if( !WSTSP::CrossSubOrder(m_pCityInfoOfMembers[l_A].m_pCityOrder, m_pCityInfoOfMembers[l_B].m_pCityOrder, l_CityInfoA.m_pCityOrder, l_CityInfoB.m_pCityOrder) ) return FALSE;		

		m_pCityInfoOfMembers.push_back(l_CityInfoA);//怀疑点：可能是因为局部空间被释放
		++l_curMembers;								//导致内存错误
		if(l_curMembers == m_MemberNum) break;

		m_pCityInfoOfMembers.push_back(l_CityInfoB);
		++l_curMembers;
	}
	return TRUE;
}
/*
功能：采用了贪心的交叉算法
输入：无
输出：True-->函数正常执行 False-->函数遇到异常
*/
BOOL WSGeneticAlogrith::MakeCross_Greedy()
{
	INT i = 0;
	INT l_A, l_B;

	while(i++ < m_CrossProbability * m_MemberNum /2)
	{
		CityInfo l_CityInfoSonA(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
		CityInfo l_CityInfoSonB(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_BaseCityInfo.m_pCityOrder);
		CityOrderDef l_ParentA, l_ParentB;

		INT l_CurNum = 0, l_CurNumA = 0, l_CurNumB = 0;
		l_CityInfoSonA.m_pCityOrder.clear(); 
		l_CityInfoSonB.m_pCityOrder.clear();

		//统一规定,开始城市均是0
		l_CityInfoSonA.m_pCityOrder.push_back(0);
		l_CityInfoSonB.m_pCityOrder.push_back(0);
		
		if(m_MemberNum < 2) break;		

		do{
			l_A = WSRandom::GenRand(0, m_MemberNum - 1);
			l_B = WSRandom::GenRand(0, m_MemberNum - 1);
		}while(l_A == l_B);//随机选择两个交配体
		l_ParentA = m_pCityInfoOfMembers[l_A].m_pCityOrder;
		l_ParentB = m_pCityInfoOfMembers[l_B].m_pCityOrder;

		while( l_ParentA.size() > 1 && l_ParentB.size() > 1)
		{
			l_CurNumA = WSTSP::GetRightIndex_Greedy( l_ParentA, l_CurNum );
			l_CurNumB = WSTSP::GetRightIndex_Greedy( l_ParentB, l_CurNum );

			l_ParentA.erase( l_ParentA.begin() + WSTSP::GetCityIndex(l_ParentA, l_CurNum) );
			l_ParentB.erase( l_ParentB.begin() + WSTSP::GetCityIndex(l_ParentB, l_CurNum) );

			if( WSTSP::CityDistance( m_BaseCityInfo.m_pCities[l_CurNumA], m_BaseCityInfo.m_pCities[l_CurNum] )
										> WSTSP::CityDistance( m_BaseCityInfo.m_pCities[l_CurNumB], m_BaseCityInfo.m_pCities[l_CurNum]) )
			{
				l_CurNum = l_CurNumB;
			}
			else l_CurNum = l_CurNumA;

			l_CityInfoSonA.m_pCityOrder.push_back(l_CurNum);
		}

		l_ParentA.clear();
		l_ParentB.clear();
		
		l_ParentA = m_pCityInfoOfMembers[l_A].m_pCityOrder;
		l_ParentB = m_pCityInfoOfMembers[l_B].m_pCityOrder;

		l_CurNum = 0;

		while( l_ParentA.size() > 1 && l_ParentB.size() > 1)
		{
			l_CurNumA = WSTSP::GetLeftIndex_Greedy( l_ParentA, l_CurNum );
			l_CurNumB = WSTSP::GetLeftIndex_Greedy( l_ParentB, l_CurNum );

			l_ParentA.erase( l_ParentA.begin() + WSTSP::GetCityIndex(l_ParentA, l_CurNum) );
			l_ParentB.erase( l_ParentB.begin() + WSTSP::GetCityIndex(l_ParentB, l_CurNum) );

			if( WSTSP::CityDistance( m_BaseCityInfo.m_pCities[l_CurNumA], m_BaseCityInfo.m_pCities[l_CurNum] )
										> WSTSP::CityDistance( m_BaseCityInfo.m_pCities[l_CurNumB], m_BaseCityInfo.m_pCities[l_CurNum]) )
			{
				l_CurNum = l_CurNumB;
			}
			else l_CurNum = l_CurNumA;

			l_CityInfoSonB.m_pCityOrder.push_back(l_CurNum);
		}
		l_ParentA.clear();
		l_ParentB.clear();

		if( WSTSP::TSPTotalDistance(&l_CityInfoSonA) < WSTSP::TSPTotalDistance(&m_pCityInfoOfMembers[l_A]) )
		{
			m_pCityInfoOfMembers[l_A].m_pCityOrder = l_CityInfoSonA.m_pCityOrder;
		}
		
		if( WSTSP::TSPTotalDistance(&l_CityInfoSonB) < WSTSP::TSPTotalDistance(&m_pCityInfoOfMembers[l_B]) )
		{
			m_pCityInfoOfMembers[l_B].m_pCityOrder = l_CityInfoSonB.m_pCityOrder;
		}

		l_CityInfoSonA.m_pCityOrder.clear();
		l_CityInfoSonB.m_pCityOrder.clear();
	}
	return TRUE;
}

BOOL WSGeneticAlogrith::MakeVariate(INT _Mode)
{
	switch( _Mode )
	{
	case 0:
		{
			MakeVariate_Normal();
			return TRUE;
		}
	case 1:
		{
			MakeVariate_Greedy();
			return TRUE;
		}
	default:
		return FALSE;
	}
}
/*
注：该函数用于个体变异运算产生新个体，不会替代原个体
*/
BOOL WSGeneticAlogrith::MakeVariate_Normal()
{
	INT i;
	for( i = 1; i < m_MemberNum; ++i )
	{
		if(WSRandom::JudgeEven(m_VarProbability)) WSTSP::RearrangeSubOrder(m_pCityInfoOfMembers[i].m_pCityOrder);
	}
	return TRUE;
}
/*
注：采用贪心的变异算法，只用更好的结果替代原个体。
*/
BOOL WSGeneticAlogrith::MakeVariate_Greedy()
{
	INT i;
	
	for( i = 1; i < m_MemberNum; ++i )
	{
		if(WSRandom::JudgeEven(m_VarProbability))
		{
			CityInfo l_VariateCityInfo(m_BaseCityInfo.m_CityNum, m_BaseCityInfo.m_pCities, m_pCityInfoOfMembers[i].m_pCityOrder);
			WSTSP::RearrangeSubOrder(l_VariateCityInfo.m_pCityOrder);
			if(WSTSP::TSPTotalDistance(&l_VariateCityInfo) < WSTSP::TSPTotalDistance(&m_pCityInfoOfMembers[i]) )
			{
				m_pCityInfoOfMembers[i].m_pCityOrder = l_VariateCityInfo.m_pCityOrder;
			}
		}
	}
	return TRUE;
}
/*
注：一代的变换
*/
BOOL WSGeneticAlogrith::OneGenerate(INT _AdaptMode, INT _CrossMode, INT _VariteMode)
{
	if(_AdaptMode < 0 || _AdaptMode > 3) return FALSE;
	if(_CrossMode < 0 || _CrossMode > 2) return FALSE;
	if(_VariteMode< 0 || _VariteMode> 1) return FALSE;

	CalculateAdapt(_AdaptMode);
	if(!MakeCross(_CrossMode)) return FALSE;
	if(!MakeVariate(_VariteMode)) return FALSE;
	ShowCityOrders();
}
BOOL WSGeneticAlogrith::StartCompute(INT _AdaptMode, INT _CrossMode, INT _VariteMode)
{	
	INT i = 0;
	if(!m_EndInNature)
	{
		if(!m_ComputeGenerates)
		{			
			INT l_Begin = clock();		
			INT l_Delta;
			while(TRUE)
			{			
				OneGenerate(_AdaptMode, _CrossMode, _VariteMode);
				if( (l_Delta = clock() - l_Begin) > 1000*m_ComputeTime )break;			
			}
		}
		else
		{
			while( i++ < m_ComputeGenerates ) 
				if(!OneGenerate(_AdaptMode, _CrossMode, _VariteMode)) return FALSE;
		}
	}
	else
	{
		FLOAT l_OptValue = 0.0;
		while(true)
		{
			for(i = 0; i < m_TimesOfNatureEnd; ++i)
			{
				if(!OneGenerate(_AdaptMode, _CrossMode, _VariteMode)) return FALSE;

				if(l_OptValue != m_pAdaptInfo[0].m_DestFunctionValue)
				{
					l_OptValue = m_pAdaptInfo[0].m_DestFunctionValue;
					break;
				}
			}
			if( i >= m_TimesOfNatureEnd ) return TRUE;
		}
	}
	return TRUE;
}

BOOL WSGeneticAlogrith::ShowCityOrders()
{
	//static int cnt = 0;
	//ofstream outfile;
	//outfile.open(m_oFileName, ios::out|ios::app);

	//INT i;
	//INT j;
	//printf("============================================================\n");
	//outfile<<"============================================================\n";
	//for(i = 0; i < m_MemberNum; ++i)
	//{
	//	
	//	//printf("TSP路径：");
	//	outfile<<"TSP路径：";
	//	for(j = 0; j < m_BaseCityInfo.m_CityNum; ++j)
	//	{
	//		//printf("%d ", m_pCityInfoOfMembers[i].m_pCityOrder[j]);
	//		outfile<<m_pCityInfoOfMembers[i].m_pCityOrder[j]<<" ";
	//	}
	//	//printf(">>>>>%f\n", m_pAdaptInfo[i].m_DestFunctionValue);
	//	outfile<<">>>>>"<< m_pAdaptInfo[i].m_DestFunctionValue<<endl;
	//}

	/*采用非标准格式输出
	//outfile<<cnt++<<" TSP路径:";
	//for(j = 0; j < m_BaseCityInfo.m_CityNum; ++j)
	//{
	//	//printf("%d ", m_pCityInfoOfMembers[i].m_pCityOrder[j]);
	//	outfile<<m_pCityInfoOfMembers[0].m_pCityOrder[j]<<" ";
	//}
	////printf(">>>>>%f\n", m_pAdaptInfo[i].m_DestFunctionValue);
	//outfile<<";"<< m_pAdaptInfo[0].m_DestFunctionValue<<endl;
	*/
	INT i;
	FLOAT l_DeltaTime;
	static int l_CurTime = clock();
	static int l_Step = 0;
	++l_Step;
	l_DeltaTime = ((FLOAT)(clock() - l_CurTime))/1000;


	//格式化输出
	ofstream outfile;
	outfile.open(m_oFileName, ios::app);
	outfile<<l_Step<<" "<<l_DeltaTime<<" "<<m_pAdaptInfo[0].m_DestFunctionValue<<endl;

	return TRUE;
}

BOOL WSGeneticAlogrith::Show(CityOrderDef _Order)
{
	//INT j;
	//printf("************************************************************\n");
	//printf("TSP路径：");
	//for(j = 0; j < m_BaseCityInfo.m_CityNum; ++j)
	//{
	//	printf("%d ", _Order[j]);
	//}
	//printf("\n");

	return TRUE;
}

VOID WSGeneticAlogrith::ShowBestRouteInfo()
{
	ofstream outfile;
	CHAR l_OutFileName[255] = {0};
	sprintf(l_OutFileName, "%s_Route.txt", m_oFileName);
	outfile.open(l_OutFileName, ios::out);
	for(int i = 0; i < m_BaseCityInfo.m_CityNum; ++i)
	{
		outfile<<m_BaseCityInfo.m_pCities[ m_pCityInfoOfMembers[0].m_pCityOrder[i] ].x<<" "<<
		m_BaseCityInfo.m_pCities[ m_pCityInfoOfMembers[0].m_pCityOrder[i] ].y<<endl;
	}
	outfile.close();
}