tsp遗传算法

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<math.h> #include<iostream> using namespace std; #define M 10 // 种群规模 #define N 31 // 省会、首府城市数量 #define T 10000 // 遗传代数 #define EARTH_RADIUS 6378.137 #define PI acos(-1) int bestOne[N]; // 最优个体 int bestDistance=100000;//最优路径 int bestT;//最优代数 int t;//当前代数 int oldPopulation[M][N]; // 父种群 int newPopulation[M][N]; // 子种群 int fit[M]; // 种群适应度 double lfit[M]; // 种群累计适应度 double pCorss=0.8; // 交叉概率 double pMutate=0.1; // 变异概率 //中国31个省会、首府城市的经纬度 double city_pos[N][2] = { {103.73, 36.03},{101.74, 36.56},{104.06, 30.67},{114.48, 38.03}, {102.73, 25.04},{106.71, 26.57},{114.31, 30.52},{113.65, 34.76}, {117.00, 36.65},{118.78, 32.04},{117.27, 31.86},{120.19, 30.26}, {115.89, 28.68},{119.30, 26.08},{113.23, 23.16},{113.00, 28.21}, {110.35, 20.02},{123.38, 41.80},{125.35, 43.88},{126.63, 45.75}, {112.53, 37.87},{108.95, 34.27},{87.68, 43.77}, {116.46, 39.92}, {121.48, 31.22},{106.54, 29.59},{117.20, 39.13},{111.65, 40.82}, {108.33, 22.84},{91.11, 29.97}, {106.27, 38.47} }; //省会城市名称 string city_name[N]={ "兰州","西宁","成都","石家庄","昆明","贵阳","武汉","郑州","济南","南京", "合肥","杭州","南昌","福州","广州","长沙","海口","沈阳","长春","哈尔滨", "太原","西安","乌鲁木齐","北京","上海","重庆","天津","呼和浩特","南宁","拉萨", "银川" }; double rad(double d) { return d * PI / 180.0; } void copyGh(int k, int kk) { int i; for (i = 0; i < N; i++) { newPopulation[k][i] = oldPopulation[kk][i]; } } double getDistance(double lat1, double lng1, double lat2, double lng2) { double radLat1 = rad(lat1); double radLat2 = rad(lat2); double a = radLat1 - radLat2; double b = rad(lng1) - rad(lng2); double s = 2 * asin(sqrt(pow(sin(a/2),2) + cos(radLat1)*cos(radLat2)*pow(sin(b/2),2))); s = s * EARTH_RADIUS; s = round(s * 10000) / 10000; return s; } /将路径作为种群适应度返回 double pathLen(int * arry){ double path = 0; // 初始化路径长度 int first_city = arry[0]; // 定位到第一个数字(城市序号) for(int i=0;i<N-1;i++) { int this_city = arry[i]; int next_city = arry[i+1]; double dis = getDistance(city_pos[this_city][0],city_pos[this_city][1], city_pos[next_city][0],city_pos[next_city][1]); path += dis; } int last_city = arry[N-1]; // 最后一个城市序号 double last_dis = getDistance(city_pos[first_city][0],city_pos[first_city][1], city_pos[last_city][0],city_pos[last_city][1]); path = path + last_dis; return path; // 返回总的路径长度 } /* 初始化种群 */ void init(){ int i,j,k; for(i=0;i<M;i++){ double r1 = ((double)rand())/(RAND_MAX+1.0); int pos1 = (int)(N*r1); int j; oldPopulation[i][0]=pos1; for(j=1;j<N;){ double r2 = ((double)rand())/(RAND_MAX+1.0); int pos2 = (int)(N*r2); oldPopulation[i][j]=pos2; for(k=0;k<j;++k){ if(oldPopulation[i][k]==oldPopulation[i][j]) break; } if(j==k) j++; } } } //计算种群的累积概率 void countLRate(){ double sumRate=0; for(int k=0;k<M;k++){ sumRate+=fit[k]; } lfit[0]=(double)(fit[0]/sumRate); for(int k=1;k<M;k++){ lfit[k]=(double)(fit[k]/sumRate+lfit[k-1]); } } void variation(int k)//变异 { double r1 = ((double)rand())/(RAND_MAX+1.0); double r2 = ((double)rand())/(RAND_MAX+1.0); int pos1 = (int)(N*r1); //第一个交叉点的位置 int pos2 = (int)(N*r2); while(pos1==pos2){ r1 = ((double)rand())/(RAND_MAX+1.0); pos1 = (int)(N*r1); } int temp = newPopulation[k][pos1]; newPopulation[k][pos1] = newPopulation[k][pos2]; newPopulation[k][pos2] = temp; // 交换两个点 } //挑选某代种群最优个体，直接复制到子代 //前提是种群的适应度已经计算出来 void selectBest(){ int k, i, maxid; int maxevaluation; maxid = 0; maxevaluation = fit[0]; for (k = 1; k < M; k++) { if (maxevaluation > fit[k]) { maxevaluation = fit[k]; maxid = k; } } if (bestDistance > maxevaluation) { bestDistance = maxevaluation; bestT = t;// 最好的染色体出现的代数; for (i = 0; i < N; i++) { bestOne[i] = oldPopulation[maxid][i]; } } // System.out.println("代数 " + t + " " + maxevaluation); // 复制染色体，k表示新染色体在种群中的位置，kk表示旧的染色体在种群中的位置 copyGh(0, maxid);// 将当代种群中适应度最高的染色体k复制到新种群中，排在第一位0 } /* 轮盘赌挑选子代个体 */ void selectChild(){ int k, i, selectId; double ran1; // 挑选概率 for (k = 1; k < M; k++) { ran1 = ((double)rand())/(RAND_MAX+1.0); for (i = 0; i < M; i++) { if (ran1 <= lfit[i]) { break; } } selectId = i; copyGh(k, selectId); } } bool hasElement(int* a, int b) { int len = sizeof(a) / sizeof(a[0]); for (int i = 0; i < len; i++) { if (a[i] == b) { return true; } } return false; } //交叉 void orderCrossover(int k1, int k2) { int child1[N]; int child2[N]; double r1 = ((double)rand())/(RAND_MAX+1.0); double r2 = ((double)rand())/(RAND_MAX+1.0); int ran1 = (int)(r1*N); int ran2 = (int)(r2*N); while (ran1 == ran2) { r2 = ((double)rand())/(RAND_MAX+1.0); ran2 = (int)(r2*N); } if (ran1 > ran2) { int temp = ran1; ran1 = ran2; ran2 = temp; } for (int i = ran1; i <= ran2; i++) { // 生成子代交叉部分 child1[i] = newPopulation[k1][i]; child2[i] = newPopulation[k2][i]; } for (int i = 0; i < N; i++) { if (i >= ran1 && i <= ran2) { continue; } for (int j = 0; j < N; j++) { if (!hasElement(child1, newPopulation[k2][j])) { child1[i] = newPopulation[k2][j]; break; } } } for (int i = 0; i < N; i++) { if (i >= ran1 && i <= ran2) { continue; } for (int j = 0; j < N; j++) { if (!hasElement(child2, newPopulation[k1][j])) { child2[i] = newPopulation[k1][j]; break; } } } } //进化 void evolution() { int k; selectBest(); selectChild(); double r; for (k = 0; k < M; k = k + 2) { r = ((double)rand())/(RAND_MAX+1.0); // 交叉概率 if (r < pCorss) { // 交叉 orderCrossover(k, k + 1); } else { r = ((double)rand())/(RAND_MAX+1.0); // 变异概率 if (r < pMutate) { variation(k); } r = ((double)rand())/(RAND_MAX+1.0);// 变异概率 if (r < pMutate) { variation(k + 1); } } } } int main(){ srand((unsigned)time(NULL));//初始化随机数种子 time_t start,finish; start = clock();//程序开始时间 int k,i; init(); // 计算初始化种群中各个个体的累积概率，lfit[max] countLRate(); cout<<"初代种群: "; for (k = 0; k < M; k++) { for (i = 0; i < N; i++) { cout<<oldPopulation[k][i]<<" "; } cout<<endl; } for (t = 0; t < T; t++) { evolution(); // 将新种群newGroup复制到旧种群oldGroup中，准备下一代进化 for (k = 0; k < M; k++) { for (i = 0; i < N; i++) { oldPopulation[k][i] = newPopulation[k][i]; } } // 计算种群适应度 for (k = 0; k < M; k++) { fit[k] = pathLen(oldPopulation[k]); } // 计算种群中各个个体的累积概率 countLRate(); } cout<<"末代种群: "; for (k = 0; k < M; k++) { for (i = 0; i < N; i++) { cout<<oldPopulation[k][i]<<" "; } cout<<endl; } cout<<bestDistance<<endl; cout<<"最佳个体: "; for (i = 0; i < N; i++) { cout<<bestOne[i]<<" "; } cout<<endl; finish=clock(); cout<<"花费时间： "; cout<<(finish-start)*1000<<"ms"; return 0; }