#include?
#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;

const?int?DIMENSION=535;				//城市個數
const?int?PERSONS=1000;					//種群個數
const?int?crosspob=0.75;				//決定是否交叉的概率
const?double?mute=0.03;					//變異概率
const?int?iternum=100;				//計劃迭代次數
ofstream?out（“optimal_solution.txt“）;
int?nmutations;
#define?max（ab）?a>b?a:b
#define?min（ab）?astruct?chrom{??
	unsigned?int?gene[DIMENSION-1];		//固定第一個城市??
	int?fitness;						//該路徑的長度
};										//表征每個染色體特征
struct?Population{???
	struct?chrom?person[PERSONS];		//有這么多個染色體???
	double?fitsum;						//適應值之和??
	int?minfit;							//最小適應度的下標
};										//種群的一些屬性

//function?declare?here*********************************
int?select（Population*?p）;
bool?Flip（float?prob）;
void?Cross（unsigned?int*?table1unsigned?int*?table2）;
void?Mutation（unsigned?int*?table）;
void?crossover（Population*?poldPopulation*?pnewint?parent1int?parent2int?i）;
void?UpdateGen（Population*?poldPopulation*?pnew）;
void?shuffle（unsigned?int*?table）;
void?ComputeFitness（Population*?pint*?distance）;
void?InitData（Population*?pint*?distance）;
//function?declare?here*********************************

bool?Flip（float?pro）
{?
	float?temp;??
	temp=（float）rand（）/（float）RAND_MAX;??
	if（temp<=pro）???return?true;??
	else???return?false;
}

int?find（unsigned?int*?tableunsigned?int?aint?startint?end）		//返回a在數組table中的下標
{????
	for（int?i=start;i<=end;i++）????
	{????
		if（a==table[i]）?????
			return?i;?
	}?
	return?-1;
}

void?exchange（unsigned?int*?tableint?index1int?index2）
{???
	unsigned?int?temp=table[index1];???
	table[index1]=table[index2];???
	table[index2]=temp;
}

void?Cross（unsigned?int*?table1unsigned?int*?table2）		//對兩個基因進行交叉操作，生成子代的兩個基因
{
	int?rand1=rand（）%（DIMENSION-101）+50;					//assure?rand1?range?from?2?to?DIMENSION-4left?and?right?side?reserve?at?least?50?elements?
	int?rand2=rand1;?
	do?
	{??
		rand2=rand（）%（DIMENSION-101）+50;
	}while（rand1==rand2）;									//assure?rand1?differ?from?rand2
	const?int?start=min（rand1rand2）;?
	const?int?end=max（rand1rand2）;?
	for（int?i=start;i<=end;i++）?
	{????
		unsigned?int?t1=table1[i];??
		unsigned?int?t2=table2[i];???????
		if（t1!=t2）??
		{??????
			int?a1=find（table1t20DIMENSION-2）;???
			exchange（table1a1i）;??????
			int?b1=find（table2t10DIMENSION-2）;??????????
			exchange（table2b1i）;??
		}
	}
}

void?Mutation（unsigned?int*?table）							//依據一定概率對基因進行變異，變異操作是2-opt的
{??????
	bool?mut=Flip（mute）;???
	if（mut）													//如果發生了變異???
	{??
		nmutations++;????
		int?rand1=rand（）/（DIMENSION-1）;????
		int?rand2;????
		do????
		{???????
			rand2=rand（）/（DIMENSION-1）;????
		}while（rand1==rand2）;????
		exchange（tablerand1rand2）;???
	}
	return;
}

void?crossover（Population*?poldPopulation*?pnewint?parent1int?parent2int?i）			//對群體中的兩個個體雜交，生成新的個體并將新個體保存進新的種群里
{??
	struct?chrom*?ch1=&（

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????8727??2012-11-19?16:11??TSPyichuan.cpp

-----------?---------??----------?-----??----

?????????????????8727????????????????????1