利用遗传算法解决TSP问题

1、HUNAN LNIVTRS1TY课程实验报告1. 实验目的利用遗传算法获得TSP问题的近似解。2. 实验要求要求学生了解遗传算法解决问题的基本流程。 对TSP问题有所了解，知道TSP 问题的难点在什么地方，如何使用遗传算法来获得一个较好的近似解。3. 实验内容已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个 城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e),其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距 离矩阵，旅行商问题就是求出一条通过所有

2、顶点且每个顶点只通过一次的具有最 短距离的回路。4. 实验软硬件环境基本Windows系统基本运行环境，VS20125实验方案(1) 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法遗传算法的基本运算过程如下：a初始化：设置进化代数计数器t=0，设置最大进化代数 T，随机生成M个个体作为初始群体P(0)。b) 个体评价：计算群体 P(t)中各个个体的适应度。c) 选择运算：将选择算子作用于群体。 选择的目的是把优化的个体直接遗传到下一代或通 过配对交叉产生新的个体再遗传到下一代。 选择操作是建立在群体中个体的适应度评估基础

3、 上的。d) 交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替 换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。(2) 用遗传算法模拟 TSP问题TSP问题及旅行商问题，假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得

4、的路径路程为所有路径之中的最小值这个问题可分为对称旅行商问题(dij=dji,任意i,j=1,2,3，n)和非对称旅行商问题(dij 丰 dji, i,j任|2,3,，n)。若对于城市v=v1,v2,v3,vn的一个访问顺序为t1,t2,t3,ti, ,tn), 其中ti v(i=1,2,3,n) tn+且记1 ,则旅行商问题的数学模型为：min l= (T d(t(i),t(i+1) ( i=1,n )旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。6.实验步骤：(1) 初始化

5、过程：用v1,v2,v3, 代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。(2) 适应度f的计算：对种群中的每个染色体vi，计算其适应度，f= d d(t(i),t(i+1)(3) 评价函数eval(vi)：用来对种群中的每个染色体 vi设定一个概率，以使该染色体被 选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha (0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha)4(i-1)。(4) 选择过程

6、：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选 择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1、对每个染色体 vi,计算累计概率 qi, qO=O;qi= d eval(vj)j=1,i;i=1,-siznopstep2、从区间(0,pop-size)中产生一个随机数r;step3、若 qi-1step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。(5) 交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复 以下过程：从0, 1中产生一个随机数r，如果r将所选的父代两两组队

7、，随机产生一个位 置进行交叉，如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 16 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 16 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'

8、;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的计算；是，结束遗传操作，跳出。实验代码：#in clude<stdio.h>#i ncludevstri ng.h>#in clude<stdlib.h>#in clude<math.h>#in clude<time.h>#define cities 10 /

9、 城市的个数#define MAXX 100 迭代次数#defi ne pc 0.8 / 交配概率#defi ne pm 0.05 / 变异概率#define num 10种群的大小int bestsoluti on;/最优染色体int distancecitiescities;/城市之间的距离struct group /染色体的结构in t citycities; 城市的顺序int adap t; 适应度double p;在种群中的幸存概率group nu m,grouptemp nu m;/随机产生cities个城市之间的相互距离void init()int i,j;memset(dist

10、a nce,0,sizeof(dista nee);sran d( un sig ned)time(NULL);for(i=0;i<cities;i+)for(j=i+1;j<cities;j+)dista nceij=ra nd()%100;dista nceji=dista nceij;/打印距离矩阵printf("城市的距离矩阵如下n");for(j=0;j<cities;j+)prin tf("%4d",dista nceij); prin tf("n");/随机产生初试群void groupproduce(

11、)int i,j,t,k,flag;for(i=0;i<num;i+)/ 初始化for(j=0;j<cities;j+)groupi.cityj=-1;sran d( un sig ned)time(NULL); for(i=0;i <nu m;i+)/产生10个不相同的数字for(j=0;j<cities;)t=ra nd()%cities;flag=1;if(groupi.cityk=t) flag=0;break;if(flag)groupi.cityj=t;j+;/打印种群基因printf("初始的种群n");for(i=0;i <nu

12、 m;i+)for(j=0;j<cities;j+)prin tf("%4d",groupi.cityj);prin tf("n");/评价函数，找出最优染色体void pin gjia()int i,j;int n1, n2;int sumdista nce,biggestsum=O;double biggestp=0;for(i=0;i <nu m;i+)sumdista nce=0;for(j=1;j<cities;j+)n 1=groupi.cityj-1;n 2=groupi.cityj;sumdista nce+=dista

13、 nce n1 n2;groupi.adapt=sumdista nee; /每条染色体的路径总和 biggestsum+=sumdista nee; /种群的总路径/计算染色体的幸存能力，路劲越短生存概率越大groupi.p=1-(double)groupi.adapt/(double)biggestsum; biggestp+=groupi.p;for(i=0;i <nu m;i+)groupi.p=groupi.p/biggestp; /在种群中的幸存概率，总和为1/求最佳路劲bestsolutio n=0;for(i=0;i <nu m;i+)if(groupi.p>

14、groupbestsoluti on .p)bestsolutio n=i;/打印适应度for(i=0;i <nu m;i+)printf("染色体%d的路径之和与生存概率分别为%4d%.4fn ",i,groupi.adapt,groupi.p);printf（"当前种群的最优染色体是 %d号染色体n",bestsolution）;/选择void xua nze()double gradie ntn um; 梯度概率double xua nze num;/选择染色体的随机概率int xua nn um;选择了的染色体/初始化梯度概率for(i=0

15、;i <nu m;i+)gradie nti=0.0;xua nzei=0.0;gradie nt0=group0.p;for(i=1;i< nu m;i+)gradie nti=gradie nti-1+groupi.p;sran d( un sig ned)time(NULL);/随机产生染色体的存活概率for(i=0;i <nu m;i+)xua nzei=(ra nd()%100);xua nzei/=100;/选择能生存的染色体for(i=0;i <nu m;i+)if(xua nzeivgradie ntj)xuani=j; /第i个位置存放第j个染色体 b

16、reak;/拷贝种群for(i=0;i <nu m;i+)grouptempi.adapt=groupi.adapt; grouptempi.p=groupi.p;for(j=0;j<cities;j+)grouptempi.cityj=groupi.cityj;/数据更新for(i=0;i <nu m;i+)temp=xua ni;groupi.adapt=grouptemptemp.adapt;groupi.p=grouptemptemp.p;for(j=0;j<cities;j+) groupi.cityj=grouptemptemp.cityj;/用于测试/*p

17、rintf("<>n");for(i=0;i <nu m;i+)for(j=0;j<cities;j+)prin tf("%4d",groupi.cityj);prin tf("n");printf("染色体%d的路径之和与生存概率分别为%4d %.4fn",i,groupi.adapt,groupi.p);*/交配,对每个染色体产生交配概率，满足交配率的染色体进行交配void jiaopei()int i,j,k,kk;int t;/参与交配的染色体的个数int poin t1,po in

18、 t2,temp; 交配断点int pointnum;int temp1,temp2;int map1cities,map2cities;double jiaopeip num;/染色体的交配概率 int jiaopeiflag num;/染色体的可交配情况 for(i=0;i<num;i+) 初始化 jiaopeiflagi=0;/随机产生交配概率sran d( un sig ned)time(NULL);for(i=0;i <nu m;i+)jiaopeipi=(ra nd()%100); jiaopeipi/=100;/确定可以交配的染色体t=0;for(i=0;i <

19、nu m;i+)if(jiaopeipi<pc)jiaopeiflagi=1;t+;t=t/2*2;/t必须为偶数/产生t/2个0-9交配断点sran d( un sig ned)time(NULL);temp1=0;/tempi号染色体和temp2染色体交配 for(i=0;i<t/2;i+)poin t1=ra nd()%cities;poin t2=ra nd()%cities;for(j=temp1;j <nu m;j+)if(jiaopeiflagj=1)temp1=j;break;for(j=temp1+1;j< nu m;j+)if(jiaopeiflag

20、j=1)temp2=j;break;/进行基因交配if(point1>point2) / 保证 point1<=point2temp=po in t1;poin t1=po in t2;poin t2=temp;memset(map1,-1,sizeof(map1);memset(map2,-1,sizeof(map2);/断点之间的基因产生映射for(k=po in t1;k<=po in t2;k+)map1grouptemp1.cityk=grouptemp2.cityk;map2grouptemp2.cityk=grouptemp1.cityk;/断点两边的基因互换f

21、or(k=0;k<poi nt1;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;for(k=po in t2+1;k<cities;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;/处理产生的冲突基因for(k=0;k<poi nt1;k+)for(kk=po in t1;kk<=po in t2;kk+)if(grouptemp1.cityk

22、=grouptemp1.citykk)grouptemp1.cityk=map1grouptemp1.cityk; break;for(k=po in t2+1;k<cities;k+)for(kk=po in t1;kk<=po in t2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)grouptemp1.cityk=map1grouptemp1.cityk; break;for(k=0;k<poi nt1;k+)for(kk=po in t1;kk<=po in t2;kk+) if(grouptemp2.cityk=grou

23、ptemp2.citykk) grouptemp2.cityk=map2grouptemp2.cityk; break;for(k=po in t2+1;k<cities;k+)for(kk=po in t1;kk<=po in t2;kk+) if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;temp仁temp2+1;/变异void bia nyi()int i,j;int t;int temp1,temp2,po int;double bia nyip num; /染色体的变异概率 int bia nyiflag num;/染色体的变异情况 for(i=0;i<num;i+)/ 初始化 bia nyiflagi=O;/随机产生变异概率sran d( un sig ned)time(NULL);for(i=0;i <nu m;i+)bia nyipi