遗传算法求解TSP旅行商问题C语言源代码

遗传算法求解TSP旅行商问题，C语言源代码。人工智能经典算法

// TSPGA.cpp : Defines the entry point for the console application.
//用遗传算法求解TSP问题的程序模板

#include 
#include 
#include 
#include “math.h“
#include “time.h“

#define CITY_NUM 30     //城市编号是0~CITY_NUM-1
#define POPSIZE 100
#define MAXVALUE 10000   //路径越短越好
#define N 10000//需要根据实际求得的路径值修正
unsigned seed=（unsigned）time（0）;


int Hash[CITY_NUM+1];
typedef struct CityPosition
{
	int x;
	int y;
}CityPosition;
// CityPosition CityPos[10]={{877}{9138}{8346}{7144}{6460}{6858}{8369}{8776}{7478}{7171}};


CityPosition CityPos[30]={{877}{9138}{8346}{7144}{6460}{6858}{8369}{8776}{7478}{7171}
{5869}{5462}{5167}{3784}{4194}{299}{764}{2260}{2562}{1854}{450}{1340}{1840}
{2442}{2538}{4126}{4521}{4435}{5835}{6232}};

double CityDistance[CITY_NUM][CITY_NUM];

typedef struct{
	int colony[POPSIZE][CITY_NUM+1];//城市种群默认出发城市编号为0，则城市编号的最后一个城市还应该为0
	double fitness[POPSIZE];// 路径适应值

	double Distance[POPSIZE];//路径实际长度
	int BestRooting[CITY_NUM+1];//最优城市路径序列
	double BestFitness;//最优路径适应值
	double BestValue;//最优路径长度
	int BestNum;
}TSP*PTSP;

void CalculatDist（）
{
	int ij;
	int 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];
	}
}

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

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））
			{
				r=rand（）%（CITY_NUM-1）+1;
			}
			   
			city.colony[i][j]=r;
		}
	}
}

void CalFitness（TSP &city）
{
	int ij;
	int startend;
	int Best=0;
	for（i=0;i		city.Distance[i]=0;
		for（j=1;j<=CITY_NUM;j++）{
			start=city.colony[i][j-1];end=city.colony[i][j];
			city.Distance[i]=city.Distance[i]+CityDistance[start][end];
		}

	//	city.fitness[i]=pow（1.1N/city.Distance[i]）;
		city.fitness[i]=N/city.Distance[i];
		if（city.fitness[i]>city.fitness[Best]）
			Best=i;
	}

	copy（city.BestRootingcity.colony[Best]）;
	city.BestFitness=city.fitness[Best];
	city.BestValue=city.Distance[Best];
	city.BestNum=Best;


}


void Select（TSP &city）
{//选择算子
	int TempColony[POPSIZE][CITY_NUM+1];
	int ijst;
	double GaiLv[POPSIZE];
	int SelectP[POPSIZE+1];
	double avg;
	double sum=0;
	for（i=0;i	{
		sum+=city.fitness[i];
	}
	fo

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      66560  2011-03-07 15:24  TSP\Debug\TSP.bsc

     文件     217144  2011-03-07 15:24  TSP\Debug\TSP.exe

     文件     255244  2011-03-07 15:24  TSP\Debug\TSP.ilk

     文件      15656  2010-12-16 16:31  TSP\Debug\TSP.obj

     文件     239716  2011-03-07 15:23  TSP\Debug\TSP.pch

     文件     525312  2011-03-07 15:24  TSP\Debug\TSP.pdb

     文件          0  2010-12-16 16:31  TSP\Debug\TSP.sbr

     文件      16318  2011-03-07 15:24  TSP\Debug\TSP2.obj

     文件          0  2011-03-07 15:24  TSP\Debug\TSP2.sbr

     文件      41984  2011-03-07 15:24  TSP\Debug\vc60.idb

     文件      53248  2011-03-07 15:24  TSP\Debug\vc60.pdb

     文件       6461  2010-12-16 16:31  TSP\TSP.CPP

     文件       4253  2010-12-16 18:28  TSP\TSP.dsp

     文件        514  2010-12-16 11:37  TSP\TSP.dsw

     文件      41984  2011-03-07 15:24  TSP\TSP.ncb

     文件      54784  2011-03-07 15:24  TSP\TSP.opt

     文件       1821  2011-03-07 15:24  TSP\TSP.plg

     文件       7393  2011-03-07 15:24  TSP\TSP2.cpp

     目录          0  2011-03-07 15:24  TSP\Debug

     目录          0  2011-03-07 15:24  TSP

----------- ---------  ---------- -----  ----

              1548392                    20