遗传算法解决TSP.doc

代码： #include stdio.h #include stdlib.h #include time.h #define MAX 100 int GetDistance(int, int []); //计算路径总长度 float FitnessFun(int, int []); //适应度函数 void RandomMatrix(int); //随机矩阵，表示两点之间的距离 void ShowMatrix(int); //显示距离矩阵 void RandomArray(int, int, int []); //随机序列，表示染色体 void ShowArray(int, int []); //显示随机序列 void GetInitialPopulation(int ***, int, int); //获得初始种群 void TSP(int, int, int ***, float, float); //遗传算法解决TSP问题 float * GetFitness(int **, int, int); //计算每个染色体的适应度 int ** GetNextBySe_Re(float *, int **, int); //获得由选择——复制产生的下一代群体 int ** GetNextByCro(float, int **, int); //获得由交叉产生的下一代群体 void GetNextByMut(float, int ***, int, int); //获得由变异产生的下一代群体 int GetOppose(int *[], int, int); //变异时取得相反数 int D[MAX][MAX]; //距离矩阵 int main(int argc, char *argv[]) { int N; //种群规模 int L; //城市个数 int **S; //种群 float Pc = 0.55; //交叉率 float Pm = 0.005; //变异率 time_t t; srand((unsigned)time(t)); printf(请输入城市个数(=%d)：, MAX); scanf(%d, L); printf(请输入初始种群规模：); scanf(%d, N); RandomMatrix(L); printf(距离矩阵:\n); ShowMatrix(L); TSP(N, L, S, Pc, Pm); return 0; } int GetDistance(int L, int chromosome[]) //计算路径总长度 { int i, distance=0; for(i=0; iL; i++) { distance += D[chromosome[i]][chromosome[(i+1)%L]]; } return distance; } float FitnessFun(int L, int chromosome[]) //适应度函数 { int distance; distance = GetDistance(L, chromosome); return (float)1/(float)distance; } void RandomMatrix(int L) //随机矩阵，表示两点之间的距离 { int i, j; for(i=0; iL; i++) { for(j=0; j=i; j++) { D[i][j] = D[j][i] = rand()%MAX; if(i != j D[i][j] == 0) { j--; } if(i == j) { D[i][j] = 0; } } } } void ShowMatrix(int L) //显示距离矩阵 { int i, j; for(i=0; iL; i++) { for(j=0; jL; j++) { printf(%4d, D[i][j]); } printf(\n); } } void RandomArray(int L, int N, int chromosome[]) //随机序列，表示染色体 { int i, j, r, flag, mutex; chromosome[0] = (rand()%N+1); for(i=1; iL; i++) { flag = 1; while(flag) { r = (rand()%N+1); mutex = 1; for(j=0; ji; j++) {