利用遗传算法解决TSP问题(DOC).doc

课程实验报告1. 实验目的利用遗传算法获得TSP问题的近似解。2.实验要求要求学生了解遗传算法解决问题的基本流程。对TSP问题有所了解,知道TSP问题的难点在什么地方,如何使用遗传算法来获得一个较好的近似解。3.实验内容已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。4.实验软硬件环境基本Windows系统基本运行环境，VS20125. 实验方案（1）遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。（2）用遗传算法模拟TSP问题TSP问题及旅行商问题,假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值这个问题可分为对称旅行商问题(dij=dji,任意i,j=1,2,3，,n)和非对称旅行商问题(dijdji,任意i,j=1,2,3，,n)。 若对于城市v=v1,v2,v3,vn的一个访问顺序为t=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且记tn+1= t1，则旅行商问题的数学模型为： min l=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-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。（5）交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从0，1中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1交叉后为： 8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1（6）变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异（该变异点xk的取值范围为ukmin,ukmax,产生一个0，1中随机数r，该点变异为x'k=ukmin+r(ukmax-ukmin)）操作。如： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 变异后： 8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1 （7）循环操作：判断是否满足设定的代数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。实验代码：#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<time.h> #define cities 10 /城市的个数 #define MAXX 100/迭代次数 #define pc 0.8 /交配概率 #define pm 0.05 /变异概率 #define num 10/种群的大小 int bestsolution;/最优染色体 int distancecitiescities;/城市之间的距离 struct group /染色体的结构 int citycities;/城市的顺序 int adapt;/适应度 double p;/在种群中的幸存概率 groupnum,grouptempnum; /随机产生cities个城市之间的相互距离 void init() int i,j; memset(distance,0,sizeof(distance); srand(unsigned)time(NULL); for(i=0;i<cities;i+) for(j=i+1;j<cities;j+) distanceij=rand()%100; distanceji=distanceij; /打印距离矩阵 printf("城市的距离矩阵如下n"); for(i=0;i<cities;i+) for(j=0;j<cities;j+) printf("%4d",distanceij); printf("n"); /随机产生初试群 void groupproduce() int i,j,t,k,flag; for(i=0;i<num;i+) /初始化 for(j=0;j<cities;j+) groupi.cityj=-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(groupi.cityk=t) flag=0; break; if(flag) groupi.cityj=t; j+; /打印种群基因 printf("初始的种群n"); for(i=0;i<num;i+) for(j=0;j<cities;j+) printf("%4d",groupi.cityj); printf("n"); /评价函数,找出最优染色体 void pingjia() int i,j; int n1,n2; int sumdistance,biggestsum=0; double biggestp=0; for(i=0;i<num;i+) sumdistance=0; for(j=1;j<cities;j+) n1=groupi.cityj-1; n2=groupi.cityj; sumdistance+=distancen1n2; groupi.adapt=sumdistance; /每条染色体的路径总和 biggestsum+=sumdistance; /种群的总路径 /计算染色体的幸存能力,路劲越短生存概率越大 for(i=0;i<num;i+) groupi.p=1-(double)groupi.adapt/(double)biggestsum; biggestp+=groupi.p; for(i=0;i<num;i+) groupi.p=groupi.p/biggestp; /在种群中的幸存概率,总和为1 /求最佳路劲 bestsolution=0; for(i=0;i<num;i+) if(groupi.p>groupbestsolution.p) bestsolution=i; /打印适应度 for(i=0;i<num;i+) printf("染色体%d的路径之和与生存概率分别为%4d %.4fn",i,groupi.adapt,groupi.p); printf("当前种群的最优染色体是%d号染色体n",bestsolution); /选择 void xuanze() int i,j,temp; double gradientnum;/梯度概率 double xuanzenum;/选择染色体的随机概率 int xuannum;/选择了的染色体 /初始化梯度概率 for(i=0;i<num;i+) gradienti=0.0; xuanzei=0.0; gradient0=group0.p; for(i=1;i<num;i+) gradienti=gradienti-1+groupi.p; srand(unsigned)time(NULL); /随机产生染色体的存活概率 for(i=0;i<num;i+) xuanzei=(rand()%100); xuanzei/=100; /选择能生存的染色体 for(i=0;i<num;i+) for(j=0;j<num;j+) if(xuanzei<gradientj) xuani=j; /第i个位置存放第j个染色体 break; /拷贝种群 for(i=0;i<num;i+) grouptempi.adapt=groupi.adapt; grouptempi.p=groupi.p; for(j=0;j<cities;j+) grouptempi.cityj=groupi.cityj; /数据更新 for(i=0;i<num;i+) temp=xuani; groupi.adapt=grouptemptemp.adapt; groupi.p=grouptemptemp.p; for(j=0;j<cities;j+) groupi.cityj=grouptemptemp.cityj; /用于测试 /* printf("<->n"); for(i=0;i<num;i+) for(j=0;j<cities;j+) printf("%4d",groupi.cityj); printf("n"); printf("染色体%d的路径之和与生存概率分别为%4d %.4fn",i,groupi.adapt,groupi.p); */ /交配,对每个染色体产生交配概率,满足交配率的染色体进行交配 void jiaopei() int i,j,k,kk; int t;/参与交配的染色体的个数 int point1,point2,temp;/交配断点 int pointnum; int temp1,temp2; int map1cities,map2cities; double jiaopeipnum;/染色体的交配概率 int jiaopeiflagnum;/染色体的可交配情况 for(i=0;i<num;i+)/初始化 jiaopeiflagi=0; /随机产生交配概率 srand(unsigned)time(NULL); for(i=0;i<num;i+) jiaopeipi=(rand()%100); jiaopeipi/=100; /确定可以交配的染色体 t=0; for(i=0;i<num;i+) if(jiaopeipi<pc) jiaopeiflagi=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(jiaopeiflagj=1) temp1=j; break; for(j=temp1+1;j<num;j+) if(jiaopeiflagj=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+) map1grouptemp1.cityk=grouptemp2.cityk; map2grouptemp2.cityk=grouptemp1.cityk; /断点两边的基因互换 for(k=0;k<point1;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp2.cityk=temp; for(k=point2+1;k<cities;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp2.cityk=temp; /处理产生的冲突基因 for(k=0;k<point1;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk; break; for(k=point2+1;k<cities;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk; break; for(k=0;k<point1;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp2.cityk=grouptemp2.citykk) grouptemp2.cityk=map2grouptemp2.cityk; break; for(k=point2+1;k<cities;k+) for(kk=point1;kk<=point2;kk+) if(grouptemp2.cityk=grouptemp2.citykk) grouptemp2.cityk=map2grouptemp2.cityk; break; temp1=temp2+1; /变异 void bianyi() int i,j; int t; int temp1,temp2,point; double bianyipnum; /染色体的变异概率 int bianyiflagnum;/染色体的变异情况 for(i=0;i<num;i+)/初始化 bianyiflagi=0; /随机产生变异概率 srand(unsigned)time(NULL); for(i=0;i<num;i+) bianyipi=(rand()%100); bianyipi/=100; /确定可以变异的染色体 t=0; for(i=0;i<num;i+) if(bianyipi<pm) bianyiflagi=1; t+; /变异操作,即交换染色体的两个节点 srand(unsigned)time(NULL); for(i=0;i<num;i+) if(bianyiflagi=1) temp1=rand()%10; temp2=rand()%10; point=groupi.citytemp1; groupi.citytemp1=groupi.citytemp2; groupi.citytemp2=point; int main() int i,j,t; init(); groupproduce(); /初始种群评价 pingjia(); t=0; while(t+<MAXX) xuanze(); /jiaopei(); bianyi(); pingjia(); /最终种群的评价 printf("n输出最终的种群评价n"); for(i=0;i<num;i+) for(j=0;j<cities;j+) printf("%4d",groupi.cityj); printf(" adapt:%4d, p:%.4fn",groupi.adapt,groupi.p); printf("最优解为%d号染色体n",bestsolution); return 0; 7.实验结果8.实验心得通过本次实验，基本了解了用遗传算法解决旅行商问题的基本原理和流程。遗传算法的原理我是知道的，但实现起来还是很难啊，在百度和各种论坛的帮助下才艰难地完成了此实验。