遗传算法解决TSP问题全

遗传算法解决TSP问题···································································································································

#include 
#include 
#include 
#include “math.h“
#include “time.h“
#include 
#include 
#define CITY_NUM 38     //城市数，城市编号是0~CITY_NUM-1
#define POPSIZE 300        //种群个体数
#define MAXVALUE 10000000   //路径最大值上限
#define N 100000//需要根据实际求得的路径值修正
unsigned seed=（unsigned）time（0）;
double Hash[CITY_NUM+1];
typedef struct CityPosition
{
	double x;
	double y;
}CityPosition;

CityPosition CityPos[38]={
    {11003.61110042102.500000}{11108.61110042373.888900}{11133.33330042885.833300}{11155.83330042712.500000}{11183.33330042933.333300}{11297.50000042853.333300}{11310.27780042929.444400}{11416.66670042983.333300}{11423.88890043000.277800}{11438.33330042057.222200}{11461.11110043252.777800}{11485.55560043187.222200}{11503.05560042855.277800}{11511.38890042106.388900}{11522.22220042841.944400}{11569.44440043136.666700}{11583.33330043150.000000}{11595.00000043148.055600}{11600.00000043150.000000}{11690.55560042686.666700}{11715.83330041836.111100}{11751.11110042814.444400}{11770.27780042651.944400}{11785.27780042884.444400}{11822.77780042673.611100}{11846.94440042660.555600}{11963.05560043290.555600}{11973.05560043026.111100}{12058.33330042195.555600}{12149.44440042477.500000}{12286.94440043355.555600}{12300.00000042433.333300}{12355.83330043156.388900}{12363.33330043189.166700}{12372.77780042711.388900}{12386.66670043334.722200}{12421.66670042895.555600}{12645.00000042973.333300}
};

double CityDistance[CITY_NUM][CITY_NUM];//城市距离词典

typedef struct{
	int colony[POPSIZE][CITY_NUM+1];//城市种群默认出发城市编号为0，则城市编号的最后一个城市还应该为0
	double fitness[POPSIZE];// 每个个体的适应值，即1/Distance[POPSIZE]
	double Distance[POPSIZE];//每个个体的总路径
	int BestRooting[CITY_NUM+1];//最优城市路径序列
	double BestFitness;//最优路径适应值
	double BestValue;//最优路径长度
	int BestNum;
}TSP*PTSP;

/*计算城市距离词典CityDistance[i][j]*/
void CalculatDist（）
{
	int ij;
	double temp1temp2;
	for（i=0;i		for（j=0;j<=CITY_NUM;j++）{//最后一个城市还应该返回到出发节点
			temp1=CityPos[j].x-CityPos[i].x;
			temp2=CityPos[j].y-CityPos[i].y;
			CityDistance[i][j]=sqrt（temp1*temp1+temp2*temp2）;
		}
	}
}
/*数组复制*/
void copy（int a[]int b[]）
{
	int i=0;
	for（i=0;i	{
		a[i]=b[i];
	}
}

/*用来检查新生成的节点是否在当前群体中，0号节点是默认出发节点和终止节点*/
bool check（TSP &cityint popint numint k）
{
	int i;
	for（i=0;i<=num;i++）{
		if（k==city.colony[pop][i]）
			return true;//新生成节点存在于已经生成的路径中
	}
	return false;//新生成节点没有存在于已经生成的路径中
}

/****************************种群初始化，即为city.colony[i][j]赋值****************************/
void InitColony（TSP &city）
{
	int ijr;
	for（i=0;i		city.colony[i][0]=0;
		city.colony[i][CITY_NUM]=0;
		city.BestValue=MAXVALUE;
		city.BestFitness=0;//适应值越大越好
	}

	for（i=0;i	{
		for（j=1;j		{
			r=rand（）%（CITY_NUM-1）+1;//产生1～CITY_NUM-1之间的随机数
			while（check（cityijr））//随机产生城市序号，即为city.colony[i][j]赋值

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-07-11 17:10  遗传算法解决TSP问题（全）\
     文件        9576  2017-07-09 17:25  遗传算法解决TSP问题（全）\data.txt
     文件        9636  2017-07-10 15:22  遗传算法解决TSP问题（全）\TSP.cpp