人工智能tsp旅行商问题实验报告.doc

人工智能实验三实验报告班级： 姓名： 学号：一 实验题目TSP 问题的遗传算法实现旅行商问题（Traveling Salesman Problem, TSP） ，又译为旅行推销员问题、货担郎问题，简称为 TSP 问题，是最基本的路线问题假设有 n 个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余 n-1 个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条应用遗传算法求解 30/10 个节点的 TSP（旅行商问题）问题，求问题的最优解二 实验目的1 熟悉和掌握遗传算法的基本概念和基本思想；2 理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统；3 通过实验培养学生利用遗传算法进行问题求解的基本技能三 实验要求1 掌握遗传算法的基本原理、各个遗传操作和算法步骤；2 要求求出问题最优解，若得不出最优解，请分析原因；3 对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；4 要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解四 数据结构请说明染色体个体和群体的定义方法struct RanSeTi //染色体的个体的定义方法{int city[cities]; //基因的排列（即城市的顺序，路径的组织）int adapt; //记录适应度double p; //记录其在种群中的幸存概率} RanSeTi [num], RanSeTi temp[num]; //用数组来存储染色体群体方法五 实验算法1 说明算法中对染色体的编码方法，适应度函数定义方法1) 染色体的编码方法:即为染色体个体定义过程中生成的基因排列（路径中城市的顺序）struct RanSeTi //染色体的个体的定义方法{int city[cities]; //基因的排列（即城市的顺序，路径的组织）int adapt; //记录适应度double p; //记录其在种群中的幸存概率} RanSeTi [num], RanSeTi temp[num]; //用数组来存储染色体群体方法2) 适应度函数定义方法：评价函数即适应度函数，在遗传算法中用来计算一个染色体优劣的函数。

在进行遗传操作和种群进化的时候，每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素适应值高的函数被选作新一代个体的可能性就会大TSP 问题中适应度函数常取路径长度的倒数 （或倒数的相关函数） ，如：)(),(),( 11121 xdxNxf nniin L其中，N 是个调节参数，根据实验情况进行确定for(i=0;ipoint2) //保证 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

//随机产生变异概率srand((unsigned)time(NULL));for(i=0;i

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

但是遗传算法可以考虑到的问题复杂度更高，更适合应用于实际2. 学习时应当重视动手实践能力：课堂上讲解的遗传算法较为简单基础，对于理论学习而言，十分适合但一旦应用于实践时，发现虽然每个部分模块自己都可以理解并且熟悉，但是对于实际应用，并且切实地解决实际问题仍存在较大的困难从理论到实践，从课本的知识到解决问题，若不及时的加以消化并且切实的应用于解决问题，可以看出知识很难为现实提供帮助因而应在学习之后及时进行上机实验，并且达到熟练掌握与运用的阶段。