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();	////vecCitys作为容器SYCity的一个对象，取它的城市数
	
	vecCityDistances.clear();		////vecCityDistances作为容器SYCityDistance的一个对象，清空，置零？
	vecCityRouter.clear();
	double fMaxCityDistance = 0.0;
	double fMinCityDistance = 100000.0;
	double fCityDistance = 0.0;
	std::vector<SYCity>::iterator iter_from, iter_to;////iter_from, iter_to作为容器SYCity的两个对象

////-------------------------计算城市之间的最大和最小距离----------------------////	
	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;	////当前外循环次数为0
	NowInnerIterNumber = 0;		////当前内循环次数为0
}

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

/*********************************************************
	Hardpanish()——计算硬度惩罚值
	输入参数： 1、FromCityIndex		源城市的索引/前一坯料索引
			   2、ToCityIndex		目标城市的索引/后一坯料索引
	返回值：   两坯料之间的硬度惩罚值，double型
*********************************************************/
double Hardpanish(SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance)
{
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;

														//待续

	return CityDistance.m_hdPanish;
}
/*********************************************************
	Widethpanish()——计算宽度度惩罚值
	输入参数： 1、FromCityIndex		源城市的索引/前一坯料索引
			   2、ToCityIndex		目标城市的索引/后一坯料索引
	返回值：   两坯料之间的宽度惩罚值，double型
*********************************************************/
double Widethpanish(SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance)
{
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;	

														//待续
	return CityDistance.m_wPanish;
}
/*********************************************************
	Gaugepanish()——计算厚度惩罚值
	输入参数： 1、FromCityIndex		源城市的索引/前一坯料索引
			   2、ToCityIndex		目标城市的索引/后一坯料索引
	返回值：   两坯料之间的厚度惩罚值，double型
*********************************************************/
double Gaugepanish(SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance)
{
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;
													
														//待续

	return CityDistance.m_hdPanish;
}

/*********************************************************
	CityLocation()——系数计算
	输入参数： 1、FromCityIndex		源城市的索引/前一坯料索引
			   2、ToCityIndex		目标城市的索引/后一坯料索引
	返回值：   坯料的位置int *型

  根据城市编号，查找在路径中的所在位置
*********************************************************/
 int * CityLocation( SYCity &City )
 {
	int *m_Location;
		
	m_Location = find(vecCityRouter.begin(),vecCityRouter.end(),City.m_nIndex);
	
	return m_Location;
 }

/*********************************************************
	Xij()——系数计算
	输入参数： 1、FromCityIndex		源城市的索引/前一坯料索引
			   2、ToCityIndex		目标城市的索引/后一坯料索引
	返回值：   两坯料之间Xij系数，int型

  根据城市编号，查找在路径中的所在位置，进而比较位置的前后，判断Xij值
*********************************************************/
int Xij(SYCity &FromCity, SYCity &ToCity )
{		
	if( FromCity.m_nIndex!=ToCity.m_nIndex && (CityLocation( ToCity )-CityLocation( FromCity ))==1 )
	{
		return 1;	
	}	

	else 
	{
		return 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;

}*/

double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance )
{
	int m_xij;
	m_xij = Xij(FromCity, ToCity);
	CityDistance.m_nFromCity = FromCity.m_nIndex;
	CityDistance.m_nToCity = ToCity.m_nIndex;
	if(m_xij)
	{
		CityDistance.m_fDistance = (CityDistance.m_hdPanish+CityDistance.m_wPanish+CityDistance.m_gPanish)*m_xij;
	}
	else
	{
		CityDistance.m_fDistance = 0.0;
	}

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

		vecCityRouter.clear();
		vecCityRouter = CityRouter;
		////这里的意思是第一次生成城市行走路径的时候完全按照城市号的顺序进行
		////下面函数是随机生成的城市行走路径
//	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;	////随机数除以城市数的余数-1
		if( swapA >= 0 )				////选取不为负的数
			break;
	}

	while(1)
	{
		swapB = (rand()%CityNumber)-1;	////随机数除以城市数的余数-1
		if( swapA != swapB && swapB >= 0 )////如果swapA不等于swapB并且swapB不为负，将路径上的位置
		{								  ////swapA与swapB的城市位置互换
			int tmp = CityRouter[swapA];
			CityRouter[swapA] = CityRouter[swapB];
			CityRouter[swapB] = tmp;
			break;
		}
	}
	vecCityRouter.clear();
	vecCityRouter = CityRouter;
}

/*********************************************************
	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坐标
			   4、coordy				城市z坐标
	返回值：  空 
*********************************************************/
void GetCoordinatebyCityIndex( int cityindex, double &coordx, double &coordy, double &coordz )
{
	coordx = 0.0;
	coordy = 0.0;
	coordz = 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;
			coordz = iter_city->m_Coordinate.m_fcodz;
		}
	}
}

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

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