ga_tsp.h

50个城市以内的TSP问题, 用遗传算法, 算子采用了pmx和ox算子。

//这里用来控制: 种群规模,城市数和演化代数
#define POP		2000    //种群规模
#define CNUM	50     //城市数
#define Gen		10000  //演化代数
#define REDRAW	5     //隔几代重绘窗口
#define PC		0.25    //杂交率
#define PM		0.2    //变异

//实现了两个杂交算子, 
//这里用来控制选择哪个杂交算子
//#define PMX_OPERATER  //PMX算子

//定义来发给主窗体的消息, 用于重绘;
#define  WM_USER1  100220

//执行遗传算法的函数, 供主窗体调用, 这是一个线程;
DWORD WINAPI EvolveProc(LPVOID lpParameter);

//用来产生min到max之间的一个四位小数的随机数
double AverageRandom(double min,double max);


//遗传算法类
class CGA_TSP
{
public:
	CGA_TSP();
	~CGA_TSP();

	//种群初始化
	void InitPopulation();

	//评估算子
	void Evaluation();

	//保留最优解
	void KeepTheBest();

	//轮盘选择
	void Rotate_Wheel_Select();

	//PMX杂交算子
	void PMX();

	//OX算子;
	void OX();

	//变异算子, 采用的是倒位变异;
	void Mutation(int);

	//计算单条路径长度
	double CalPathLongth(int p[CNUM]);

	//类似于模拟退火, 用来决定变异若后代比父体差时是否能取代父体
	bool MY_SA(int t);

public:
	//城市平面位置(取0-500的方形平面内的随机点)
	POINT city[CNUM];

	//种群
	int   path[POP][CNUM];

	//用于保存当前最优个体, 不是理论上的最优解
	int   bestPath[CNUM];

	//种群中各个体的代价值
	double  distance[POP];

	//最优个体的代价值
	double  lowestDistance;
};