人工智能TSP旅行商问题实验报告

1、精选文档 人工智能实验三实验报告 可编辑 班级： 姓名： 学号： 实验题目 TSP 问题的遗传算法实现 ），又译为旅行推销员问题、货担郎 n 个可直达的城市，一销售商从其 旅行商问题（ Traveling Salesman Problem, TSP 问题，简称为 TSP 问题，是最基本的路线问题。假设有 中的某一城市出发，不重复地走完其余 n-1 个城市并回到原出发点，在所有可能的路径中 求出路径长度最短的一条。 应用遗传算法求解 30/10个节点的TSP （旅行商问题）问题，求问题的最优解。 二 实验目的 熟悉和掌握遗传算法的基本概念和基本思想； 理解和掌握遗传算法的各个操作算子，能够用选定

2、的编程语言设计简单的遗传优化 系统； 通过实验培养学生利用遗传算法进行问题求解的基本技能。 三 实验要求 1 掌握遗传算法的基本原理、各个遗传操作和算法步骤； 2 要求求出问题最优解，若得不出最优解，请分析原因； 3 对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值； 4 要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。 四 数据结构 请说明染色体个体和群体的定义方法。 struct RanSeTi / 染色体的个体的定义方法 int citycities; / 基因的排列（即城市的顺序，路径的组织） int adapt; / 记录适应度 double p; /

3、 记录其在种群中的幸存概率 RanSeTi num, RanSeTi tempnum;/ 用数组来存储染色体群体方法 五 实验算法 1 说明算法中对染色体的编码方法，适应度函数定义方法 1） 染色体的编码方法 : 即为染色体个体定义过程中生成的基因排列（路径中城市的顺序） struct RanSeTi / 染色体的个体的定义方法 int citycities; / 基因的排列（即城市的顺序，路径的组织） int adapt; / 记录适应度 double p; / 记录其在种群中的幸存概率 RanSeTi num, RanSeTi tempnum;/ 用数组来存储染色体群体方法 在进 2） 适

4、应度函数定义方法： 评价函数即适应度函数， 在遗传算法中用来计算一个染色体优劣的函数。 行遗传操作和种群进化的时候， 每个染色体的适应值是决定它是否进入下一轮种群 进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。 TSP 问题中适应度函数常取路径长度的倒数（或倒数的相关函数） ，如： n 1 f(Xi,X2, , xn) Nd(Xi ,Xi 1) d(xn Xi) 其中， N是个调节参数，根据实验情况进行确定。 for(i=0;i nu m;i+) sumdista nce=O; for(j=1;jcities;j+) n1= Ran SeTi i.cityj-1; n2= Ra

5、n SeTi i.cityj; sumdista nce+=dista ncen 1 n2; Ra nSeTi i.ad apt=sumdista nee; /每条染色体的路径总和 biggestsum+=sumdista nee; /种群的总路径 2采用的选择、交叉、变异操作算子的具体操作 1) 选择操作 我们定义f(xi)为第i (i=1,2,3.popsize )个染色体的适应度，则每个个体被 选中的概率 popsize 是： P(Xi) f (Xi)f (Xj) 本题中具体使用的是期望值方法 / 初始化梯度概率 for(i=0;inum;i+) gradienti=0.0; xuanz

6、ei=0.0; gradient0=group0.p; for(i=1;inum;i+) gradienti=gradienti-1+groupi.p; srand(unsigned)time(NULL); / 随机产生染色体的存活概率 for(i=0;inum;i+) xuanzei=(rand()%100); xuanzei/=100; / 选择能生存的染色体 for(i=0;inum;i+) for(j=0;jnum;j+) if(xuanzeigradientj) 精选文档 xuani=j; / 第 i 个位置存放第 j 个染色体 break; / 拷贝种群 for(i=0;inum;

7、i+) grouptempi.adapt=groupi.adapt; grouptempi.p=groupi.p; for(j=0;jcities;j+) grouptempi.cityj=groupi.city j; / 数据更新 for(i=0;inum;i+) temp=xuani; groupi.adapt=grouptemptemp.adapt; groupi.p=grouptemptemp.p; for(j=0;jcities;j+) 2) 交叉操作： 交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作。 部分匹配交叉、顺序交叉、改进的启发式顺序交叉 /temp1

8、号染色体和 temp2 染色体交配 for(i=0;it/2;i+) point1=rand()%cities; point2=rand()%cities; for(j=temp1;jnum;j+) if(jiaopeiflagj=1) temp1=j; break; for(j=temp1+1;jpoint2) / 保证 point1=point2 temp=point1; point1=point2; point2=temp; memset(map1,-1,sizeof(map1); memset(map2,-1,sizeof(map2); / 断点之间的基因产生映射 for(k=poin

9、t1;k=point2;k+) map1grouptemp1.cityk=grouptemp2.cityk; map2grouptemp2.cityk=grouptemp1.cityk; / 断点两边的基因互换 for(k=0;kpoint1;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; for(k=point2+1;kcities;k+) temp=grouptemp1.cityk; grouptemp1.cityk=grouptemp2.cityk; grouptemp2.cityk=temp; / 处理产生的冲

10、突基因 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.cityk=grouptemp1.citykk) grouptemp1.cityk=map1grouptemp1.cityk; 可编辑 精选文档 break; for(k=0;kpoi

11、nt1;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.cityk=map2grouptemp2.cityk; break; temp1=temp2+1; 3) 变异操作 TSP 问题中，经常采取的变

12、异操作主要有：位点变异、逆转变异、对换变异、插入 变异。 / 随机产生变异概率 srand(unsigned)time(NULL); for(i=0;inum;i+) bianyipi=(rand()%100); bianyipi/=100; / 确定可以变异的染色体 t=0; for(i=0;inum;i+) if(bianyipipm) bianyiflagi=1; t+; / 变异操作 ,即交换染色体的两个节点 srand(unsigned)time(NULL); for(i=0;inum;i+) if(bianyiflagi=1) temp1=rand()%10; temp2=rand

13、()%10; point=groupi.citytemp1; groupi.citytemp1=groupi.citytemp2; groupi.citytemp2=point; 3 实验中采用的算法参数的最佳选择值是多少 #define cities 10/30 #define MAXX 150 #define pc 0.72 #define pm 0.02 #define num 20 / 城市的个数 / 迭代次数 / 交配概率 / 变异概率 / 种群的大小 六 实验结果 1 要求有实验运行结果截图，以及必要的说明 .007 0507 4?B 4VB V 498 9B 497 507 49

14、0 ?3 4?7 7 b0497 .0507 R 3J 0 591 591 591 591 591 bib 394 bl 59 i (2) 计算群体上每个个体的适应度值 ; (3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体 ; (4) 按概率 Pc 进行交叉操作 ; (5) 按概率 Pm 进行变异操作 ; (6) 没有满足某种停止条件，则转第 (2) 步，否则进入 (7) ； (7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 成功找到种群中适应度值最优的染色体作为问题的满意解或最优解。 若失败， 分析可得失败原因为： 随机生成的 cities 个城市之间的相互距离、 随机产生初 试群有可能不存在适应度值最优的染色体 七 实验总结及体会 1. 同一问题可能有不同的几种算法相对应解决 ： 对于此类旅行者问题， 原在数据结构和算法课中学过迪杰斯特拉算法， 也可以高效 快速的解决给定好初值的最短路径问题； 在本课中，有学到了新的算法： TSP 算法，此算法从遗传学角度，开辟了一个新的 视野。通过每次迭代求出的局部最优解和最终求出的全局最优解。 两种不同的算法可以求解同一问题， 但是角度完全不一样， 从目前自己实验的结果 而言， 对于小数据量的输入均可以快速高效的完成题目。但是遗传算法可以考虑到的