利用遗传算法解决TSP问题

./课程实验报告1.实验目的利用遗传算法获得TSP问题的近似解。2.实验要求要求学生了解遗传算法解决问题的基本流程。对TSP问题有所了解,知道TSP问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。3.实验内容已知n个城市之间的相互距离,现有一个推销员必须遍访这n个城市,并且每个城市只能访问一次,最后又必须返回出发城市。如何安排他对这些城市的访问次序,可使其旅行路线的总长度最短？用图论的术语来说,假设有一个图g=<v,e>,其中v是顶点集,e是边集,设d=<dij>是由顶点i和顶点j之间的距离所组成的距离矩阵,旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。4.实验软硬件环境基本Windows系统基本运行环境,VS2012实验方案〔1〕遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a>初始化：设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P<0>。b>个体评价：计算群体P<t>中各个个体的适应度。c>选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d>交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e>变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P<t>经过选择、交叉、变异运算之后得到下一代群体P<t1>。f>终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。〔2〕用遗传算法模拟TSP问题TSP问题与旅行商问题,假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值这个问题可分为对称旅行商问题<dij=dji,,任意i,j=1,2,3,…,n>和非对称旅行商问题<dij≠dji,,任意i,j=1,2,3,…,n>。若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=<t1,t2,t3,…,ti,…,tn>,其中ti∈v<i=1,2,3,…,n>,且记tn+1=t1,则旅行商问题的数学模型为：minl=σd<t<i>,t<i+1>>〔i=1,…,n〕旅行商问题是一个典型的组合优化问题,并且是一个np难问题,其可能的路径数目与城市数目n是成指数型增长的,所以一般很难精确地求出其最优解,本文采用遗传算法求其近似解。6.实验步骤：〔1〕初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数,并且随机产生pop-size个初始染色体,每个染色体为1到18的整数组成的随机序列。〔2〕适应度f的计算：对种群中的每个染色体vi,计算其适应度,f=σd<t<i>,t<i+1>>。〔3〕评价函数eval<vi>：用来对种群中的每个染色体vi设定一个概率,以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例,既通过轮盘赌,适应性强的染色体被选择产生后台的机会要大,设alpha∈<0,1>,本文定义基于序的评价函数为eval<vi>=alpha*<1-alpha>.^<i-1>。〔4〕选择过程：选择过程是以旋转赌轮pop-size次为基础,每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1、对每个染色体vi,计算累计概率qi,q0=0;qi=σeval<vj>j=1,…,i;i=1,…,pop-size.step2、从区间<0,pop-size>中产生一个随机数r；step3、若qi-1step4、重复step2和step3共pop-size次,这样可以得到pop-size个复制的染色体。〔5〕交叉过程：本文采用常规单点交叉。为确定交叉操作的父代,从到pop-size重复以下过程：从[0,1]中产生一个随机数r,如果r将所选的父代两两组队,随机产生一个位置进行交叉,如：814213863257343242216123568563185633211交叉后为：814213863251856332116123568563734324221〔6〕变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程,在r选择多个染色体vi作为父代。对每一个选择的父代,随机选择多个位置,使其在每位置按均匀变异〔该变异点xk的取值X围为[ukmin,ukmax],产生一个[0,1]中随机数r,该点变异为x'k=ukmin+r<ukmax-ukmin>〕操作。如：81421386325734324221变异后：814213106322734524121〔7〕循环操作：判断是否满足设定的代数xzome,否,则跳入适应度f的计算；是,结束遗传操作,跳出。实验代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<time.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;i<cities;i++>{for<j=i+1;j<cities;j++>{distance[i][j]=rand<>%100;distance[j][i]=distance[i][j];}}//打印距离矩阵printf<"城市的距离矩阵如下\n">;for<i=0;i<cities;i++>{for<j=0;j<cities;j++>printf<"%4d",distance[i][j]>;printf<"\n">;}}//随机产生初试群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++>{//产生10个不相同的数字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++;}}}//打印种群基因printf<"初始的种群\n">;for<i=0;i<num;i++>{for<j=0;j<cities;j++>printf<"%4d",group[i].city[j]>;printf<"\n">;}}//评价函数,找出最优染色体voidpingjia<>{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<"当前种群的最优染色体是%d号染色体\n",bestsolution>;}//选择voidxuanze<>{inti,j,temp;doublegradient[num];//梯度概率doublexuanze[num];//选择染色体的随机概率intxuan[num];//选择了的染色体//初始化梯度概率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;srand<<unsigned>time<NULL>>;//随机产生染色体的存活概率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];}//用于测试/*printf<"<>\n">;for<i=0;i<num;i++>{for<j=0;j<cities;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;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;point2=rand<>%cities;for<j=temp1;j<num;j++>if<jiaopeiflag[j]==1>{temp1=j;break;}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;}//处理产生的冲突基因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]];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]];break;}}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]];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]];break;}}temp1=temp2+1;}}//变异voidbianyi<>{inti,j;intt;inttemp1,temp2,point;doublebianyip[num];//染色体的变异概率intbianyiflag[num];//染色体的变异情况for<i=0;i<num;i++>//初始化bianyiflag[i]=0;//随机产生变异概率srand<<unsigned>time<NULL>>;for<i=0;i<num;i++>{bianyip[i]=<rand<>%100>;bianyip[i]/=100;}//确定可以变异的染色体t=0;