tsp的人工智能求解

《tsp的人工智能求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ＴＳＰ的人工智能求解TSP的人工智能求解●●●学校：成都信息工程学院班级：数学学院信息与计算科学08-2班姓名：昌仙容（2008062049）夏晓菲（2008062042）颜晓晓（2008062050）●●●17ＴＳＰ的人工智能求解TSP的人工智能求解问题摘要TSP（TravelingSalesmanProblem）问题，又译为旅行商问题，是数学领域著名问题之一。假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求得的路径路程和为所有路径

2、和之中的最小值。该问题可简化为一个图论问题：假设有一个图G=(V,E)，其中V是顶点集，E是边集，设D=(dij)是由所有顶点i和顶点j（ｉ，ｊ＝１，２．．．．ｎ）之间的距离所组成的n*n距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。本文主要运用遗传算法，C语言变成实现对经过的城市进行Grefenstette编码，交叉和变异，之后对算法进行不断修正循环，得到一个最优解，即是最短距离。关键字：TSP图论遗传算法GrefenstetteC交叉变异17ＴＳＰ的人工智能求解１问题的重述1.1背景T

3、SP（TravelingSalesmanProblem）问题，又译为旅行商问题，是一个比较古老的问题，最早可以追溯到1759年Euler提出的骑士旅行问题。1984年，由美国兰德公司推动，TSP成为近代组合优化领域的一个经典难题。应该说，TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题，它已经被证明属于NP难题。很多实际应用问题，例如印制电路板的钻孔路线方案、连锁店的货物配送录像等，经过简化处理后，均可以建模为旅行商问题，因而对旅行商问题的求解方法的研究也具有重要的应用价值。此外，研究求解旅行上问题的遗传算法，对促进遗

4、传算法本身的发展也具有重要的意义。1.2问题假设有一个旅行商要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后必须要回到原来出发的城市。路径的选择目标是要求所得的路径路程为所有路径之中的最小值。本文中，给出具体的10个城市的坐标，利用遗传算法的思想对该问题进行具体求解。10个城市TSP坐标如下：城市XYA5.21.5B4.23.617ＴＳＰ的人工智能求解C4.72.8D4.12.2E0.93.8F4.76.1G1.52.9H3.42.1I3.73.6J2.62.52符号说明V顶点的集合C过所有定点

5、且最后回到起点的圈（不重复）vi第i个城市的标号，i=1，2，…10E所有边的集合eijvi到vj的边wijvi到vj距离Tx巡回路线G巡回路线城市列表gi在访问中第n个被访问的城市W圈C的权值Pm变异概率F适应度函数17ＴＳＰ的人工智能求解3模型假设1假设n取10已经足够大2假设变异概率以及适应度函数准确3在交叉运算和变异运算中没有产生不满足约束条件或无实际意义的巡回路线4设随机选取的r准确4问题分析这可以归结为一个图论问题：给出一个图G=（V，E），每个边eij∈E，且每一个边e上都有非负权值w（e），寻找一个G的一个回路C

6、，使得C不重复过定点vi（i=1，2，…n）,使C的总权W（C）=∑w（e）（其中e∈E）最小。我们可以知道，总的旅程路线为组合数（n-1）！/2，TSP搜索空间随着城市数n的增加而增大，我们一般很难精确地求出其精确的最优解，因此我们利用遗传算法的思想对旅行商所经过的城市进行编码，将问题空间的数据映射成遗传空间的基因串结构数据。用遗传算法解决TSP，一个旅程很自然地表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用，因此我们利用Grefenstette方法对其进行编码，对这些已经编码的数据，我们再利用遗传算法常用的单

7、点交叉对路径进行交叉变换，并且利用变异概率对路径进行进一步修正，从而得到接近的解。5模型建立5.1交叉模型的建立17ＴＳＰ的人工智能求解5.1.1城市编码的设计常规的交叉运算和变异运算使群体中产生一些不满足问题约束条件或者无实际意义的巡回录像，为了克服这种编码方法的缺点，基于对各个城市的访问顺序，我们采用由Grefenstette等提出的一种新的巡回路线编码方法，该方法可以使得任意的基因型个体都能够对应一条具有实际意义的巡回路线，下面对这种新的编码方法进行介绍：对于一个旅行商问题的城市列表M，假定各个城市的一个访问顺序为T：T=

8、(t1,t2,t3,…,ti,…tn)规定每访问完一个城市，就从城市列表M中将该城市删除，则用第i个访问的城市ti在所有未访问的城市列表M-{t1,t2,…ti-1}中对应位置序号gi就可以表示具体访问哪个城市，如此处理玩M中的所有的城市。将所有的gi排列在一起