sacode.cpp

对模拟退火算法的实现

#include <StdAfx.h>
#include <math.h>
#include <algorithm>
using std::random_shuffle;
using std::swap;

/*********************************************************
	InitialSA()——模拟退火算法的初始化
	1. 根据直角坐标生成城市距离矩阵
	2. 计算初始温度
*********************************************************/
void InitialSA()
{
	CityNumber = vecCitys.size();
	
	vecCityDistances.clear();
	double fMaxCityDistance = 0.0;
	double fMinCityDistance = 100000.0;
	double fCityDistance = 0.0;
	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;
			fCityDistance = CountCityDistance( *iter_from, *iter_to, tmp_citydistance );

			if( fCityDistance > fMaxCityDistance )
				fMaxCityDistance = fCityDistance;

			if( fCityDistance < fMinCityDistance )
				fMinCityDistance = fCityDistance;

			vecCityDistances.push_back( tmp_citydistance );
		}
	}

	int rate = 20;
	InitialTemperature = CountInitialTemperatureMaxMin( fMaxCityDistance, fMinCityDistance, rate );
	NowTemperature = InitialTemperature;
	NowExternalIterNumber = 0;
	NowInnerIterNumber = 0;
}

/*********************************************************
	ClearSA()——清空残留数据
*********************************************************/
void ClearSA()
{
	vecCitys.clear();
	vecCityDistances.clear();
	CityNumber = 0;
	InitialTemperature = 0.0;
	NowTemperature = 0.0;
	NowExternalIterNumber = 0;
	NowInnerIterNumber = 0;
}

/*********************************************************
	CountCityDistance()——计算城市之间的距离
	输入参数： 1、FromCity			源城市引用
			   2、ToCity			目标城市引用
			   3、CityDistance		城市距离利用，返回值
	返回值：   源城市与目标城市之间的距离，double型
*********************************************************/
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
	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;

}

/*********************************************************
	CountInitialTemperatureMaxMin()——计算起始温度
	输入参数： 1、maxdis	城市之间的最大距离
			   2、mindis	城市之间的最小距离
			   3、rate		比例系数
	返回值：   起始温度，double型
	计算方法参见《现代优化计算方法》（邢文训等编著） p117 
*********************************************************/
double CountInitialTemperatureMaxMin( double maxdis, double mindis, int rate )
{
	return( rate*( CityNumber*maxdis - CityNumber*mindis ) );
}

/*********************************************************
	CreateCityRouter()——生成城市行走路径
	输入参数： 1、CityRouter	城市行走路径的vector引用，返回值
	返回值：   空
	注：生成1->2->3->......->n的城市行走顺序，作为算法初值
*********************************************************/
void CreateCityRouter( CityRouterDef &CityRouter )
{
	for( int i=1;i<=CityNumber;i++ )
		CityRouter.push_back( i );

//	random_shuffle(CityRouter.begin(), CityRouter.end()); 
}

/*********************************************************
	CreateCityRouter2opt()——从某行走路径的邻域中随机选择一个新的行走路径，邻域映射为2-opt
	输入参数： 1、preCityRouter		原先行走路径的vector引用
			   2、CityRouter		新的行走路径的vector引用，返回值
	返回值：   空
*********************************************************/
void CreateCityRouter2opt( CityRouterDef &preCityRouter, CityRouterDef &CityRouter )
{
	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 )
{
	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 )
{
	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 );
}

/*********************************************************
	CountDownTemperature()——计算外层循环的下降后的温度
	输入参数： 1、nowtemp		当前温度
			   2、DownMode		下降方式，保留
	返回值：   下降后的温度，double型
	注：		温度下降方式 T（k+1） = K*T（k），K=0.95温度下降方式 T（k+1） = K*T（k），K=0.95
*********************************************************/
double CountDownTemperature( double nowtemp, int DownMode )
{
	return( 0.95*nowtemp );
}

/*********************************************************
	JudgeOverInnerLoop()——判断是否结束某一温度下的内层循环
	输入参数： 1、JudgeMode		判断方式，保留
	返回值：   是否结束标志位，BOOL型
	注：		某一温度下的循环次数是固定的，即城市个数的三次方
*********************************************************/
BOOL JudgeOverInnerLoop( int JudgeMode )
{
	if( NowInnerIterNumber >= CityNumber*CityNumber*CityNumber )  //*CityNumber)
		return TRUE;
	else
		return FALSE;
}

/*********************************************************
	JudgeOverExternalLoop()——判断是否结束模拟退火算法
	输入参数： 1、JudgeMode		判断方式，保留
	返回值：   是否结束标志位，BOOL型
	注：		使用“零度法”的判断方式，T（k）<= 0.01，结束计算
*********************************************************/
BOOL JudgeOverExternalLoop( int JudgeMode )
{
	if( NowTemperature <= 0.01 )		//InitialTemperature*0.001 )
		return TRUE;
	else
		return FALSE;
}

/*********************************************************
	FormRouterString()——根据行走路径生成路径字符串，供显示使用
	输入参数： 1、CityRouter		给定行走路径的引用
	返回值：   行走路径的显示字符串
*********************************************************/
CString FormRouterString( SYRouter &CityRouter )
{
	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;
}

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

/*********************************************************
	GetRouterFileString()——获得指定路径的城市坐标字符串
	输入参数：	1、CityRouter			城市路径索引 
				2、strTemp				城市坐标字符串
	返回值：  空 
*********************************************************/
void GetRouterFileString( SYRouter &CityRouter, CString &strTemp )
{
	strTemp.Empty();

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