智能作业1

SY1505319刘济基于遗传算法的TSP问题遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。TSP问题及旅行商问题,假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。下面用C语言模拟遗传算法模拟TSP问题，选取10个城市。代码如下:#includestdio.h#includestring.h#includestdlib.h#includemath.h#includetime.h#definecities10//城市的个数#defineMAXX100//迭代次数#definepc0.8//交配概率#definepm0.05//变异概率#definenum10//种群的大小intbestsolution;//最优染色体intdistance[cities][cities];//城市之间的距离structgroup//染色体的结构{intcity[cities];//城市的顺序intadapt;//适应度doublep;//在种群中的幸存概率}group[num],grouptemp[num];//随机产生cities个城市之间的相互距离voidinit(){inti,j;memset(distance,0,sizeof(distance));srand((unsigned)time(NULL));for(i=0;icities;i++){for(j=i+1;jcities;j++){distance[i][j]=rand()%100;distance[j][i]=distance[i][j];}}//打印距离矩阵printf(城市的距离矩阵如下\n);for(i=0;icities;i++){for(j=0;jcities;j++)printf(%4d,distance[i][j]);printf(\n);}}//随机产生初试群voidgroupproduce(){inti,j,t,k,flag;for(i=0;inum;i++)//初始化for(j=0;jcities;j++)group[i].city[j]=-1;srand((unsigned)time(NULL));for(i=0;inum;i++){//产生10个不相同的数字for(j=0;jcities;){t=rand()%cities;flag=1;for(k=0;kj;k++){if(group[i].city[k]==t){flag=0;break;}}if(flag){group[i].city[j]=t;j++;}}}//打印种群基因printf(初始的种群\n);for(i=0;inum;i++){for(j=0;jcities;j++)printf(%4d,group[i].city[j]);printf(\n);}}//评价函数,找出最优染色体voidpingjia(){inti,j;intn1,n2;intsumdistance,biggestsum=0;doublebiggestp=0;for(i=0;inum;i++){sumdistance=0;for(j=1;jcities;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;inum;i++){group[i].p=1-(double)group[i].adapt/(double)biggestsum;biggestp+=group[i].p;}for(i=0;inum;i++)group[i].p=group[i].p/biggestp;//在种群中的幸存概率,总和为1//求最佳路劲bestsolution=0;for(i=0;inum;i++)if(group[i].pgroup[bestsolution].p)bestsolution=i;//打印适应度for(i=0;inum;i++)printf(染色体%d的路径之和与生存概率分别为%4d%.4f\n,i,group[i].adapt,group[i].p);printf(当前种群的最优染色体是%d号染色体\n,bestsolution);}//选择voidxuanze(){inti,j,temp;doublegradient[num];//梯度概率doublexuanze[num];//选择染色体的随机概率intxuan[num];//选择了的染色体//初始化梯度概率for(i=0;inum;i++){gradient[i]=0.0;xuanze[i]=0.0;}gradient[0]=group[0].p;for(i=1;inum;i++)gradient[i]=gradient[i-1]+group[i].p;srand((unsigned)time(NULL));//随机产生染色体的存活概率for(i=0;inum;i++){xuanze[i]=(rand()%100);xuanze[i]/=100;}//选择能生存的染色体for(i=0;inum;i++){for(j=0;jnum;j++){if(xuanze[i]gradient[j]){xuan[i]=j;//第i个位置存放第j个染色体break;}}}//拷贝种群for(i=0;inum;i++){grouptemp[i].adapt=group[i].adapt;grouptemp[i].p=group[i].p;for(j=0;jcities;j++)grouptemp[i].city[j]=group[i].city[j];}//数据更新for(i=0;inum;i++){temp=xuan[i];group[i].adapt=grouptemp[temp].adapt;group[i].p=grouptemp[temp].p;for(j=0;jcities;j++)group[i].city[j]=grouptemp[temp].city[j];}//用于测试/*printf(-------------------------------\n);for(i=0;inum;i++){for(j=0;jcities;j++)printf(%4d,group[i].city[j]);printf(\n);printf(染色体%d的路径之和与生存概率分别为%4d%.4f\n,i,group[i].adapt,group[i].p);}*/}//交配,对每个染色体产生交配概率,满足交配率的染色体进行交配voidjiaopei(){inti,j,k,kk;intt;//参与交配的染色体的个数intpoint1,point2,temp;//交配断点intpointnum;inttemp1,temp2;intmap1[cities],map2[cities];doublejiaopeip[num];//染色体的交配概率intjiaopeiflag[num];//染色体的可交配情况for(i=0;inum;i++)//初始化jiaopeiflag[i]=0;//随机产生交配概率srand((unsigned)time(NULL));for(i=0;inum;i++){jiaopeip[i]=(rand()%100);jiaopeip[i]/=100;}//确定可以交配的染色体t=0;for(i=0;inum;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;it/2;i++){point1=rand()%cities;point2=rand()%cities;for(j=temp1;jnum;j++)if(jiaopeiflag[j]==1){temp1=j;break;}for(j=temp1+1;jnum;j++)if(jiaopeiflag[j]==1){temp2=j;break;}//进行基因交配if(point1point2)//保证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;kpoint1;k++){temp=group[temp1].city[k];group[temp1].city[k]=group[temp2].city[k];group[temp2].city[k]=temp;}for(k=point2+1;kcities;k++){temp=group[temp1].city[k];group[temp1].city[k]=group[temp2].city[k];group[temp2].city[k]=temp;}//处理产生的冲突基因for(k=0;kpoint1;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]];break;}}for(k=point2+1;kcities;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]];break;}}for(k=0;kpoint1;k++){for(kk=point1;kk=point2;kk++)if(group[temp2].city[k]==group[temp2].city[kk]){gr