//?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