gasatsp.h

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

#include <vector>

/*///////////////////////////////////////////////
              SA 参数设置
///////////////////////////////////////////////*/
#define INITEMPER          1000    //初始温度
#define DECRATE            0.95    //温度下降系数
#define MALKOVLEN          1000    //马尔可夫链长度             

/*********************************************************
	#define宏定义——GA的参数设置
*********************************************************/
#define CROSSOVER_P				0.5					//交配概率
#define MUTATION_P				0.3					//变异概率
#define EVAL_BASE				0.5					//基于序评价基数
#define POP_CITYNUMBER_RATE		4					//群体个数与城市个数之比
#define FITNESS_MODE			1					//评价函数计算方式
#define CROSSOVER_MODE			2					//交叉方式
#define MUTATION_MODE			1					//变异方式
#define TOTAL_GENERATION		5000				//迭代次数

struct SYCoordinate
{
	SYCoordinate()
	{
		m_fcodx = 0.0;
		m_fcody = 0.0;
	}

	double m_fcodx;
	double m_fcody;
};

struct SYCity
{
	SYCity()
	{
		m_nIndex = 0;
		m_strName.Empty();
	}

	int m_nIndex;					//城市编号
	CString m_strName;				//城市名称
	SYCoordinate m_Coordinate;		//城市坐标
};

struct SYCityDistance
{
	SYCityDistance()
	{
		m_nFromCity = 0;
		m_nToCity = 0;
		m_fDistance = 0.0;
	}

	int m_nFromCity;				//源城市
	int m_nToCity;					//目标城市
	double m_fDistance;				//城市之间的距离
};

typedef std::vector<int>	CityRouterDef;

void CreateCityRouter( CityRouterDef &CityRouter );
void CreateCityRouter2opt( CityRouterDef &preCityRouter, CityRouterDef &CityRouter );
double CountTotalDistance( CityRouterDef &CityRouter );
double CountCityDistance( SYCity &FromCity, SYCity &ToCity, SYCityDistance &CityDistance );
double FindCityDistance( int FromCityIndex, int ToCityIndex );

struct SYRouter
{
	SYRouter()
	{
		CreateCityRouter( m_CityRouter );
		m_fTotalDistance = CountTotalDistance( m_CityRouter );
		m_fFitness = 0.0;
	}

	SYRouter( CityRouterDef &preCityRouter )
	{
		CreateCityRouter2opt( preCityRouter, m_CityRouter );
		m_fTotalDistance = CountTotalDistance( m_CityRouter );
		m_fFitness = 0.0;
	}

	void operator=(const SYRouter& srcRouter )
	{
		m_CityRouter = srcRouter.m_CityRouter;
		m_fTotalDistance = srcRouter.m_fTotalDistance;
		m_fFitness = 0.0;
	}

	CityRouterDef m_CityRouter;
	float m_fTotalDistance;
	float m_fFitness;
};

int OpenDataFile( CString &strFileName );
int OneIterGACompution(float currTemper);
double GetMinRouterFromPop( CString &strTemp );
int GetTotalGeneration();
void GetMinRouterFileStringFromPop( CString &strTemp );
void FormInitialPop();

SYRouter GetMinRouter();
SYRouter GetMaxRouter();
void ComputeFitness(float currTemper);
void GenerateNewPop(float currTemper);
void AddPop(int popIndex, float currentTemper);