利用遗传算法解决TSP问答

1、闭旳2第HUNAN LNIVERS1TY课程实验报告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 丸Iji,任意 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，则旅行商问题的数学模型为：min l= od(t(i),t(i+1)(i=1,n)旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。6.实验步骤

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

6、(i-1)。(4) 选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群 选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体 vi,计算累计概率 qi , qO=O;qi=oeval(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中

7、产生一个随机数r，如果r将所选的父代两两组队，随机产生一个 位置进行交叉，如：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,产生一

8、个0，1中随机数r，该点变异为 xk=ukm in+r（ukmax-ukm in）操作。如：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#include#include#include#include#define cities 10 / 城市的个数#define MAXX 100/ 迭代次数#define pc 0.8 / 交配概率#define pm

9、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(

10、i=0;icities;i+)for(j=i+1;jcities;j+)distanceij=rand()%100; distanceji=distanceij;/ 打印距离矩阵printf( 城市的距离矩阵如下 n);for(i=0;icities;i+)for(j=0;jcities;j+)printf(%4d,distanceij);printf(n);/ 随机产生初试群void groupproduce()int i,j,t,k,flag;for(i=0;inum;i+)/ 初始化for(j=0;jcities;j+)groupi.cityj=-1; srand(unsigned)ti

11、me(NULL);for(i=0;inum;i+)/ 产生 10 个不相同的数字for(j=0;jcities;)t=rand()%cities;flag=1;for(k=0;kj;k+)if(groupi.cityk=t)flag=0;break;if(flag)groupi.cityj=t;j+;/ 打印种群基因printf( 初始的种群 n);for(i=0;inum;i+)for(j=0;jcities;j+)printf(%4d,groupi.cityj);printf(n);/ 评价函数 ,找出最优染色体void pingjia()int i,j;int n1,n2;int sum

12、distance,biggestsum=0;double biggestp=0;for(i=0;inum;i+)sumdistance=0;for(j=1;jcities;j+)n1=groupi.cityj-1;n2=groupi.cityj; sumdistance+=distancen1n2;groupi.adapt=sumdistance; / 每条染色体的路径总和 biggestsum+=sumdistance; / 种群的总路径/ 计算染色体的幸存能力 ,路劲越短生存概率越大for(i=0;inum;i+) groupi.p=1-(double)groupi.adapt/(doub

13、le)biggestsum; biggestp+=groupi.p;for(i=0;inum;i+)groupi.p=groupi.p/biggestp;/ 在种群中的幸存概率 ,总和为 1/ 求最佳路劲 bestsolution=0;for(i=0;igroupbestsolution.p)bestsolution=i;/ 打印适应度for(i=0;inum;i+)printf( 染色体 %d 的路径之和与生存概率分别为 %4d %.4fn,i,groupi.adapt,groupi.p);printf( 当前种群的最优染色体是 %d 号染色体 n,bestsolution);/ 选择voi

14、d xuanze()int i,j,temp;double gradientnum;/梯度概率double xuanzenum;/ 选择染色体的随机概率int xuannum;/ 选择了的染色体/ 初始化梯度概率for(i=0;inum;i+)gradienti=0.0;xuanzei=0.0;gradient0=group0.p;gradienti=gradienti-1+groupi.p;srand(unsigned)time(NULL);/ 随机产生染色体的存活概率for(i=0;inum;i+)xuanzei=(rand()%100);xuanzei/=100;/ 选择能生存的染色体f

15、or(i=0;inum;i+)for(j=0;jnum;j+)if(xuanzeigradientj)xuani=j; / 第 i 个位置存放第 j 个染色体 break;/ 拷贝种群for(i=#;inum;i+)grouptempi.adapt=groupi.adapt;grouptempi.p=groupi.p;for(j=0;jcities;j+)grouptempi.cityj=groupi.cityj;/ 数据更新for(i=0;inum;i+)temp=xuani;groupi.adapt=grouptemptemp.adapt;groupi.p=grouptemptemp.p;

16、for(j=0;jcities;j+)groupi.cityj=grouptemptemp.cityj;/ 用于测试/*printf(n);for(i=0;inum;i+)printf(%4d,groupi.cityj);for(j=0;jcities;j+)printf(n);printf( 染色体 %d 的路径之和与生存概率分别为 %4d %.4fn,i,groupi.adapt,groupi.p);*/ 交配 ,对每个染色体产生交配概率 ,满足交配率的染色体进行交配void jiaopei()int i,j,k,kk;int t;/ 参与交配的染色体的个数int point1,point

17、2,temp;/交配断点int pointnum;int temp1,temp2;int map1cities,map2cities;double jiaopeipnum;/ 染色体的交配概率int jiaopeiflagnum;/ 染色体的可交配情况for(i=0;inum;i+)/ 初始化jiaopeiflagi=0;/ 随机产生交配概率srand(unsigned)time(NULL);for(i=0;inum;i+)jiaopeipi=(rand()%100);jiaopeipi/=100;/ 确定可以交配的染色体t=0;for(i=0;inum;i+)if(jiaopeipipc)j

18、iaopeiflagi=1;t+;t=t/2*2;/t 必须为偶数/ 产生 t/2 个 0-9 交配断点srand(unsigned)time(NULL);temp1=0;/temp1 号染色体和 temp2 染色体交配point1=rand()%cities;for(i=0;it/2;i+)point2=rand()%cities;for(j=temp1;jnum;j+)if(jiaopeiflagj=1)temp1=j;break;for(j=temp1+1;jpoint2) / 保证 point1=point2temp=point1;point1=point2;point2=temp;m

19、emset(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;kpoint1;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp; for(k=point2+1;kcit

20、ies;k+)temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;/ 处理产生的冲突基因for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+) if(grouptemp1.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+) if(grouptemp1.city

21、k=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk;break;for(k=0;kpoint1;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cityk=map2grouptemp2.cityk;break;for(k=point2+1;kcities;k+)for(kk=point1;kk=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)grouptemp2.cit

22、yk=map2grouptemp2.cityk;break;temp1=temp2+1;/ 变异void bianyi()int i,j;int t;int temp1,temp2,point;double bianyipnum; /染色体的变异概率int bianyiflagnum;/ 染色体的变异情况for(i=0;inum;i+)/ 初始化 bianyiflagi=0;/ 随机产生变异概率srand(unsigned)time(NULL);for(i=0;inum;i+)bianyipi=(rand()%100);bianyipi/=100;/ 确定可以变异的染色体t=0;for(i=0

23、;inum;i+)if(bianyipipm)bianyiflagi=1;t+;/ 变异操作 ,即交换染色体的两个节点 srand(unsigned)time(NULL);for(i=0;inum;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

24、(t+MAXX)xuanze();/jiaopei();bianyi();pingjia();/ 最终种群的评价printf(n 输出最终的种群评价 n);for(i=0;inum;i+)for(j=0;jcities;j+)printf(%4d,groupi.cityj);printf( adapt:%4d, p:%.4fn,groupi.adapt,groupi.p);printf( 最优解为 %d 号染色体 n,bestsolution);return 0;7.实验结果 D；供习 iVtsp.exe10331033095610221033103409570957102309S?1023103410240?S710236 86 39 00 i0A0390.10280.1H28S.10386.S7660.1028M.0966 乩1阴8 6.B766 0-1038 0-096&0.B9560-0956nu12 2 10 2 OU 4 4 8