人工智能实验报告02 邹维韬

实验2.TSP问题的遗传算法实现100112062012302516邹维韬内容:结合家乡交通网络图作业,实现基于遗传算法的遍历方案。要求:

熟练掌握遗传算法的原理及应用描述：旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。实验代码#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<time.h>#defineINFINITY100000000//无穷大#definecities20//城市的个数#definepc0.8//交配概率#definepm0.01//变异概率#definenum15//种群的大小#defineMAX_VEX_NUM20#defineMAX_INT10000000#defineTRUE1#defineFALSE0#defineNOTHING-1intD[MAX_VEX_NUM];intfinal[MAX_VEX_NUM];intprevious[MAX_VEX_NUM];intMAXX;//迭代次数intbestsolution;//最优染色体intdistance[cities][cities];//城市之间的距离intShortestPath(inta,intb)//最短路径{ inti,j,min,v; for(i=0;i<MAX_VEX_NUM;i++){ D[i]=0; final[i]=0; previous[i]=-1; } /*初始化*/ for(i=0;i<MAX_VEX_NUM;i++) { D[i]=distance[a][i]; final[i]=FALSE; previous[i]=NOTHING; } D[0]=0; final[0]=TRUE;/*初始化v0顶点属于S集*/ for(i=1;i<MAX_VEX_NUM;i++)/*进行MAX_VEX_NUM-1次循环*/ { min=MAX_INT;/*当前所知据v0的最短距离*/ for(j=0;j<MAX_VEX_NUM;j++) { if(final[j]==FALSE){ if(min>D[j]){ min=D[j]; v=j; } } } final[v]=TRUE; D[0]=0; if(i==1) { previous[v]=0; } for(j=0;j<MAX_VEX_NUM;j++){ if(!final[j])/*第j个顶点在V-S中*/ { if(D[j]>(distance[v][j]+min)) { D[j]=distance[v][j]+min;/*修改D[j]*/ previous[j]=v; } else { if(distance[0][j]!=MAX_INT) previous[j]=0; } } } } returnD[b];}structgroup//染色体的结构{ intcity[cities];//城市的顺序 intadapt;//适应度 doublep;//在种群中的幸存概率}group[num],grouptemp[num];//初始化城市距离voidinitCity(){ inti,j; memset(distance,0,sizeof(distance)); //srand((unsigned)time(NULL)); for(i=0;i<cities;i++) { for(j=i+1;j<cities;j++) { distance[i][j]=INFINITY; distance[j][i]=distance[i][j]; } } distance[0][1]=116;//为省去小数点，城市距离单位为0.1千米 distance[0][6]=135; distance[0][7]=126; distance[1][0]=116; distance[1][2]=179; distance[1][6]=198; distance[2][1]=179; distance[2][3]=146; distance[3][2]=146; distance[3][4]=104; distance[4][3]=104; distance[3][5]=161; distance[5][3]=161; distance[4][5]=191; distance[5][4]=191; distance[5][6]=182; distance[6][5]=182; distance[5][7]=175; distance[7][5]=175; distance[6][8]=108; distance[8][6]=108; distance[7][9]=194; distance[9][7]=194; distance[9][10]=136; distance[10][9]=136; distance[6][11]=180; distance[11][6]=180; distance[8][10]=113; distance[10][8]=113; distance[8][14]=112; distance[14][8]=112; distance[10][14]=114; distance[14][10]=114; distance[8][11]=155; distance[11][8]=155; distance[8][12]=159; distance[12][8]=159; distance[11][13]=178; distance[13][11]=178; distance[12][13]=163; distance[13][12]=163; distance[14][15]=140; distance[15][14]=140; distance[15][16]=150; distance[16][15]=150; distance[16][17]=166; distance[17][16]=166; distance[10][17]=142; distance[17][10]=142; distance[14][17]=139; distance[17][14]=139; distance[17][18]=162; distance[18][17]=162; distance[18][19]=167; distance[19][18]=167; distance[17][19]=179; for(i=0;i<cities;i++) { for(j=0;j<cities;j++) { distance[i][j]=ShortestPath(i,j); } } //打印距离矩阵}//随机产生初始种群voidgroupproduce(){ inti,j,t,k,flag; for(i=0;i<num;i++)//初始化 for(j=0;j<cities;j++) group[i].city[j]=-1; srand((unsigned)time(NULL)); for(i=0;i<num;i++) { //产生23个不相同的数字 for(j=0;j<cities;) { t=rand()%cities; flag=1; for(k=0;k<j;k++) { if(group[i].city[k]==t) { flag=0; break; } } if(flag) { group[i].city[j]=t; j++; } } } //打印种群基因}//评价函数,找出最优染色体voidassess(){ inti,j; intn1,n2; intsumdistance,biggestsum=0; doublebiggestp=0; for(i=0;i<num;i++) { sumdistance=0; for(j=1;j<cities;j++) { n1=group[i].city[j-1]; n2=group[i].city[j]; sumdistance+=distance[n1][n2]; } group[i].adapt=sumdistance;//每条染色体的路径总和 biggestsum+=sumdistance;//种群的总路径 } //计算染色体的幸存能力,路径越短生存概率越大 for(i=0;i<num;i++) { group[i].p=1-(double)group[i].adapt/(double)biggestsum; biggestp+=group[i].p; } for(i=0;i<num;i++) group[i].p=group[i].p/biggestp;//在种群中的幸存概率,总和为1 //求最佳路径 bestsolution=0; for(i=0;i<num;i++) if(group[i].p>group[bestsolution].p) bestsolution=i; //打印适应度 for(i=0;i<num;i++) printf("染色体%d的适应度与生存概率分别为%4d%.4f\n",i,group[i].adapt,group[i].p); printf("\n当前种群的最优染色体是%d号染色体组合，适应度为:%4d\n\n",bestsolution,group[bestsolution].adapt);}//选择voidselect(){ inti,j,temp; doublegradient[num];//梯度概率 doublexuanze[num];//选择染色体的随机概率 intxuan[num];//选择了的染色体 srand((unsigned)time(NULL)); //初始化梯度概率 for(i=0;i<num;i++) { gradient[i]=0.0; xuanze[i]=0.0; } gradient[0]=group[0].p; for(i=1;i<num;i++) gradient[i]=gradient[i-1]+group[i].p; //随机产生染色体的存活概率 for(i=0;i<num;i++) { xuanze[i]=(rand()%100); xuanze[i]/=100; } //选择能生存的染色体 for(i=0;i<num;i++) { for(j=0;j<num;j++) { if(xuanze[i]<gradient[j]) { xuan[i]=j;//第i个位置存放第j个染色体 break; } } } //拷贝种群 for(i=0;i<num;i++) { grouptemp[i].adapt=group[i].adapt; grouptemp[i].p=group[i].p; for(j=0;j<cities;j++) grouptemp[i].city[j]=group[i].city[j]; } //数据更新 for(i=0;i<num;i++) { temp=xuan[i]; group[i].adapt=grouptemp[temp].adapt; group[i].p=grouptemp[temp].p; for(j=0;j<cities;j++) group[i].city[j]=grouptemp[temp].city[j]; }}//交配,对每个染色体产生交配概率,满足交配率的染色体进行交配//交配,对每个染色体产生交配概率,满足交配率的染色体进行交配voidcross(){ inti,j,k,kk; intt;//参与交配的染色体的个数 intpoint1,point2,temp;//交配断点 intpointnum; inttemp1,temp2; intmap1[cities],map2[cities]; doublejiaopeip[num];//染色体的交配概率 intjiaopeiflag[num];//染色体的可交配情况 intkkk,flag=0; //初始化 for(i=0;i<num;i++) { jiaopeiflag[i]=0; } //随机产生交配概率 srand((unsigned)time(NULL)); for(i=0;i<num;i++) { jiaopeip[i]=(rand()%100); jiaopeip[i]/=100; } //确定可以交配的染色体 t=0; for(i=0;i<num;i++) { if(jiaopeip[i]<pc) { jiaopeiflag[i]=1; t++; } } t=t/2*2;//t必须为偶数 //产生t/2个0-9交配断点 srand((unsigned)time(NULL)); temp1=0; //temp1号染色体和temp2染色体交配 for(i=0;i<t/2;i++) { point1=rand()%cities;//交配点1 point2=rand()%cities;//交配点2 //选出一个需要交配的染色体1 for(j=temp1;j<num;j++) { if(jiaopeiflag[j]==1) { temp1=j; break; } } //选出另一个需要交配的染色体2与1交配 for(j=temp1+1;j<num;j++) { if(jiaopeiflag[j]==1) { temp2=j; break; } } //进行基因交配 if(point1>point2)//保证point1<=point2 { temp=point1; point1=point2; point2=temp; } //初始化 memset(map1,-1,sizeof(map1)); memset(map2,-1,sizeof(map2)); //断点之间的基因产生映射 for(k=point1;k<=point2;k++) { map1[group[temp1].city[k]]=group[temp2].city[k]; map2[group[temp2].city[k]]=group[temp1].city[k]; } //断点两边的基因互换 for(k=0;k<point1;k++) { temp=group[temp1].city[k]; group[temp1].city[k]=group[temp2].city[k]; group[temp2].city[k]=temp; } for(k=point2+1;k<cities;k++) { temp=group[temp1].city[k]; group[temp1].city[k]=group[temp2].city[k]; group[temp2].city[k]=temp; } //printf("处理冲突---------------------\n"); //处理染色体1产生的冲突基因 for(k=0;k<point1;k++) { for(kk=point1;kk<=point2;kk++) { if(group[temp1].city[k]==group[temp1].city[kk]) { group[temp1].city[k]=map1[group[temp1].city[k]]; for(kkk=point1;kkk<=point2;kkk++) { if(group[temp1].city[k]==group[temp1].city[kkk]) { flag=1; break; } } if(flag==1) { kk=point1-1; flag=0; } else { flag=0; break; } } } } for(k=point2+1;k<cities;k++) { for(kk=point1;kk<=point2;kk++) { if(group[temp1].city[k]==group[temp1].city[kk]) { group[temp1].city[k]=map1[group[temp1].city[k]]; for(kkk=point1;kkk<=point2;kkk++) { if(group[temp1].city[k]==group[temp1].city[kkk]) { flag=1; break; } } if(flag==1) { kk=point1-1; flag=0; } else { flag=0; break; } } } } //处理2染色体产生的冲突基因 for(k=0;k<point1;k++) { for(kk=point1;kk<=point2;kk++) { if(group[temp2].city[k]==group[temp2].city[kk]) { group[temp2].city[k]=map2[group[temp2].city[k]]; for(kkk=point1;kkk<=point2;kkk++) { if(group[temp2].city[k]==group[temp2].city[kkk]) { flag=1; break; } } if(flag==1) { kk=point1-1; flag=0; } else { flag=0; break; } } } } for(k=point2+1;k<cities;k++) { for(kk=point1;kk<=point2;kk++) { if(group[temp2].city[k]==group[temp2].city[kk]) { group[temp2].city[k]=map2[group[temp2].city[k]]; for(kkk=point1;kkk<=point2;kkk++) { if(group[temp2].city[k]==group[temp2].city[kkk]) { flag=1; break; } } if(flag==1) { kk=point1-1; flag=0; } else { flag=0; break; } } } } temp1=temp2+1; }}//变异voidmutation(){ inti,j; intt; inttemp1,temp2,point; doublebianyip[num];//染色体的变异概率 intbianyiflag[num];//染色体的变异情况 for(i=0;i<num;i++)//初始化 bianyiflag[i]=0; //随机产生变异概率 srand((unsigned)time(NULL)); srand((unsigned)time(NULL)); for(i